P04 hands-on — LSM storage engine, block by block

Durability first, then the Bloom filter that makes reads survivable.

Source: handson/h04_lsm.py --- run it with python3 handson/h04_lsm.py
Full project spec: P04 — Log-Structured Storage Engine

The order of this file is the order the mechanisms have to be built in. The write-ahead log comes first, because a storage engine that loses acknowledged writes is not a storage engine and every later optimisation is meaningless without it. The crash test in the assembly is therefore not a nice extra: it is the only result on the page that would make the others worth reading.

After durability comes the read path, and the read path is where the design earns its name. Writes are cheap because they are appended; reads are expensive because a key could be in any run. The sparse index, the Bloom filter, and compaction are three different answers to that one problem, and the file measures each of them separately so you can see how much each actually buys.

Contents

• Block 1 — The record format
• Block 2 — Write-ahead log
• Block 3 — Memtable and flush
• Block 4 — Sparse index
• Block 5 — Bloom filter
• Block 6 — The read path
• Block 7 — Compaction, and the three amplifications
• The assembly
• The design space
• Latency: the numbers that force the design
• Advanced algorithms and data structures
• Hardware: what the medium dictates
• How this connects to the rest of the track
• Failure modes at scale
• Primary sources
• Running it
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — The record format

Teaches: a length-prefixed, checksummed record is the atom of durability

The problem. Every durable structure in this engine is a sequence of records in a file. The record format decides what a crash can do to you, so it is the first thing built and the last thing you want to change.

@block(1, "The record format", "a length-prefixed, checksummed record is the atom of durability")
def b1(s, show):
    def pack(k, v):
        body = struct.pack("<II", len(k), len(v)) + k + v
        return struct.pack("<I", zlib.crc32(body)) + struct.pack("<I", len(body)) + body
    def unpack(buf, off):
        if off + 8 > len(buf): return None, off
        crc, blen = struct.unpack_from("<II", buf, off)
        if off + 8 + blen > len(buf): return None, off        # torn tail
        body = buf[off+8: off+8+blen]
        if zlib.crc32(body) != crc: return None, off          # corruption
        kl, vl = struct.unpack_from("<II", body, 0)
        return (body[8:8+kl], body[8+kl:8+kl+vl]), off + 8 + blen
    r = pack(b"alpha", b"1")
    got, _ = unpack(r, 0)
    assert got == (b"alpha", b"1")
    torn, _ = unpack(r[:-3], 0)
    bad = bytearray(r); bad[-1] ^= 0xFF
    corrupt, _ = unpack(bytes(bad), 0)
    if show:
        print(f"  record for ('alpha','1') = {len(r)} bytes: crc|len|klen|vlen|k|v")
        print(f"  round-trip: {got}")
        print(f"  truncated tail -> {torn}   (normal after a crash, not corruption)")
        print(f"  flipped bit    -> {corrupt}   (detected by CRC, never served)")
    return {"pack": pack, "unpack": unpack}

Reading the implementation

• Length prefix before payload so the reader knows how far to advance without scanning for a delimiter. Delimiter-based formats need escaping, and escaping is where parser bugs live.
• Checksum covering the payload so a torn write is detected rather than interpreted. On real hardware a power cut can leave a 4 KiB block half-written: the header is new, the body is old, and every field parses fine. Only the checksum catches that.
• The pair together give the reader the two things it needs at every position: is there a complete record here and is it intact. A format missing either cannot be safely replayed after a crash, which is block 2's entire subject.

What the numbers say

Output:

  record for ('alpha','1') = 22 bytes: crc|len|klen|vlen|k|v
  round-trip: (b'alpha', b'1')
  truncated tail -> None   (normal after a crash, not corruption)
  flipped bit    -> None   (detected by CRC, never served)

Beyond the toy

Real engines add framing at a second granularity. RocksDB's WAL is a sequence of 32 KiB blocks, and a record that does not fit is split into fragments tagged FIRST/MIDDLE/LAST. That looks like unnecessary complexity until you want to resynchronise: a reader that lands mid-file can scan to the next block boundary and resume, whereas a pure record stream is unreadable after any damage. The trade is a little space and a lot of recoverability.

CRC32C rather than CRC32 is the standard choice because it has a hardware instruction (SSE4.2, ARMv8 CRC extensions) reaching 20+ GB/s against 1--2 GB/s in software. At small record sizes this is invisible; during a bulk load it is 5--10% of total CPU.

