books / ddia / ch-03SHEET 3 / 11 · REV ASIGN IN
MODULE 3 · DESIGNING DATA-INTENSIVE APPLICATIONS CH 3

Build Your Own Storage Engine

Never overwrite in place — append, and everything else in a database is just cleaning up after that one decision.

The idea

The world's simplest database is two lines of shell. One appends key,value to a file. The other greps for the last occurrence of a key. It genuinely works, and its write path is fast, because appending to the end of a file is the cheapest thing a disk does. Every serious storage engine keeps that instinct: never overwrite in place, append.

That database has two obvious problems. Reads scan the whole file, and the file grows forever. You fix reads with an in-memory map from key to byte offset, so a read is one lookup plus one seek. You fix growth by cutting the log into segments and compacting them, copying only each key's newest value into a fresh file. That is Bitcask, a real production engine. What it still cannot do is range queries, and it still needs every key to fit in memory.

The clever move is to keep each segment sorted by key. Range scans become sequential reads, merging segments becomes the merge step of mergesort, and the index can be sparse. You cannot append to a sorted file on disk, but you can in memory: collect writes in a sorted memtable, flush it out as a sorted segment when it gets big, and read memtable first then segments newest to oldest. That arrangement is an LSM-tree, the engine inside LevelDB, RocksDB and Cassandra.

Two loose ends remain. If the process dies, the memtable holds writes you already acknowledged, so you append every write to a write-ahead log first and replay it on restart. And looking up a key that does not exist forces you to check every segment, so a Bloom filter per segment turns most of those reads into no-ops. Then compare the whole thing to a B-tree engine like SQLite, and the write-versus-read amplification trade-off stops being a slogan and becomes a number you measured.

The bench — 4 exercises

EX 01

The Two-Line Database, Done Properly

Build an append-only log with an in-memory hash index and compaction — the Bitcask shape. It teaches why appending is fast and why dead data has to be swept up separately.

  1. Define a tiny text protocol (SET k v, GET k, DEL k) and make writes append a record to the active segment file
  2. Keep an in-memory map from key to (segment, offset); serve reads with one lookup and one seek
  3. Roll to a new segment past a small size threshold, and write tombstone records for DEL
  4. Implement compaction: merge segments into a new file keeping only each key's newest value, rename it into place, delete the old ones
  5. On startup, rebuild the index by scanning segments oldest to newest
hint

Compaction must write a NEW file and rename it into place — never rewrite a segment where it sits. That atomic-rename trick recurs all module.

hint

Set the segment size very small (a few hundred KB) while developing so multi-segment behavior shows up in seconds.

DONE WHEN

· 100k writes with heavy overwrites: every read returns the newest value

· After compaction, on-disk bytes shrink to roughly the live-set size

· Reads keep succeeding while compaction runs

· Kill and restart cleanly: all keys still readable

EX 02

Sort It on the Way Down

Rework the write path into an LSM-tree — memtable, SSTables, a k-way streaming merge and a hand-rolled Bloom filter. This is where range scans become possible and merging becomes cheap.

  1. Buffer writes in an in-memory sorted structure (skiplist, balanced tree, or sorted array) and flush it to a sorted SSTable at a size threshold
  2. Write a sparse index per SSTable — one offset every N entries — and scan between offsets on read
  3. Serve reads from memtable first, then SSTables newest to oldest; add SCAN lo hi returning sorted results
  4. Compact by streaming a k-way merge you write yourself, never loading whole segments into memory
  5. Add a Bloom filter per SSTable using double hashing from two base hashes, consulted before touching the file
hint

A tombstone is data, not absence. Deleting only the memtable entry lets an older SSTable resurrect the key — carry the tombstone through merges until no older segment can contradict it.

hint

Size the Bloom filter at roughly 10 bits per key with k=2 to land around a 1% false-positive rate.

hint

Test SCAN mid-flush: results must interleave memtable and segment data correctly.

DONE WHEN

· SCAN over a million keys returns complete, correctly sorted results

· Under a sustained write storm the segment count stays bounded

· Peak memory during a merge stays well below the total size of the segments being merged

· Over 90% of lookups for never-written keys read zero segment files

EX 03

kill -9 Certified

Add a write-ahead log with checksums and crash recovery, then kill your own engine mid-write-storm until it stops losing data. This is the difference between writing to a file and being on disk.

  1. Append each write, with a CRC32 checksum, to a WAL and flush it to disk before replying OK
  2. On startup, load SSTables then replay the WAL into a fresh memtable
  3. Truncate any torn tail record whose checksum fails instead of crashing or inventing a value
  4. Rotate or delete the WAL only once its memtable is safely flushed to an SSTable
  5. Expose an fsync-per-write mode and a batched mode, and measure the throughput gap between them
hint

"I wrote it to the file" and "it is on disk" are different claims — if acknowledged writes vanish, you are missing the fsync, not the append.

hint

Drive the crashes from a script with a seeded random kill time so a failure is reproducible.

hint

Write large values in the storm to widen the append window and actually produce a torn tail.

DONE WHEN

· Twenty randomized SIGKILLs mid-storm: every acknowledged write is present and correct after restart

· The engine accepts new writes immediately after every recovery

· A crash landing mid-append recovers without hanging, crashing, or returning a bogus value

· Earlier exercises' checks still pass against the recovered store

EX 04

The Other Tribe

Race your LSM engine against SQLite's B-tree on write-heavy and read-heavy workloads, and measure write amplification instead of reciting it.

  1. Run identical operation streams against both engines: 95% random writes, then 95% Zipfian point reads
  2. Record p50/p95/p99 latency and throughput per workload per engine
  3. Measure bytes physically written per byte of logical data by watching data-directory growth
  4. Write a short note explaining why the LSM wins writes, why the B-tree wins point reads, and where compaction pauses show up in your p99
hint

Match durability settings — put SQLite in WAL mode with synchronous=FULL if your engine fsyncs. Unfair pragmas are how database marketing works.

hint

If your numbers do not show the expected shape, explain why rather than tuning until they do.

hint

Stretch: store the same records as one file per column with run-length encoding and race an AVG query against a row scan.

DONE WHEN

· Both workloads ran at real volume with percentile numbers recorded for each engine

· A write-amplification factor is computed for both engines

· Your trade-off note names a concrete cause for each result you saw

· Stretch: the column-store aggregate beats the row scan by a clear margin

Go deeper (after the bench)

Read DDIA Ch. 3 (pp. 69-103): "Hash Indexes" and "SSTables and LSM-Trees" before exercises 1-2, "B-Trees" and "Column-Oriented Storage" before the benchmark — Kleppmann's comparison section is the answer key to your trade-off note, so write yours first. Then read the Bitcask paper (Sheehy & Smith, 2010, free six-page PDF): exercise 1 is that paper implemented, and reading it afterwards is a rare chance to recognize every decision in a production design doc.