lsm

package
v0.6.0 Latest Latest
Warning

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

 Go to latest Published: Jun 17, 2026 License: MIT Imports: 17 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	SSTableMagic   = 0x53535442 // "SSTB"
	SSTableVersion = 1
	IndexInterval  = 128 // Create index entry every N keys
)

Variables

View Source 
var ErrIncompatibleFilters = &BloomFilterError{"incompatible bloom filters"}

Functions

func EntryCompare 

func EntryCompare(a, b *Entry) int

EntryCompare compares two entries by key

func ListSSTables 

func ListSSTables(dir string) ([][]*SSTable, error)

ListSSTables returns all SSTable files in a directory. Returns partial results even if some SSTables fail to open, along with an error describing the failures. Callers should check both the result and error.

func SSTablePath 

func SSTablePath(dir string, level int, id int) string

SSTablePath generates a path for a new SSTable

Types

type BlockCache 

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

BlockCache is an LRU cache for frequently accessed data blocks

func NewBlockCache 

func NewBlockCache(capacity int) *BlockCache

NewBlockCache creates a new LRU block cache

func (*BlockCache) Clear 

func (bc *BlockCache) Clear()

Clear removes all entries from the cache

func (*BlockCache) Delete 

func (bc *BlockCache) Delete(key string)

Delete removes an entry from the cache

func (*BlockCache) Get 

func (bc *BlockCache) Get(key string) ([]byte, bool)

Get retrieves a value from the cache

func (*BlockCache) Put 

func (bc *BlockCache) Put(key string, value []byte)

Put adds a value to the cache

func (*BlockCache) Size 

func (bc *BlockCache) Size() int

Size returns the current number of entries

func (*BlockCache) Stats 

func (bc *BlockCache) Stats() (hits, misses int64, hitRate float64)

Stats returns cache statistics

type BloomFilter 

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