Block 2 — Write-ahead log

Teaches: log BEFORE data, or a crash leaves neither version

The problem. A write must be durable before it is acknowledged, and the data structure it belongs in is in memory. The write-ahead log resolves that by making durability and structure two separate concerns — and the ordering rule in its name is not a suggestion.

@block(2, "Write-ahead log", "log BEFORE data, or a crash leaves neither version")
def b2(s, show):
    class WAL:
        def __init__(self, path): self.path = path; self.f = open(path, "ab")
        def append(self, k, v, sync=False):
            self.f.write(s["pack"](k, v))
            self.f.flush()
            if sync: os.fsync(self.f.fileno())
        def replay(self):
            buf = open(self.path, "rb").read(); off = 0; out = []
            while off < len(buf):
                rec, noff = s["unpack"](buf, off)
                if rec is None: break                     # stop at first bad record
                out.append(rec); off = noff
            return out, len(buf) - off
    w = WAL(os.path.join(DIR, "wal"))
    for i in range(50): w.append(f"k{i:03}".encode(), f"v{i}".encode())
    w.f.flush()
    with open(w.path, "ab") as f: f.write(b"\x01\x02\x03")   # simulate a torn write
    recs, leftover = w.replay()
    if show:
        print(f"  50 records written, then 3 junk bytes appended (a torn write)")
        print(f"  replay recovered {len(recs)} records, stopped with {leftover} bytes left")
        print("  a partial record at the tail is EXPECTED after a crash. Stopping")
        print("  there is correct; scanning past it is how you serve garbage.")
    return {"WAL": WAL}

Reading the implementation

The rule is log before data, and the failure it prevents is subtle. If you mutate the data structure first and crash before logging, the change is lost — tolerable. If you write the data file first and crash before logging, you have a half-updated file and no record of intent — you cannot roll forward or back. The log is what makes recovery a decision rather than a guess.

• f.flush() moves bytes from the process buffer into the kernel page cache.
• os.fsync() asks the kernel to push them to the device and blocks until it says they are there.

Only the second survives a power cut, and this is the single most common durability bug in storage code. It is also the reason the measured fsync cost of 90--105 µs (numbers.md) dominates the write path: at ~100 µs per flush, a naive one-fsync-per-write engine tops out near 10,000 writes/second regardless of how fast everything else is.

What the numbers say

Output:

  50 records written, then 3 junk bytes appended (a torn write)
  replay recovered 50 records, stopped with 3 bytes left
  a partial record at the tail is EXPECTED after a crash. Stopping
  there is correct; scanning past it is how you serve garbage.

Beyond the toy

Group commit is the standard escape and it is pure amortisation: collect all writes that arrive during an in-flight flush, fsync once, acknowledge them all. Throughput rises with concurrency while per-write latency stays at one flush, which is why database write throughput often improves as you add clients — a counter-intuitive curve that this mechanism explains.

The durability knob is a real product decision, not a purity question:

Kafka's acks settings, PostgreSQL's synchronous_commit, and RocksDB's WriteOptions::sync are all this table exposed as configuration — and every one of them defaults to something less than full durability, because the default has to be usable.

Block 3 — Memtable and flush

Teaches: sorted in memory, immutable on disk

The problem. Writes need to be fast, which means memory. Reads need ordering, which means sorted. Disk needs sequential access, which means immutable. The memtable-and-flush pattern satisfies all three by keeping a mutable sorted structure in RAM and only ever writing whole immutable sorted runs.

@block(3, "Memtable and flush", "sorted in memory, immutable on disk")
def b3(s, show):
    def flush(memtable, path):
        items = sorted(memtable.items())
        with open(path, "wb") as f:
            offsets = []
            for k, v in items:
                offsets.append((k, f.tell()))
                f.write(s["pack"](k, v))
        return items, offsets
    mt = {f"key{i:04}".encode(): f"val{i}".encode() for i in rng.sample(range(500), 200)}
    items, offs = flush(mt, os.path.join(DIR, "sst0"))
    if show:
        print(f"  memtable {len(mt)} keys (a dict) -> SSTable, sorted on disk")
        print(f"  first three keys: {[k.decode() for k,_ in items[:3]]}")
        print(f"  sorted: {items == sorted(items)}")
        print("  sortedness makes range scans a merge and lookups a binary search;")
        print("  immutability makes concurrent reads lock-free.")
    return {"flush": flush}

