golsm

package module
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 2, 2024 License: MIT Imports: 20 Imported by: 0

README

goLSM: An LSM Tree based Key-Value Storage Engine in Go

Introduction

goLSM is an LSM tree based storage engine written in Go. It offers a simple key-value interface and is designed to be used as an embedded storage engine. It is designed to offer high-write throughput with reasonable read performance.

Features

  1. Simple key-value interface: Put(key, value), Get(key), Delete(key), RangeScan(startKey, endKey).
  2. Multi-component LSM tree: Includes a high-throughput in-memory component and multiple disk-based components for persistence.
  3. Read-optimized: Uses a Bloom filters and on-disk indexes to speed up reads.
  4. Automatic compaction: Automatically compacts disk-based components using a tiered compaction strategy to control read and write amplification.
  5. Crash recovery: Uses a custom write-ahead log to allow for crash recovery.

Usage

Opening a DB instance

First, you need to open an storage engine instance. You can do this using the Open function from the golsm package. This function takes three arguments: the directory where the LSM tree will be stored, the maximum size of the in-memory component before it is flushed, and a boolean indicating whether to enable the write-ahead log (WAL).

dir := "db_directory"
// Open a new LSM tree instance with a 64MB in-memory component, and enable crash recovery.
db, err := golsm.Open(dir, 64_000_000, true)
Writing to the DB

You can write key-value pairs to the DB using the Put method. The key should be a string and value can be any byte slice.

err := db.Put("key", []byte("value"))

Updating a key is the same as writing to it.

Reading from the DB
Get

You can read a value from the DB using the Get method. This method takes a key and returns the corresponding value.

value, err := db.Get("key")
RangeScan

You can perform a range scan on the DB using the RangeScan method. This method takes two keys and returns all key-value pairs where the key is within the range of the two keys.

// Get all key-value pairs where the key is between "key1" and "key5".
pairs, err := db.RangeScan("key1", "key5")

if err != nil {
    // Handle error.
}

for _, pair := range pairs {
    fmt.Println(pair.Key, pair.Value)
}
Deleting from the DB

You can delete a key-value pair from the DBD using the `Delete`` method. This method takes a key and removes the corresponding key-value pair from the tree.

err := db.Delete("key")
Closing the DB

Finally, you should close the DB when you're done using it. You can do this using the Close method. Closing the DB will flush the in-memory component to disk, close the write-ahead log, and run any scheduled compactions.

err := db.Close()

Documentation

Index

Constants

View Source 
const (
	SSTableFilePrefix  = "sstable_"
	WALDirectorySuffix = "_wal"
)

Variables

View Source 
var (
	Command_name = map[int32]string{
		0: "PUT",
		1: "DELETE",
		2: "WRITE_SST",
	}
	Command_value = map[string]int32{
		"PUT":       0,
		"DELETE":    1,
		"WRITE_SST": 2,
	}
)

Enum value maps for Command.

View Source 
var File_serialization_proto protoreflect.FileDescriptor

Functions

This section is empty.

Types

type BloomFilter 

type BloomFilter struct {
	Bitset []bool `protobuf:"varint,1,rep,packed,name=bitset,proto3" json:"bitset,omitempty"`
	Size   int64  `protobuf:"varint,2,opt,name=size,proto3" json:"size,omitempty"`
	// contains filtered or unexported fields
}

func (*BloomFilter) Add 

func (bf *BloomFilter) Add(item []byte)

Add adds an item to the Bloom filter.

func (*BloomFilter) Descriptor deprecated 

func (*BloomFilter) Descriptor() ([]byte, []int)

Deprecated: Use BloomFilter.ProtoReflect.Descriptor instead.

func (*BloomFilter) GetBitset 

func (x *BloomFilter) GetBitset() []bool

func (*BloomFilter) GetSize 

func (x *BloomFilter) GetSize() int64

func (*BloomFilter) ProtoMessage 

func (*BloomFilter) ProtoMessage()

func (*BloomFilter) ProtoReflect 

func (x *BloomFilter) ProtoReflect() protoreflect.Message

func (*BloomFilter) Reset 

func (x *BloomFilter) Reset()

func (*BloomFilter) String 

func (x *BloomFilter) String() string

func (*BloomFilter) Test 

func (bf *BloomFilter) Test(item []byte) bool

Test checks if an item might be in the Bloom filter.

type Command 

type Command int32
const (
	Command_PUT       Command = 0
	Command_DELETE    Command = 1
	Command_WRITE_SST Command = 2
)

func (Command) Descriptor 

func (Command) Descriptor() protoreflect.EnumDescriptor

func (Command) Enum 

func (x Command) Enum() *Command

func (Command) EnumDescriptor deprecated 

func (Command) EnumDescriptor() ([]byte, []int)

Deprecated: Use Command.Descriptor instead.

func (Command) Number 

func (x Command) Number() protoreflect.EnumNumber

func (Command) String 

func (x Command) String() string

func (Command) Type 

func (Command) Type() protoreflect.EnumType

type EntrySize 

type EntrySize int64

Alias for int64 size

type Index 

type Index struct {
	Entries []*IndexEntry `protobuf:"bytes,1,rep,name=entries,proto3" json:"entries,omitempty"`
	// contains filtered or unexported fields
}

func (*Index) Descriptor deprecated 

func (*Index) Descriptor() ([]byte, []int)

Deprecated: Use Index.ProtoReflect.Descriptor instead.

func (*Index) GetEntries 

func (x *Index) GetEntries() []*IndexEntry

func (*Index) ProtoMessage 

func (*Index) ProtoMessage()

func (*Index) ProtoReflect 

func (x *Index) ProtoReflect() protoreflect.Message

func (*Index) Reset 

func (x *Index) Reset()

func (*Index) String 

func (x *Index) String() string

type IndexEntry 

type IndexEntry struct {
	Key    string `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
	Offset int64  `protobuf:"varint,2,opt,name=offset,proto3" json:"offset,omitempty"`
	// contains filtered or unexported fields
}

