lsm

package
v1.10.0 Latest Latest
Warning

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

 Go to latest Published: Oct 22, 2026 License: MIT Imports: 20 Imported by: 0

Documentation

Index

Constants

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

	// MaxEntryFieldSize bounds a key or value length read from a file.
	//
	// The format stores each length as a uint32, so a corrupt or truncated
	// SSTable can ask for up to 4 GiB per field, and readEntry passed that
	// number straight to make(). This is the defect #477 fixed for the mmap
	// snapshot decoders; the SSTable decoder had it too. The bound is far
	// above any legitimate entry and far below what an allocator will accept
	// without complaint.
	MaxEntryFieldSize = 64 << 20
)

Variables

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

Functions

func CheckInvariants added in v1.4.0 

func CheckInvariants(l *LSMStorage) ([]string, error)

CheckInvariants returns one string for each violated invariant. An empty slice means healthy. The error return is for a check that could not run at all, never for a violation.

It exists for the reason #468 promoted the pkg/storage checker out of the test binary: a consumer that suspects a corrupt store must be able to ask, and an assertion only a test can make is an assertion the shipped artefact does not carry.

What it covers, and what it does not: the level set against the files on the disk. It says nothing about the contents of an SSTable, about the bloom filters, or about the block cache. A clean result is therefore a statement about bookkeeping, not about data.

PRECONDITION: the store is quiescent. Stop the background workers, or call this before they start. It takes lsm.mu for reading, which excludes a level swap but NOT a flush between its two critical sections.

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 ListSSTablesWithFS added in v1.4.0 

func ListSSTablesWithFS(dir string, fs vfs.FileSystem) ([][]*SSTable, error)

ListSSTablesWithFS enumerates SSTables on a caller-supplied filesystem driver.

It reads the directory rather than calling filepath.Glob, because Glob goes straight to the real filesystem and a driver cannot fail it. A listing that cannot fail is a listing whose error path is untested.

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) Snapshot added in v1.4.0 

func (bc *BlockCache) Snapshot() map[string][]byte

Snapshot copies the cache's contents.

CheckInvariants compares it with what the levels hold. Iterating the live list under the caller's lock would need the cache's internals to leak, and the copy also means the check cannot be perturbed by a concurrent eviction half way through.

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 NewCompactorWithFS added in v1.4.0 

func NewCompactorWithFS(dataDir string, strategy CompactionStrategy, fs vfs.FileSystem) *Compactor

NewCompactorWithFS creates a compactor on a caller-supplied driver.

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.

A file that is already gone counts as removed. The postcondition this is asked for is absence, not a successful syscall, and treating ENOENT as a failure made the operation impossible to retry: the first pass removes what it can and stops short on one file, so a second pass reports every file the first one succeeded on. The compaction sweep found that immediately after the retry was added.

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

	// FS is the filesystem driver. Nil means vfs.Default(), which is what
	// production uses. A test supplies a fault or crash driver here.
	FS                   vfs.FileSystem
	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) GetEntry added in v1.4.0 

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

GetEntry retrieves the entry for a key, tombstone included.

Get cannot express "deleted here": it returns (nil, false) both for a tombstone and for an absent key, so a caller that searches several levels in turn cannot stop at a delete and falls through to an older level holding the pre-delete value. GetEntry carries that third state. lsm.Get uses it, and Get stays as the filtering form its own callers expect.

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) MergeOlder added in v1.4.0 

func (mt *MemTable) MergeOlder(older *MemTable)

MergeOlder inserts each entry from older that this table does not hold.

The receiver's entries are newer by construction: older was moved aside by a flush, and this table took the writes that arrived after that. So a key in both keeps the receiver's value, tombstones included.

A flush that fails uses this to put the entries back. Dropping them instead would lose writes that Put had already acknowledged and that a reader could still see a moment earlier, and it would leave the block cache holding keys that no table holds.

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 live entries in range [start, end). A tombstone is omitted.

func (*MemTable) ScanEntries added in v1.4.0 

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

ScanEntries returns entries in range [start, end), tombstones included.

Scan drops tombstones, which is right for a caller looking at one table and wrong for a caller merging several: the dropped tombstone lets an older table revive the key. lsm.Scan merges, so it uses this.

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 NewSSTableWithFS added in v1.4.0 

func NewSSTableWithFS(path string, entries []*Entry, fs vfs.FileSystem) (sst *SSTable, err error)

NewSSTableWithFS writes an SSTable on a caller-supplied filesystem driver. Intended for testing; see pkg/vfs and docs/adr/0002.

func OpenSSTable 

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

OpenSSTable opens an existing SSTable

func OpenSSTableWithFS added in v1.4.0 

func OpenSSTableWithFS(path string, fs vfs.FileSystem) (*SSTable, error)

OpenSSTableWithFS opens an SSTable on a caller-supplied filesystem driver.

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 live value by key. A tombstone reads as absent.

func (*SSTable) GetEntry added in v1.4.0 

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

GetEntry retrieves the entry for a key, tombstone included. See MemTable.GetEntry for why the third state matters to a merging caller.

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)

func (*SSTable) ScanEntries added in v1.4.0 

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

ScanEntries returns entries in range [start, end), tombstones included. See MemTable.ScanEntries for why a merging caller needs them.

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.