Reading the implementation

The write path is: append to WAL (durable, unordered) → insert into memtable (ordered, volatile) → acknowledge. Both halves are needed, and the memtable is what makes the read path possible without scanning the log.

When the memtable fills, it is sorted and written out in one sequential pass — and this is where the design earns its throughput. Individual random inserts became one large sequential write, which on an HDD is a 100× difference and on NVMe still 3--10×. That transformation is the whole idea of "log-structured".

The structure choice matters more than it looks. RocksDB's default memtable is a skip list rather than a B-tree or red-black tree, because skip lists support lock-free concurrent insertion — several writer threads can make progress without a global lock. The cost is worse cache locality (pointer chasing again, cf. P02) once the memtable exceeds L2.

What the numbers say

Output:

  memtable 200 keys (a dict) -> SSTable, sorted on disk
  first three keys: ['key0000', 'key0007', 'key0008']
  sorted: True
  sortedness makes range scans a merge and lookups a binary search;
  immutability makes concurrent reads lock-free.

Beyond the toy

The flush must be atomic with respect to readers: a reader must see either the old set of runs or the new one, never a partially written file. That is the write-temp-then-rename discipline again — the same primitive as P03's segments, P06's task commit and P07's checkpoint.

Two operational details this toy omits:

• Immutable memtables. Real engines swap the active memtable for a fresh one and flush the old one in the background, so writes never block on a flush. With a single memtable, a flush stalls every writer for its duration.
• WAL truncation. Once a memtable's contents are in an SSTable, the corresponding WAL is garbage. Systems that forget this fill the disk with logs describing data that is already safely elsewhere.

Block 4 — Sparse index

Teaches: one entry per BLOCK, not per key -- that is what fits in RAM

The problem. A sorted run of a million keys cannot have an in-memory index entry per key — that is the index you were trying to avoid. The sparse index is the observation that you only need enough to find the right block.

@block(4, "Sparse index", "one entry per BLOCK, not per key -- that is what fits in RAM")
def b4(s, show):
    def build_sparse(offsets, every=16):
        return offsets[::every]
    def seek(sparse, key):
        lo = None
        for k, off in sparse:
            if k <= key: lo = off
            else: break
        return lo or 0
    mt = {f"key{i:04}".encode(): f"v{i}".encode() for i in range(1000)}
    items, offs = s["flush"](mt, os.path.join(DIR, "sst1"))
    sp = build_sparse(offs, 16)
    if show:
        print(f"  {len(offs)} keys -> {len(sp)} sparse entries ({len(offs)//len(sp)}x smaller)")
        print(f"  lookup 'key0500': scan starts at byte {seek(sp, b'key0500')}, "
              f"not byte 0")
        print("  a dense index over a billion keys does not fit in memory. A sparse")
        print("  one narrows to a block, and you scan the block.")
    return {"build_sparse": build_sparse, "seek": seek}

Reading the implementation

One entry per block, not per key. A lookup binary-searches the sparse index in RAM to find the block that could contain the key, then reads exactly that block and searches within it. The cost is one binary search (nanoseconds) plus one I/O.

The arithmetic is what makes it work. With 4 KiB blocks and 32-byte keys, one entry per block indexes ~128 keys, so the in-memory index is ~1% of the data. For a 100 GB run that is 1 GB of index — still large, which is why real engines add a second level (an index of the index) and cache index blocks in the block cache like any other page.

This is the same idea as an OS page table's multi-level structure (P12) and as fractional cascading: keep a coarse map in fast memory that reduces the slow-memory search to one access.

What the numbers say

Output:

  1000 keys -> 63 sparse entries (15x smaller)
  lookup 'key0500': scan starts at byte 13282, not byte 0
  a dense index over a billion keys does not fit in memory. A sparse
  one narrows to a block, and you scan the block.

Beyond the toy

• Block size is the trade. Larger blocks mean a smaller index and better compression ratios but more bytes read per point lookup. 4--64 KiB is the usual range; scan-heavy workloads go large, point-lookup-heavy workloads go small.
• Prefix compression. Sorted keys share prefixes, so storing the delta from the previous key shrinks both the block and the index substantially. RocksDB's restart-interval design makes prefix compression compatible with binary search by resetting the prefix every N keys.
• The index is not the only in-memory structure per run — there is also the Bloom filter (block 5), and the two together are what "memory overhead" means in the RUM conjecture's third axis.