func (*IndexEntry) Descriptor deprecated 

func (*IndexEntry) Descriptor() ([]byte, []int)

Deprecated: Use IndexEntry.ProtoReflect.Descriptor instead.

func (*IndexEntry) GetKey 

func (x *IndexEntry) GetKey() string

func (*IndexEntry) GetOffset 

func (x *IndexEntry) GetOffset() int64

func (*IndexEntry) ProtoMessage 

func (*IndexEntry) ProtoMessage()

func (*IndexEntry) ProtoReflect 

func (x *IndexEntry) ProtoReflect() protoreflect.Message

func (*IndexEntry) Reset 

func (x *IndexEntry) Reset()

func (*IndexEntry) String 

func (x *IndexEntry) String() string

type KVPair 

type KVPair struct {
	Key   string
	Value []byte
}

type LSMTree 

type LSMTree struct {
	// contains filtered or unexported fields
}

func Open 

func Open(directory string, maxMemtableSize int64, recoverFromWAL bool) (*LSMTree, error)

Opens an LSMTree. If the directory does not exist, it will be created. directory: The directory where the SSTables will be stored. maxMemtableSize: The maximum size of the memtable in bytes before it is flushed to an SSTable. runRecovery: If true, the LSMTree will recover from the WAL on startup. On startup, the LSMTree will load all the SSTables handles (if any) from disk into memory.

func (*LSMTree) Close 

func (l *LSMTree) Close() error

func (*LSMTree) Delete 

func (l *LSMTree) Delete(key string) error

Delete a key-value pair from the LSMTree.

func (*LSMTree) Get 

func (l *LSMTree) Get(key string) ([]byte, error)

Get the value for a given key from the LSMTree. Returns nil if the key is not found. This function will first look in the memtable, then in the SSTables.

func (*LSMTree) Put 

func (l *LSMTree) Put(key string, value []byte) error

Insert a key-value pair into the LSMTree.

func (*LSMTree) RangeScan 

func (l *LSMTree) RangeScan(startKey string, endKey string) ([]KVPair, error)

RangeScan returns all the entries in the LSMTree that have keys in the range [startKey, endKey]. The entries are returned in sorted order of keys.

type Memtable 

type Memtable struct {
	// contains filtered or unexported fields
}

In-memory table that supports writes, reads, deletes, and range scans.

func NewMemtable 

func NewMemtable() *Memtable

Create a new Memtable.

func (*Memtable) Clear 

func (m *Memtable) Clear()

Clears the Memtable.

func (*Memtable) Delete 

func (m *Memtable) Delete(key string)

Delete a key-value pair from the Memtable. Not thread-safe.

func (*Memtable) Get 

func (m *Memtable) Get(key string) *MemtableEntry

Retrieve a value from the Memtable. Not thread-safe.

func (*Memtable) GetEntries 

func (m *Memtable) GetEntries() []*MemtableEntry

Generates serializable list of memtable entries in sorted order for SSTable. Not thread-safe.

func (*Memtable) Len 

func (m *Memtable) Len() int

Get the number of entries in the Memtable. Includes tombstones. Not thread-safe.

func (*Memtable) Put 

func (m *Memtable) Put(key string, value []byte)

Insert a key-value pair into the Memtable. Not thread-safe.

func (*Memtable) RangeScan 

func (m *Memtable) RangeScan(startKey string, endKey string) []*MemtableEntry

Range scan the Memtable, inclusive of startKey and endKey. Not thread-safe.

func (*Memtable) SizeInBytes 

func (m *Memtable) SizeInBytes() int64

Get the size of the Memtable in bytes. Not thread-safe.

