kv
A log-structured key-value store: WAL → memtable → SSTables with bloom filters. Watch a write travel the LSM path.
1 Operations
Every put/delete appends to the WAL first, then the memtable. Past the size limit the memtable flushes to an immutable SSTable. Lookups check memtable → newest SSTable → …, stopping at the first answer including a tombstone.
2 Storage pipeline
1 · WAL
2 · Memtable
3 · SSTables
3 Bloom filter
Bits set when the newest SSTable was written. Probe a key: green bits are the hash positions; one clear bit means definitely absent — no disk read.
4 Read path trace
Where a get looked, in order, and why it stopped.
5 What the design gets right
A delete does not delete anything
It writes a tombstone. An older value may still sit in an older file — dropping the marker lets it come back on the next read. Tombstones are only discarded after a full merge.
Log before memory
If the memtable were updated first and the process died before the append, the write would have been acknowledged and then vanished. WAL first, always.
File before truncate
A flush writes the SSTable, fsyncs it, then clears the log. Truncating first would lose everything the memtable held if the crash landed between.
Bloom: no false negatives
The filter may say "maybe present" for an absent key; it must never say "absent" for a present one. Splitmix64 avalanche on the second hash keeps false positives near 1%.