Block 5 — Bloom filter

Teaches: the read path's whole viability, for 10 bits per key

The problem. With \(R\) runs on disk, a lookup for a key that does not exist must prove absence in every run. That is \(R\) I/Os for a negative answer, and negative lookups are the common case in a write-heavy workload. The Bloom filter turns that \(O(R)\) disk cost into an \(O(R)\) memory cost.

@block(5, "Bloom filter", "the read path's whole viability, for 10 bits per key")
def b5(s, show):
    class Bloom:
        def __init__(self, n, bpk=10):
            self.m = max(8, int(n * bpk)); self.k = max(1, round(bpk * math.log(2)))
            self.bits = bytearray((self.m + 7) // 8)
        def _p(self, key):
            d = hashlib.blake2b(key, digest_size=16).digest()
            h1 = int.from_bytes(d[:8], "little"); h2 = int.from_bytes(d[8:], "little") | 1
            for i in range(self.k): yield (h1 + i * h2) % self.m
        def add(self, key):
            for p in self._p(key): self.bits[p >> 3] |= 1 << (p & 7)
        def __contains__(self, key):
            return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._p(key))
    n = 20000
    keys = [f"present{i}".encode() for i in range(n)]
    if show:
        print(f"  {'bits/key':>9}{'k':>4}{'theory':>10}{'measured':>10}{'RAM':>10}")
        for bpk in (4, 8, 10, 16):
            bf = Bloom(n, bpk)
            for k in keys: bf.add(k)
            assert all(k in bf for k in keys), "FALSE NEGATIVE -- not a Bloom filter"
            absent = [f"absent{i}".encode() for i in range(40000)]
            meas = sum(1 for k in absent if k in bf) / len(absent)
            th = (1 - math.exp(-bf.k * n / bf.m)) ** bf.k
            print(f"  {bpk:>9}{bf.k:>4}{th:>10.5f}{meas:>10.5f}"
                  f"{len(bf.bits)/1024:>9.0f}K")
        print("  never a false negative -- that is the one guarantee. Theory tracks")
        print("  measurement within a few percent at every setting.")
    return {"Bloom": Bloom}

Reading the implementation

• One-sided error, and the side matters. A Bloom filter may say "maybe present" for an absent key (a wasted read) but never "absent" for a present key (a lost result). The whole design is safe because the error direction is the harmless one — the same property that makes P02's PQ codes and P03's planner estimates usable.
• Kirsch–Mitzenmacher double hashing. Instead of \(k\) independent hash functions, compute two and derive the rest as \(h_i = h_1 + i\cdot h_2\). The false-positive rate is asymptotically unchanged and the cost drops from \(k\) hashes to 2 — a result that is both practically important and pleasant to verify numerically, which proofs.md P2--P3 does.
• The optimal number of probes is \(k = (m/n)\ln 2\), giving \(\varepsilon = 0.6185^{m/n}\). At 10 bits per key that is 0.0082 — under 1% of negative lookups touch the disk.

What the numbers say

Output:

   bits/key   k    theory  measured       RAM
          4   3   0.14689   0.14565       10K
          8   6   0.02158   0.02160       20K
         10   7   0.00819   0.00758       24K
         16  11   0.00046   0.00065       39K
  never a false negative -- that is the one guarantee. Theory tracks
  measurement within a few percent at every setting.

30.0 block reads → 0.239 for absent keys is the headline, and the measured present-key improvement (15.80 → 1.13) is the one people forget: filters help positive lookups too, because a key present in the newest run still has to be proved absent from all the older ones.

Beyond the toy

• Blocked Bloom filters. A textbook filter does \(k\) probes into a large bit array — \(k\) independent cache misses, ~850 ns at \(k\)=7 and 121 ns per miss. Constraining all \(k\) probes to a single 512-bit cache line makes it one miss for a slightly worse false-positive rate. Every production engine does this, and it is the same locality argument as P02's vector layout.
• Monkey's result. Giving every level the same bits-per-key is provably suboptimal: deeper levels hold exponentially more keys but are probed just as often, so they should get fewer bits. Reallocating under a fixed memory budget strictly reduces total false positives — same memory, better reads.
• Ribbon filters approach the information-theoretic space bound more closely (~30% less space at equal FPR) by solving a small linear system over GF(2) instead of hashing, at higher construction cost.
• Filters do not help range scans. A WHERE k BETWEEN a AND b must touch every run regardless, which is why range-heavy workloads favour levelled compaction (fewer runs) far more strongly than point-lookup workloads do.

