Part 9 · 1 chapters · ~8 min

Build: LSM Engine, Document Store and Ring

The capstone: an LSM key-value engine with a memtable, SSTable writer and reader, Bloom filters and leveled compaction; a small document store with a BSON-like encoding, a B-tree and a secondary index; and a consistent-hashing ring with tunable-consistency reads and writes.

Three builds

code

lsm/          memtable (sorted map) + WAL; flush to SSTable (sorted blocks, index, Bloom filter); get() newest-first;
              leveled compaction merging overlapping files; tombstones dropped at the last level; a crash-recovery test
docstore/     encode/decode a BSON subset (string, int64, double, bool, document, array); a B-tree keyed by _id;
              createIndex(field) maintaining a second B-tree; find({field: value}) using it; a 16 MB size check
ring/         nodes with 64 virtual tokens each (DS P12); RF = 3; put/get at ONE, QUORUM, ALL; simulated node failures;
              hinted handoff; a read-repair on mismatched replicas; measure stale reads at ONE vs QUORUM
reuse: the BYO course's redis and storage repos have related pieces to start from