P04 — Log-Structured Storage Engine

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P04 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Medium · 99 hours · Weeks 35–43 · Stage 2 · Rust

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Architecture
• Showcase — Do This Before You Start
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

This is the project that makes you a systems engineer rather than an application engineer, and the reason is a single idea: you cannot optimise read amplification, write amplification, and space amplification simultaneously. Improving one degrades at least one other. This is the RUM conjecture, and reading it takes ninety seconds while feeling it takes nine weeks.

Once felt, it generalises everywhere. In P02 you traded recall for latency. In P03 you traded storage for recovery time. In P05 you will trade consistency for availability. In P14 you will trade precision for throughput. Every one of those is the same shape of argument, and this project is where the shape becomes obvious.

It is also, concretely, the engine underneath most of the infrastructure you already operate: RocksDB inside Kafka Streams and Flink, LevelDB's descendants inside DynamoDB and Cassandra, and the same segment-and-merge structure inside every Lucene index and therefore inside OpenSearch. You have been operating LSM trees for years.

Prerequisites

• P03's crash-test harness (reused directly)
• Rust: ownership, Result, traits, iterators. If Rust is new, P11-I was your introduction and this is the first place it pays off
• Understanding of disk behaviour: sequential vs random throughput on your actual device, measured — do that in milestone 1, not from memory

Duration and Size

Medium, 99 hours, 9 weeks. The largest Medium project in the journey.

Central Technical Questions

1. Why is an append-only design faster to write than an in-place one? Quantify it on your disk — the answer differs by 100× between spinning rust and NVMe.
2. What does compaction actually buy, and what does it cost while it runs?
3. What are the three amplifications for each strategy? Derive, then measure, then explain the gap.
4. How much RAM does a Bloom filter save you, in disk reads, for absent keys?
5. Why does p99 latency spike during compaction, and what are the mitigations?
6. Why is a Zipfian workload fundamentally different from a uniform one for this structure? The answer is about which blocks stay in cache.

Architecture