Block 6 — The read path

Teaches: newest run first, and count every block you touch

The problem. All the machinery above exists to serve one function: get(key). This block assembles it and — more importantly — instruments it, so the cost is a measured quantity rather than an argument.

@block(6, "The read path", "newest run first, and count every block you touch")
def b6(s, show):
    class Run:
        def __init__(self, items, bpk=10):
            self.d = dict(items)
            self.bloom = s["Bloom"](max(1, len(items)), bpk) if bpk else None
            if self.bloom:
                for k in self.d: self.bloom.add(k)
        def get(self, key, stats, use_bloom=True):
            if use_bloom and self.bloom is not None and key not in self.bloom:
                stats["skipped"] += 1; return None
            stats["block_reads"] += 1
            return self.d.get(key)
    def make_db(n_runs=30, per_run=1500, bpk=10):
        runs, all_keys = [], []
        for r in range(n_runs):
            items = [(f"k:{r}:{i}".encode(), f"v{i}".encode()) for i in range(per_run)]
            all_keys += [k for k, _ in items]
            runs.append(Run(items, bpk))
        return runs, all_keys
    def get(runs, key, use_bloom=True):
        st = {"block_reads": 0, "skipped": 0}
        for run in reversed(runs):
            v = run.get(key, st, use_bloom)
            if v is not None: return v, st
        return None, st
    if show:
        runs, keys = make_db()
        st = get(runs, b"nope", True)[1]
        print(f"  30 runs. absent key WITH bloom: {st['block_reads']} block reads, "
              f"{st['skipped']} skipped")
        st = get(runs, b"nope", False)[1]
        print(f"  absent key WITHOUT bloom:      {st['block_reads']} block reads")
        print("  that ratio IS the read path. Everything else is bookkeeping.")
    return {"make_db": make_db, "get": get, "Run": Run}

Reading the implementation

• Newest run first, stop at the first hit. Correctness depends entirely on this ordering: a key overwritten in a newer run must shadow the older value, and a tombstone must shadow a live value. Search order is the versioning scheme.
• stats["block_reads"] and stats["skipped"] are the design's most valuable lines. Wall-clock time varies with cache state and machine; block reads are the invariant, and counting them is what turns "the Bloom filter feels helpful" into 30.0 → 0.239. Every storage engine worth using exposes these counters, and building them in from the start is the difference between optimising and guessing.
• The read path is \(O(R)\) filter probes plus \(\varepsilon R + 1\) block reads. That formula is the read-amplification term in the RUM trade, and it is why compaction (block 7) exists.

What the numbers say

Output:

  30 runs. absent key WITH bloom: 0 block reads, 30 skipped
  absent key WITHOUT bloom:      30 block reads
  that ratio IS the read path. Everything else is bookkeeping.

Beyond the toy

Real read paths add two layers this one omits, both caches:

• Block cache — recently read data blocks, in the engine's own memory, usually LRU or CLOCK (P12 is the same algorithm).
• OS page cache — underneath, and the source of the measurement trap in numbers.md §14, where a benchmark reported 14.9 GB/s and 1.06M IOPS by reading from RAM it believed was disk.

Which is why serious storage engines often use direct I/O: not for speed, but so that the cache they are reasoning about is the one they control.

The other omission is iterators. A range scan must merge \(R\) sorted runs, which is a \(k\)-way merge with a heap — \(O(\log R)\) per output key — and it cannot use Bloom filters at all. Range performance and point performance are different problems with different optimal configurations.

Block 7 — Compaction, and the three amplifications

Teaches: you are choosing which cost to pay

The problem. Every design decision so far has deferred work: writes are fast because they are unordered, reads are slow because of that, and space grows because nothing is deleted. Compaction is where the deferred bill is paid, and the policy decides which of the three costs you pay.

