Capstone: Quarry's Storage Engine
In short: Quarry's storage engine is every piece from this section wired
together. Writes land in a memtable, flush to an sstable, and cascade through
compaction exactly like lesson 5 — and every write also write-through-updates
an LRU cache from lesson 3. Reads check that cache first, for free; only a
miss ever touches the LSM levels, and even then a Bloom filter (section 8)
skips any sstable that provably doesn't hold the key. Running a fixed,
seeded mix of reads and writes through the whole thing gives three numbers
that actually matter in production: write amplification (what writes
cost later), hit rate (how often the cache saves a disk probe at all),
and read path length (how many probes a miss costs when it does happen).
None of those three numbers can be reasoned about separately — they trade
against each other through memtable_limit, compaction_threshold and
cache_capacity, and the only way to see the trade is to run it.
Wire the cache in front of the LSM levels
A write touches both halves of the engine; a read only touches the LSM half when the cache has nothing for it:
a is a hit on its second read — the write-through cache already had it.
b is a miss the first time (nothing's been written yet), then a hit once
it's written. c is a miss from start to finish: it was never written in
this trace, so there's nothing anywhere to find. Only the misses would ever
reach probe_count_bloom in the real engine; every hit is answered entirely
out of the cache dict, no disk probe at all.
Run a fixed workload and read the three numbers off it
A hand-written trace can't show what a realistic mix of reads and writes
does at scale. generate_workload builds a reproducible one, and
run_storage_engine reports the three numbers that matter:
40 operations over 8 keys: write amplification of 1.38 (every byte written costs 1.38 bytes of real disk I/O once compaction is counted), a 34% cache hit rate, and only 6 total disk probes across every miss — most misses find their key in the first sstable the Bloom filter lets through, or get ruled out before a probe happens at all.
Quick practice
cache_values = {"a": 1, "b": 2}
cache_order = ["b", "a"]
key = "c"
hit = key in cache_values
print(hit)def cache_touch(order, cache_capacity, key):
new_order = [key] + [x for x in order if x != key]
if len(new_order) > cache_capacity:
new_order.pop()
return new_order
order = []
for key in ["a", "b", "c"]:
order = cache_touch(order, 2, key)
print(order)🎯 Your turn
Build run_storage_engine(ops, memtable_limit, compaction_threshold, cache_capacity, m, k): replay a fixed, seeded operation mix through the
whole engine and report write amplification, cache hit rate and total read
probes.
run_storage_engine(generate_workload(8, 40, seed=3), 3, 2, 4, 32, 3)→{'write_amplification': 1.38, 'hit_rate': 0.34, 'total_probes': 6}
Hint: flush_and_compact is one write's worth of lesson 5's run_lsm
pipeline — call it after every write. A write also write-through-updates the
cache with cache_touch. A read checks the cache dict first (0 probes on a
hit); on a miss, probe_count_bloom finds it in the LSM levels, and the key
then joins the cache too.
Press ▶ Run, try the Live App chips, then ✓ Check.