Write your naive design first.

  put(k,v) ─► WAL.append(k,v) ─► fsync? ─► memtable (skiplist / BTreeMap)
                                              │ size > threshold
                                              ▼
                                       immutable memtable ──flush──► SSTable (L0)
                                                                        │
   get(k) ──► memtable ──► immutable ──► L0 tables (newest first) ──► L1 ... Ln
                 │              │            │                          │
                 └──────────────┴────────────┴── Bloom filter per table ─┘
                                                 sparse index per table
                                                 block cache

  SSTable layout:
    ┌──────────────┬──────────────┬─────────────┬──────────────┬────────┐
    │ data blocks  │ bloom filter │ sparse index│ footer(offsets)│ CRC32C │
    │ (4-64 KB,    │ (10 bits/key)│ (1 entry    │                │        │
    │  sorted, ea. │              │  per block) │                │        │
    │  CRC'd)      │              │             │                │        │
    └──────────────┴──────────────┴─────────────┴──────────────┴────────┘

The three amplifications, derived

Let \(T\) be the level size ratio (fanout, conventionally 10) and \(L\) the number of levels.

Leveled compaction. Each level holds non-overlapping runs and is \(T\)× the size of the one above. Merging one level into the next rewrites roughly \(T\) bytes of the target for every byte of source, so:

• write amplification ≈ \(T \cdot L + 1\) (the +1 is the memtable flush)
• read amplification ≈ \(L + 1\) tables consulted per point read (before Bloom)
• space amplification ≈ \(1 + 1/T \approx 1.1\) — at most one obsolete copy per key

Size-tiered compaction. Runs of similar size accumulate and are merged together, so each byte is rewritten roughly once per level:

• write amplification ≈ \(L + 1\)
• read amplification ≈ \(T \cdot L\) runs, since each level holds up to \(T\) of them
• space amplification ≈ 2× or worse, since \(T\) copies of a key can coexist and compaction needs free space equal to the inputs

Computed for \(T = 10\), 64 MB base level:

Read that table as a choice, not a ranking. Leveled writes each byte ~31 times to keep reads at 4 tables and space at 1.1×. Size-tiered writes each byte ~4 times and pays with 30 tables per read and 2.1× the disk. On write-heavy ingest, size-tiered is 8× cheaper in device wear; on read-heavy serving, leveled is 7× cheaper in seeks. There is no third option that wins both, and that is the RUM conjecture with numbers attached.

What Bloom filters do to the read path

A point read for an absent key must consult every run. With 40 runs that is 40 random reads to answer "no". A Bloom filter per run turns most into an in-memory rejection.

The optimal configuration for \(m\) bits over \(n\) keys is \(k = (m/n)\ln 2\) hashes giving \(\text{fpr} = 0.6185^{m/n}\) (full derivation and a working implementation in tools/bloom.py). Measured against theory, 100k keys, 200k absent probes:

Theory matches measurement within 5%. The fill ratio sits at 0.5 at every optimum — that is the entropy argument showing up in the data.

Translated to the read path with 40 runs on disk:

125 KB of RAM per 100k keys turns 40 disk reads into 0.33. That is why 10 bits/key is the near-universal default, and now you can derive it rather than cite it.

One measurement caution the tool also demonstrates: at 24 bits/key the predicted fpr is ~10⁻⁵, so 200k probes expect ~1.2 false positives. Observing 0 or 3 is Poisson noise, not a result. To measure a rate \(p\) you need ~\(100/p\) trials for a 10% relative standard error. State the resolution of your experiment before you report a ratio.

Showcase — Do This Before You Start

W2 · walkthroughs/w2_lsm.py · ~60 minutes

A working miniature of this project: forty runs, a Bloom filter each, and the measurement that contradicts "Bloom filters only help misses".

cd walkthroughs && python3 w2_lsm.py

It is 80-ish lines and it surfaces this project's central surprise in an evening rather than in week six. Run it before committing the weeks.

Implementation Milestones

Concepts To Study

• Sequential vs random I/O, on SSD and on NVMe specifically — including why the gap is smaller than the folklore and why it still matters (write amplification inside the FTL)
• Write-ahead logging, group commit, and the fsync-per-write cost
• Memtables: skiplists vs balanced trees; why skiplists are the traditional choice (lock-free insertion) and why BTreeMap is fine here
• SSTable format design: block size as a read-amplification/space trade
• Sparse indexes: one index entry per block, not per key, and the memory this saves
• Bloom filters: the derivation above; also why they cannot support range queries, and what a prefix Bloom filter is
• Compaction strategies: size-tiered, leveled, FIFO, and the hybrid RocksDB actually ships
• The three amplifications and the RUM conjecture
• Tombstones and the delete-then-compact problem: why a range delete is worse
• Block cache and how it interacts with the page cache (double caching)
• Checksums: CRC32C, hardware acceleration, per-block granularity
• Write stalls and backpressure: what happens when compaction cannot keep up

Primary-Source Readings

Budget: 15 hours — the largest reading budget in the journey, because this literature is unusually good.

Monkey is the best paper on this list and the one most likely to give you a hypothesis worth testing: it shows the optimal Bloom allocation gives more bits to smaller levels, because a level's contribution to false-positive cost is independent of its size while its memory cost is not. Your E7 tests it.

Experiments

E3 is the deliverable. A single figure with read/write ratio on the x-axis, cost on the y-axis, one line per strategy, and the crossover marked — that plot is a portfolio artifact.

E13 is the one people skip and shouldn't. An LSM engine under sustained overload does not degrade gracefully by default; it accumulates compaction debt until reads collapse. Finding your engine's breaking point, and what it does when it breaks, is more valuable than another 10% on throughput.

Benchmarks and Metrics

Instrument amplification with counters inside the code, not by watching iostat. You need to attribute bytes to a cause, and the OS cannot do that for you.

Correctness Tests

1. Model-based testing. Run every operation against both your engine and a BTreeMap; assert identical results after every op. The single highest-value test here — write it at milestone 3.
2. Crash consistency at ≥50 randomised kill points: every acknowledged write present, no unacknowledged write present.
3. Newest version wins across memtable, L0, and all levels.
4. Tombstones survive compaction until the bottom level.
5. Range scan completeness: every live key exactly once, in order, newest version.
6. Level invariant (leveled): no overlapping key ranges within a level ≥ 1. Assert after every compaction.
7. Bloom filters never produce false negatives. Assert on every inserted key.
8. Block CRC detects a single flipped bit in every block type.
9. Idempotent recovery: recover twice, identical state.
10. Compaction preserves semantics: full-scan equality before and after.
11. Fuzz: random operation sequences with random crashes, compared against the model.

Failure Tests

Expected Difficulties

1. Compaction is where the bugs live, and they are concurrency bugs with a file system attached. Mitigation: single-threaded compaction first, and the model-based test running throughout.
2. Amplification instrumentation has to be designed in. Retrofitting byte counters after the fact means missing paths. Do it in milestone 2.
3. Rust plus a new domain is two hard things. Mitigation: P11-I gave you the language; keep the data structures boring (BTreeMap, Vec<u8>) and spend your difficulty budget on the storage logic.
4. "Just use BTreeMap for the memtable" feels like cheating. It is not. The memtable is not the mechanism under study.
5. Benchmarks on a laptop with an active page cache lie. Your working set must exceed RAM, or you are benchmarking the page cache. State your working-set-to-RAM ratio on every result.
6. The 9-week ceiling is real. If leveled compaction is unfinished at week 9, ship size-tiered, state the limitation, and move on.

Scope Boundaries

In scope: single-node, single-column-family, byte-string keys and values, point reads, range scans, deletes, crash recovery, two compaction strategies.

Out of scope: transactions, MVCC snapshots (P03 has your snapshot experience), column families, secondary indexes, a network layer, replication (P05), a SQL layer, compression (mention in the report; do not implement), and multi-threaded compaction until the extension.

Deliverables

1. lsmdb/ — embeddable Rust crate with a CLI and a benchmark runner
2. FORMAT.md — byte-level SSTable and WAL layout
3. REPORT.md centred on the E3 crossover figure and the E4 amplification comparison
4. workloads/ — the generator, reusable in P05
5. Notebook entries for E3, E7, E12, E13
6. The amplification-counter instrumentation as a reusable pattern

Exit Criteria

• Model-based test passes over ≥10⁶ random operations
• Crash test passes at ≥50 randomised kill points
• Both compaction strategies implemented and running
• E3 complete: the crossover figure exists, with the crossing ratio stated
• E4 complete: all three amplifications measured for both strategies, compared against the derived table, gaps explained
• Bloom fpr measured against theory with the measurement resolution stated
• p99 during compaction reported alongside steady state
• E13 run: the engine's overload behaviour characterised
• REPORT.md written with a falsified prediction

Extension Ideas

• Monkey-style Bloom allocation measured against uniform. Small, sharp, real.
• Learned index blocks replacing the sparse index (Kraska et al.). Measure lookup time and memory; be honest that the win is usually small and workload-dependent.
• Adaptive compaction: switch strategy based on the observed read/write ratio. A research direction.
• Prefix Bloom filters for range queries with a common prefix.
• Multi-threaded compaction with a measured scaling curve and a stall analysis.

Connections

Backward: P03 gives you the crash-test harness and the recovery-time measurement that motivated this whole project. P11-I gave you Rust.

Forward:

• → P05 (Distributed KV): this engine is the per-node storage. Its WAL becomes the replicated log's local persistence; its snapshots become Raft snapshots.
• → P07 (Streaming): stateful operator state is an LSM in every real system (RocksDB in Flink and Kafka Streams). Your checkpointing reuses this.
• → P12 (Kernel): page cache, I/O scheduling, and fsync semantics become things you implement rather than call.
• → P15: interaction/item storage.

References

• O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4), 1996.
• Rosenblum, M., Ousterhout, J. K. The Design and Implementation of a Log-Structured File System. SOSP 1991.
• Chang, F. et al. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006.
• Athanassoulis, M., Kester, M. S., Maas, L. M., Stoica, R., Idreos, S., Ailamaki, A., Callaghan, M. Designing Access Methods: The RUM Conjecture. EDBT 2016.
• Dayan, N., Athanassoulis, M., Idreos, S. Monkey: Optimal Navigable Key-Value Store. SIGMOD 2017.
• Dong, S., Callaghan, M., Galanis, L., Borthakur, D., Savor, T., Strum, M. Optimizing Space Amplification in RocksDB. CIDR 2017.
• Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13(7), 1970.
• Kirsch, A., Mitzenmacher, M. Less Hashing, Same Performance: Building a Better Bloom Filter. ESA 2006. The double-hashing trick used in tools/bloom.py.
• Kraska, T., Beutel, A., Chi, E. H., Dean, J., Polyzotis, N. The Case for Learned Index Structures. SIGMOD 2018.
• Pillai, T. S. et al. All File Systems Are Not Created Equal. OSDI 2014.
• Ghemawat, S., Dean, J. LevelDB. github.com/google/leveldb — read db_impl.cc and version_set.cc after milestone 9.