@block(7, "Compaction, and the three amplifications", "you are choosing which cost to pay")
def b7(s, show):
    def amp(T, L):
        return dict(lev=(T*L+1, L+1, 1+1/T), tier=(L+1, T*L, 2.0))
    if show:
        print(f"  {'data':>8}{'levels':>8}{'leveled W/R/S':>20}{'tiered W/R/S':>18}")
        for gb in (1, 8, 64, 512):
            L = max(1, math.ceil(math.log(gb*1e9/64e6, 10)))
            a = amp(10, L)
            print(f"  {gb:>6}GB{L:>8}"
                  f"{a['lev'][0]:>10.0f}/{a['lev'][1]:.0f}/{a['lev'][2]:.2f}"
                  f"{a['tier'][0]:>12.0f}/{a['tier'][1]:.0f}/{a['tier'][2]:.2f}")
        print("  leveled writes each byte ~31x to keep reads at 4 runs and space at")
        print("  1.1x. Size-tiered writes 4x and pays with 30 runs and 2x the disk.")
        print("  No third option wins both. That is the RUM conjecture.")
    return {"amp": amp}

Reading the implementation

The three amplifications are not independent knobs; they are three faces of one choice (RUM conjecture):

\[ \text{read amp} \sim \text{runs to probe}, \quad \text{write amp} \sim \text{times a key is rewritten}, \quad \text{space amp} \sim \frac{\text{bytes on disk}}{\text{bytes live}} \]

With fanout \(T\) and \(L = \log_T(N/M)\) levels:

They are the same structure with the merge trigger moved, and they sit at opposite ends of the read/write trade. Cassandra defaults to tiered (write- optimised), RocksDB to levelled (read-optimised), and both let you set it per level — which is what lazy levelling and Dostoevsky exploit: tiered at the small levels where writes concentrate, levelled at the largest level where most of the data lives and reads land.

What the numbers say

Output:

      data  levels       leveled W/R/S      tiered W/R/S
       1GB       2        21/3/1.10           3/20/2.00
       8GB       3        31/4/1.10           4/30/2.00
      64GB       3        31/4/1.10           4/30/2.00
     512GB       4        41/5/1.10           5/40/2.00
  leveled writes each byte ~31x to keep reads at 4 runs and space at
  1.1x. Size-tiered writes 4x and pays with 30 runs and 2x the disk.
  No third option wins both. That is the RUM conjecture.

Beyond the toy

• Compaction is a background job competing with the foreground. It consumes I/O bandwidth and CPU, so the p99 during compaction is the only p99 that exists in production. A benchmark run on a freshly loaded, fully compacted database measures a state your system will never be in.
• Write stalls. If ingest outruns compaction, L0 files accumulate, read amplification climbs, and the engine eventually throttles or halts writers. The symptom is a latency cliff rather than a slope, and the cause is a rate mismatch invisible at low load.
• Space during compaction. A levelled compaction needs room for both input and output simultaneously. A disk at 80% capacity can fail to compact — which makes it fuller. This is a genuine production failure mode with no graceful recovery.
• The hardware assumption is dated and worth re-examining. LSMs convert random writes to sequential because random/sequential was ~100× on HDD. On NVMe it is 3--10×, which is why B-trees remain competitive and why Bε-trees (batching updates in internal nodes) became interesting again. The right structure is a function of the storage medium, and the medium changed.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nSeven blocks = a storage engine. Now measure what it costs.\n")
    for bpk, label in ((0, "no filter"), (4, "4 bits/key"), (10, "10 bits/key"), (16, "16 bits/key")):
        runs, keys = s["make_db"](30, 1500, bpk)
        use = bpk > 0
        absent = [f"missing{i}".encode() for i in range(1500)]
        present = [rng.choice(keys) for _ in range(1500)]
        ra = sum(s["get"](runs, k, use)[1]["block_reads"] for k in absent) / len(absent)
        rp = sum(s["get"](runs, k, use)[1]["block_reads"] for k in present) / len(present)
        if bpk == 0:
            print(f"  {'config':<13}{'absent reads':>14}{'present reads':>15}")
        print(f"  {label:<13}{ra:>14.3f}{rp:>15.2f}")
    print("\n  Absent keys: 30 reads -> 0.25. That is the Bloom filter earning its")
    print("  125 KB per 100k keys, and it is why LSM reads are viable at all.")
    print("  Present keys: 15.5 -> 1.1. The folklore says filters only help misses;")
    print("  measured, they help hits too, because a hit must SKIP the newer runs.")
    print("\n  Crash test -- the property that matters more than any throughput number:")
    w = s["WAL"](os.path.join(DIR, "wal2"))
    for i in range(200): w.append(f"key{i}".encode(), f"val{i}".encode(), sync=(i % 50 == 0))
    w.f.flush()
    with open(w.path, "r+b") as f:                        # simulate kill -9 mid-write
        f.seek(0, 2); size = f.tell(); f.truncate(size - 7)
    recs, left = w.replay()
    print(f"    wrote 200, truncated 7 bytes off the tail, recovered {len(recs)}")
    print(f"    every recovered record is intact: "
          f"{all(k.startswith(b'key') for k, _ in recs)}")
    print("\n  Built: record format -> WAL -> memtable/flush -> sparse index ->")
    print("  bloom -> read path -> amplification.")
    print("  Missing, on the project page: real SSTable blocks (m4), tombstones (m7),")
    print("  merging iterators (m8), both compaction strategies (m9/m10), and the")
    print("  crossover figure (E3) that is the project's headline deliverable.")

