LSM Memtable + Merge (Go)
Topics: LSM-tree, memtable, tombstones, k-way merge, compaction
Problem
Model the write path of a log-structured merge (LSM) store — the design behind LevelDB, RocksDB,
Cassandra. Writes go to an ordered in-memory memtable; deletes are tombstones (markers, not
removals). Flushing the memtable yields a key-sorted run, and compaction merges runs.
type Entry struct { Key, Val string; Tombstone bool }
func NewMemtable() *Memtable
func (m *Memtable) Set(key, val string)
func (m *Memtable) Delete(key string) // writes a tombstone
func (m *Memtable) Get(key string) (string, bool)
func (m *Memtable) Flush() []Entry // sorted by key, tombstones included
func Merge(runs [][]Entry) []Entry
Flush returns the memtable's entries sorted by key, keeping tombstones (they must shadow
older runs).Merge(runs) takes runs oldest-first, newest-last (each already sorted) and produces one
sorted run where, per key, the newest run wins; if that winning entry is a tombstone, the key
is omitted.
Merge([{k:old}, {k:new}]) → [k:new]
Merge([{k:v}, {k:✗}]) → [] (tombstone shadows)
Merge([{k:✗}, {k:again}]) → [k:again] (resurrected by newer run)
Key concepts
- Tombstones: a delete is a write — it has to be flushed so it can hide an older value during a
merge; only at the final merge does the key disappear.
- k-way merge: advance a cursor per run; repeatedly take the smallest key, and among runs sitting
on it, the highest-indexed (newest) wins.
- Why LSM: all writes are sequential appends; reads merge layers — the classic write-optimized
store.
Entry, the memtable, and Set/Delete/Get are provided; you implement Flush and Merge.
Run
go test -v ./challenges/lsm-merge/go/
Sign in to submit your solution.