type MemtableEntry 

type MemtableEntry struct {
	Key       string  `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
	Command   Command `protobuf:"varint,2,opt,name=command,proto3,enum=grpcapi.Command" json:"command,omitempty"`
	Value     []byte  `protobuf:"bytes,3,opt,name=value,proto3,oneof" json:"value,omitempty"`
	Timestamp int64   `protobuf:"varint,4,opt,name=timestamp,proto3" json:"timestamp,omitempty"`
	// contains filtered or unexported fields
}

func (*MemtableEntry) Descriptor deprecated 

func (*MemtableEntry) Descriptor() ([]byte, []int)

Deprecated: Use MemtableEntry.ProtoReflect.Descriptor instead.

func (*MemtableEntry) GetCommand 

func (x *MemtableEntry) GetCommand() Command

func (*MemtableEntry) GetKey 

func (x *MemtableEntry) GetKey() string

func (*MemtableEntry) GetTimestamp 

func (x *MemtableEntry) GetTimestamp() int64

func (*MemtableEntry) GetValue 

func (x *MemtableEntry) GetValue() []byte

func (*MemtableEntry) ProtoMessage 

func (*MemtableEntry) ProtoMessage()

func (*MemtableEntry) ProtoReflect 

func (x *MemtableEntry) ProtoReflect() protoreflect.Message

func (*MemtableEntry) Reset 

func (x *MemtableEntry) Reset()

func (*MemtableEntry) String 

func (x *MemtableEntry) String() string

type SSTable 

type SSTable struct {
	// contains filtered or unexported fields
}

func OpenSSTable 

func OpenSSTable(filename string) (*SSTable, error)

Opens an SSTable file for reading and returns a handle to it.

func SerializeToSSTable 

func SerializeToSSTable(messages []*MemtableEntry, filename string) (*SSTable, error)

Writes a list of MemtableKeyValue to a file in SSTable format. Format of the file is: 1. Bloom filter size (OffsetSize) 2. Bloom filter data (BloomFilter Protobuf) 3. Index size (OffsetSize) 4. Index data (Index Protobuf) 5. Entries data

The entries data is written in as: 1. Size of the entry (OffsetSize) 2. Entry data (MemtableEntry Protobuf)

func (*SSTable) Close 

func (s *SSTable) Close() error

func (*SSTable) Front 

func (s *SSTable) Front() *SSTableIterator

Returns an iterator for the SSTable. The iterator is positioned at the beginning of the SSTable.

func (*SSTable) Get 

func (s *SSTable) Get(key string) (*MemtableEntry, error)

Reads the value for a given key from the SSTable. Returns nil if the key is not found.

func (*SSTable) GetEntries 

func (s *SSTable) GetEntries() ([]*MemtableEntry, error)

GetEntries returns all the values in the SSTable.

func (*SSTable) RangeScan 

func (s *SSTable) RangeScan(startKey string, endKey string) ([]*MemtableEntry, error)

RangeScan returns all the values in the SSTable between startKey and endKey inclusive.

type SSTableIterator 

type SSTableIterator struct {
	Value *MemtableEntry // Current entry
	// contains filtered or unexported fields
}

func (*SSTableIterator) Close 

func (i *SSTableIterator) Close() error

Closes the iterator.

func (*SSTableIterator) Next 

func (i *SSTableIterator) Next() *SSTableIterator

Returns the next entry in the SSTable. Returns nil if there are no more entries.

type WALEntry 

type WALEntry struct {
	Key       string  `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
	Command   Command `protobuf:"varint,2,opt,name=command,proto3,enum=grpcapi.Command" json:"command,omitempty"`
	Value     []byte  `protobuf:"bytes,3,opt,name=value,proto3,oneof" json:"value,omitempty"`
	Timestamp int64   `protobuf:"varint,4,opt,name=timestamp,proto3" json:"timestamp,omitempty"`
	// contains filtered or unexported fields
}

func (*WALEntry) Descriptor deprecated 

func (*WALEntry) Descriptor() ([]byte, []int)

Deprecated: Use WALEntry.ProtoReflect.Descriptor instead.

func (*WALEntry) GetCommand 

func (x *WALEntry) GetCommand() Command

func (*WALEntry) GetKey 

func (x *WALEntry) GetKey() string

func (*WALEntry) GetTimestamp 

func (x *WALEntry) GetTimestamp() int64

func (*WALEntry) GetValue 

func (x *WALEntry) GetValue() []byte

func (*WALEntry) ProtoMessage 

func (*WALEntry) ProtoMessage()

func (*WALEntry) ProtoReflect 

func (x *WALEntry) ProtoReflect() protoreflect.Message

func (*WALEntry) Reset 

func (x *WALEntry) Reset()

func (*WALEntry) String 

func (x *WALEntry) String() string

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.