Output:

Seven blocks = a storage engine. Now measure what it costs.

  config         absent reads  present reads
  no filter            30.000          15.80
  4 bits/key            4.465           3.19
  10 bits/key           0.239           1.13
  16 bits/key           0.013           1.01

  Absent keys: 30 reads -> 0.25. That is the Bloom filter earning its
  125 KB per 100k keys, and it is why LSM reads are viable at all.
  Present keys: 15.5 -> 1.1. The folklore says filters only help misses;
  measured, they help hits too, because a hit must SKIP the newer runs.

  Crash test -- the property that matters more than any throughput number:
    wrote 200, truncated 7 bytes off the tail, recovered 199
    every recovered record is intact: True

  Built: record format -> WAL -> memtable/flush -> sparse index ->
  bloom -> read path -> amplification.
  Missing, on the project page: real SSTable blocks (m4), tombstones (m7),
  merging iterators (m8), both compaction strategies (m9/m10), and the
  crossover figure (E3) that is the project's headline deliverable.

The design space

Storage engines sit on the RUM conjecture: you may optimise any two of Read overhead, Update overhead, and Memory overhead, at the cost of the third. The families below are points on that surface, not competitors.

With fanout \(T\) and \(L = \log_T(N/M)\) levels, the two LSM rows are the same structure with the compaction trigger moved, and they trade read for write amplification along exactly the RUM axis. Levelled merges eagerly so each level holds one sorted run — few runs to probe, but every key is rewritten \(O(T)\) times per level. Tiered waits until \(T\) runs accumulate — one rewrite per level, but \(T\)× more runs to search. Choosing between them is choosing your read/write ratio, and RocksDB's popularity owes much to letting you set it per level.

Latency: the numbers that force the design

Two ratios drive everything:

1. fsync ≈ 100 µs ≈ 800 syscalls ≈ 10⁵ DRAM accesses. Durability is the single most expensive thing the engine does, so the WAL batches many logical writes into one flush, and group commit exists to amortise it across concurrent writers.
2. Random/sequential ≈ 100× on HDD, ≈ 3--10× on NVMe. The LSM was designed when that ratio was 100×, which is why it converts random writes into sequential ones. On NVMe the argument is weaker — and that, not fashion, is why B-trees remain competitive on modern hardware, and why Bε-trees (which batch updates in internal nodes) became interesting again.

Where the read path actually spends time

A get on a key that is absent — the common case in a write-heavy workload — must prove absence in every run. Without filters that is \(R\) block reads; the blocks above measure 30.0 → 0.239 at 10 bits/key. The Bloom filter converts an \(O(R)\) IO cost into an \(O(R)\) memory cost plus \(\varepsilon R\) IOs, and with 10 bits/key \(\varepsilon \approx 0.0082\) (proofs.md P3).

The filter itself is a random-access structure: \(k\) probes into an \(m\)-bit array, each a likely cache miss. At 121 ns per miss and \(k = 7\), a filter probe is ~850 ns if the filter is not cached — which is why blocked Bloom filters (all \(k\) probes inside one 512-bit cache line) are standard in RocksDB. They trade a slightly worse false-positive rate for one cache miss instead of seven. This is the same locality argument as P02's vector layout.

Advanced algorithms and data structures

