I built a persistent LSM-Tree storage engine in Go from scratch

GO-LSM: BUILDING A LOG-STRUCTURED MERGE-TREE ENGINE

INTRODUCTION:

I've always been curious about the internals of databases, so I decided to build my own Log-Structured Merge-Tree (LSM-Tree) engine in Go to understand the "magic" behind write-optimized storage.

Go-LSM is a persistent Key-Value engine that manages the full lifecycle of data from volatile RAM to immutable disk storage.

TECHNICAL HIGHLIGHTS:

1. THE DURABILITY LAYER (WAL)

To ensure zero data loss, I implemented an append-only Write-Ahead Log.

• Custom binary protocol: [Type][KeyLen][ValLen][Key][Value] • File.Sync() to force kernel flushes to physical hardware • Ensures absolute durability on system crashes

2. SKIPLIST MEMTABLE

Instead of a standard tree, I used a SkipList for the in-memory layer.

• Provides O(log n) search and insertion without the rebalancing complexity of Red-Black trees • Keeps keys lexicographically sorted for the eventual SSTable flush • Enables efficient memory-to-disk transitions

3. SSTABLE FOOTER-BASED INDEXING

My SSTables are binary-searchable on disk using a tail-first reading strategy:

• Jump to the last 8 bytes of a file to find the Index Block pointer • Avoid full file scans by reading directly to the index • Execute binary search on sorted keys for O(log n) disk lookups

4. MAINTENANCE LAYER: COMPACTION

Built a K-Way Merge compaction engine that handles performance optimization:

• Processes multiple SSTable layers and merges them into single, optimized files • Handles "Read Amplification" by reducing the number of files to check per query • Processes "Tombstones" to finalize deletions and reclaim disk space

5. TOOLING & DEBUGGING

Custom binary parsers transform raw binary files into human-readable tables:

• lsm-dump: View sorted SSTable contents • lsm-wal-dump: Inspect unflushed Write-Ahead Log entries • Enables deep inspection of internal storage layers

KEY ENGINEERING LESSONS:

Moving from standard application development to systems programming required a fundamental shift in how I think about memory and I/O:

• ENDIANNESS LOGIC: Handling Big-Endian vs. Little-Endian conversions for cross-platform compatibility • FILE OFFSET MANAGEMENT: Manually managing byte offsets and file pointer positioning • CONCURRENCY & THREAD SAFETY: Implementing thread-safe mechanisms for MemTable flushing • BINARY PROTOCOL DESIGN: Creating efficient, compact data encodings for durability

REPOSITORY:

https://github.com/Jyotishmoy12/LSM-Tree-in-Golang