How devfiqi/lsm-engine works
This Go repository implements an embedded LSM key-value engine. The principal workflow enters through the DB API: writes are WAL-backed before reaching the in-memory table, flushes create SSTables and feed compaction, while reads check memory before searching tables. The graph also shows recovery, skip-list storage, and the SSTable lookup accelerators. Relationships are based on source excerpts and README statements; no unsampled implementation was inspected.
Main entry points: db.go DB Engine · reader.go SSTable Reader · compaction.go K-way Merge · writer.go SSTable Writer
Components 17
Engine API
- DB Engine
db/db.go - Storage API
types.go - Engine Errors
errors.go
Write Buffer
- MemTable
memtable/memtable.go - Concurrent Skip-list
skiplist/skiplist.go - Write-Ahead Log
wal/wal.go
SSTable Storage
- SSTable Flush
sstable/writer.go - SSTable Writer
sstable/writer.go - SSTable Reader
sstable/reader.go - SSTable Files
sstable/writer.go - Data Blocks
sstable/reader.go
Recovery & Compaction
- WAL Recovery
wal/recover.go - Compaction Manager
compaction/compaction.go - K-way Merge
compaction/compaction.go
Lookup Structures
- Bloom Filter
bloom/bloom.go - Sparse Index
sstable/reader.go
Other components
- Application
Connections 21
- Application → DB Engine: calls
README.md - Storage API → DB Engine: defines API
types.go - DB Engine → WAL Recovery: recovers WAL
db/db.go - WAL Recovery → Write-Ahead Log: replays records
- DB Engine → MemTable: writes and reads
db/db.go - MemTable → Write-Ahead Log: appends first
memtable/memtable.go - MemTable → Concurrent Skip-list: stores entries
memtable/memtable.go - DB Engine → SSTable Flush: flushes on full
db/db.go - SSTable Flush → SSTable Writer: encodes entries
sstable/writer.go - SSTable Writer → SSTable Files: writes files
sstable/writer.go - DB Engine → Compaction Manager: registers flush
db/db.go - Compaction Manager → K-way Merge: runs compaction
compaction/compaction.go - K-way Merge → SSTable Reader: scans inputs
compaction/compaction.go - K-way Merge → SSTable Writer: writes merged output
compaction/compaction.go - K-way Merge → Bloom Filter: builds filter
compaction/compaction.go - SSTable Writer → Bloom Filter: embeds filter
sstable/writer.go - DB Engine → SSTable Reader: searches tables
db/db.go - SSTable Reader → Bloom Filter: checks membership
sstable/reader.go - SSTable Reader → Sparse Index: searches index
sstable/reader.go - SSTable Reader → Data Blocks: scans selected block
sstable/reader.go - Engine Errors → DB Engine: reports failures