• Ribbon filters (Dillinger & Walzer, 2021) reach the space-efficiency limit more closely than Bloom, at ~30% less space for the same FPR, using a solvable linear system over GF(2) instead of hashing.
• Monkey (Dayan, Athanassoulis & Idreos, SIGMOD 2017) shows the standard practice of giving every level the same bits-per-key is provably suboptimal: since deeper levels hold more keys but are probed as often, allocating fewer bits to them minimises total false positives under a fixed memory budget. Same memory, strictly better reads.
• Dostoevsky and lazy levelling hybridise: tiered at the smaller levels (cheap writes) and levelled at the largest (cheap reads), which dominates both pure strategies for most workloads.
• Fractional cascading and sparse indexes are the same idea as the block above: keep one key per block in memory so a lookup is a binary search in RAM plus exactly one IO.
• SkipList vs B-tree memtable. RocksDB's default memtable is a skip list because it supports lock-free concurrent inserts; the tradeoff is worse cache locality than a B-tree, which matters once the memtable exceeds L2.
• Log-structured everything. The same transformation appears in F2FS and in SSD firmware itself: the FTL is a log-structured store with garbage collection, so an LSM on an SSD is a log on a log — which is where write amplification stacking comes from, and why discard/TRIM hints matter.

Hardware: what the medium dictates

• HDD: seek 10 ms dominates everything. Design for sequential-only: LSM, large blocks, no random reads in the write path.
• SATA/NVMe SSD: random reads are cheap and parallel. Queue depth is the new lever — one thread issuing 4 KiB reads gets ~10k IOPS; 64 in flight gets 500k+. Engines therefore need asynchronous IO (io_uring, P12) to reach device throughput at all.
• Persistent memory (Optane, now discontinued but architecturally instructive): ~300 ns loads, byte-addressable, which collapses the distinction between the WAL and the memtable and produced a research line on failure-atomic data structures.
• Zoned namespaces (ZNS): the device exposes append-only zones and refuses random writes, pushing the FTL's job into the engine. An LSM maps onto ZNS almost exactly — one zone per SSTable — and eliminates the double garbage collection.

How this connects to the rest of the track

• P03 is this engine with vectors as values, and reuses segments, tombstones and compaction verbatim.
• P07's state backend is literally RocksDB in Flink — an LSM holding streaming state, checkpointed by the mechanism in that project's block 6.
• P12's page cache is the layer beneath this one, and the page-cache trap in numbers.md §14 is the measurement error that layer causes.
• P02's PQ codes and this project's Bloom filters are the same pattern: an approximate test in fast memory guarding an exact one in slow.
• P05 replicates this engine's log; the WAL and the Raft log are the same abstraction with different durability quorums.

Failure modes at scale

• Write stalls. Ingest outruns compaction, L0 files accumulate, the engine throttles or halts writers. The visible symptom is a latency cliff, not a gradual slope, and the cause is a rate mismatch that was invisible at low load.
• Space amplification during compaction: a levelled compaction needs room for both input and output. A disk that is 80% full can fail to compact, which makes it fuller.
• fsync lying. Some devices and filesystems acknowledge before the data is durable; the crash test in the assembly is only as trustworthy as the layer underneath. Real validation requires power-cut testing or a fault-injecting filesystem.
• Tombstone accumulation: deletes make reads slower until compaction, and a full-table delete can make a scan pathologically slow — the Cassandra operational classic.

Primary sources

• O'Neil et al., The Log-Structured Merge-Tree (Acta Informatica, 1996).
• Athanassoulis et al., Designing Access Methods: The RUM Conjecture (EDBT 2016).
• Dayan, Athanassoulis & Idreos, Monkey: Optimal Navigable Key-Value Store (SIGMOD 2017).
• Dayan & Idreos, Dostoevsky (SIGMOD 2018).
• Kirsch & Mitzenmacher, Less Hashing, Same Performance (2006) — the two-hash trick used in the blocks above.
• Dillinger & Walzer, Ribbon Filter (2021).
• Rosenblum & Ousterhout, The Design and Implementation of a Log-Structured File System (1991) — where all of this starts.

Running it

python3 handson/h04_lsm.py            # every block, then the assembly
python3 handson/h04_lsm.py --block 3  # just block 3 and its prerequisites
python3 handson/h04_lsm.py --quiet    # the assembly only

What to do with this

The measurement to add is write amplification under a sustained random-write load, which is the number that decides whether an LSM is the right structure at all. Then implement levelled compaction alongside the tiered scheme here and watch the RUM trade move: levelling cuts read amplification and raises write amplification, and the crossover depends on your read/write ratio rather than on anyone's benchmark.

Milestones, experiments, readings and exit criteria for this project: P04 — Log-Structured Storage Engine.