BloomFilter is a probabilistic data structure for set membership testing - False positives possible (may say key exists when it doesn't) - False negatives impossible (if it says key doesn't exist, it definitely doesn't)

func NewBloomFilter 

func NewBloomFilter(expectedItems int, falsePositiveRate float64) *BloomFilter

NewBloomFilter creates a Bloom filter optimized for the given parameters expectedItems: number of items to store falsePositiveRate: desired false positive rate (e.g., 0.01 for 1%)

func (*BloomFilter) Add 

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

Add adds a key to the Bloom filter

func (*BloomFilter) Contains 

func (bf *BloomFilter) Contains(key []byte) bool

Contains is an alias for MayContain for better API usability

func (*BloomFilter) EstimateFalsePositiveRate 

func (bf *BloomFilter) EstimateFalsePositiveRate(itemCount int) float64

EstimateFalsePositiveRate estimates current false positive rate

func (*BloomFilter) HashCount 

func (bf *BloomFilter) HashCount() int

HashCount returns the number of hash functions

func (*BloomFilter) MarshalBinary 

func (bf *BloomFilter) MarshalBinary() []byte

MarshalBinary serializes the Bloom filter

func (*BloomFilter) MayContain 

func (bf *BloomFilter) MayContain(key []byte) bool

MayContain checks if a key might be in the set Returns true if key might exist (with false positive rate) Returns false if key definitely doesn't exist

func (*BloomFilter) Merge 

func (bf *BloomFilter) Merge(other *BloomFilter) error

Merge combines another Bloom filter into this one (OR operation) Both filters must have the same size and hash count

func (*BloomFilter) Reset 

func (bf *BloomFilter) Reset()

Reset clears all bits in the filter

func (*BloomFilter) Size 

func (bf *BloomFilter) Size() int

Size returns the size of the filter in bits

func (*BloomFilter) UnmarshalBinary 

func (bf *BloomFilter) UnmarshalBinary(data []byte) error

UnmarshalBinary deserializes the Bloom filter

type BloomFilterError 

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

func (*BloomFilterError) Error 

func (e *BloomFilterError) Error() string

type CompactionPlan 

type CompactionPlan struct {
	Level       int
	SSTables    []*SSTable
	OutputLevel int
}

CompactionPlan describes which SSTables to compact

type CompactionStats 

type CompactionStats struct {
	TotalCompactions int64
	BytesRead        int64
	BytesWritten     int64
	KeysRemoved      int64 // Deleted or duplicate keys
}

CompactionStats tracks compaction metrics

type CompactionStrategy 

type CompactionStrategy interface {
	SelectCompaction(levels [][]*SSTable) *CompactionPlan
}

CompactionStrategy defines how SSTables are compacted

type Compactor 

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

Compactor performs SSTable compaction

func NewCompactor 

func NewCompactor(dataDir string, strategy CompactionStrategy) *Compactor

NewCompactor creates a new compactor

func (*Compactor) CleanupOldSSTables 

func (c *Compactor) CleanupOldSSTables(sstables []*SSTable) error

CleanupOldSSTables removes old SSTables after compaction. Continues on errors to avoid leaving the LSM tree in an inconsistent state. Returns an error aggregating all deletion failures.

func (*Compactor) Compact 

func (c *Compactor) Compact(plan *CompactionPlan) (result []*SSTable, err error)

Compact merges SSTables according to the plan. This is a critical background operation - panic recovery prevents corruption. On error, any partially created output SSTables are cleaned up.

type Entry 

type Entry struct {
	Key       []byte
	Value     []byte
	Timestamp int64
	Deleted   bool // Tombstone for deletions
}

Entry represents a key-value pair with metadata

type IndexEntry 

type IndexEntry struct {
	Key    []byte
	Offset uint64
}

IndexEntry represents an entry in the sparse index

type LSMOptions 

type LSMOptions struct {
	DataDir              string
	MemTableSize         int // Bytes (default 4MB)
	CompactionStrategy   CompactionStrategy
	EnableAutoCompaction bool
}

LSMOptions configures LSM storage

func DefaultLSMOptions 

func DefaultLSMOptions(dataDir string) LSMOptions

DefaultLSMOptions returns default LSM configuration

type LSMStats 

type LSMStats struct {
	// High-frequency counters use atomics (lock-free)
	WriteCount      atomic.Int64
	ReadCount       atomic.Int64
	FlushCount      atomic.Int64
	CompactionCount atomic.Int64
	BytesWritten    atomic.Int64
	BytesRead       atomic.Int64

	MemTableSize    int
	SSTableCount    int
	Level0FileCount int
	// contains filtered or unexported fields
}

LSMStats tracks LSM storage statistics using lock-free atomic counters for high-frequency operations (reads/writes) to avoid contention.

type LSMStatsSnapshot 

type LSMStatsSnapshot struct {
	WriteCount      int64
	ReadCount       int64
	FlushCount      int64
	CompactionCount int64
	BytesWritten    int64
	BytesRead       int64
	MemTableSize    int
	SSTableCount    int
	Level0FileCount int
}

LSMStatsSnapshot is a point-in-time snapshot of LSM statistics

type LSMStorage 

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

LSMStorage is the main LSM-tree storage engine

func NewLSMStorage 

func NewLSMStorage(opts LSMOptions) (*LSMStorage, error)

NewLSMStorage creates a new LSM storage engine

func (*LSMStorage) Close 

func (lsm *LSMStorage) Close() error

Close flushes pending writes and stops background workers

func (*LSMStorage) Delete 

func (lsm *LSMStorage) Delete(key []byte) error

Delete removes a key (writes tombstone)

func (*LSMStorage) Get 

func (lsm *LSMStorage) Get(key []byte) ([]byte, bool)

Get retrieves a value by key

func (*LSMStorage) GetStats 

func (lsm *LSMStorage) GetStats() LSMStatsSnapshot

GetStats returns current statistics as a snapshot

func (*LSMStorage) PrintStats 

func (lsm *LSMStorage) PrintStats()

PrintStats prints storage statistics

func (*LSMStorage) Put 

func (lsm *LSMStorage) Put(key, value []byte) error

Put writes a key-value pair

func (*LSMStorage) Scan 

func (lsm *LSMStorage) Scan(start, end []byte) (map[string][]byte, error)

Scan returns all key-value pairs in range [start, end)

func (*LSMStorage) Sync 

func (lsm *LSMStorage) Sync() error

Sync forces a flush of the current memtable to disk

type LeveledCompactionStrategy 

type LeveledCompactionStrategy struct {
	Level0FileLimit int     // Max files in L0 before compaction
	LevelSizeRatio  float64 // Size ratio between levels (default 10.0)
	MaxLevels       int     // Maximum number of levels
}

LeveledCompactionStrategy implements leveled compaction (like LevelDB/RocksDB) - Level 0: Multiple overlapping SSTables (from MemTable flushes) - Level 1+: Non-overlapping SSTables, size increases by 10x per level

func DefaultLeveledCompaction 

func DefaultLeveledCompaction() *LeveledCompactionStrategy

DefaultLeveledCompaction returns default leveled compaction config

func (*LeveledCompactionStrategy) SelectCompaction 

func (lcs *LeveledCompactionStrategy) SelectCompaction(levels [][]*SSTable) *CompactionPlan

SelectCompaction determines which SSTables to compact

type MappedSSTable 

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

MappedSSTable is a memory-mapped SSTable for fast reads

func OpenMappedSSTable 

func OpenMappedSSTable(path string) (*MappedSSTable, error)

OpenMappedSSTable opens an SSTable using memory-mapped I/O

func (*MappedSSTable) Close 

func (sst *MappedSSTable) Close() error

Close closes the memory-mapped file

func (*MappedSSTable) Get 

func (sst *MappedSSTable) Get(key []byte) (*Entry, bool)

Get retrieves a value by key using memory-mapped I/O

func (*MappedSSTable) Iterator 

func (sst *MappedSSTable) Iterator() ([]*Entry, error)

Iterator returns all entries

func (*MappedSSTable) Scan 

func (sst *MappedSSTable) Scan(start, end []byte) ([]*Entry, error)

Scan returns entries in range [start, end)

type MemTable 

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

MemTable is an in-memory write buffer using a sorted map

func NewMemTable 

func NewMemTable(maxSize int) *MemTable

NewMemTable creates a new MemTable

func (*MemTable) Clear 

func (mt *MemTable) Clear()

Clear removes all entries (used after flush)

func (*MemTable) Delete 

func (mt *MemTable) Delete(key []byte) error

Delete marks a key as deleted (tombstone)

func (*MemTable) Get 

func (mt *MemTable) Get(key []byte) (*Entry, bool)

Get retrieves a value by key

func (*MemTable) IsFull 

func (mt *MemTable) IsFull() bool

IsFull returns true if MemTable should be flushed

func (*MemTable) Iterator 

func (mt *MemTable) Iterator() []*Entry

Iterator returns all entries in sorted order

func (*MemTable) Put 

func (mt *MemTable) Put(key, value []byte) error

Put adds or updates a key-value pair

func (*MemTable) Scan 

func (mt *MemTable) Scan(start, end []byte) []*Entry

Scan returns entries in range [start, end)

func (*MemTable) Size 

func (mt *MemTable) Size() int

Size returns the approximate size in bytes

type MergeIterator 

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

MergeIterator merges multiple sorted iterators

func NewMergeIterator 

func NewMergeIterator(sstables []*SSTable) (*MergeIterator, error)

NewMergeIterator creates an iterator that merges multiple SSTables

func (*MergeIterator) Next 

func (mi *MergeIterator) Next() (*Entry, bool)

Next returns the next entry in sorted order across all iterators

type SSTable 

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

SSTable represents a Sorted String Table on disk

func NewSSTable 

func NewSSTable(path string, entries []*Entry) (*SSTable, error)

NewSSTable creates a new SSTable from MemTable entries

func OpenSSTable 

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

OpenSSTable opens an existing SSTable

func (*SSTable) Close 

func (sst *SSTable) Close() error

Close closes the SSTable file

func (*SSTable) Delete 

func (sst *SSTable) Delete() error

Delete removes the SSTable file

func (*SSTable) Get 

func (sst *SSTable) Get(key []byte) (*Entry, bool)

Get retrieves a value by key

func (*SSTable) Iterator 

func (sst *SSTable) Iterator() ([]*Entry, error)

Iterator returns all entries

func (*SSTable) Scan 

func (sst *SSTable) Scan(start, end []byte) ([]*Entry, error)

Scan returns entries in range [start, end)

type SSTableHeader 

type SSTableHeader struct {
	Magic       uint32
	Version     uint32
	EntryCount  uint64
	IndexOffset uint64
}

SSTableHeader represents the header of an SSTable file

type SSTableIterator 

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

SSTableIterator iterates over an SSTable

func NewSSTableIterator 

func NewSSTableIterator(sst *SSTable) (*SSTableIterator, error)

NewSSTableIterator creates an iterator for an SSTable

func (*SSTableIterator) Next 

func (it *SSTableIterator) Next() (*Entry, bool)

Next advances the iterator

func (*SSTableIterator) Peek 

func (it *SSTableIterator) Peek() (*Entry, bool)

Peek returns current entry without advancing

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.