Distributed Systems Engineer — Build Databases & Consensus From Scratch

"What I cannot create, I do not understand." — Richard Feynman

A lab-based curriculum for becoming a senior distributed systems engineer by building the systems you'll one day operate, debug, and replace: LevelDB (LSM-tree storage), SQLite (B-tree storage + SQL), and the three canonical consensus algorithms — Raft, Paxos, and ZAB — all implemented from scratch in Rust, Go, and C++.

Why This Repo Exists

Most engineers treat databases and consensus as black boxes. This curriculum makes them transparent. You will:

• Write storage engines that flush, compact, recover, and serve concurrent reads.
• Implement consensus protocols that survive node crashes, network partitions, and message reordering.
• Reason about hardware trade-offs: SSD vs HDD seek latency, write amplification, fsync cost, io_uring vs blocking I/O, cache-line locality, NUMA effects.
• Compare algorithm families: LSM vs B-tree, level-based vs size-tiered compaction, Raft vs Multi-Paxos vs ZAB.
• Build the same thing three times — once in each language — to internalize the design (not the syntax).

Curriculum at a Glance

See PHASES.md for the full breakdown with learning objectives per lab.

How To Use This Repo

1. Read TOOLS.md and install the required toolchains (Rust, Go, C++/CMake).
2. Start with db-01-storage-primitives/. Each lab is self-contained and has the same shape:

   db-NN-<name>/
   ├── CONCEPTS.md       # The "why" — read this first
   ├── references.md     # Papers and source-code links to study
   ├── docs/
   │   ├── analysis.md       # Design trade-offs (hardware, algorithmic)
   │   ├── broader-ideas.md  # Extensions, alternatives, future work
   │   ├── execution.md      # Toolchain versions, quick-start commands
   │   ├── observation.md    # Debugging, profiling, monitoring
   │   └── verification.md   # Pass/fail checks for your implementation
   ├── steps/            # Numbered, sequential implementation guides
   │   ├── 01-*.md
   │   └── 02-*.md
   └── src/
       ├── rust/         # Cargo workspace
       ├── go/           # Go module
       └── cpp/          # CMake project
   

3. Work through steps/ in order. The reference code in src/ is a target — try to write your own first, then compare.
4. Run the checks in docs/verification.md before moving on.

What You Will Build

By the end of the curriculum you will have implemented (×3 languages):

• A crash-safe write-ahead log with CRC32 checksums and group commit.
• A skip-list MemTable, an SSTable file format with block compression, and level-based compaction.
• A page-oriented B+-tree with a pager, rollback journal, and WAL mode.
• A hand-written SQL tokenizer, parser, AST, and bytecode virtual machine.
• A transaction manager with MVCC snapshot reads and serializable writes.
• A complete Raft implementation with snapshotting and membership changes.
• Single-decree Paxos and Multi-Paxos with a stable leader.
• A simplified ZAB broadcast layer with epoch transitions.
• A 3-node distributed KV store combining Raft with your LevelDB clone.
• A capstone mini distributed SQL database (the storage engine, the SQL frontend, and Raft replication — all your own code).

Prerequisites

• Comfortable with C-family syntax in at least one systems language (you'll pick up the other two as you go).
• Familiarity with binary trees, hash tables, and Big-O analysis.
• Basic Linux command-line and git.
• Not required: prior distributed systems knowledge, SQL internals knowledge, or database engine experience. We build it all from the ground up.

Pedagogical Style

Modeled after cstack/db_tutorial (concept-first, incremental, runnable code at every step) and the ai-engineering/ lab repo (consistent 8-part CONCEPTS.md, docs/, steps/, src/ structure).

Every CONCEPTS.md follows the same 8-part framework:

1. What Is It — one-paragraph executive summary
2. Why It Matters — concrete benefits
3. How It Works — ASCII architecture diagram
4. Core Terminology — table of precise definitions
5. Mental Models — analogies for intuition
6. Common Misconceptions — myths corrected
7. Interview Talking Points — what to say in a senior systems interview
8. Connections to Other Labs — how this fits the bigger picture

Status

See PHASES.md for per-lab status.

License

MIT — see source headers in each implementation.

Phases & Labs

This curriculum has 5 phases and 23 labs. Phases build on each other, but within Phase 4 (consensus) you can do Raft → Paxos → ZAB in any order after the foundations in db-16.

Legend: ✅ complete · 🟡 scaffolded · ⬜ planned

Phase 1 — Storage Primitives & Foundations

Before you can build a database, you need to understand the medium it lives on.

Phase 2 — LevelDB / LSM-Tree

Build a production-shape LSM-tree key-value store, the way Google built LevelDB and Meta forked it into RocksDB.

Phase 3 — SQLite / B-Tree

Build a B+-tree storage engine, a pager, a SQL parser, a bytecode VM, and a transaction manager.

Phase 4 — Consensus Algorithms

The three canonical consensus families — implemented, tested, and compared.

Phase 5 — Advanced Storage & Capstone

Suggested Pace

• Full-time learner: ~2 labs per week ⇒ ~12 weeks end-to-end.
• Side-project learner: ~1 lab every 1–2 weeks ⇒ ~6 months.
• Reading-only path: skim CONCEPTS.md + docs/analysis.md per lab ⇒ ~1 week for the entire curriculum.

Recommended Progression

Phase 1 (must do all 4 in order)
   │
   ├─→ Phase 2 (LevelDB)  ──┐
   │                        │
   └─→ Phase 3 (SQLite) ────┤
                            ↓
                         Phase 4 (Consensus)
                            ↓
                         Phase 5 (Capstone)

Phase 2 and Phase 3 are independent — pick the storage style that excites you first. Phase 4 only references Phase 1 fundamentals, so you can detour into consensus early if you want. Phase 5's capstone assumes all four prior phases.

Glossary

A unified glossary of terms used across all labs. Terms are grouped by domain.

Storage & I/O

Hardware

Data Structures

Consensus

Transactions

SQL Engine

Operational

Toolchain Setup

All labs target Linux-first with macOS as a supported secondary platform. Windows is not supported (no io_uring, no O_DIRECT semantics we rely on; use WSL2 instead).

Required Versions

Per-Language Setup

Rust

# rustup is the canonical installer.
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
rustup default stable
rustup component add clippy rustfmt
cargo install cargo-nextest        # faster, parallel test runner
cargo install cargo-flamegraph     # used in db-22

Verify:

rustc --version    # rustc 1.78.0 or newer
cargo --version

Go

# macOS
brew install go
# Linux: download from https://go.dev/dl/ — distro packages are usually old.

# Useful tools
go install honnef.co/go/tools/cmd/staticcheck@latest
go install golang.org/x/perf/cmd/benchstat@latest

Verify:

go version    # go1.22 or newer

C++

# macOS
xcode-select --install
brew install cmake ninja llvm

# Linux (Debian/Ubuntu)
sudo apt-get install -y build-essential cmake ninja-build clang-17 clang-format-17 \
                        libsnappy-dev liburing-dev

Verify:

clang++ --version   # Clang 16 or newer
cmake --version     # 3.28 or newer

Optional but recommended:

• liburing-dev — required only for db-21 (io_uring lab) on Linux.
• libsnappy-dev — used in db-06 (SSTable block compression).
• valgrind / lldb — for memory and crash debugging.

Per-Lab Build Commands

Every lab src/<lang>/ is self-contained and has these commands:

docs/execution.md in each lab repeats the exact commands with the lab-specific binary names.

OS-Specific Notes

Linux

• io_uring requires kernel ≥ 5.1 (≥ 5.6 for most useful features). Check with uname -r.
• O_DIRECT works on most filesystems but is rejected by tmpfs — use a real disk path in tests.
• For accurate latency benchmarks, disable CPU frequency scaling: sudo cpupower frequency-set -g performance.

macOS

• No io_uring — db-21 falls back to kqueue + worker pool. The lab explains the difference.
• O_DIRECT does not exist; use F_NOCACHE via fcntl (the lab provides the wrapper).
• fsync(2) does not guarantee data hits stable storage on macOS — use fcntl(F_FULLFSYNC). Labs handle this.

Editor / IDE

Any editor works. VS Code with these extensions is what the reference implementations were written in:

• rust-lang.rust-analyzer
• golang.go
• llvm-vs-code-extensions.vscode-clangd
• ms-vscode.cmake-tools

Sanity Check Script

Run this once after setup to verify everything works:

cd db-01-storage-primitives
( cd src/rust && cargo build --release ) && \
( cd src/go && go build ./... ) && \
( cd src/cpp && cmake -B build -G Ninja && cmake --build build ) && \
echo "All three toolchains OK."

Storage Primitives

The lab that earns you the right to talk about databases.

1. What Is It

This lab teaches the physical layer that every storage engine sits on top of: how data moves between a process's memory and a block device. You will learn the OS page model, the byte-order question (endianness), the three main file I/O styles (read/write, pread/pwrite, mmap, O_DIRECT), buffer alignment, and the durability primitive fsync. You'll also internalize the latency numbers for HDD, SATA SSD, and NVMe SSD that drive every storage design decision in the rest of the curriculum. The deliverable is a tiny page allocator plus a hexdump utility, written three times — once in Rust, once in Go, and once in C++ — exercising pread/pwrite against a real disk file.

2. Why It Matters

• Every later lab depends on these primitives. LSM-trees, B-trees, WALs — they're all built on pread/pwrite/fsync and an understanding of the page cache.
• Choosing the right I/O style changes throughput by 10–100×. A naïve read loop is not the same as pread from many threads, which is not the same as io_uring, which is not the same as mmap.
• Hardware shapes the algorithm. LSM-trees exist because random writes on HDDs were catastrophic. NVMe IOPS now make some classic assumptions wrong. Knowing the numbers prevents cargo-culting designs from the wrong decade.
• fsync is the single most expensive syscall in any database. Understanding when it must be called — and when you can amortize it — is the difference between 100 commits/sec and 100,000 commits/sec.

3. How It Works

                  User process
   ┌───────────────────────────────────────────────────┐
   │   Your code: page_allocator, db.put("key", val)   │
   │           buffer = [u8; PAGE_SIZE]                │
   └────────────┬───────────────────┬──────────────────┘
                │                   │
                │  pread/pwrite     │  mmap
                │  (explicit copy)  │  (page-fault driven)
                ▼                   ▼
        ┌─────────────────────────────────────┐
        │       Kernel page cache (RAM)       │  ← cached pages,
        │   4 KiB pages, indexed by inode+off │     LRU-evicted
        └────────────────┬────────────────────┘
                         │  block layer
                         │  (scheduler, mq-deadline / none for NVMe)
                         ▼
                ┌─────────────────────┐
                │  Device driver      │  fsync() blocks here
                │  (NVMe / SATA AHCI) │  until disk acks
                └─────────┬───────────┘
                          ▼
                ┌─────────────────────┐
                │  Storage hardware   │  HDD:  ~5 ms  random
                │  HDD / SSD / NVMe   │  SSD:  ~100 µs random
                │                     │  NVMe: ~50  µs random
                └─────────────────────┘

Three things to internalize from this picture:

1. Without O_DIRECT, you always go through the kernel page cache. Your pread may hit a warm cache (memcpy speed) or cold cache (full disk I/O). Latency variance is enormous.
2. fsync is the only way to tell the device to flush its own write cache. Without it, "the write returned" means "the kernel accepted it", not "it survives a power loss".
3. mmap and pread are fundamentally different mental models. mmap makes I/O implicit (page faults), pread makes it explicit (syscalls). LMDB chose mmap. SQLite, LevelDB, and PostgreSQL chose pread/pwrite. We will use pread/pwrite for predictability, and discuss mmap in the analysis.

4. Core Terminology

5. Mental Models

The page cache is a transparent cache, not a database. Think of pread like Map::get: if the key is in the cache, it's a memcpy; if it's not, the kernel goes to disk for you. You can't observe a cache miss with timing alone in production — that's the whole point of caches and the whole reason benchmarks lie.

fsync is a phone call to the disk. All other writes are "I told the postman" — fast, no guarantee. fsync is "I waited on the line while the disk confirmed the package arrived." Phone calls are slow. Group commits = bundling 100 packages into one call.

mmap is "make the file look like an array". pread is "I will ask for bytes one request at a time". The first is convenient. The second is predictable. Convenience and predictability are usually at war.

Sequential vs random I/O on an HDD is 100× different. On NVMe it's 2–3×. This is why LSM-trees won the 2000s and why "just append" got rediscovered in the 2010s and why NVMe makes some of those assumptions less critical in the 2020s. Hardware shapes design.

6. Common Misconceptions

1. "write returning means my data is safe." False. The kernel buffered it. Only fsync (or fdatasync for data-only, or F_FULLFSYNC on macOS) guarantees durability.
2. "mmap is faster than pread because there's no syscall." Often false. mmap access generates page faults, which are also context switches into the kernel, plus they're synchronous (you can't overlap them with computation as easily). LMDB-style designs win when the working set fits in RAM; they suffer on writes due to fsyncing the mapping.
3. "SSDs make random vs sequential irrelevant." Partially true. Random reads are fast, but random writes still incur garbage collection and write amplification at the firmware level. Sequential writes still reduce hardware WA significantly.
4. "4 KiB is always the right page size." No. It matches OS page size, which is friendly for mmap and for the page cache. But LevelDB uses 4 KiB blocks (read amp) and 64 MiB SSTables (sequential writes). PostgreSQL uses 8 KiB pages. The "right" page size depends on workload.
5. "fsync flushes only my file." On many filesystems and many older kernels, fsync could flush more (or less) than expected. Modern ext4/xfs are sane, but historical PostgreSQL fsync bugs (2018) showed that the contract is more subtle than it looks.

7. Interview Talking Points

• "For a write-heavy OLTP workload on local NVMe, I'd start with direct pwrite + fdatasync rather than mmap. mmap makes durable writes ambiguous — msync(MS_SYNC) is a heavier hammer than fdatasync because it covers the whole mapping, and you give up control over write ordering."
• "My rule of thumb: HDD random read ≈ 5 ms, SATA SSD ≈ 100 µs, NVMe ≈ 50 µs, RAM ≈ 100 ns, L1 ≈ 1 ns. Every five orders of magnitude is where a different design becomes interesting. LSM-trees collapse the gap between random and sequential by converting random writes to sequential ones."
• "fsync is what amortizes the difference between 100 commits/sec and 100,000 commits/sec. Group commit batches N concurrent transactions into one fsync, trading latency (one transaction may wait ~5 ms for a batch) for throughput (100× more committed transactions per fsync). Postgres, MySQL InnoDB, and SQLite all do this."
• "O_DIRECT isn't a free win. You skip the page cache, so you have to implement your own cache and your buffers must be aligned. PostgreSQL deliberately uses the page cache and lets the OS do that work for it. Oracle and Sybase use O_DIRECT. The choice depends on whether you trust your buffer manager more than the kernel's."

8. Connections to Other Labs

• db-02 — uses the page-aligned allocator from here for skip-list and hash-table node storage.
• db-03 — the WAL is literally pwrite + fdatasync in a loop; this lab gives you the muscle memory.
• db-06 — SSTable blocks are read via pread at known offsets; this lab is the read side.
• db-11 — the SQLite pager is a pread/pwrite-based page cache; you'll reimplement what the kernel does for you here.
• db-21 — revisits I/O with io_uring (Linux) and O_DIRECT for the advanced cases; this lab establishes the baseline.

References — Storage Primitives

Canonical Papers & Specifications

• POSIX pread/pwrite/fsync — https://pubs.opengroup.org/onlinepubs/9699919799/functions/pread.html
• Linux open(2) (for O_DIRECT, O_DSYNC) — https://man7.org/linux/man-pages/man2/open.2.html
• Linux fsync(2) — https://man7.org/linux/man-pages/man2/fsync.2.html
• Linux io_uring design — https://kernel.dk/io_uring.pdf (Jens Axboe, 2019). Read for db-21.
• macOS F_FULLFSYNC — man fcntl on macOS; see also Apple Tech Note TN1150.

Hardware Numbers

• "Latency Numbers Every Programmer Should Know" — Jeff Dean, 2012. https://gist.github.com/jboner/2841832
• "What Every Programmer Should Know About Memory" — Ulrich Drepper, 2007. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf (long but seminal)
• NVMe specification — https://nvmexpress.org/specifications/ (skim §3 on queues, §4 on commands)

Battle Stories

• "PostgreSQL's fsync surprise" — https://lwn.net/Articles/752063/. Why fsync semantics on Linux were subtler than database authors assumed. Read this.
• "Files are Hard" — Dan Luu. https://danluu.com/file-consistency/. Survey of how filesystems can lose your data.
• "mmap-based databases vs. read/write-based databases" — Andy Pavlo et al., "Are You Sure You Want to Use MMAP in Your Database Management System?", CIDR 2022. https://db.cs.cmu.edu/mmap-cidr2022/. Required reading if you ever consider mmap.

Implementation References

• SQLite OS interface — https://www.sqlite.org/src/file/src/os_unix.c (search for unixSync to see real-world fsync handling, including the macOS F_FULLFSYNC workaround)
• LevelDB env_posix.cc — https://github.com/google/leveldb/blob/main/util/env_posix.cc (look at PosixWritableFile::Sync)
• LMDB — http://www.lmdb.tech/doc/ (the canonical mmap database; read for contrast)

Books

• "Operating Systems: Three Easy Pieces" — Arpaci-Dusseau. Free at https://pages.cs.wisc.edu/~remzi/OSTEP/. Chapters 39–44 (persistence) are exactly this lab.
• "Designing Data-Intensive Applications" — Martin Kleppmann, O'Reilly. Chapter 3 ("Storage and Retrieval") frames the LSM vs B-tree debate that drives Phases 2 and 3.

Analysis — Storage Primitives

This document is for the design decisions and the trade-offs. The CONCEPTS.md told you what exists; this tells you why we picked one over the other and what you'd reach for in different conditions.

Decision 1: pread/pwrite over read/write

We use pread/pwrite (explicit offsets) instead of read/write + lseek.

Verdict: pread/pwrite is strictly better for database-style access patterns. The only reason to use the cursor variant is when you genuinely have a single sequential reader (e.g., tail -f).

Decision 2: pread/pwrite over mmap

This is more nuanced. We use explicit I/O for all labs except where we deliberately study mmap.

The Pavlo et al. CIDR 2022 paper (linked in references.md) is the definitive teardown. TL;DR: mmap is fine when (a) the dataset fits in RAM, (b) the workload is read-heavy, and (c) you don't care about latency tails. For everything else, pread/pwrite wins.

Decision 3: Page Size = 4 KiB

We pick 4 KiB as the default page size in this lab and reconsider in later labs.

Rule of thumb: page size ≈ the device sector size × small constant. With NVMe at 4 KiB LBA and the OS page also at 4 KiB, going smaller is fighting the hardware and going larger is amortizing a smaller win.

Decision 4: Endianness on Disk

Our on-disk format is little-endian. Justified by:

1. x86 and ARM (in normal mode) are little-endian. Big-endian on these platforms means a byte swap on every read.
2. Network protocols use big-endian by convention, but our on-disk format is not a network protocol — it's only read by the same machine (or by an explicit migration tool).
3. LevelDB and RocksDB use little-endian for fixed-width fields, with varints for variable-width. We follow that convention for compatibility of mental model.
4. SQLite uses big-endian for historical reasons (the format dates to 2000, when MIPS/PowerPC/SPARC were still common). It's a legitimate alternative; we just optimize for the modern hardware reality.

Always use explicit conversion functions at the I/O boundary. Never memcpy an int to disk and hope. Our Rust code uses u64::to_le_bytes; Go uses encoding/binary.LittleEndian; C++20 uses std::endian + std::byteswap.

Decision 5: When to call fsync

The cost of fsync on consumer NVMe is roughly:

• Single-threaded latency: ~50 µs–1 ms depending on outstanding writes
• Throughput-limited: roughly 5,000–20,000 fsync/sec before contention dominates

The cost on a HDD is 5–15 ms per fsync. That's why ye olde databases did group commit.

The right policy depends on durability requirements:

The right design for Phase 2's WAL is group commit: when a writer finishes, it waits on a condition variable; the WAL writer thread pwrites pending records, fdatasyncs once, then wakes every waiter. We'll build this in db-03.

macOS Caveat

On macOS, fsync(fd) does not flush the drive's write cache — it only sends the data to the drive. To get true durability you must call fcntl(fd, F_FULLFSYNC), which can be 10–100× slower than fsync on the same hardware. SQLite, LevelDB, and Postgres all handle this. Our wrapper in src/*/fsync_full.* does the platform dispatch.

Decision 6: O_DIRECT — Not in This Lab

We don't use O_DIRECT in Lab 01 because:

1. It requires aligned buffers (typically 4 KiB), aligned offsets, and aligned I/O sizes.
2. It bypasses the page cache, so you must implement your own — which is a buffer manager (Phase 3, db-11).
3. It's not available on macOS — you'd use fcntl(fd, F_NOCACHE, 1) as the closest analogue, but it has weaker semantics.

We revisit O_DIRECT in db-21-storage-engine-advanced once we have a buffer manager worth talking about.

Hardware Numbers Cheat-Sheet

Memorize these. They drive every storage design decision:

L1 cache hit            1   ns
Branch mispredict       3   ns
L2 cache hit           ~4   ns
L3 cache hit          ~15   ns
DRAM access          ~100   ns       — 100× L1
Context switch       ~1–5  µs
NVMe random read      ~50  µs        — 500× DRAM
NVMe sequential read  ~5   µs/4KB
SATA SSD random read ~100  µs
SATA SSD seq read    ~10   µs/4KB
HDD random read       ~5   ms        — 100,000× DRAM
HDD sequential read  ~30   µs/4KB    (~150 MB/s)
fsync on NVMe       ~50 µs–1 ms
fsync on HDD          ~10 ms
F_FULLFSYNC (macOS)   ~10–50 ms      — actually flushes drive cache
Network RTT same DC   ~500 µs
Network RTT same region ~1 ms
Network RTT cross-region ~50–150 ms  — drives Raft heartbeat tuning in db-17

Five-order-of-magnitude gaps are where the design changes. Between L1 and DRAM (100×), you can ignore it. Between DRAM and disk (1000×), you can't. Between disk and network cross-region (1000× again), distributed systems get hard.

What Breaks at Scale

• Filesystem journal contention: fsync on ext4 serializes through the FS journal. Many concurrent fsyncs on the same FS don't scale linearly. Mitigation: one WAL file per database, dedicated FS for WAL.
• Page cache thrashing: when working set > RAM, every pread is a miss. The kernel's LRU is generic; an app-aware cache (Phase 2's block cache, Phase 3's pager) does better.
• fsync failure handling: on Linux, a failed fsync can mark dirty pages as clean — silently losing your data. This is the "fsyncgate" referenced in the references. Mitigation: panic on fsync error and crash-recover from the WAL (modern Postgres does this).
• NVMe queue depth: NVMe shines with QD=32–128 in flight. A single-threaded pread loop runs at QD=1 and leaves most of the drive idle. io_uring (Phase 5) fixes this.

Execution — Storage Primitives

Prerequisites

You've completed the toolchain setup in ../../TOOLS.md. To confirm:

rustc --version      # ≥ 1.78
go version           # ≥ 1.22
clang++ --version    # ≥ 16  (or g++ ≥ 13)
cmake --version      # ≥ 3.28

Quick Start — All Three Languages

From the lab root:

# Rust
( cd src/rust && cargo build --release )
./src/rust/target/release/pagealloc write /tmp/lab01.bin 0 "hello, disk"
./src/rust/target/release/pagealloc read  /tmp/lab01.bin 0
./src/rust/target/release/pagealloc hexdump /tmp/lab01.bin

# Go
( cd src/go && go build -o /tmp/pagealloc-go ./cmd/pagealloc )
/tmp/pagealloc-go write /tmp/lab01.bin 0 "hello, disk"
/tmp/pagealloc-go read  /tmp/lab01.bin 0
/tmp/pagealloc-go hexdump /tmp/lab01.bin

# C++
( cd src/cpp && cmake -B build -G Ninja -DCMAKE_BUILD_TYPE=Release && cmake --build build )
./src/cpp/build/pagealloc write /tmp/lab01.bin 0 "hello, disk"
./src/cpp/build/pagealloc read  /tmp/lab01.bin 0
./src/cpp/build/pagealloc hexdump /tmp/lab01.bin

All three binaries are byte-compatible — write with one, read with another, get the same bytes.

CLI Reference (all three implementations)

Tests

# Rust
( cd src/rust && cargo test )

# Go
( cd src/go && go test ./... )

# C++
( cd src/cpp && cmake --build build && ctest --test-dir build --output-on-failure )

Each test suite covers:

1. Round-trip: write then read returns the same bytes.
2. Cross-implementation: a file written by Rust must read correctly with the Go and C++ binaries (run by scripts/cross_test.sh).
3. fsync is called on write (verified by strace -e fsync in the cross_test script on Linux).
4. Endianness sanity: the page header uses little-endian and is identical across implementations.

Environment Variables

Observation — Storage Primitives

How to look inside the page cache, watch syscalls, measure latency, and prove to yourself that your code is doing what you think.

Looking at the Page Cache

Linux

# What's in the page cache for our file? (Requires `pcstat` or vmtouch.)
go install github.com/tobert/pcstat/pcstat@latest
pcstat /tmp/lab01.bin

# Drop the page cache (requires root) — to test "cold" reads.
sync && sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'

macOS

# `purge` drops the unified buffer cache (requires admin password).
sudo purge

# `fs_usage` is the macOS strace-for-files.
sudo fs_usage -w -f filesys ./src/rust/target/release/pagealloc

Watching Syscalls

# Linux
strace -e trace=openat,pread64,pwrite64,fsync,fdatasync \
       ./src/go/pagealloc-go write /tmp/lab01.bin 0 "hello"

# macOS  (sudo required for dtrace)
sudo dtruss -f -t pread,pwrite,fsync ./src/cpp/build/pagealloc write /tmp/lab01.bin 0 "hello" 2>&1

You should see — in order:

openat(AT_FDCWD, "/tmp/lab01.bin", O_RDWR|O_CREAT, 0644) = 3
pwrite64(3, "hello\0\0...", 4096, 0)                    = 4096
fdatasync(3)                                            = 0
close(3)                                                = 0

If you see read(3, ...) without an offset, you're using buffered I/O — that's wrong for this lab. If you see no fsync/fdatasync, your durability is fake.

Measuring Latency

The bench subcommand measures cold-cache and warm-cache pread latency:

# Preallocate a 100 MB file, then do 10000 random 4 KiB reads.
./src/rust/target/release/pagealloc bench /tmp/lab01.bin 25600 10000

Expected output:

preallocated: 25600 pages = 102400 KiB
warm-cache reads:   p50=3.1 µs   p99=8.4 µs   throughput=315 MB/s
dropped page cache
cold-cache reads:   p50=78 µs    p99=210 µs   throughput=51 MB/s

The exact numbers depend on your hardware. The shape matters:

• Warm p50 ≈ 1–5 µs: that's a memcpy from the page cache. No actual disk I/O.
• Cold p50 ≈ 50–200 µs on NVMe, 5–15 ms on a spinning disk.
• p99 > 10× p50: latency tails are real; this motivates io_uring and dedicated I/O threads.

Profiling Tools

Rust

cargo install cargo-flamegraph
cd src/rust
cargo flamegraph --release --bin pagealloc -- bench /tmp/lab01.bin 25600 100000
# open flamegraph.svg in your browser

Go

cd src/go
go test -bench=BenchmarkPread -cpuprofile=cpu.prof ./...
go tool pprof -http=:8080 cpu.prof

C++

# Linux
perf record -F 999 -g ./src/cpp/build/pagealloc bench /tmp/lab01.bin 25600 100000
perf report

# macOS (use Instruments.app or sample)
sample pagealloc 5 -file /tmp/sample.txt

Watching Disk Throughput

# Linux  (iostat from sysstat package)
iostat -dx 1 nvme0n1

# macOS
sudo fs_usage -w -f diskio

While running pagealloc bench, watch r/s (reads per second), rkB/s, and await (avg I/O latency in ms). For NVMe, expect r/s to plateau in the thousands for QD=1; you'd need io_uring (Lab 21) to push it into the hundreds of thousands.

Verifying Endianness

# Write the integer 0x01020304 into a fresh file (we'll write it as bytes via hexdump).
./src/rust/target/release/pagealloc write /tmp/endian.bin 0 ""
# In a separate REPL session, use whichever language you prefer to write a binary u32 to the file.
# Then xxd the file:
xxd /tmp/endian.bin | head -1

A little-endian system writes 04 03 02 01 for the value 0x01020304. If you see 01 02 03 04, either your machine is big-endian (unlikely on x86/ARM) or your code is using to_be_bytes somewhere.

Verification — Storage Primitives

The pass/fail checks for this lab. If all eight pass for all three implementations, you are done.

Per-Implementation Checks

For each of src/rust, src/go, src/cpp:

V1 — Builds

# Rust
( cd src/rust && cargo build --release ) && echo "RUST OK"
# Go
( cd src/go && go build ./... ) && echo "GO OK"
# C++
( cd src/cpp && cmake -B build -G Ninja -DCMAKE_BUILD_TYPE=Release && cmake --build build ) && echo "CPP OK"

V2 — Unit Tests Pass

( cd src/rust && cargo test --release ) && echo "RUST TESTS OK"
( cd src/go   && go test ./... )         && echo "GO TESTS OK"
( cd src/cpp/build && ctest --output-on-failure ) && echo "CPP TESTS OK"

V3 — Round-Trip

# Per binary:
$BIN write /tmp/v3.bin 5 "hello, lab"
$BIN read  /tmp/v3.bin 5 | grep -q "^hello, lab$" && echo "V3 OK"

V4 — fsync Is Called (Linux only)

strace -e fsync,fdatasync -o /tmp/syscalls.log $BIN write /tmp/v4.bin 0 "x"
grep -E 'fsync|fdatasync' /tmp/syscalls.log && echo "V4 OK"

(Expected: at least one of fsync(...) or fdatasync(...) in the trace. On macOS substitute sudo dtruss -t fsync.)

Cross-Implementation Checks

V5 — Byte-Compatibility

Files written by one implementation must read identically with the others.

RUST=./src/rust/target/release/pagealloc
GO=./src/go/pagealloc-go
CPP=./src/cpp/build/pagealloc

$RUST write /tmp/v5.bin 3 "cross-lang ok"
$GO   read  /tmp/v5.bin 3 | grep -q "^cross-lang ok$" && echo "GO read RUST OK"
$CPP  read  /tmp/v5.bin 3 | grep -q "^cross-lang ok$" && echo "CPP read RUST OK"

$GO   write /tmp/v5.bin 7 "go writes"
$CPP  read  /tmp/v5.bin 7 | grep -q "^go writes$" && echo "CPP read GO OK"
$RUST read  /tmp/v5.bin 7 | grep -q "^go writes$" && echo "RUST read GO OK"

V6 — Hexdump Identical

$RUST hexdump /tmp/v5.bin > /tmp/v6.rust.hex
$GO   hexdump /tmp/v5.bin > /tmp/v6.go.hex
$CPP  hexdump /tmp/v5.bin > /tmp/v6.cpp.hex
diff /tmp/v6.rust.hex /tmp/v6.go.hex && diff /tmp/v6.rust.hex /tmp/v6.cpp.hex && echo "V6 OK"

V7 — Endianness Sanity

The first 8 bytes of each non-empty page should be a little-endian magic constant 0x44534531_50414745 (DSE1PAGE reversed):

xxd -l 8 /tmp/v5.bin | head -1
# Expected: 00000000: 4547 4150 3145 5344

If you see 4453 4531 5041 4745, your implementation is writing big-endian — fix that.

V8 — Benchmark Smoke

$RUST bench /tmp/v8.bin 1024 1000
# Expected: prints both warm-cache and cold-cache p50/p99 lines without crashing.

Master Script

A single command to run everything (provided as scripts/verify.sh):

bash scripts/verify.sh

Expected output ends with:

====================================================
ALL 8 CHECKS PASSED for RUST, GO, CPP
====================================================

If any check fails, the script exits non-zero and prints which check + which implementation failed.

Broader Ideas — Storage Primitives

Where to go after this lab if you want to push deeper. Each idea is a self-contained extension or alternative.

1. Replace pread with io_uring (Linux)

The single biggest jump from this lab's design to a modern engine is moving from synchronous syscalls to async submission queues. With pread at QD=1, NVMe runs at ~5% of its IOPS. With io_uring at QD=32+, it hits the spec sheet.

• Lab pointer: db-21-storage-engine-advanced does this end-to-end.
• Self-study: implement a pread_async API now that internally still uses pread but queues requests through a crossbeam channel (Rust) / goroutine pool (Go) / std::jthread worker pool (C++). When you then swap the backend for io_uring, no API consumer changes.
• Reference: Jens Axboe's "Efficient IO with io_uring" (https://kernel.dk/io_uring.pdf), §3.

2. Page Layout — Slotted Pages vs Fixed-Size Records

Our pages are zero-padded ASCII. Real engines use slotted pages:

┌────────┬────────────────────────────┬──────┐
│ header │ slot[0] slot[1] ...        │ free │
│        │ → offsets into page        │      │
├────────┴────────────────────────────┴──────┤
│ ← record N ← record 1 ← record 0           │  (grows from end)
└────────────────────────────────────────────┘

This lets variable-length records share a page without external fragmentation. PostgreSQL, MySQL InnoDB, and SQLite all use slotted pages. Try this: extend pagealloc so each page holds a slot directory and stores up to 16 variable-length keys per page. This is the warm-up for db-10.

3. Copy-on-Write Pages (LMDB-style)

Instead of overwriting a page in place, allocate a fresh page and update the parent to point to it. This is how LMDB achieves single-writer MVCC without a WAL. Pros: simpler crash recovery (just point at the last committed root). Cons: requires a GC for unreferenced pages, doubles write amplification.

• Reference: Howard Chu's LMDB tech docs, http://www.lmdb.tech/doc/
• Self-study: extend the allocator to track free pages and never overwrite; introduce a "commit" op that just writes a new root pointer atomically.

4. Write Coalescing & Group Commit

Right now every write calls fsync immediately. Even a single concurrent writer benefits from group commit:

#![allow(unused)]
fn main() {
// Pseudocode
let mut pending = vec![];
loop {
    pending.push(receive_write_request());
    if elapsed_since_last_fsync > 100us || pending.len() > 64 {
        pwrite_all(pending);
        fdatasync();
        for req in pending.drain(..) { req.notify_done(); }
    }
}
}

• Lab pointer: db-03-write-ahead-log builds this for the WAL. Try it here as warm-up.
• Trade-off: latency increases by 100us, throughput rises by ~50× under contention.

5. Direct I/O + Aligned Buffers

O_DIRECT (Linux) or F_NOCACHE (macOS) bypasses the page cache. To use it you need 4-KiB-aligned buffers (in Rust: Layout::from_size_align(4096, 4096)?; in C++: posix_memalign(&buf, 4096, 4096); in Go: trickier — use golang.org/x/sys/unix.Mmap with MAP_ANON).

• When this matters: when your app has a better cache than the kernel (e.g., Phase 2's block cache). Oracle, MySQL with O_DIRECT, and most flash-tuned engines pick this.
• Self-study: add a pagealloc write-direct subcommand that opens with O_DIRECT and demonstrates the alignment requirement (the program must fail predictably if the buffer is unaligned).

6. Sparse Files & Hole Punching

Files don't have to be contiguous. fallocate(FALLOC_FL_PUNCH_HOLE) releases blocks back to the filesystem without changing the file size. Useful for LSM-tree SSTable compaction (free space after removing dead keys) and for journal log truncation.

• Reference: man 2 fallocate
• Self-study: add pagealloc punch <file> <page_no> and verify with du -h <file> that the file's apparent size is unchanged but on-disk size shrinks.

7. Crash Testing with dm-flakey (Linux)

The hard part of storage code is testing the failure cases. dm-flakey is a Linux device-mapper target that simulates random write failures.

# 5-second window of normal operation, then 1 second of dropping writes, repeat.
sudo dmsetup create flakey-dev --table "0 $size flakey /dev/loop0 0 5 1 1 drop_writes"

Mount your test filesystem on /dev/mapper/flakey-dev and run your pagealloc write loop across the drop window. Without fsync, you should lose data. With fsync, the writes that completed should survive. This is how the real engines test durability.

8. Comparing mmap Yourself

We argued for pread/pwrite. Don't take our word for it — implement pagealloc-mmap as a fourth implementation. Compare:

Plot the results, write down what surprised you. Bring those numbers to the mmap Pavlo paper (in references.md) and check whether they match.

9. Persistent Memory (PMEM, Optane)

Intel Optane is dead, but Persistent Memory programming patterns survive in CXL.mem and in research kernels. PMEM is byte-addressable like RAM, persistent like SSD, with clwb + sfence as the durability primitive (no fsync). The persistent memory programming library (PMDK) is what to read.

• Reference: https://pmem.io/pmdk/
• Why it matters: if/when CXL persistent memory becomes commodity, every storage engine in this curriculum will need a rewrite. Already, WiscKey, SplitFS, and uTree are research designs assuming PMEM.

10. Beyond Disk: Object Storage as a Backing Store

Modern cloud-native databases (Snowflake, Databricks, BigQuery) don't pwrite to local disks — they PUT 4 MiB objects to S3. The trade-offs are wildly different (high latency, infinite throughput, eventual consistency until 2020). The closest "primitives lab" for that world would replace pread/pwrite with HTTP range requests. Worth thinking about, especially before db-23's capstone.

• Reference: "Lakehouse: A New Generation of Open Platforms" (Armbrust et al., CIDR 2021)

Step 1 — Open a File and Write Bytes

Goal

Build the smallest possible thing that touches the disk: open a file, write some bytes at a known offset, close the file. You'll do this three times — once in Rust, Go, and C++ — so you can feel how each language exposes the same pread/pwrite/fsync primitives.

Prerequisites

• Toolchain installed per ../../TOOLS.md.
• An empty editor and a terminal in this lab's directory.

What You're Building

A function with this signature (conceptually):

write_page(path: string, page_no: u64, bytes: [u8]) -> Result

• Opens (or creates) path for read+write.
• Computes offset = page_no * PAGE_SIZE (with PAGE_SIZE = 4096).
• Zero-pads bytes to exactly PAGE_SIZE.
• pwrites the padded buffer at offset.
• Calls fdatasync (or fsync if fdatasync is unavailable).
• Closes the file.

Why pwrite, not write

The classic POSIX write syscall uses the file's seek pointer (lseek). That makes it stateful — two threads writeing to the same fd will race. pwrite takes an explicit offset and is thread-safe. Every database in this curriculum uses pwrite. No lseek in our code, ever.

Why PAGE_SIZE = 4096

It matches the OS page size on x86_64 and ARM64, which means the kernel page cache, the device LBA, and your write are all the same unit. Mismatched sizes cause read-modify-write at the kernel layer: writing 100 bytes requires the kernel to first read the 4 KiB page containing those bytes, modify, and write back. By always writing a full page, you avoid that hidden cost.

Why fdatasync Over fsync

fsync flushes data and metadata (file size, modification time). For a write that doesn't change the file size — the common case in a steady-state database — fdatasync skips the metadata flush, saving a few hundred microseconds per call on average. Use fdatasync when you can.

Rust Implementation

In ../src/rust/src/lib.rs we use the std::os::unix::fs::FileExt::write_at extension, which compiles to pwrite64 on Linux and macOS. Look at the function write_page.

Key idiom:

#![allow(unused)]
fn main() {
use std::os::unix::fs::FileExt;
file.write_all_at(&buf, offset)?;
file.sync_data()?;   // == fdatasync
}

sync_data is Rust's portable name for fdatasync on Linux and fcntl(F_FULLFSYNC) on macOS (Rust 1.78+ uses F_BARRIERFSYNC on macOS, which is a faster middle ground).

Go Implementation

In ../src/go/pagealloc.go, the WriteAt method is pwrite, and f.Sync() is fsync. There is no first-class fdatasync in os, so we call unix.Fdatasync(fd) from golang.org/x/sys/unix.

if _, err := f.WriteAt(buf, offset); err != nil { return err }
return unix.Fdatasync(int(f.Fd()))

On macOS, unix.Fdatasync is not exported (the kernel doesn't have it). We fall back to unix.FcntlInt(fd, unix.F_FULLFSYNC, 0). The wrapper in fsync_full.go handles the platform branch.

C++ Implementation

In ../src/cpp/src/pagealloc.cc:

ssize_t n = ::pwrite(fd, buf.data(), buf.size(), offset);
if (n != static_cast<ssize_t>(buf.size())) return std::errc::io_error;
::fdatasync(fd);

On macOS we use ::fcntl(fd, F_FULLFSYNC). The dispatch is in fsync_full.cc.

Try It

cd src/rust && cargo build --release
./target/release/pagealloc write /tmp/step1.bin 0 "first page"
xxd -l 32 /tmp/step1.bin

Expected output:

00000000: 4547 4150 3145 5344 0000 0000 0000 0000  EGAP1ESD........
00000010: 6669 7273 7420 7061 6765 0000 0000 0000  first page......

The first 8 bytes are our little-endian page magic 0x44534531_50414745 (read as bytes left-to-right: 45 47 41 50 31 45 53 44). Bytes 16+ contain your ASCII payload "first page" followed by zero-padding to 4 KiB.

What Just Happened

1. You opened a file (open(2) with O_RDWR | O_CREAT).
2. You wrote exactly one page at exactly one offset (pwrite(2)).
3. You forced the data to stable storage (fdatasync(2) or F_FULLFSYNC on macOS).
4. You closed the fd, which does not flush — close(2) returns immediately.

On a power loss between step 3 and step 4, your write survives. Without step 3, it might not.

Next

In Step 2 you'll add the read path and a hexdump utility, and verify that all three implementations produce byte-identical files.

Step 2 — pread and Hexdump

Goal

Implement the read side (pread) and a hexdump utility, then prove cross-implementation byte-compatibility: a file written by Rust must read identically from Go and C++.

The Read Side

Symmetric to Step 1:

read_page(path: string, page_no: u64) -> [u8; PAGE_SIZE]

• Open the file read-only.
• pread(fd, buf, PAGE_SIZE, page_no * PAGE_SIZE).
• Return the buffer (caller will strip trailing zeros or use the magic header to validate).

Rust

#![allow(unused)]
fn main() {
file.read_exact_at(&mut buf, offset)?;
}

Go

n, err := f.ReadAt(buf, offset)
if err != nil && err != io.EOF { return nil, err }

ReadAt returns io.EOF if n < len(buf) — this is normal for the last page of a file that hasn't been preallocated. Tests handle this case.

C++

ssize_t n = ::pread(fd, buf.data(), buf.size(), offset);
if (n < 0) return std::errc::io_error;
buf.resize(n);   // shrink if short read

Page Header Format

Every non-empty page in our format begins with a 16-byte header:

offset  size  field
------  ----  -----
   0     8    magic = 0x44534531_50414745  (LE: 45 47 41 50 31 45 53 44 ; ASCII reversed: "EGAP1ESD")
   8     2    version = 1
  10     2    flags = 0
  12     4    payload_len  (LE u32, number of bytes used after the header)
  16     n    payload bytes
n+16     —    zero-pad to PAGE_SIZE

This is a deliberately simple format — we'll grow it in later labs. For now it gives us:

• A magic number to detect "is this a valid page?"
• A version field to evolve the format later.
• An explicit payload length so we don't have to scan for zeros (zeros are valid bytes in real data).

The Hexdump Utility

A canonical 16-byte-per-line hex dump:

00000000: 4547 4150 3145 5344 0100 0000 0a00 0000  EGAP1ESD........
00000010: 6669 7273 7420 7061 6765 0000 0000 0000  first page......
00000020: 0000 0000 0000 0000 0000 0000 0000 0000  ................
...

Format spec:

• 8-digit hex offset, then : .
• 16 bytes per line, grouped 2 bytes per word, separated by single space.
• 2-space gap before the ASCII rendering.
• ASCII rendering: printable ASCII as itself, otherwise ..

This format matches xxd output for easy diff-based cross-language verification.

Cross-Implementation Test

This is the most important check in this lab. Run scripts/cross_test.sh:

bash scripts/cross_test.sh

What it does (excerpt):

$RUST write /tmp/xt.bin 0 "from rust"
$GO   write /tmp/xt.bin 1 "from go"
$CPP  write /tmp/xt.bin 2 "from cpp"

$RUST hexdump /tmp/xt.bin > /tmp/h.rust
$GO   hexdump /tmp/xt.bin > /tmp/h.go
$CPP  hexdump /tmp/xt.bin > /tmp/h.cpp

diff /tmp/h.rust /tmp/h.go || { echo "RUST/GO mismatch"; exit 1; }
diff /tmp/h.rust /tmp/h.cpp || { echo "RUST/CPP mismatch"; exit 1; }
echo "cross-language byte-compat OK"

If this fails, the most common bugs are:

1. Wrong endianness on the magic or payload_len.
2. Forgetting to zero-pad the page (one impl leaves junk past the payload).
3. Off-by-one on the offset calculation (page_no * PAGE_SIZE vs (page_no + 1) * PAGE_SIZE).

What Just Happened

You now have a portable, file-format-compatible storage primitive across three languages. This is the foundation for every later lab — the WAL in db-03 is exactly this with append-only semantics, and the SSTable in db-06 is this with a richer block format.

Next

Step 3: measure latency, demonstrate the page cache, and understand why your second read of a page is 1000× faster than the first.

Step 3 — Benchmark and the Page Cache

Goal

See the page cache with your own eyes by measuring warm-cache and cold-cache pread latency. This is the experiment that should make you suspicious of every microbenchmark you ever read.

The Benchmark

pagealloc bench <file> <pages> <iters>:

1. Preallocate file to pages * 4 KiB using a sequential write loop.
2. fsync to make sure it's on disk.
3. Time iters random preads of one page each.
4. Drop the page cache.
5. Time iters random preads again.
6. Print p50/p99/p999 for each phase plus throughput in MB/s.

Implementation lives in:

• ../src/rust/src/bin/pagealloc.rs (bench subcommand)
• ../src/go/cmd/pagealloc/main.go (bench subcommand)
• ../src/cpp/src/main.cc (bench subcommand)

Dropping the Page Cache

On Linux:

sync && sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'

Our benchmark binary calls this automatically if it can. If it can't (no sudo), it prints a warning and skips the cold phase.

On macOS:

sudo purge

Same logic — the binary attempts it, warns if it can't.

Expected Numbers

On a modern laptop with NVMe:

$ ./pagealloc bench /tmp/bench.bin 65536 50000   # 256 MB file, 50k iters
preallocated 65536 pages = 262144 KiB

WARM cache:
  iterations : 50000
  p50        : 1.2 µs
  p99        : 5.8 µs
  p99.9      : 18 µs
  throughput : 1840 MB/s

dropped page cache

COLD cache:
  iterations : 50000
  p50        : 64 µs
  p99        : 180 µs
  p99.9      : 340 µs
  throughput : 56 MB/s

Two observations:

1. Warm cache is ~50× faster than cold. The page cache makes microbenchmarks lie. If you benchmarked a database after running the benchmark for warmup, you measured memcpy, not disk.
2. p99 is 4–5× p50 even on cold cache. Latency tails come from queue depth, kernel scheduling, NVMe garbage collection. This motivates io_uring (Lab 21) and request hedging in distributed systems (Lab 20).

On a Spinning Disk (if you have one)

COLD cache:
  p50        : 6.4 ms     ← 100× worse than NVMe
  p99        : 18 ms
  throughput : 0.6 MB/s   ← versus 56 MB/s on NVMe

This 100× gap is why LSM-trees exist. Random reads on HDD are unworkable for OLTP; engines either:

• Avoid them (sequential append-only logs).
• Hide them behind cache (large block caches + bloom filters).
• Punt to SSD (HDD as cold tier only).

Throughput vs Latency

Watch what happens with iters = 1000 vs iters = 100000:

$ ./pagealloc bench /tmp/bench.bin 65536 1000
WARM throughput : 4200 MB/s

$ ./pagealloc bench /tmp/bench.bin 65536 100000
WARM throughput : 1800 MB/s

Higher iteration counts include more cache eviction (as the random distribution gradually evicts pages we already cached), exposing memory bandwidth and TLB misses. Real workloads sit between these. A single benchmark number is almost always wrong.

Try This

Add a flag to control the access pattern: sequential vs random. Sequential preads benefit from the kernel's read-ahead heuristic. On the same NVMe device you should see:

RANDOM     cold : 56 MB/s
SEQUENTIAL cold : 2400 MB/s    ← 40× faster, all due to read-ahead

This is why scans are cheap and point lookups are expensive — even on SSD.

What Just Happened

You measured the page cache, the access pattern's effect on throughput, and the gap between p50 and p99. These three insights drive every storage design in this curriculum:

• Page cache exists → your in-process block cache (Lab 8) must be smarter than LRU on raw bytes, otherwise you're duplicating the kernel's work.
• Sequential >> random → LSM-tree compaction (Lab 7) sorts data on disk to convert all future reads to sequential ranges.
• p99 >> p50 → consensus heartbeats (Lab 17) must tolerate occasional 100× slow fsyncs without triggering elections.

Next

You've finished Lab 01. Run docs/verification.md to confirm all 8 checks pass. Then move on to db-02-data-structures-for-storage.

Data Structures for Storage

Status: Complete. Companion to db-01 and prerequisite for db-05 (MemTable) and db-10 (B-Tree).

1. What Is It

This lab is about the in-memory data structures that databases use, and why those choices change completely when the data is on disk. We build two structures from scratch:

• A skip list — an ordered, probabilistic, pointer-based map. This is what LevelDB and RocksDB use for their MemTable, and what Redis uses for sorted sets.
• A hash table with open-addressing + Robin Hood probing — an unordered, array-backed map. This is what you use when you need O(1) point lookups and don't need ordering.

We then benchmark them against each other on three workloads (insert, point lookup, range scan) and explain why the numbers come out the way they do.

This lab does not implement a B-Tree or a B+-Tree — those are on-disk structures and arrive in db-10. The lesson here is why a B-Tree dominates on disk even though a skip list or hash table is faster in RAM.

2. Why It Matters

Every database has a critical-path data structure for "find this key":

If you pick the wrong structure you don't get "a little slower" — you get "100× slower" or "we run out of memory at 100M keys." The cost model for an in-memory structure (cycles, cache misses) is not the cost model for an on-disk one (page reads, sync latency), and a structure tuned for one will lose badly in the other domain.

3. How It Works

Skip list

A skip list is a stack of linked lists. The bottom list contains every key in sorted order. Each higher list contains a random subset of the keys below it, sampled with probability p (we use p = 0.5). To find a key, you walk right on the highest level until you'd overshoot, then drop down a level, repeat.

level 3:  HEAD ────────────────────────────────────────────────►  NIL
              │                                                  │
level 2:  HEAD ────────► [13] ───────────────► [42] ────────────► NIL
              │           │                     │                │
level 1:  HEAD ──► [7] ─► [13] ─► [21] ───────► [42] ─► [55] ──► NIL
              │     │     │       │             │       │       │
level 0:  HEAD ► [3]►[7]►[13]►[21]►[34]►[39]►[42]►[51]►[55] ──► NIL

Searching for 39 from the top:

1. L3: HEAD → NIL (overshoot from HEAD), drop to L2
2. L2: HEAD → 13 → 42? 42 > 39, drop to L1
3. L1: 13 → 21 → 42? 42 > 39, drop to L0
4. L0: 21 → 34 → 39. Found.

Expected time: O(log n) with constant factor 1/p · log_{1/p}(n). With p = 0.5 that's 2 · log₂ n comparisons.

Hash table (open addressing, Robin Hood)

An array of 2^k slots. Hash the key, mod by table size, that's the home slot. If occupied by a different key, probe linearly (slot+1, slot+2, ...). Robin Hood twist: when you probe past slot i for the d-th time, and the resident at slot i has been probed only d' < d times, swap them — the "rich" entry gets displaced by the "poor" one. This bounds the worst-case probe distance to roughly the mean.

home(K1)=2   home(K2)=2   home(K3)=4
  hash before insert:
  ┌──┬──┬────┬────┬────┬──┬──┬──┐
  │  │  │ K1 │ K2 │ K3 │  │  │  │
  └──┴──┴────┴────┴────┴──┴──┴──┘
   0  1   2    3    4   5  6  7
  (K1 home=2 dist=0, K2 home=2 dist=1, K3 home=4 dist=0)

  insert K4 with home=2:
   probe slot 2 (K1, dist 0); K4 dist=0; equal — keep going
   probe slot 3 (K2, dist 1); K4 dist=1; equal — keep going
   probe slot 4 (K3, dist 0); K4 dist=2 > 0 — STEAL, K3 displaced
   probe slot 5 (empty); place K3 with dist=1
  result:
  ┌──┬──┬────┬────┬────┬────┬──┬──┐
  │  │  │ K1 │ K2 │ K4 │ K3 │  │  │
  └──┴──┴────┴────┴────┴────┴──┴──┘

Loads up to ~0.9 work well with Robin Hood; we resize at 0.85 (× 2 capacity, rehash all).

When in-memory and on-disk diverge

A skip-list node holding a 16-byte key + 16-byte value + 4 forward pointers is ~64 bytes in memory. The same record packed into a B+-Tree leaf page (4 KiB page, no per-record pointers) is ~36 bytes — no level header, no forward-pointer array. And the B+-Tree co-locates ~100 records in one page, so a range scan of 100 keys is 1 page read instead of 100 random reads.

On disk:

• A pointer is an 8-byte offset that triggers a page read (~100 µs cold).
• A cache miss is ~100× a cache hit.
• A page is 4 KiB whether you read 1 byte or 4096.

Therefore on-disk structures want high fan-out, low height, contiguous siblings, no random pointer chasing. Skip lists violate all four; B+-Trees satisfy all four.

4. Core Terminology

5. Mental Models

"A skip list is a binary search you can mutate cheaply"

A balanced BST and a skip list have the same asymptotic complexity. The skip list wins because it has no rebalancing: no rotations, no recoloring. Each insert is one geometric coin flip + N forward-pointer writes (N = node height, ≈ log₂ n expected). This makes it much easier to make concurrent — LevelDB's MemTable allows lock-free reads while a writer inserts, because a partially-published node is invisible until the bottom-level pointer is CAS'd in.

"A hash table is a sparse array you pretend is dense"

If keys were integers in [0, N) you'd use an array. A hash function fakes that: it maps any key into [0, capacity). Collisions are the cost of the lie. Robin Hood specifically equalizes the cost of the lie across keys, so the worst-case lookup is close to the average.

"Cost models differ by 5 orders of magnitude"

L1 cache hit                        ~1 ns
Main memory                       ~100 ns
NVMe SSD random read (cold)       ~100 µs   ← 1000× RAM
HDD seek                           ~10 ms   ← 100× SSD
Cross-DC round trip                ~50 ms

A "fast" in-memory structure becomes irrelevant if it issues 10 page reads where a B+-Tree issues 1. The B+-Tree's "slow" O(log_B n) with B = 256 beats the skip list's "fast" O(log₂ n) on disk by a factor of log₂(256) = 8 — every level you avoid saves 100 µs.

6. Common Misconceptions

• "Skip lists are slow because they're probabilistic." No — the expected and with-high-probability bounds are tight. The variance is small for any list above ~1000 keys. Failure modes are bad RNG seed (we use a deterministic xorshift here) and adversarial key insertion patterns (irrelevant for hashed keys; mitigated by per-instance seed).
• "Hash tables have O(1) worst case." Average, not worst. A pathological hash function or adversarial keys produce O(n) chains. Robin Hood mitigates variance but does not change the worst case.
• "You should always use a hash table when you don't need ordering." Two cases where skip lists or trees win even unordered: (a) you need iteration in any deterministic order across runs; (b) memory is tight and you can't afford the 15–40% slack of a hash table at safe load factors.
• "Open addressing wastes memory because of empty slots." Chaining wastes more in practice: every chain node is a heap allocation with a header (malloc arenas + pointer + next ptr ≈ 32 bytes overhead per entry). Linear-probing hash tables with 70% load factor still use less memory than std::unordered_map.
• "A B-Tree is just a balanced BST with more children." No: B+-Trees keep all data in leaves and chain leaves with sibling pointers, making range scans O(1) per page after the initial descent.
• "std::unordered_map / Go map / Python dict are the gold standard." They're general-purpose. Specialized hash tables (Abseil's flat_hash_map, Rust's hashbrown, F14) beat them by 2–5× on most workloads. Database authors often roll their own.

7. Interview Talking Points

• "Why does LevelDB use a skip list for the MemTable instead of a red-black tree?" → Lockless reads via single-pointer CAS publish; no rotations; easier to implement correctly.
• "Why isn't a hash table good enough for a MemTable?" → MemTable flushes to an SSTable, which is a sorted file. A hash table would require sorting at flush time (O(n log n)); a skip list is already sorted, so flush is O(n) sequential.
• "When would you use chaining vs open addressing?" → Open addressing for small fixed-size values (better cache); chaining when values are large and you want pointer stability across resizes.
• "What's the cost model on disk that breaks skip lists?" → Each level traversal is a potential page read. With log₂ n levels you pay log₂ n × 100 µs. A B+-Tree with fan-out 256 has log_256 n levels, so 3 page reads for 16 M keys vs 24.
• "Why is Robin Hood probing useful?" → Bounds variance: the maximum probe distance grows as O(log n) w.h.p., and lookups for missing keys become almost as fast as hits because you can stop as soon as you see a slot with smaller PSL than yours.
• "What's the alternative to tombstones?" → Backward-shift deletion: walk forward from the deleted slot, shift each non-home entry left until you hit an empty slot or a home-slotted entry. O(probe-length) per delete, no tombstone bookkeeping.

8. Connections to Other Labs

• db-01 Storage Primitives — the page abstraction the disk structures use.
• db-03 WAL — the WAL is appended before the MemTable insert; failure recovery rebuilds the MemTable by replaying the WAL.
• db-04 Bloom Filters — sits in front of the SSTable; same family of probabilistic in-memory structures.
• db-05 LSM MemTable — uses the skip list from this lab, adds a snapshot / immutable flip.
• db-10 B-Tree Fundamentals — contrast with this lab; same problem, different cost model.
• db-21 Storage Engine Advanced — concurrent skip list (CAS publish), concurrent hash table (extendible hashing, lock striping).

References — db-02 Data Structures for Storage

Skip lists

• Pugh, W. (1990). "Skip Lists: A Probabilistic Alternative to Balanced Trees." CACM 33(6). The original paper; six pages, very readable.
  https://www.cs.umd.edu/~pugh/galileo/papers/CACM_Skiplist_1990.pdf
• LevelDB MemTable source — skip list with a single allocator arena.
  https://github.com/google/leveldb/blob/main/db/skiplist.h
• RocksDB InlineSkipList — production skip list with per-node tail allocation.
  https://github.com/facebook/rocksdb/blob/main/memtable/inlineskiplist.h
• Redis t_zset.c — skip list with per-node span field for O(log n) rank queries.
  https://github.com/redis/redis/blob/unstable/src/t_zset.c

Hash tables

• Celis, P., Larson, P.-Å., Munro, J. I. (1985). "Robin Hood Hashing." FOCS '85. Original paper.
• Pedro Celis's thesis on Robin Hood hashing (1986). The probe-distance analysis is here.
  https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
• Emmanuel Goossaert's deep dive — accessible and runnable.
  https://codecapsule.com/2013/11/11/robin-hood-hashing/
• Google Abseil flat_hash_map — SIMD probing on top of open addressing.
  https://abseil.io/about/design/swisstables
• Rust hashbrown — port of Abseil's SwissTable; the implementation behind std::collections::HashMap.
  https://github.com/rust-lang/hashbrown

Cost models & cache

• Drepper, U. (2007). "What Every Programmer Should Know About Memory."
  https://akkadia.org/drepper/cpumemory.pdf
• Jeff Dean's "Numbers Every Programmer Should Know" — the canonical latency hierarchy.
  https://gist.github.com/jboner/2841832
• Pavlo, A. "Database Storage I" (CMU 15-445). The disk-vs-RAM cost-model lecture.
  https://15445.courses.cs.cmu.edu/fall2023/slides/03-storage1.pdf

Tree structures (preview for db-10)

• Bayer, R., McCreight, E. (1972). "Organization and Maintenance of Large Ordered Indices." Acta Informatica. The original B-Tree paper.
• Comer, D. (1979). "The Ubiquitous B-Tree." ACM Computing Surveys. The canonical survey.

Background

• Sedgewick & Wayne, Algorithms 4th ed.
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS) 3rd ed. — Ch. 11 (hash tables), Ch. 17 (amortized analysis).

Analysis — Design Decisions

Every choice here is reversible in code but irreversible in performance: change one, all the others bend with it.

D1. Skip list over balanced BST (red-black, AVL)

Choice: skip list. The simplicity (no rotations, no rebalancing, no parent pointers) is the value proposition. Worst-case absolute bound is irrelevant when we control the hash that feeds keys in.

When you'd flip: real-time systems where a probabilistic O(n) blowup is unacceptable. Database MemTables don't qualify.

D2. Hash table: open addressing + Robin Hood, not chaining

Choice: open addressing, linear probing, Robin Hood. The cache-miss saving is decisive at small/medium values, which is the database use case.

When you'd flip: large values (≥1 KiB) where you want pointer stability so external references survive resize.

D3. p = 0.5 for skip list, not p = 0.25

The expected number of comparisons per search is (1/p) · log_{1/p}(n). Minimizing this gives p = 1/e ≈ 0.37. In practice:

We pick p = 0.5 because (a) bit-shift sampling (count trailing zeros of a random u64) is one instruction, and (b) the code stays trivial. The 30% theoretical improvement from p=1/e is not worth the table-lookup or log math.

D4. Max level = 32

A skip list with p=0.5 and n entries has expected max level log₂ n. At max level 32 we support n = 2^32 ≈ 4 G entries before quality degrades. Going higher costs a forward-pointer slot per node forever (8 bytes per extra level). Going lower caps the structure size.

D5. Hash function: FNV-1a 64-bit

We need a hash that is:

• High quality enough for non-adversarial keys (passes basic distribution tests)
• Fast for small keys (~10 cycles per 8 bytes)
• Identical in all three languages so cross-language tests can compare counts

FNV-1a is 6 lines of code, deterministic, and produces nearly the same probe-distance distribution as xxHash3 for keys ≤ 32 bytes. We use it because we control the input keys in this lab; in production you'd switch to xxHash3 or SipHash.

When you'd flip: keys controlled by adversaries → SipHash with a per-instance random key.

D6. Load factor 0.85, grow ×2

Robin Hood handles load factor up to ~0.9 well; beyond that the variance of probe distance blows up. We resize at 0.85 to leave headroom and double the capacity (and rehash). Cost of resize is amortized O(1) per insert.

D7. Backward-shift deletion, no tombstones

Tombstones simplify code but bloat the table over time — a "delete-then-insert" workload fills the table with markers and forces a resize. Backward-shift deletion costs O(PSL) per delete (typically <5 slots) and keeps the table compact. The implementation walks forward from the deleted slot, moves each entry one slot left until reaching an empty slot or an entry whose PSL is 0.

D8. Seed: deterministic per-instance, random across instances

The skip list RNG must not be deterministically the same across runs. But within one process run we want reproducible behavior for debugging. The CLI accepts an optional seed; tests pass a fixed value.

Cost-model cheat sheet

Every random pointer dereference is a potential L3 miss → 100 ns. A skip list with 20 levels traverses 20 such pointers in the worst case = 2 µs. A linear-probing hash table touches 1–2 cache lines = ~10 ns. Hash table is ~100× faster for point lookups in RAM, and the gap grows as the working set leaves L3.

What breaks at scale

Execution — How to Build and Run

Quick start (per language)

# Rust
cd src/rust
cargo build --release
cargo test --release
./target/release/dsbench --help

# Go
cd src/go
go test ./...
go build -o bin/dsbench ./cmd/dsbench
./bin/dsbench --help

# C++
cd src/cpp
cmake -S . -B build && cmake --build build
ctest --test-dir build
./build/dsbench --help

CLI: dsbench

A single binary per language that exercises both data structures.

Library API

Same shape in all three languages.

SkipList::new(seed)            -> SkipList
SkipList::insert(key, value)   -> bool     (true if newly inserted, false if replaced)
SkipList::get(key)             -> Option<value>
SkipList::remove(key)          -> bool
SkipList::len()                -> usize
SkipList::iter()               -> sorted iterator over (key, value)

HashTable::new(capacity)       -> HashTable
HashTable::insert(key, value)  -> bool
HashTable::get(key)            -> Option<value>
HashTable::remove(key)         -> bool
HashTable::len()               -> usize
HashTable::load_factor()       -> f64
HashTable::max_probe()         -> usize

Keys and values are byte strings.

Verifying

./scripts/verify.sh        # invariants per structure
./scripts/cross_test.sh    # cross-language behavioral checks

Observation — Looking Inside the Structures

What you should see

This lab is at its best when you stop trusting the numbers and start looking at the memory layout.

1. Histogram of skip-list node heights

The skip list with p=0.5 should produce a geometric distribution: ~half the nodes at level 0 only, ~quarter reaching level 1, etc.

./target/release/dsbench skiplist insert 100000

Sample output:

level   count    %
    0  50032   50.0   ████████████████████████████████████████████████
    1  25021   25.0   █████████████████████████
    2  12508   12.5   █████████████
    3   6234    6.2   ██████
    4   3098    3.1   ███
    5   1581    1.6   ██
    6    778    0.8   █
    ...
   max level used = 16

If your distribution is skewed (e.g., level 0 is 25% instead of 50%) your RNG or sampling code is wrong. The most common bug is rng() & 1 evaluated once and reused.

2. Hash-table probe-distance histogram

./target/release/dsbench hashtable insert 1000000

Sample output (Robin Hood, load 0.477):

probe distance   count       %
            0   633412     63.3
            1   235108     23.5
            2    87412      8.7
            3    32104      3.2
            4    10001      1.0
            5     1652      0.2
            6      298      0.0
            7       12      0.0
            8        1      0.0
   mean = 0.55   max = 8   capacity = 2097152   load = 0.477

With pure linear probing (no Robin Hood) the tail extends much further.

3. Memory accounting

./target/release/dsbench bench mem 1000000

Sample:

skip list  : 1,000,000 entries, ~80 B/entry
hash table : 1,000,000 entries, ~25 B/entry  (cap=2097152, load=0.477)

What "working" looks like

• Skip list: max level grows like log₂ n + 5 (slight overshoot from variance).
• Hash table: mean probe < 1, max probe < 10 at load ≤ 0.85.
• Bench: hash table 5–20× faster than skip list on point ops.
• Memory: hash table is 2–4× smaller per entry.

What "broken" looks like

• Mean probe distance climbs above 2 → poor hash function or table not actually power-of-two-sized.
• Max skip-list level stuck at 1–2 with 1M entries → RNG broken; bit-test always falls through.
• Same level distribution from one run to the next → seed not random.
• Hash table size doesn't grow after 85% load → resize trigger not firing.
• max_probe 3–4× above the theoretical bound → almost always the hash function. We hit this with raw FNV-1a 64-bit (max_probe ≈ 200 at N=100k vs expected ≤ 66). Adding a SplitMix64 finalizer fixed it. The pure-FNV variant typoed its prime constant too — see step 02 for the canonical value 0x00000100000001b3 and the three pinned vectors ("", "a", "foobar").

What scripts/cross_test.sh proves

Runs dsbench skiplist iter N seed in Go, Rust, and C++ and diffs all three outputs. If they aren't byte-identical, one of the three has drifted on hash function, RNG, or ordering — usually the easiest single signal for catching a port regression.

Verification — Invariants

scripts/verify.sh runs the language-default binary (Rust by default) through these checks. scripts/cross_test.sh then re-runs the same scenarios in Go and C++ and asserts the behaviorally observable outputs match. The internal layouts are not required to match — only the API behavior.

Running

./scripts/verify.sh          # ~5s, runs Rust binary
DSE_BIN=./src/go/bin/dsbench ./scripts/verify.sh
DSE_BIN=./src/cpp/build/dsbench ./scripts/verify.sh

./scripts/cross_test.sh      # builds all 3, runs cross-language checks

What to do when a check fails

Broader Ideas — Where to Go Next

Extensions you can build on top of this lab. Each is a 0.5–2 day exercise.

1. Concurrent skip list with lock-free reads

LevelDB's MemTable allows concurrent readers while a single writer inserts. The trick: nodes are made visible by a single atomic store of the bottom-level forward pointer — once that store lands, the node exists; before, it doesn't. Higher-level pointers can race because they're only used to speed up a search; if they point to a not-yet-visible node, the next compare won't match and the search retries.

Implement: an AtomicPtr per forward pointer, a single writer (enforced by external mutex or compare_exchange), no per-node lock. Test: spawn 8 readers + 1 writer, run for 10s, assert no reader observes a partial node.

2. Concurrent hash table: lock striping + extendible hashing

Lock striping: 64 stripe mutexes; key's stripe = hash & 63. A write locks its stripe; reads either lock-read or use seqlock counters.

Extendible hashing: instead of full-table resize, split one bucket at a time when it grows past a threshold.

3. ART (Adaptive Radix Tree)

A radix tree variant that uses 4 different internal node layouts (4, 16, 48, 256 children) and adapts based on density. Wins for variable-length keys with shared prefixes (URLs, paths). [Leis et al., ICDE 2013].

4. Cuckoo hashing

Two hash functions, two candidate slots per key. Lookups are guaranteed 2 reads. Used in Memcached extensions.

5. Hopscotch hashing

Each entry must live within H slots of its home (typically H=32). Bounded probe distance like Robin Hood with stronger guarantee.

6. B+-Tree (preview db-10)

Write an in-memory B+-Tree with fan-out 64, leaves chained, and compare to skip list on range scans. This sets up the "why on-disk B-Trees beat skip lists" intuition before you've touched disk.

7. Skip list with rank queries (Redis ZRANK)

Add a span field per forward pointer = "number of bottom-level nodes this pointer skips over." Now rank(key) is O(log n) instead of O(n). ~50 LOC of additions.

8. Bloom filter (preview db-04)

In front of the hash table: a 1-bit-per-position array sized for ~1% false-positive rate at expected N. Measure: at 50%-miss workloads the Bloom filter saves you cache misses; at 95%-hit workloads it's pure overhead.

9. xor / cuckoo / ribbon filters

Modern variants (xor [Graf & Lemire 2020], ribbon [Dillinger 2021]) get the same false-positive rate as Bloom with 25–35% less memory.

10. Cache-conscious skip list

Replace the per-node forward-pointer array with a contiguous tail allocation (RocksDB's InlineSkipList). Compare cache miss rates: same algorithm, half the misses.

11. Persistent / immutable variants

Build an immutable skip list where insert returns a new root, sharing 99% of nodes with the old one. Useful for snapshots, MVCC.

When you've explored a couple, you're ready for db-03 Write-Ahead Log, where the durability story begins.

Step 1 — Implement the Skip List

Goal

Build a sorted map with O(log n) expected insert/lookup/remove and O(n) ordered iteration.

API

SkipList::new(seed: u64) -> SkipList
SkipList::insert(key, value) -> bool   // false if replaced existing
SkipList::get(key) -> Option<value>
SkipList::remove(key) -> bool
SkipList::len() -> usize
SkipList::iter() -> iterator<(key, value)>
SkipList::max_level_used() -> usize
SkipList::level_histogram() -> [usize; MAX_LEVEL]

Constants

• MAX_LEVEL = 32
• P = 0.5 (sample via count_trailing_zeros(rng()) % MAX_LEVEL)

Data layout

SkipList {
    head:    Node*       // dummy sentinel at MAX_LEVEL
    level:   usize       // current max level used (1..=MAX_LEVEL)
    len:     usize
    rng:     u64         // xorshift64 state
}

Node {
    key:      Vec<u8>
    value:    Vec<u8>
    forward:  Vec<Option<Box<Node>>>   // length = height of this node
}

In Rust we use Box<Node> for ownership and raw pointers for siblings (or Option<NonNull<Node>> for safer raw pointers). In Go, *Node is the natural choice. In C++, std::unique_ptr<Node> for the sole owner of level-0 next, raw pointers for higher levels.

For simplicity we use a single ownership style: level-0 owns nodes; higher levels hold raw pointers. Drop walks the level-0 chain once.

Insert pseudocode

update[0..MAX_LEVEL] = HEAD
x = head
for i in (level-1)..=0:
    while x.forward[i] != null && x.forward[i].key < key:
        x = x.forward[i]
    update[i] = x

if x.forward[0] != null && x.forward[0].key == key:
    x.forward[0].value = value
    return false                       // replaced

new_level = random_level()
if new_level > level:
    for i in level..new_level: update[i] = HEAD
    level = new_level

node = new Node(key, value, new_level)
for i in 0..new_level:
    node.forward[i] = update[i].forward[i]
    update[i].forward[i] = node
len += 1
return true

Random level

fn random_level(rng: &mut u64) -> usize {
    *rng ^= *rng << 13;
    *rng ^= *rng >> 7;
    *rng ^= *rng << 17;
    let lvl = (rng.trailing_zeros() as usize) + 1;
    min(lvl, MAX_LEVEL)
}

Tests

Step 2 — Implement the Hash Table

Goal

Open-addressing hash table with linear probing + Robin Hood + backward-shift deletion.

API

HashTable::new(initial_capacity_pow2: usize) -> HashTable
HashTable::insert(key, value) -> bool          // false if replaced
HashTable::get(key) -> Option<value>
HashTable::remove(key) -> bool
HashTable::len() -> usize
HashTable::capacity() -> usize
HashTable::load_factor() -> f64
HashTable::max_probe() -> usize
HashTable::probe_histogram() -> Vec<usize>

Hash function

FNV-1a 64-bit followed by a SplitMix64 finalizer (identical in all three languages):

offset = 0xcbf29ce484222325
prime  = 0x00000100000001b3        # = 1_099_511_628_211
h = offset
for byte in key:
    h ^= byte
    h = h * prime  (wrapping)
return splitmix64_finalize(h)

fn splitmix64_finalize(mut h: u64) -> u64 {
    h ^= h >> 30; h = h.wrapping_mul(0xbf58476d1ce4e5b9);
    h ^= h >> 27; h = h.wrapping_mul(0x94d049bb133111eb);
    h ^= h >> 31;
    h
}

Plain FNV-1a has notoriously poor avalanche on short, sequential keys — running it raw against Robin Hood probing blows up max_probe (we measured 206 vs the expected ≲66 bound at N=100k). The SplitMix64 finalizer is bijective (adds no collisions) and re-mixes the high bits down, which restores the geometric PSL distribution.

Known-answer vectors (pin these in tests across all three languages):

Slot layout

Slot {
    occupied: bool        // or use psl = MAX as sentinel
    psl:      u32         // probe sequence length
    hash:     u64
    key:      Vec<u8>
    value:    Vec<u8>
}

We store the full 64-bit hash inside each slot so resizes don't re-hash keys, and so that get can compare hashes (cheap) before keys (expensive).

Insert (Robin Hood)

if (len + 1) / capacity > 0.85: resize(capacity * 2)

h = hash(key)
i = h & (capacity - 1)
psl = 0
loop:
    if !slots[i].occupied:
        slots[i] = (key, value, h, psl); occupied; len += 1
        return true
    if slots[i].hash == h && slots[i].key == key:
        slots[i].value = value
        return false                 // replaced
    if slots[i].psl < psl:
        swap(slots[i], (key, value, h, psl))   // steal
    i = (i + 1) & (capacity - 1)
    psl += 1

Get

h = hash(key)
i = h & (capacity - 1)
psl = 0
loop:
    if !slots[i].occupied: return None
    if slots[i].psl < psl: return None      // would have stolen
    if slots[i].hash == h && slots[i].key == key:
        return Some(slots[i].value)
    i = (i + 1) & (capacity - 1)
    psl += 1

Remove (backward-shift)

i = find_slot(key)
if not found: return false
loop:
    j = (i + 1) & (capacity - 1)
    if !slots[j].occupied || slots[j].psl == 0:
        slots[i].occupied = false
        len -= 1
        return true
    slots[i] = slots[j]
    slots[i].psl -= 1
    i = j

Resize

new_slots = [empty; capacity * 2]
old = swap(slots, new_slots); capacity *= 2; len = 0
for slot in old where occupied:
    insert(slot.key, slot.value)   // re-uses hash if you cache it

Tests

Step 3 — Benchmark and Compare

Goal

Quantify the cost difference between the two structures on three workloads.

Workloads

Procedure

1. Seed both structures with N (10k, 100k, 1M, 10M) random 8-byte keys + 8-byte values.
2. For each workload, take iters random accesses, time the loop, divide by iters.
3. Report p50, p99, mean, total throughput.

Expected outcomes (M2 Pro, release, N=1M)

What the numbers prove

• For unordered point access, never use a skip list. The factor-of-20 gap is from cache-miss count: hash table touches ~1 line, skip list touches ~20 (one per level).
• For ordered access, the skip list is the only option of the two. Range scans on a hash table require collecting all entries and sorting — O(n log n) setup vs O(k) for the skip list.
• The memory gap is real and gets worse for tiny values. Skip-list forward-pointer arrays dominate when value size is < ~64 B.

How to run

./target/release/dsbench bench point 1000000
./target/release/dsbench bench mem   1000000

Optional: cache-miss measurement

# Linux
perf stat -e cache-misses,cache-references ./target/release/dsbench bench point 1000000

# macOS (Instruments → Counters template, capture by PID)
xcrun xctrace record --template 'Counters' --launch ./target/release/dsbench bench point 1000000

Write-Ahead Log (WAL)

Status: complete — runnable in Rust, Go, C++.

1. What Is It

A WAL is an append-only file that records intent-to-modify before the actual data pages are updated. On crash, the recovery routine replays the WAL from the last checkpoint, restoring the database to a consistent state.

client write  ──►  append record  ──►  fsync(WAL)  ──►  ack client
                                                          │
                                                          ▼
                                                  later: apply to data file
                                                  later: checkpoint & truncate WAL

The critical invariant is the write order: WAL hits stable storage before the client is told the write committed. If the process dies between the fsync and the data-page update, recovery re-applies the logged operation. If it dies before the fsync, the client never got an ack, so losing the record is acceptable.

2. Why It Matters

Every serious database has one: PostgreSQL's WAL, MySQL's redo log, SQLite's WAL mode, RocksDB's WAL, LevelDB's LOG file, Kafka's segments.

3. How It Works

Record framing used in this lab (mirrors LevelDB's simplified record format minus the block-grouping):

 ┌─────────┬─────────┬──────────────────────┐
 │ len(u32)│ crc(u32)│ payload (len bytes)  │
 └─────────┴─────────┴──────────────────────┘
       4         4              N

• len and crc are little-endian.
• crc is CRC-32 (IEEE 802.3 polynomial, reflected) of the payload only.
• Records are written back-to-back with no padding.
• Recovery iterates from offset 0 and stops at the first record whose header is short, whose payload is short, or whose CRC fails. The valid prefix is replayed; the bad tail is silently truncated on next open.

file:
   ┌───┬───┬─────┬───┬───┬─────┬───┬───┬──┐  ← crashed mid-write
   │L=8│CRC│ A…  │L=4│CRC│ B…  │L=9│CRC│??│
   └───┴───┴─────┴───┴───┴─────┴───┴───┴──┘
                                ▲          ▲
                                │          └─ short payload → stop, truncate from here
                                └─ last fully-flushed record

4. Core Terminology

5. Mental Models

1. The log is the source of truth, the data file is the cache. Recovery reconstructs from the log.
2. CRC is for detection, not correction. It tells you where the good prefix ends; it does not heal damage.
3. fsync is a barrier, not a universal durability guarantee. Consumer SSDs and FUSE filesystems sometimes lie. Use fio --fdatasync=1 to spot-check hardware.
4. Sequential I/O wins. Even on SSDs, sequential writes have better SLC-cache and GC behavior than random ones.

6. Common Misconceptions

• "write() already put it on disk." No — kernel page cache. fsync is required for durability.
• "CRC + length is enough." Necessary, not sufficient. A record with both len and crc zeroed is indistinguishable from len=0,crc=crc32([]). We disallow len=0 (treat as EOF).
• "Group commit hurts latency." Tiny median bump for a 10–100× throughput win and lower tail latency under load.
• "fsync == O_DIRECT." Different layers. O_DIRECT bypasses the page cache; fsync flushes it.

7. Interview Talking Points

• Distinguish redo log (PostgreSQL/InnoDB), WAL mode (SQLite WAL), journal mode (SQLite default).
• Why CRC the payload, not the header? (Need length first; header CRC catches the wrong failures.)
• fsync vs fdatasync vs sync_file_range.
• Group commit mechanics and tradeoff.
• Why WAL alone doesn't beat torn writes on the data file → full-page writes in WAL after each checkpoint.

8. Connections to Other Labs

• db-01 — every append here is a pwrite + fsync from db-01.
• db-05, db-09 — LSM writes always hit the WAL first.
• db-11 — SQLite WAL mode reuses this exact pattern around a B-tree pager.
• db-13 — commit records & 2PC live in the WAL.
• db-17 — Raft's replicated log is, mechanically, a WAL.

References — Write-Ahead Log

Papers

• ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. C. Mohan et al., 1992. The canonical WAL paper; introduces the redo–undo discipline still used everywhere.
• The Log-Structured Merge-Tree (LSM-Tree). P. O'Neil et al., 1996. Section 2 motivates why a separate sequential log is necessary even for in-memory writes.

Code

• LevelDB db/log_format.h — record types & block structure that inspired this lab's framing.
• RocksDB db/log_writer.cc — production-grade group-commit implementation.
• PostgreSQL src/backend/access/transam/xlog.c — full-page writes, redo machinery.

CRC

• A Painless Guide to CRC Error Detection Algorithms. Ross Williams, 1993. Plain-English walk-through of polynomial division and reflected algorithms.
• Linux kernel lib/crc32.c — reference table-driven implementation.

Filesystems & fsync

• Can Applications Recover from fsync Failures? Anthony Rebello et al., USENIX ATC 2020. Surveys the depressing landscape of partial fsync failures.
• Files are hard. Dan Luu, 2017. Survey blog post on every way fsync, rename, and friends betray you.
• man 2 fsync, man 2 fdatasync, man 2 open (O_DSYNC, O_SYNC).

Analysis — Write-Ahead Log

Problem statement

Make a stream of writes durable and crash-recoverable without paying for a random in-place fsync per write.

Constraints

Design decisions

1. Header = len(u32 LE) || crc32(u32 LE). Small (8 B), aligned, endian-fixed. We deliberately keep the CRC out of the length so we can stream-checksum the body.
2. CRC is over the payload only. The header itself is implicitly validated by use — a corrupt len either points beyond EOF (short read) or to data whose CRC won't match.
3. len == 0 is disallowed, used as the EOF sentinel. Empty payloads are rare in practice and avoiding the ambiguity simplifies the reader (len=0,crc=0 happens naturally in a hole of zeros from a sparse file or pre-allocated extent).
4. Little-endian on disk. Everyone runs LE now (x86, ARM, RISC-V — even POWER prefers it). No htole32 dance saves ~5 LOC per language.
5. CRC table generated at startup, not hardcoded. 1 KB, computed in microseconds. Easier to audit, and lets us swap polynomials in tests.
6. One file, one writer, one fd. No segment rotation in this lab — that lives in db-07 (compaction) and db-09 (LevelDB). Single-file WAL is enough to teach framing.
7. sync() is a separate method. The caller decides commit boundaries. Production systems may add append_sync(payload) that batches a group commit; we leave that for bench mode.

Why this design over alternatives

• vs LevelDB's block-grouped framing: LevelDB pads records to 32KB blocks for alignment and easier corruption isolation. Beautiful, but doubles the code volume. We follow this lab's bias of "minimum to teach the concept, plus one cross-language cross-check".
• vs JSON / protobuf framing: would require schema management. CRC + raw bytes is the smallest possible recoverable framing.
• vs a per-record fsync: we expose a separate sync() so the user can choose between durability per-record (call after every append) and group commit (call periodically).

Failure modes addressed

Failure modes NOT addressed in this lab

• Bit-flip in the header itself that produces a plausible (len, crc) pair (probability ≈ 2⁻³²). Production systems mitigate with a record-type byte (LevelDB) or magic bytes (Kafka).
• Multi-process writers. Use O_APPEND + ≤PIPE_BUF append for that; see db-09 / db-21.
• Disk full mid-write. Treat as torn write at EOF (the trailing record fails CRC and is dropped on recovery); the caller's append() returns an I/O error that they must handle.

Execution — How to Build and Run

Quick start (per language)

# Rust
cd src/rust
cargo build --release
cargo test --release
./target/release/walbench --help

# Go
cd src/go
go test ./...
go build -o bin/walbench ./cmd/walbench
./bin/walbench --help

# C++
cd src/cpp
cmake -S . -B build && cmake --build build
ctest --test-dir build
./build/walbench --help

CLI: walbench

A single binary per language exercising the WAL.

Library API

Same shape in all three languages.

Wal::open(path)            -> Wal           // creates or opens for append, scans to EOF
Wal::append(payload)       -> u64 offset    // record start offset in file
Wal::sync()                -> ()            // fdatasync (or fsync) the file
Wal::len()                 -> u64           // bytes on disk (post-append, post-sync)
Wal::close()               -> ()            // implicit on Drop in Rust / RAII in C++

Wal::iter(path)            -> iterator<Vec<u8>>   // streams records; stops at first bad/short

open scans forward at startup to (a) find true EOF after a partial-write recovery and (b) optionally truncate the file to that position so the next append doesn't append after a known-bad tail. We do truncate in this implementation — the alternative (leave the bad tail in place) makes file size useless and complicates len().

Verifying

./scripts/verify.sh        # invariants per implementation
./scripts/cross_test.sh    # write in lang A, read in lang B, all six pairs

Observation — Looking at the Bytes

1. Hexdump a freshly written WAL

./build/walbench append /tmp/wal 3 4
xxd /tmp/wal

00000000: 0400 0000 b3ca 9eb5 4141 4141 0400 0000  ........AAAA....
00000010: b3ca 9eb5 4242 4242 0400 0000 b3ca 9eb5  ....BBBB........
00000020: 4343 4343                                CCCC

What you should see:

• Three 12-byte records (4 header + 4 payload * 3 = 36 bytes, but actually 8+4 = 12 each = 36 ✓).
• Identical headers because every payload is "AAAA" / "BBBB" / "CCCC" — same length, different CRC.
• 04 00 00 00 is len = 4 in little-endian.
• The next 4 bytes are the payload's CRC, also little-endian.

If your file is suspiciously large (e.g., starts with garbage 0x00 or 0xFF runs), open() is opening the file with the wrong flags or your buffer is uninitialized.

2. Group commit vs per-record sync

./build/walbench append-sync /tmp/wal 10000 64       # fsync per record
./build/walbench bench-group  /tmp/wal 10000 64 1    # group=1, same thing
./build/walbench bench-group  /tmp/wal 10000 64 64   # 64 records per fsync
./build/walbench bench-group  /tmp/wal 10000 64 512  # 512 per fsync

Sample (M2 Pro, APFS):

mode             throughput
per-record sync     1,800 records/s   (~556 µs/sync)
group=64          110,000 records/s
group=512         260,000 records/s

Two takeaways: per-record sync is 3 orders of magnitude slower; group size has diminishing returns past ~256 because the bottleneck shifts to write() itself.

3. Tail truncation in action

./build/walbench append /tmp/wal 5 16
wc -c /tmp/wal                       # 120 bytes (5 × 24)
printf '\xff\xff\xff\xff' >> /tmp/wal
wc -c /tmp/wal                       # 124 bytes
./build/walbench read /tmp/wal       # reads 5, then "stop: short header" (124-120 = 4 < 8)
./build/walbench append /tmp/wal 1 16
wc -c /tmp/wal                       # 144 bytes — open() truncated the garbage, then appended

The reopen-truncate behavior is the most easily-missed correctness detail. If it's broken, your second append ends up inside the corrupted region and the file becomes unreadable after recovery.

4. CRC sensitivity

Bit-flipping one byte of a 64-byte payload should kill the CRC of that record but leave everything before it valid:

./build/walbench append /tmp/wal 10 64
./build/walbench corrupt /tmp/wal 100 0x00     # mid-payload of record ~4
./build/walbench read /tmp/wal | tail
# expected: prints ~3 OK records then "stop: bad crc"

What "working" looks like

• Hexdump shows tightly packed 8-byte-header + payload pairs, no padding.
• Group commit is at least 50× faster than per-record sync.
• Tail truncation works on first reopen, regardless of how much garbage you appended.

What "broken" looks like

• A reader that hangs or panics on garbage — fix the bounds checks in the iter loop.
• File size grows but throughput is flat — you're probably calling fsync inside append accidentally.
• CRC doesn't trip on single-bit flips — wrong polynomial (likely you used the un-reflected version, see scripts/verify.sh).
• Cross-language test fails — endianness or CRC table bug. Print the first 16 bytes of the file from each language and compare.

Verification — What to Test and How

Property tests (per language)

Cross-language test

scripts/cross_test.sh performs a six-way matrix: for each writer ∈ {go, rust, cpp} and reader ∈ {go, rust, cpp}, write 500 records of varying sizes with a fixed seed in the writer language, read them in the reader language, assert the payload list matches exactly.

This catches:

• Endianness mistakes in len/crc.
• Different CRC polynomials or initial value / final XOR.
• Off-by-one in header parse.
• fsync not being called before the reader runs (we close the writer between phases).

Manual smoke

./build/walbench append /tmp/wal 100 64
./build/walbench read /tmp/wal | tail
# expected: OK n=100 bytes=7300
./build/walbench corrupt /tmp/wal 50 0xFF
./build/walbench read /tmp/wal | tail
# expected: stops well before record 100, reports bad record

What "passing" means

• All 8 property tests green in all three languages.
• cross_test.sh exits 0 (9 successful writer×reader runs).
• Manual smoke: corruption stops the reader cleanly, no panic / no segfault, no infinite loop.

Broader Ideas — Beyond the Minimum

Things worth knowing that aren't in the lab code.

Block-grouped framing (LevelDB / RocksDB)

LevelDB pads records into 32 KB blocks and uses a 1-byte type field (FULL, FIRST, MIDDLE, LAST) to handle records that straddle blocks. Benefit: corruption in one block can't propagate; recovery can resync to the next block boundary. Cost: more code, slightly more space.

Group commit, properly

Real systems run a "log writer" goroutine/thread:

clients ──► append to buffer ──► wake writer ──► fsync once ──► broadcast cond var

The writer batches all records that arrived during the previous fsync into the next fsync. Latency stays bounded by (max fsync time) + (one batch fill); throughput scales until you saturate the SSD's IOPS.

O_DSYNC vs application-level fsync

O_DSYNC makes every write() durable before returning. Removes the need for explicit fsync, but you lose the chance to batch. Real DBs prefer explicit fsync for that reason.

sync_file_range and friends

Linux-only. sync_file_range(fd, off, len, SYNC_FILE_RANGE_WRITE) flushes only a byte range. PostgreSQL uses this for "lazy" checkpoints to avoid stalling on huge fsyncs. Doesn't sync metadata, so still need a final fsync.

Pre-allocation & fallocate

For predictable I/O, pre-allocate the next WAL segment with fallocate(FALLOC_FL_ZERO_RANGE | FALLOC_FL_KEEP_SIZE). This avoids metadata updates on each grow and gives the FS a contiguous extent. PostgreSQL pre-zeroes 16 MB segments.

Direct I/O & alignment

O_DIRECT bypasses the page cache; useful when the DB has its own buffer pool. Requires 512 B or 4 KB aligned buffers and offsets. Modern recommendation: prefer io_uring + O_DIRECT over POSIX AIO. Returns in db-21.

Mixing data files and WAL on the same disk

Bad idea for HDDs (head contention), neutral for SSDs (no head), bad for low-end SSDs (write amplification competes). Production systems put WAL on a separate device when latency-sensitive.

When the WAL is the database

LSM-trees, Kafka, NATS JetStream, Pulsar, Apache BookKeeper — these treat the log as the primary structure and let secondary indexes / merge trees / consumers catch up. The data file in our toy example was hypothetical; LSMs make it explicit. See db-05 onward.

Encryption / compression

• Compression per record: trivial, but blocks the Vec<u8> reuse pattern. Better to compress whole segments at checkpoint time.
• Encryption per record: AEAD (AES-GCM or ChaCha20-Poly1305) replaces CRC32 — the auth tag is your CRC. PostgreSQL's TDE proposals use this.

Replication

Once you have a sequential log of operations, replicating it is "just" send-and-replay. This is the entire conceptual basis of Raft and ZAB — see db-17 / db-19. The framing tricks here transfer directly.

What goes wrong at scale

• fsync amplification: every fsync touches the FS journal, which serializes against other fsyncs. Solution: large group commit batches.
• Long fsync tails: 99th-percentile fsync on a busy NVMe can be 100ms+. Solution: pipeline; never block a hot-path thread on fsync.
• Filesystems that lie: ext4 with data=writeback may complete fsync before journaling. APFS, ZFS, btrfs each have their own quirks. Empirical test with fio is the only safe answer.

Step 1 — Record framing & CRC

Goal

Define the on-disk format and a streaming CRC32 implementation that matches between Rust, Go, and C++.

Format recap

 ┌─────────┬─────────┬──────────────────────┐
 │ len(u32)│ crc(u32)│ payload (len bytes)  │
 └─────────┴─────────┴──────────────────────┘
       4         4              N

• Both u32 fields are little-endian.
• CRC is over the payload only.
• len == 0 is the EOF sentinel (an empty payload cannot be appended).

CRC32 — table-driven, reflected

poly = 0xEDB88320  // reflected IEEE 802.3 polynomial
table[256]: built once at startup
for each input byte b:
    crc = (crc >> 8) ^ table[(crc & 0xff) ^ b]
return crc ^ 0xFFFFFFFF                  // final XOR
initial value before processing: 0xFFFFFFFF

Known-answer vectors

Pin these in every language's unit tests. They are the canonical crc32 IEEE vectors used by zlib, gzip, Ethernet, and the LevelDB log.

Rust outline

#![allow(unused)]
fn main() {
pub fn crc32_ieee(bytes: &[u8]) -> u32 {
    let mut c: u32 = 0xFFFF_FFFF;
    for &b in bytes {
        c = (c >> 8) ^ TABLE[((c & 0xff) ^ b as u32) as usize];
    }
    c ^ 0xFFFF_FFFF
}
}

Go outline

func Crc32IEEE(b []byte) uint32 {
    c := uint32(0xFFFFFFFF)
    for _, x := range b {
        c = (c >> 8) ^ table[byte(c)^x]
    }
    return c ^ 0xFFFFFFFF
}

C++ outline

inline std::uint32_t Crc32Ieee(std::span<const std::uint8_t> b) noexcept {
    std::uint32_t c = 0xFFFFFFFFu;
    for (auto x : b) c = (c >> 8) ^ kTable[(c & 0xff) ^ x];
    return c ^ 0xFFFFFFFFu;
}

Trap: which CRC?

There are at least eight in common use. IEEE (reflected, init 0xFFFFFFFF, final XOR 0xFFFFFFFF) is what we want. 0x04C11DB7 un-reflected is not the same value despite being the same polynomial.

If your test gives 0x4DBDF21C for "a", you're using CRC-32C (Castagnoli). Different polynomial, different table.

Step 2 — Append, sync, iterate

Goal

Implement Wal::open / append / sync / iter consistently in all three languages.

API recap

open(path)        -> Wal      // O_RDWR | O_CREAT, scan-and-truncate the tail
append(payload)  -> u64       // returns the record's start offset
sync()           -> ()        // fdatasync (or fsync on platforms without it)
len()            -> u64       // bytes in the live valid region
iter(path)       -> Iterator  // yields each payload until first short/bad record

open — scan & truncate

The crucial subroutine. After a crash, the file may end in a partial header or partial payload. open finds the last valid record's end and truncates the file to that length, so subsequent appends append cleanly.

pos = 0
loop:
    if file_size - pos < 8: break              // not enough for header
    read 8 bytes at pos: (len, crc)
    if len == 0: break                          // EOF sentinel / sparse hole
    if pos + 8 + len > file_size: break         // payload short
    read len bytes at pos+8
    if crc32(payload) != crc: break
    pos += 8 + len
if pos != file_size:
    ftruncate(file, pos)
return Wal { fd, write_offset = pos }

append

hdr[0..4] = len.to_le_bytes()
hdr[4..8] = crc32(payload).to_le_bytes()
pwrite(fd, hdr,     write_offset)
pwrite(fd, payload, write_offset + 8)
offset_returned = write_offset
write_offset += 8 + len
return offset_returned

We do not fsync inside append. Callers do that explicitly via sync() to enable group commit.

sync

• Linux: fdatasync(fd)
• macOS: fcntl(fd, F_FULLFSYNC, 0) for true device-level sync; falls back to fsync(fd) if F_FULLFSYNC fails (e.g., not on APFS).
• Windows: FlushFileBuffers(handle) (out of scope here).

In this lab we use fdatasync (Linux) and fsync (macOS) for simplicity; production should consider F_FULLFSYNC on macOS because plain fsync does not guarantee device-level durability on Apple's filesystems.

iter — read-only replay

Mirrors open's scan loop but yields each payload instead of advancing a write cursor. Stops on the same conditions (len == 0, short header, short payload, bad CRC). Never panics on garbage.

Tests to pin behavior

Gotchas

• macOS fsync does not flush the disk write cache. Use F_FULLFSYNC for tests that must outlive a power loss.
• Rust File::write_all does not call flush on the kernel level, only the userspace BufWriter. We use raw pwrite via nix / std::os::unix::fs::FileExt::write_all_at to skip the userspace buffer entirely.
• Go os.File.Write is unbuffered by default, but bufio.Writer is not. Make sure your Wal does not wrap the file in a bufio.Writer — that defers writes invisibly and confuses sync.

Step 3 — Group commit benchmark

Goal

Quantify the cost of fsync and the throughput win from group commit.

Workload

bench-group PATH N BATCH:

for i in 0..N:
    append(payload)
    if (i+1) % BATCH == 0: sync()
sync()   // final

PATH is a brand-new file each run. N = 50_000 is a good starting point on a modern SSD.

Numbers to look for (M2 Pro, APFS, 64-byte payload)

Two effects worth noting:

• Sync time is roughly constant up to ~4KB: the bottleneck is the per-fsync overhead (syscall + journal commit), not the byte count.
• Returns diminish past batch ~256: bandwidth becomes the next limit. Past ~4096 you start hitting tail-latency cliffs.

What "broken" looks like

• Per-record throughput is the same as group=64: your sync() isn't doing anything (no-op, wrong fd, or bufio.Writer swallowing the write).
• Throughput keeps climbing past group=4096: you may not be calling sync() at all between batches.
• macOS numbers look impossibly fast: plain fsync does not flush the device cache. Re-run with F_FULLFSYNC to compare.

Comparing to a Linux box

On NVMe + ext4:

The shape is identical; absolute numbers depend on the device's flush latency.

Bloom Filters and Hashing

Status: complete — runnable in Rust, Go, C++.

1. What Is It

A Bloom filter is a probabilistic set: add(x) always succeeds; contains(x) returns either definitely not present or probably present. It uses a fixed-size bit array m and k independent hash functions; add(x) sets bits at positions h_1(x) mod m, …, h_k(x) mod m; contains(x) returns true iff all those bits are set.

add("foo"):
   h1=37 h2=812 h3=4    →  bits[37]=bits[812]=bits[4]=1

contains("bar"):
   h1=99 h2=812 h3=120  →  bits[99]=0  ⇒  definitely absent
contains("foo"):
   h1=37 h2=812 h3=4    →  all 1  ⇒  probably present

False positives are inherent (any other key that hits the same k bits looks present); false negatives are impossible (a stored key set its bits, and we never unset).

2. Why It Matters

Filter sizes are tiny: at the textbook optimum (~9.6 bits/key for 1% FPR) a million keys fit in 1.2 MB. Cache-resident.

3. How It Works

For n inserts into m bits with k hashes (assuming independent uniform hashes), the probability a given bit is still zero is (1 - 1/m)^(kn) ≈ e^(-kn/m), so the false-positive rate is

$$\text{FPR} \approx \left(1 - e^{-kn/m}\right)^k$$

Differentiating with respect to k yields the optimal hash count

$$k^* = \frac{m}{n}\ln 2 \approx 0.693 \cdot \frac{m}{n}$$

and the achievable FPR at $k^*$:

$$\text{FPR}^* \approx 0.6185^{,m/n}$$

So 10 bits/key ⇒ ~1% FPR with 7 hashes; 20 bits/key ⇒ ~0.01% with 14 hashes.

Kirsch–Mitzenmacher double hashing

We do not compute k independent hashes. Per Kirsch & Mitzenmacher (2006), it is sufficient — with no measurable FPR penalty — to compute one 64-bit hash, split it into halves h1 and h2, and synthesize:

g_i(x) = h1(x) + i * h2(x)   for i = 0..k-1

This is what LevelDB, RocksDB, and most production filters do.

In this lab the underlying 64-bit hash is FNV-1a64 of the key, then mixed once through SplitMix64 to spread the bits. (FNV-1a64 alone is biased in its high bits, and the Kirsch–Mitzenmacher splitting cares about both halves being well-distributed.)

On-disk / on-wire layout

 ┌─────────┬─────────┬───────────────────────────┐
 │ k (u32) │ m (u64) │  bits  (⌈m/8⌉ bytes, LE)  │
 └─────────┴─────────┴───────────────────────────┘

Identical layout across Rust/Go/C++ so all three can read each other's filters byte-for-byte.

4. Core Terminology

5. Mental Models

1. Bloom is a hash-collision amplifier. One hash collision is rare; needing k of them simultaneously is rarer. The filter trades memory for that compounding.
2. A Bloom filter is a negative index. Use it to avoid work; never use it to prove presence.
3. Hash quality matters less than independence. Once individual bits are well-distributed, the Kirsch–Mitzenmacher trick gives you arbitrarily many "independent" hashes for free.
4. You can compose them. Union ⇒ bitwise OR (with same m, k). Approximate intersection ⇒ bitwise AND (overestimates).

6. Common Misconceptions

• "FPR depends on the number of bits set." It depends on m, n, and k. Two filters with the same fill factor but different k have different FPR.
• "Bigger k is always better." Past $k^*$, FPR climbs again because each insert sets more bits, accelerating saturation.
• "I can resize a Bloom filter." No — bit positions depend on m. Resize by building a fresh filter from the underlying data (or by maintaining a scalable filter, which is a series of growing Bloom filters).
• "Cryptographic hashes are required." Wasted CPU. Anything well-distributed and fast (FNV, xxhash, MurmurHash3, CityHash) works.
• "remove would be cheap if I just cleared the bits." It would also clear bits set by every other key that shares positions. Counting Bloom exists for this reason.

7. Interview Talking Points

• Derive $k^* = (m/n) \ln 2$ and the resulting FPR formula from first principles.
• Explain Kirsch–Mitzenmacher and why it doesn't increase FPR (citation: Less Hashing, Same Performance, ESA 2006).
• Walk through how RocksDB pairs a Bloom filter with each SSTable — and how the new ribbon filter improves on that.
• Quantify: "for 1% FPR you need ~10 bits/key; for one-in-a-million, ~30."
• Contrast Bloom vs. Cuckoo vs. xor filters and their tradeoffs.

8. Connections to Other Labs

• db-06 — every SSTable carries an embedded Bloom filter.
• db-07 — compaction rebuilds filters because input filters can't be merged exactly.
• db-08 — filter block is cached separately from data blocks.
• db-09 — LookupKey flow consults the per-table filter before reading the index block.
• db-21 — prefix Bloom filters, partitioned filters, ribbon filters.

References — Bloom Filters and Hashing

Foundational papers

• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, CACM 1970. The original 2-page paper. https://dl.acm.org/doi/10.1145/362686.362692
• Adam Kirsch & Michael Mitzenmacher, Less Hashing, Same Performance: Building a Better Bloom Filter, ESA 2006. https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
• Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, Cuckoo Filter: Practically Better Than Bloom, CoNEXT 2014. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
• Thomas M. Graf & Daniel Lemire, Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters, JEA 2020. https://arxiv.org/abs/1912.08258
• Peter C. Dillinger & Stefan Walzer, Ribbon Filter: Practically Smaller Than Bloom and Xor, 2021. https://arxiv.org/abs/2103.02515

Production code to read

• LevelDB filter policy: https://github.com/google/leveldb/blob/main/util/bloom.cc
• RocksDB filter blocks: https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter
• RocksDB ribbon filter implementation: https://github.com/facebook/rocksdb/blob/main/util/ribbon_impl.h

Survey & blog posts

• Daniel Lemire, "All about Bloom filters" series: https://lemire.me/blog/tag/bloom-filter/
• Jeff Dean's classic numbers-every-programmer-should-know — useful when sizing filters against disk-seek and RAM costs.
• Hadron, "How RocksDB sizes filters": https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide

Hash functions

• Fowler–Noll–Vo (FNV) reference: http://www.isthe.com/chongo/tech/comp/fnv/
• SplitMix64 (Vigna & Steele's high-quality mixer): https://prng.di.unimi.it/splitmix64.c
• Austin Appleby, MurmurHash3: https://github.com/aappleby/smhasher/wiki/MurmurHash3
• xxHash by Yann Collet: https://github.com/Cyan4973/xxHash

Related labs

• db-02 — data structures for storage reused the FNV-1a64 hash now wrapped here.
• db-06 — SSTable format embeds the filter generated here.

Analysis — Bloom Filters and Hashing

Problem statement

Build a fixed-memory probabilistic set that:

1. Never reports false negatives (lookups for present keys always return true).
2. Reports false positives at a tunable, well-understood rate.
3. Is fast enough to consult in the hot path of a key-value store lookup (≈ nanoseconds).
4. Has an on-disk representation identical across Rust, Go, and C++ so the same filter built in any language can be read by any other.

Constraints

Design decisions

1. Base hash = FNV-1a64 then SplitMix64 mixing. FNV-1a64 is trivial to implement identically across languages; SplitMix64 finalizing fixes its weak avalanche so the upper and lower 32 bits are both well-distributed. The two 32-bit halves become h1 and h2 for double hashing.
2. Kirsch–Mitzenmacher: g_i = h1 + i*h2, all u64 arithmetic, with the final mod m using a single u128-multiplication trick (Daniel Lemire, Fast Random Integer Generation in an Interval, 2018) so we don't pay for a div.
3. Bit array is little-endian byte-packed, bit i lives in bytes[i/8] >> (i%8) & 1. Same convention LevelDB and RocksDB use.
4. Header = k(u32 LE) || m(u64 LE). 12 bytes total. We deliberately put k first so a partial-read of just the header reveals the hash count without needing m.
5. No checksum on the filter itself. Bloom filters can tolerate a flipped bit (it adds at most a few keys' worth of false positives); pages-level checksumming belongs to db-06 (SSTable).
6. new_with_fpr(n, fpr) constructor. Picks m = ceil(-n * ln(fpr) / (ln 2)^2) and k = round((m/n) * ln 2). Caps k at 30 to avoid degenerate sizing for absurdly small FPRs.

Why this design over alternatives

• vs MurmurHash3 / xxhash: faster and arguably higher quality, but each is hundreds of lines to re-implement identically in three languages. FNV+SplitMix is 12 lines per language and indistinguishable in our use case.
• vs k independent hashes: 2× CPU for no measurable FPR change (Kirsch & Mitzenmacher 2006).
• vs Cuckoo / xor filters: more space-efficient at low FPR but much more code. Worth a separate lab — db-21.
• vs in-language hashers (std::hash, hash/fnv, std::hash<string>): per-language differences — Go's maphash is randomized per process; C++ std::hash<string> is implementation-defined. None of them survive cross-language interop.

Failure modes addressed

Failure modes NOT addressed

• Concurrent inserts. Single writer model. Concurrent add corrupts overlapping byte writes. Lock externally or use atomic OR per byte — covered in db-08 / db-21.
• Adversarial keys. FNV-1a64 is not cryptographic — an attacker can craft collisions to inflate FPR. Use SipHash / xxh3 (with secret seed) if filter inputs are attacker-controlled.
• Deletion. Use a counting Bloom or a cuckoo filter. See db-21.

Execution — How to Build and Run

Quick start (per language)

# Rust
cd src/rust
cargo build --release
cargo test --release
./target/release/bloombench --help

# Go
cd src/go
go test ./...
go build -o bin/bloombench ./cmd/bloombench
./bin/bloombench --help

# C++
cd src/cpp
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build
./build/bloombench --help

CLI: bloombench

A single binary per language. Subcommands have the same shape across all three so cross-language tests can shell out polyglot.

Library API

fnv1a64(bytes) -> u64
splitmix64(u64) -> u64
mix64(bytes) -> u64                   // = splitmix64(fnv1a64(bytes))

BloomFilter::new(m_bits, k) -> Bloom
BloomFilter::with_fpr(n, fpr) -> Bloom
  - picks m, k optimally; caps k at 30
Bloom::add(bytes)
Bloom::contains(bytes) -> bool
Bloom::k(), Bloom::m_bits(), Bloom::m_bytes()
Bloom::encode() -> Vec<u8>            // header || bits
Bloom::decode(bytes) -> Bloom         // inverse, validates header

On-disk / on-wire layout

 ┌─────────┬─────────┬─────────────────────────┐
 │ k (u32) │ m (u64) │  bits  ⌈m/8⌉ bytes      │
 │         │         │  bit i = bytes[i/8] >> (i mod 8) & 1
 └─────────┴─────────┴─────────────────────────┘
       4         8                  ⌈m/8⌉

All integers little-endian. No padding. No internal checksum.

Verifying

./scripts/verify.sh        # per-language unit + property tests
./scripts/cross_test.sh    # writer/reader cross-product over {go,rust,cpp}

Observation — Looking at the Bits

1. Hexdump a freshly built filter

./build/bloombench build /tmp/bf 4 0.05
xxd /tmp/bf

00000000: 0500 0000 1f00 0000 0000 0000 1206 92    ...............

Reading the header: k=5, m=31 bits ⇒ ⌈31/8⌉ = 4 bytes of bits. The trailing 12 06 92 … is the bit vector with 4 keys mixed in. The actual high byte may differ depending on how m is rounded.

For 1000 keys at 1% FPR you should see roughly 9.6 bits/key ⇒ 1200 bytes of bits, and k ≈ 7.

2. Sanity-check the hash chain

./build/bloombench hash foobar
# fnv1a64=85944171f73967e8  splitmix=...  h1=...  h2=...

Known FNV-1a64 vectors (used in tests):

All three languages must print the same fnv1a64 and same splitmix64 for any given input. If they don't, cross-language interop is dead on arrival.

3. Empirical FPR matches the formula

./build/bloombench build /tmp/bf 100000 0.01
./build/bloombench fpr-test /tmp/bf 100000 1000000
# expected: observed=0.0098  theoretical≈0.0100   (within ±20% with 1M samples)

If observed FPR is much higher than theoretical:

• k is wrong (probably 0 or 1 due to integer truncation; check with_fpr math).
• Hash is biased (FNV without SplitMix mixing — the high bits are clumped).
• mod m step has a bias (using h % m with non-prime m is OK; using h & (m-1) only works when m is a power of two).

If observed FPR is much lower: probably double-counting or your "random absent" key generator overlaps with the present set — verify input.

4. Bit density vs FPR

for fpr in 0.10 0.05 0.01 0.001 0.0001; do
  ./build/bloombench build /tmp/bf 10000 $fpr
  ls -l /tmp/bf
done

Sample row sizes (header + body):

The 9.6 bits/key heuristic for 1% FPR is the one most often quoted in interviews.

5. Cross-language byte-identical filters

for lang in go rust cpp; do
  ./src/$lang/.../bloombench build /tmp/bf.$lang 1000 0.01
done
md5sum /tmp/bf.*    # all three identical

If any digest differs, suspect (in order): endian, bit ordering inside the byte, integer types of the header, or hash mismatch.

What "working" looks like

• Bytes 0..3 = k, bytes 4..11 = m, bytes 12..end = bits. No padding.
• Empirical FPR is within ±2× of theoretical for any (n, fpr) you try.
• All three languages produce identical filters and read each other's filters.

What "broken" looks like

• contains(k) returns false for a key you just inserted ⇒ false negative ⇒ critical bug. Likely indexing math: set and get disagree about bit-within-byte.
• FPR is 100% ⇒ all bits are 1 ⇒ either m was rounded down to 0 or you're indexing past the bit array.
• FPR is 0% with realistic load ⇒ add is a no-op or contains always returns true on the "absent" path.
• Cross-language readers disagree ⇒ print the first 16 bytes of each filter and the first three h1, h2 values for a known key; one of them is wrong.

Verification — What to Test and How

Per-language property tests

Cross-language test

scripts/cross_test.sh performs the writer × reader matrix for {go, rust, cpp}²:

1. Each writer builds a filter for the same fixed-seed key set (1 000 keys).
2. Filters must be byte-identical (md5sum over filter file).
3. Each reader opens each writer's filter and runs:
   • 1 000 known-present queries → must all return present
   • 1 000 known-absent queries (different seed) → results must match across readers

This catches:

• Endian or bit-order bugs in the header / bit array.
• Hash mismatch (fnv1a64 or splitmix64 differs).
• mod m reduction differs (Lemire's u128 trick vs % should yield identical indices).

What "passing" means

• All 8 property tests green in all three languages.
• cross_test.sh exits 0 with 9 byte-identical filter writers and 9 passing reader runs.
• Manual smoke: hexdump of a 4-key filter matches the structure described in docs/observation.md.

Broader Ideas — Beyond the Minimum

Block / partitioned filters

RocksDB partitions the filter so that one filter probe touches only a single cache line. Trade: marginally higher FPR for ~3× faster contains on cache-cold filters. See Optimizing Bloom Filter: Challenges, Solutions, and Comparisons (Luo et al., IEEE 2019).

Cuckoo filters

Replace bit array with a hash table of fingerprints. Same FPR as Bloom at lower bits/key (~6 bits/key for 1% FPR), and supports remove. Slower to build, occasionally fails to insert when over-full. Excellent for membership tests with a known max size and a need for deletion.

Xor filters

Build-once, query-many. ~9% smaller than Cuckoo at the same FPR, faster lookup (always exactly 3 memory accesses). Bad fit if you insert incrementally; great for static datasets like compiled SSTable filters.

Ribbon filters (RocksDB 6.15+)

A linear-algebra reformulation of xor filters. ~30% smaller than Bloom at the same FPR, slightly slower lookup, ~10× slower to build. RocksDB now uses these as the default for SSTable filters.

Prefix Bloom filters

When most queries are by prefix (e.g. userid:12345:*), build the filter from prefixes instead of full keys. Saves space and lets prefix-range queries use the filter.

Scaling without resizing

A scalable Bloom filter (Almeida et al., 2007) chains a sequence of progressively larger filters with progressively tighter FPRs. add writes to the youngest; contains ORs across all. Memory grows logarithmically with n.

Compressed Bloom filters

If you transmit a Bloom filter over a network, sparsity makes it gzip well. Mitzenmacher (2002) showed that optimizing for compressed size leads to a different k than optimizing for in-memory FPR.

Cardinality estimation: HyperLogLog vs Bloom

Bloom tells you "in set" with FPR; HLL gives you |set| ± ~2% with constant memory. Often used in the same systems for different questions.

Filters in distributed systems

• Bigtable / HBase: block-level filters per SSTable.
• Cassandra: row-level filter per SSTable, plus a key cache.
• Akamai / CDNs: "did this URL get cached?" Bloom-based pre-checks.
• Gmail: per-user spam fingerprint filters.
• Bitcoin SPV clients (BIP 37): filters published to full nodes to indicate which addresses the SPV wallet cares about. Famously broken from a privacy standpoint — the filter leaks the address set.

Adversarial considerations

Bloom-filter parameters and hashes are usually public. If users can choose keys, they can craft collisions that fill the filter and push FPR to 100%. Defenses:

1. Use a keyed hash (SipHash) seeded at filter creation.
2. Cap inserts or fall back to an exact structure beyond a threshold.
3. Periodically rebuild.

Information-theoretic lower bound

Carter et al. (1978) prove that any approximate set with FPR ε requires at least n * log2(1/ε) bits — that's ~6.64 bits/key for 1% FPR. Bloom uses ~9.6 (44% overhead). Xor filters approach the bound at ~9% overhead. Ribbon filters get within ~3%.

Step 01 — Hash chain (FNV-1a64 → SplitMix64 → double hashing)

Before any filter logic, get the hash chain identical across all three languages. If fnv1a64("foobar") doesn't return 0x85944171f73967e8 everywhere, nothing else will work.

1. FNV-1a64

Algorithm:

hash = 0xcbf29ce484222325
for byte in input:
    hash ^= byte
    hash = hash * 0x100000001b3        // wrapping 64-bit multiplication
return hash

Known test vectors:

Side-by-side:

#![allow(unused)]
fn main() {
pub fn fnv1a64(bytes: &[u8]) -> u64 {
    let mut h: u64 = 0xcbf29ce484222325;
    for &b in bytes {
        h ^= b as u64;
        h = h.wrapping_mul(0x100000001b3);
    }
    h
}
}

func FNV1a64(b []byte) uint64 {
    var h uint64 = 0xcbf29ce484222325
    for _, x := range b {
        h ^= uint64(x)
        h *= 0x100000001b3
    }
    return h
}

std::uint64_t Fnv1a64(const std::uint8_t* p, std::size_t n) {
    std::uint64_t h = 0xcbf29ce484222325ULL;
    for (std::size_t i = 0; i < n; ++i) {
        h ^= p[i];
        h *= 0x100000001b3ULL;
    }
    return h;
}

⚠️ Two-byte traps: don't use FNV-1 (not 1a — different order of XOR vs multiply); don't use the 32-bit prime or basis (different constants).

2. SplitMix64 finalizer

FNV-1a64 has decent low bits but biased high bits. SplitMix64 (Vigna & Steele) is a single-step bit mixer that produces near-perfect avalanche on a 64-bit input. We apply it to FNV's output so that both the upper and lower 32-bit halves are usable as independent hashes.

splitmix64(x):
    x = x + 0x9e3779b97f4a7c15
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb
    return  x ^ (x >> 31)

Known vectors:

The combined hash we actually use:

mix64(bytes) := splitmix64(fnv1a64(bytes))
h1 = mix64(bytes) & 0xffffffff               // low 32 bits
h2 = mix64(bytes) >> 32                       // high 32 bits

3. Synthesizing k indices (Kirsch–Mitzenmacher)

For a bit array of size m and k hashes:

for i in 0..k:
    g = h1 + i * h2          // wrapping 64-bit add
    idx = g mod m            // reduce to [0, m)
    use bits[idx]

The reduction g mod m is hot. Naive % works but a modulo on a 64-bit integer is ~20 cycles. RocksDB and others use Lemire's fast reduction:

fastmod(g, m) = ((g as u128) * (m as u128)) >> 64

(Equivalent to floor(g * m / 2^64), a near-uniform map of [0, 2^64) to [0, m).) Either approach is fine for correctness — but pick one and use it in all three languages, otherwise the bit positions diverge and cross-language tests break.

This lab uses plain % because it's identical across languages with no language-specific u128 syntax to worry about. Performance difference is irrelevant at filter-construction scale.

Test gate

Before moving on, all three bloombench hash foobar invocations must print:

fnv1a64=85944171f73967e8
splitmix=...        (same value across languages)
h1=...  h2=...      (same values across languages)

If those don't match, the rest of the lab cannot succeed.

Step 02 — Bit array, add, contains

The bit array

Backed by a Vec<u8> / []byte / std::vector<uint8_t> of length ⌈m / 8⌉. Indexing is little-endian within each byte:

bit i  →  byte index  = i / 8
         bit within  = i % 8         // bit 0 is the LSB
         test:  (bytes[i/8] >> (i%8)) & 1
         set:    bytes[i/8] |= 1 << (i%8)

Side-by-side:

#![allow(unused)]
fn main() {
fn set_bit(bits: &mut [u8], i: u64) {
    let idx = (i / 8) as usize;
    let off = (i % 8) as u8;
    bits[idx] |= 1u8 << off;
}
fn get_bit(bits: &[u8], i: u64) -> bool {
    let idx = (i / 8) as usize;
    let off = (i % 8) as u8;
    (bits[idx] >> off) & 1 == 1
}
}

func setBit(bits []byte, i uint64) {
    bits[i/8] |= 1 << (i % 8)
}
func getBit(bits []byte, i uint64) bool {
    return bits[i/8]&(1<<(i%8)) != 0
}

inline void SetBit(std::uint8_t* b, std::uint64_t i) {
    b[i / 8] |= std::uint8_t{1} << (i % 8);
}
inline bool GetBit(const std::uint8_t* b, std::uint64_t i) {
    return (b[i / 8] >> (i % 8)) & 1u;
}

⚠️ Pick one bit-order now. LSB-first (above) matches LevelDB and is the natural choice in C. MSB-first matches some networking specs (TCP option encoding). Whichever you pick, all three implementations must agree.

add(key)

add(key):
    h = mix64(key)
    h1 = h & 0xffffffff
    h2 = h >> 32
    for i in 0..k:
        idx = (h1 + i * h2) mod m
        set_bit(idx)

Notes:

• All arithmetic is wrapping 64-bit (u64/uint64/std::uint64_t).
• i * h2 overflows for large k. That's fine — mod m will still produce a valid index. Languages with overflow checks (Rust debug mode) need wrapping_mul/wrapping_add.
• We compute h once per key, then derive k indices. That's the entire Kirsch–Mitzenmacher win.

contains(key)

contains(key):
    h = mix64(key)
    h1 = h & 0xffffffff
    h2 = h >> 32
    for i in 0..k:
        idx = (h1 + i * h2) mod m
        if not get_bit(idx):
            return false
    return true

Early-exit on the first zero bit. With FPR 1% and a random absent key, you typically exit after 1 or 2 probes.

Three-language add skeleton

#![allow(unused)]
fn main() {
pub fn add(&mut self, key: &[u8]) {
    let h = mix64(key);
    let h1 = h as u32 as u64;
    let h2 = h >> 32;
    for i in 0..self.k as u64 {
        let idx = h1.wrapping_add(i.wrapping_mul(h2)) % self.m;
        set_bit(&mut self.bits, idx);
    }
}
}

func (b *Bloom) Add(key []byte) {
    h := Mix64(key)
    h1 := h & 0xffffffff
    h2 := h >> 32
    for i := uint64(0); i < uint64(b.k); i++ {
        idx := (h1 + i*h2) % b.m
        setBit(b.bits, idx)
    }
}

void Bloom::Add(const std::uint8_t* k, std::size_t n) {
    std::uint64_t h = Mix64(k, n);
    std::uint64_t h1 = h & 0xffffffffULL;
    std::uint64_t h2 = h >> 32;
    for (std::uint64_t i = 0; i < k_; ++i) {
        std::uint64_t idx = (h1 + i * h2) % m_;
        SetBit(bits_.data(), idx);
    }
}

Test gate

• Insert keys "k0".."k999" (UTF-8). contains("kN") must be true for every N. Any false negative is a critical bug.
• Filter must be byte-identical across the three languages (md5sum).

What broken looks like

• contains is sometimes false for present keys → set and get disagree on bit-within-byte. Suspect LSB vs MSB.
• Cross-language filters differ → mod m reduction differs (one uses & instead of % and m isn't a power of two), or h1/h2 halves are swapped.
• contains is always true → m was constructed as 0; bit array is empty so every (h % 0) panics or all indices land in a never-cleared byte.

Step 03 — Sizing, encode/decode, FPR measurement

Picking m and k from (n, fpr)

Given target false-positive rate p and expected key count n:

$$m = \left\lceil \frac{-n \cdot \ln p}{(\ln 2)^2} \right\rceil$$

$$k = \max\left(1,; \text{round}\left(\frac{m}{n} \cdot \ln 2\right)\right)$$

Reference numbers (compute once, hard-code in tests):

Implementation:

with_fpr(n, p):
    ln2     = ln(2)
    m_real  = -(n as f64) * ln(p) / (ln2 * ln2)
    m       = ceil(m_real)
    k_real  = (m as f64 / n as f64) * ln2
    k       = round(k_real) clamped to [1, 30]
    return BloomFilter::new(m, k)

The clamp on k prevents pathological cases. with_fpr(1, 1e-100) would request k ≈ 332 and almost certainly saturate the filter.

Encode

[ k: u32 LE ][ m: u64 LE ][ bits: ⌈m/8⌉ bytes ]

#![allow(unused)]
fn main() {
pub fn encode(&self) -> Vec<u8> {
    let mut out = Vec::with_capacity(12 + self.bits.len());
    out.extend_from_slice(&self.k.to_le_bytes());
    out.extend_from_slice(&self.m.to_le_bytes());
    out.extend_from_slice(&self.bits);
    out
}
}

func (b *Bloom) Encode() []byte {
    out := make([]byte, 12+len(b.bits))
    binary.LittleEndian.PutUint32(out[0:4], b.k)
    binary.LittleEndian.PutUint64(out[4:12], b.m)
    copy(out[12:], b.bits)
    return out
}

std::vector<std::uint8_t> Bloom::Encode() const {
    std::vector<std::uint8_t> out(12 + bits_.size());
    EncodeU32LE(out.data() + 0, k_);
    EncodeU64LE(out.data() + 4, m_);
    std::memcpy(out.data() + 12, bits_.data(), bits_.size());
    return out;
}

Decode

decode(bytes):
    if len(bytes) < 12: error
    k = read u32 LE @ 0
    m = read u64 LE @ 4
    body = bytes[12:]
    if len(body) != ⌈m/8⌉: error
    return BloomFilter { k, m, bits: body }

Validate sizes. If k == 0 or m == 0, reject — those are nonsense.

Measuring FPR

fpr-test(filter, n, m_queries):
    seed reader rng to disjoint stream
    hits = 0
    for q in 0..m_queries:
        key = generate distinctly-not-inserted key
        if filter.contains(key):
            hits += 1
    observed = hits / m_queries
    theoretical = (1 - exp(-k * n / m))^k
    print observed, theoretical

Generating known-absent keys: use the same family as the inserted ones, but with indices ≥ n. If insert used "key0", "key1", ..., "key{n-1}", query with "q0", "q1", ... — different prefix guarantees no accidental overlap.

A million absent queries gives ±10% noise on a 1% FPR estimate; that's the sample size used in the test fpr_within_2x.

Test gate

• with_fpr(1000, 0.01) returns k=7 and m ∈ [9 581, 9 591].
• encode then decode gives an identical filter.
• fpr-test with n=10 000, m_queries=100 000 reports observed FPR within 2× of theoretical (well within ±50%).
• The encoded filter is byte-identical across Rust / Go / C++.

What broken looks like

• k=0 from with_fpr → integer truncation; you used int(k_real) instead of round.
• Decode fails on a perfectly valid file → endian mismatch or header offset wrong.
• Observed FPR is exactly 1.0 → bit array got written but indices land outside its range (modulo bug).
• Observed FPR is exactly 0.0 → contains always returns false; bit array isn't being touched on add (you forgot to mutate self).

LSM MemTable

Lab: db-05 — the in-memory write buffer of an LSM-tree.

1. What Is It

A MemTable is the in-memory, sorted write buffer at the top of every Log-Structured Merge tree (LSM). All writes — put, delete, range updates — land in the MemTable first, indexed by key, and only later get flushed to immutable on-disk SSTables (see db-06). It is paired with a Write-Ahead Log (db-03) for durability: WAL gives crash recovery; the MemTable gives fast point and range lookups.

This lab implements a deterministic, byte-identical MemTable across Rust, Go, and C++ that can be serialized to disk and read back in any of the three languages.

2. Why It Matters

• Write throughput. Writes touch only RAM (plus a single sequential WAL append). Random puts become sequential disk traffic.
• Read recency. The MemTable is the freshest copy of any key; a get must consult it first before falling through to L0..Ln SSTables.
• Flush boundary. Once the MemTable hits its size cap (write_buffer_size in LevelDB/RocksDB), it freezes, a new MemTable rotates in, and the frozen one is written sequentially to an SSTable on background threads.
• Tombstones. Deletes are inserts of tombstone records; the MemTable must preserve them through flush so older SSTables can be shadowed.

3. How It Works

                writes                      reads
                  │                           │
                  ▼                           ▼
   ┌──────── MemTable (active) ─────────┐  point/range
   │   sorted map: key → (type, value)  │◄──────────┐
   │   tombstones live alongside values │           │
   └──────────────────┬─────────────────┘           │
        size > cap?   │                              │
                      ▼                              │
       ┌── Immutable MemTable (frozen) ─┐            │
       │   flushing in the background    │◄───────────┤
       └──────────────────┬──────────────┘           │
                          ▼                          │
                   SSTable on disk ─────────────────►┘
                   (db-06 format)

Internally the MemTable is a sorted associative container with byte-lexicographic key ordering:

• Rust: BTreeMap<Vec<u8>, Entry> (Vec<u8>'s Ord is lex over bytes).
• Go: map[string]Entry + key slice sorted on dump/iteration.
• C++: std::map<std::vector<uint8_t>, Entry> (operator< on vectors is lex).

Production LSMs (LevelDB, RocksDB) use a skip list because it offers concurrent lock-free reads and allocations from an arena. For this lab the simpler tree is fine — what matters is the order-determinism and the on-disk byte layout.

4. Core Terminology

5. Mental Models

• Three-layer journal. WAL = durability log. MemTable = sorted index over the WAL's recent tail. SSTable = compacted, immutable snapshot. The MemTable is the short-term, queryable face of the WAL.
• Latest write wins. For a single point lookup the MemTable always shadows any on-disk data; a tombstone in the MemTable hides every prior value of that key.
• Flush is amplification's first knob. Larger MemTables → fewer, bigger L0 SSTables → less compaction work but more recovery time and RAM. Production tunes this between 16 MiB and 256 MiB.
• Why sorted? Because the flush writes the SSTable in a single sequential pass — no on-disk sort needed if the MemTable is already ordered.

6. Common Misconceptions

• "The MemTable is the WAL." No. The WAL is unsorted, append-only, and may contain redundant updates for the same key. The MemTable is sorted and deduplicated.
• "Tombstones can be GC'd in the MemTable." No — they must be flushed; only after compaction confirms no older SSTable holds the key can a tombstone be dropped.
• "You can skip the WAL if writes are batched." The MemTable lives in RAM. Without the WAL a crash loses every unflushed write.
• "Skip list is the only valid structure." A B-tree, ART, or sorted vector with occasional rebuild are all viable; skip list wins for the specific concurrency pattern of one writer + many readers.

7. Interview Talking Points

• Explain why an LSM uses a MemTable + WAL instead of writing directly to a sorted on-disk file (random I/O kills throughput).
• Walk through the lifecycle: put → WAL append → MemTable insert → eventually frozen → flushed → compacted.
• Describe how a get traverses MemTable → immutable MemTable → L0 SSTables → Ln, stopping at the first match (value or tombstone).
• Cost of tombstones: read amplification grows because we cannot skip a level just because we found nothing; we might still find a tombstone later.
• Why a MemTable's flush is a sorted sequential write — and why this is the primary trick that makes LSMs faster than B-trees for write-heavy workloads.

8. Connections to Other Labs

• db-03 (WAL): every MemTable write is preceded by a WAL append; the WAL is replayed into a fresh MemTable on startup.
• db-04 (Bloom filters): SSTables produced by MemTable flush carry Bloom filters for negative lookups.
• db-06 (SSTable format): the flush target; this lab's flush_to is the producer side of db-06's open.
• db-07 (compaction): consumes SSTables that came from MemTable flushes.
• db-09 (LevelDB complete): stitches all of the above into a working KV store.

References — db-05 LSM MemTable

Primary sources

• O'Neil, Cheng, Gawlick, O'Neil (1996). The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4). The original paper. https://www.cs.umb.edu/~poneil/lsmtree.pdf

• Sanjay Ghemawat & Jeff Dean. LevelDB. The reference open-source LSM. See db/memtable.{h,cc} and db/skiplist.h. https://github.com/google/leveldb

• Facebook RocksDB Wiki — MemTable. https://github.com/facebook/rocksdb/wiki/MemTable Covers SkipList, HashSkipList, HashLinkList, and Vector MemTable factories.

Skip lists

• William Pugh (1990). Skip Lists: A Probabilistic Alternative to Balanced Trees. CACM 33(6): 668–676. https://homepage.cs.uiowa.edu/~ghosh/skip.pdf

• LevelDB's skiplist implementation — concurrent single-writer/many-reader, lock-free reads via memory-order acquire/release. https://github.com/google/leveldb/blob/main/db/skiplist.h

Alternative data structures

• Bw-tree (Microsoft, 2013): lock-free B+ tree variant used in Hekaton.
• Adaptive Radix Tree (ART, 2013): compact, cache-friendly trie used by HyPer and DuckDB. https://db.in.tum.de/~leis/papers/ART.pdf
• Masstree (Mao, Kohler, Morris, 2012): trie-of-B+trees, very fast for variable length keys.

Tombstones and snapshot reads

• RocksDB DeleteRange. Tombstones over key ranges, important for prefix deletes. https://github.com/facebook/rocksdb/wiki/DeleteRange

• LevelDB sequence numbers. Each MemTable entry is internally tagged with a 56-bit sequence and 8-bit type byte; this lab simplifies to just the type byte. See db/dbformat.h kValueTypeForSeek.

Real-world tunings

• Cassandra: uses Memtable with off-heap allocators; flushed to SSTables on size, time, or commit-log pressure.
• HBase: MemStore per column family; configurable via hbase.hregion.memstore.flush.size.
• InfluxDB IOx & TimescaleDB: apply LSM ideas to time-series, with time-bucketed MemTables.

Further reading

• Mark Callaghan's blog (RocksDB engineering): https://smalldatum.blogspot.com/
• Chen Luo & Michael Carey (2020). LSM-based Storage Techniques: A Survey. VLDB J. https://arxiv.org/abs/1812.07527

Analysis — db-05 LSM MemTable

Problem

Implement the in-memory write buffer of an LSM-tree such that

1. it supports put, delete (tombstone insertion), get, and ordered iteration;
2. it can be serialized to disk in a deterministic byte layout shared by Rust, Go, and C++;
3. the same dump can be reloaded in any of the three languages;
4. iteration order is byte-lexicographic on keys.

Constraints

• Keys are arbitrary byte sequences up to 2^32 − 1 bytes (u32 length prefix).
• Values are arbitrary byte sequences up to 2^32 − 1 bytes; for tombstones the value length is 0.
• Cross-language interop: the dump format must be identical byte-for-byte and the cross-test script asserts SHA-256 equality of the three dumps.
• No allocator tricks: simplicity over LevelDB-style arena/skiplist; we use the standard sorted map in each language.
• No concurrency in this lab: single-threaded API. Concurrency arrives in db-09.

Design decisions

Why a sorted associative container, not a skip list?

Production LSMs (LevelDB, RocksDB) use skip lists because they support concurrent lock-free reads and arena allocation. For this teaching lab those benefits are irrelevant — what matters is determinism, byte-identical serialization, and the fact that iteration is in key order so the flush is a sequential write. Any sorted container satisfies that:

All three give the same iteration order for identical input, which is what cross-test checks.

Tombstones as entries

A delete(k) replaces whatever entry k had with Entry::Tombstone. Crucially the key is not erased — the tombstone must propagate to the SSTable to shadow older on-disk versions of the key.

On-disk dump layout

   offset  size  field
   ------  ----  --------------------------------
        0     4  magic ASCII "MMT1"
        4     4  count: u32 LE (entry count)
        8     ?  entries, sorted by key ascending:
                   [ klen: u32 LE ]
                   [ vlen: u32 LE ]   (0 if tombstone)
                   [ type: u8     ]   (0 = Value, 1 = Tombstone)
                   [ key bytes    ]
                   [ value bytes  ]

All multi-byte integers little-endian; the file is self-delimiting via count and each entry's two length prefixes. No checksum at this layer — the WAL (db-03) and the SSTable (db-06) carry their own.

Size accounting

size_bytes() returns the on-disk dump size assuming the current contents flush immediately: 8 bytes header + per entry (9 + klen + vlen). This is what an LSM would compare against write_buffer_size.

Error model

The decoder validates:

• magic == MMT1,
• enough bytes remain for each header field and the declared key/value spans,
• type is 0 or 1,
• tombstones have vlen == 0,
• no trailing garbage,
• keys appear in strictly ascending order.

A failure returns an explicit error (Error::* in Rust, error in Go, std::invalid_argument / std::runtime_error in C++) rather than panicking. The encoder cannot fail (no I/O at that layer).

Trade-offs

• No sequence numbers. Real LSMs prepend a 64-bit (seqno << 8) | type to every internal key so MVCC snapshots can pick the right version. We collapse to "latest write wins" because db-13 reintroduces MVCC.
• No range tombstones. Each delete shadows exactly one key. RocksDB-style range deletes are db-09 work.
• No prefix bloom or compressed entries. The MemTable is in RAM; flushing to a proper SSTable (db-06) is where compression and block boundaries appear.
• Allocation policy: Vec/vector/[]byte-per-entry, not an arena. Allocator pressure becomes interesting only at multi-million-key scales, which we exercise in db-22 benchmarking.

Alternatives considered

• Skip list with arena (LevelDB style). Better concurrency, cache locality, and drop-the-whole-arena freeing — but the data structure complexity (random levels, acquire/release pointer ops) would dwarf the lab's pedagogical point.
• Sorted vector with binary search. Lowest memory overhead, but every put is O(n) due to mid-vector insertion. Fine for tiny tables (<1 K entries), terrible beyond that.
• HashMap with periodic sort. Fast inserts, but iteration is no longer cheap; every flush triggers a sort. Acceptable if flush is rare, painful otherwise.
• B-epsilon tree. Batches writes inside internal nodes, blurring the line with LSM. Out of scope.

Execution — db-05 LSM MemTable

Library API (Rust shape; mirrored in Go and C++)

#![allow(unused)]
fn main() {
pub enum Entry { Value(Vec<u8>), Tombstone }

pub struct MemTable { /* sorted map */ }

impl MemTable {
    pub fn new() -> Self;
    pub fn len(&self) -> usize;
    pub fn size_bytes(&self) -> usize;
    pub fn put(&mut self, key: &[u8], value: &[u8]);
    pub fn delete(&mut self, key: &[u8]);
    pub fn get(&self, key: &[u8]) -> Option<&Entry>;
    pub fn iter(&self) -> impl Iterator<Item = (&[u8], &Entry)>;
    pub fn encode(&self) -> Vec<u8>;
    pub fn decode(bytes: &[u8]) -> Result<Self, Error>;
}
}

Go: func New() *MemTable, func (*MemTable) Put / Delete / Get / Iter / Encode, func Decode([]byte) (*MemTable, error). Iter yields a slice of (key, entry) pairs in sorted order.

C++: class MemTable with the same names; Iter() returns a const reference to the underlying std::map.

CLI: memtable

memtable <subcommand> [args]

Subcommands:
  new PATH                       create an empty MemTable at PATH
  put PATH KEY VALUE             open PATH, put, save
  del PATH KEY                   open PATH, delete (writes tombstone), save
  get PATH KEY                   print 'value: <hex>' | 'tombstone' | 'absent'
  iter PATH                      print one line per entry: TYPE KEY VALUE  (hex)
  bulk PATH N                    open or create PATH, insert key0..key{N-1}
                                 with values val0..val{N-1}, save
  size PATH                      print 'entries=N size_bytes=B'

Iter output format (deterministic, used by cross-test):

V <hex-key> <hex-value>
T <hex-key>

Hex is lowercase, no 0x prefix, no separators.

Build & test

Per language:

# Rust
cd src/rust && cargo test --release && cargo build --release

# Go
cd src/go && go test ./... && go build -o bin/memtable ./cmd/memtable

# C++
cd src/cpp && cmake -S . -B build -DCMAKE_BUILD_TYPE=Release \
            && cmake --build build && ( cd build && ctest --output-on-failure )

Or run all at once:

bash scripts/verify.sh

Cross-language interop test

scripts/cross_test.sh:

1. Build all three binaries.
2. Drive each one through the same sequence of bulk 100, a handful of puts with overwrites, and a handful of dels.
3. SHA-256 each dump; assert all three match.
4. For each writer/reader pair, run iter and check the output is byte-identical.

If any pair differs, the script prints the failing combination and exits non-zero.

Manual playground

$ memtable new /tmp/m.bin
$ memtable put /tmp/m.bin alpha "first"
$ memtable put /tmp/m.bin beta  "second"
$ memtable put /tmp/m.bin alpha "first-updated"   # overwrite
$ memtable del /tmp/m.bin beta                    # tombstone
$ memtable iter /tmp/m.bin
V 616c706861 66697273742d75706461746564
T 62657461
$ memtable get /tmp/m.bin alpha
value: 66697273742d75706461746564
$ memtable get /tmp/m.bin beta
tombstone
$ memtable get /tmp/m.bin gamma
absent
$ memtable size /tmp/m.bin
entries=2 size_bytes=37

37 = 8 (header) + (9+5+13) + (9+4+0) = 8 + 27 + 13 — two entries with key "alpha"/value "first-updated" and tombstone for key "beta".

What broken looks like

Observation — db-05 LSM MemTable

Hex layout of a tiny dump

Three operations: put alpha first, put beta second, del beta.

hexdump -C m.bin

00000000  4d 4d 54 31 02 00 00 00  05 00 00 00 05 00 00 00  |MMT1............|
00000010  00 61 6c 70 68 61 66 69  72 73 74 04 00 00 00 00  |.alphafirst.....|
00000020  00 00 00 01 62 65 74 61                          |....beta|

Annotated:

Total: 40 bytes; matches size_bytes() = 8 + (9+5+5) + (9+4+0) = 40.

Cross-language byte equality

scripts/cross_test.sh produces three files rust.bin, go.bin, cpp.bin. With the verify script in this lab:

$ shasum -a 256 *.bin
b67…  rust.bin
b67…  go.bin
b67…  cpp.bin

If any one of the three differs we either have endianness disagreement, key ordering disagreement, or someone wrote the type byte in a different position.

Memory layout intuition

key                          entry
"abc"  ──►  Entry::Value("..."  10 bytes)
"abd"  ──►  Entry::Tombstone
"abz"  ──►  Entry::Value(""      0 bytes)   # empty value is legal and ≠ tombstone
"zz"   ──►  Entry::Value("..."  4096 bytes)

Notes:

• The key length is not stored alongside the in-memory entry — only at encode time.
• An empty value ("") is a valid value, distinct from Tombstone. The type byte is what discriminates them.

size_bytes() table

For a MemTable with n entries of average key length k̄ and average value length v̄, with a fraction f being tombstones:

$$ \text{size_bytes}(n, k̄, v̄, f) = 8 + n \cdot (9 + k̄) + n(1-f) \cdot v̄ $$

For default LSM tunings:

(Compare to a real LevelDB write_buffer_size of 4 MiB or RocksDB's 64 MiB default — the table above shows you'd flush a 10K-entry buffer at about a megabyte.)

What an empty MemTable looks like

hexdump -C empty.bin
00000000  4d 4d 54 31 00 00 00 00                           |MMT1....|

8 bytes. size_bytes() returns 8. len() returns 0.

Iteration order corner cases

keys = ["", "\x00", "\x00\x00", "a", "ab", "b"]

Sorted byte-lex order:

""         (empty key — sorts first)
"\x00"
"\x00\x00"
"a"
"ab"
"b"

Empty keys are legal in this design (klen = 0). They are useful when the key is something like a single byte tag followed by an optional suffix.

Verification — db-05 LSM MemTable

Unit tests (per language)

Cross-language interop (scripts/cross_test.sh)

The same scripted scenario runs in each language:

new   → bulk 100 → put "key50" "REPLACED"
                → del "key10"
                → put "" "empty-key-value"
                → del "key99"
                → save

This produces dumps rust.bin, go.bin, cpp.bin. The script then:

1. SHA-256s all three dumps. All must match — this is the byte-identical gate.
2. 3×3 reader matrix. Every reader (rust/go/cpp) runs iter on every writer's dump. The lines must be identical across all 9 combinations.
3. get spot-check. Each reader queries key50, key10, key99, "", and an absent key nonexistent; results must be value: 5245504c41434544 (REPLACED), tombstone, tombstone, value: 656d7074792d6b65792d76616c7565, absent respectively across all readers.

End-to-end verification (scripts/verify.sh)

bash scripts/verify.sh

Builds and tests all three languages, then runs the cross-test. Final line must be ALL GREEN.

Manual sanity checks

• memtable new /tmp/m && wc -c /tmp/m → exactly 8 bytes.
• memtable bulk /tmp/m 1000 && memtable size /tmp/m → matches the formula 8 + 1000 * (9 + len("keyN") + len("valN")) summed over N=0..999.
• Hexdump the first 16 bytes of any dump and confirm magic + count.

What broken looks like

Broader Ideas — db-05 LSM MemTable

The MemTable in this lab is intentionally minimal. Real systems extend it in many directions; this doc maps the design space.

Concurrency-friendly structures

• Skip list (LevelDB, RocksDB). Single writer + many readers, lock-free reads via memory-order acquire/release. The dominant choice for LSM MemTables.
• Bw-tree (Hekaton). Lock-free B+ tree using delta records and a mapping table; shines on multi-writer workloads.
• ART (Adaptive Radix Tree). Cache-friendly trie; very fast point lookups, used by HyPer, DuckDB, and recent CockroachDB internals for some indexes.
• Masstree. Trie-of-B+trees; outperforms skip list on long variable keys.

Arena allocation

LevelDB's MemTable allocates all skip-list nodes from a bump-arena. Freeing is O(1) (drop the arena). RocksDB has a configurable Arena and a ConcurrentArena for parallel writes. Real benefit: less fragmentation and one cache-line probe per allocation. Our lab uses standard allocators because the lesson is the data layout, not the allocator.

Sequence numbers & MVCC

Production LSMs prepend a 64-bit sequence number (and an 8-bit type byte) to every internal key. Snapshot reads pick the latest sequence ≤ the snapshot's tag. db-13 revisits this when we add MVCC; here we collapse to last-write-wins.

Range tombstones

A single tombstone shadows one key. RocksDB's DeleteRange tombstones cover a key range [start, end) and live in a separate auxiliary structure inside the MemTable (RangeDelAggregator). This avoids exploding the MemTable size when bulk-deleting. Adding it would require:

1. A RangeTombstone struct: (start, end, seqno).
2. A second sorted container inside MemTable.
3. get consults both: a key shadowed by an overlapping range tombstone returns Tombstone even if it has a Value entry.

Multiple MemTables (active + immutable list)

Production engines keep one active MemTable plus a list of immutable MemTables awaiting flush. Reads consult [active, ...immutables, L0, L1, ...] in order. Writers swap atomically (active → immutable + new empty active) when the size cap is hit. This decouples flush latency from write latency.

Write amplification interplay

The MemTable size cap (write_buffer_size) is the first knob in the LSM write amplification dial:

• Larger MemTable → fewer, bigger L0 SSTables → less L0 compaction → lower write amp but slower recovery and more RAM.
• Smaller MemTable → more L0 SSTables → more compaction work → higher write amp but fast recovery.

RocksDB and Cassandra default in the range 64–256 MiB; LevelDB defaults to 4 MiB.

Persistent MemTables (PMEM)

Intel Optane / CXL persistent memory blurs the WAL+MemTable boundary: the MemTable itself lives in persistent memory, so the WAL is unnecessary. Papers from VLDB 2018–2020 (NoveLSM, SLM-DB, FloDB) explore this.

Encryption

Cassandra and RocksDB optionally encrypt at-rest data including the MemTable's flushed SSTables. The MemTable itself is in RAM and inherits process-memory protection. Encrypting in-memory pages requires hardware support (SGX, AMD SEV).

Compression of in-memory entries

For very long values, RocksDB can compress values inside the MemTable using LZ4 or ZSTD via the MemTableRep's EncodeKey hook. Trades CPU for memory; useful when RAM is the limit.

Skip-list level distribution

Pugh's original skip list uses geometric level distribution with p=0.5 (max levels = log₂ n). LevelDB sets max levels = 12 and branching = 4; RocksDB defaults max = 16, branching = 4. Lower branching → taller list → more memory but better adaptivity.

Adversarial concerns

• Memory amplification via tombstones. A flood of deletes can make the MemTable hold many entries with no live data; eventually all tombstones must propagate to SSTables and may take generations of compaction to GC.
• Skew-induced flush storms. A hot key prefix can keep one MemTable bucket pinned while others empty; with hash-partitioned MemTables (HashSkipList) this is pronounced.

Beyond LSM

• B-epsilon trees (TokuDB / Percona) batch writes inside internal B+ tree nodes; no separate MemTable.
• Anti-caching (HyPer, VoltDB) keeps the working set in memory and evicts cold rows to disk; inverts the LSM model.
• WiscKey decouples keys (LSM) from values (separate log) to slash write amplification for large values.

Step 01 — Sorted map + Entry type

Build the in-memory MemTable: a sorted associative container from byte-key to an Entry that is either Value(bytes) or Tombstone. Implement put, delete, get, iter, and len / size_bytes in all three languages with the same iteration order (byte-lex).

Why this first

The MemTable's iteration order is the contract that the on-disk format and the SSTable flush both depend on. If three languages disagree on order, every later step falls apart. So this step is a one-language-after-the-other implementation of the same BTreeMap-equivalent, with a shared unit test that inserts a permutation and checks the order.

Entry type

#![allow(unused)]
fn main() {
// Rust
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Entry {
    Value(Vec<u8>),
    Tombstone,
}
}

// Go
type EntryType uint8
const (
    EntryValue EntryType = 0
    EntryTombstone EntryType = 1
)
type Entry struct {
    Type  EntryType
    Value []byte // empty if Tombstone
}

// C++
namespace dse::memtable {
    enum class EntryType : std::uint8_t { Value = 0, Tombstone = 1 };
    struct Entry {
        EntryType type;
        std::vector<std::uint8_t> value; // empty if Tombstone
    };
}

The type-byte numbering (0 = Value, 1 = Tombstone) is part of the on-disk contract — don't reorder it.

Container choice

#![allow(unused)]
fn main() {
// Rust — Vec<u8>'s Ord is byte-lex; BTreeMap iterates in key order
use std::collections::BTreeMap;
pub struct MemTable {
    map: BTreeMap<Vec<u8>, Entry>,
    bytes: usize,
}
}

// Go — unordered map; sort keys on iteration / encode
type MemTable struct {
    m     map[string]Entry
    bytes int
}

func (t *MemTable) sortedKeys() []string {
    keys := make([]string, 0, len(t.m))
    for k := range t.m {
        keys = append(keys, k)
    }
    sort.Strings(keys) // byte-lex on string is the same as on []byte
    return keys
}

// C++ — std::map's comparator is operator< on vector<uint8_t>, which is lex
class MemTable {
    std::map<std::vector<std::uint8_t>, Entry> map_;
    std::size_t bytes_ = 0;
};

put / delete

#![allow(unused)]
fn main() {
pub fn put(&mut self, key: &[u8], value: &[u8]) {
    self.bytes -= self.entry_bytes(key);
    self.map.insert(key.to_vec(), Entry::Value(value.to_vec()));
    self.bytes += self.entry_bytes(key);
}

pub fn delete(&mut self, key: &[u8]) {
    self.bytes -= self.entry_bytes(key);
    self.map.insert(key.to_vec(), Entry::Tombstone);
    self.bytes += self.entry_bytes(key);
}

fn entry_bytes(&self, key: &[u8]) -> usize {
    match self.map.get(key) {
        None => 0,
        Some(Entry::Value(v)) => 9 + key.len() + v.len(),
        Some(Entry::Tombstone) => 9 + key.len(),
    }
}
}

Go and C++ use the same accounting trick: subtract the old entry's contribution, update, add the new contribution.

iter

#![allow(unused)]
fn main() {
pub fn iter(&self) -> impl Iterator<Item = (&[u8], &Entry)> {
    self.map.iter().map(|(k, e)| (k.as_slice(), e))
}
}

func (t *MemTable) Iter() []KeyEntry {
    out := make([]KeyEntry, 0, len(t.m))
    for _, k := range t.sortedKeys() {
        out = append(out, KeyEntry{Key: []byte(k), Entry: t.m[k]})
    }
    return out
}

const std::map<std::vector<std::uint8_t>, Entry>& Iter() const noexcept {
    return map_;
}

Test — order determinism

Insert this permutation in each language and assert iteration yields the keys in the canonical sorted order:

inputs (insert order):  ["b", "a", "", "\x00\x00", "ab", "\x00"]
expected iter order:    ["", "\x00", "\x00\x00", "a", "ab", "b"]

This catches:

• Go forgetting to sort.
• C++ using std::map<std::string, ...> (where '\0' ends the string and breaks comparisons on binary keys).
• Anyone using a hash map.

What to verify before moving on

• put then get returns the value just written.
• delete then get returns Tombstone (not absent).
• Overwriting a key keeps len() at 1.
• The permutation test above passes.
• size_bytes() increases by exactly 9 + klen + vlen for each new key and stays flat when overwriting.

Step 02 — Encode / Decode the dump

Serialize the MemTable to a byte-identical on-disk layout and parse it back.

Layout (recap from analysis.md)

  magic   "MMT1"            (4 bytes)
  count   u32 LE            (4 bytes)
  repeat count times, in ascending key order:
      klen   u32 LE
      vlen   u32 LE         (0 for tombstone)
      type   u8             (0 = Value, 1 = Tombstone)
      key    klen bytes
      value  vlen bytes

Rust

#![allow(unused)]
fn main() {
pub fn encode(&self) -> Vec<u8> {
    let mut out = Vec::with_capacity(self.size_bytes());
    out.extend_from_slice(b"MMT1");
    out.extend_from_slice(&(self.map.len() as u32).to_le_bytes());
    for (k, e) in &self.map {
        let (vlen, t, v) = match e {
            Entry::Value(v) => (v.len() as u32, 0u8, v.as_slice()),
            Entry::Tombstone => (0, 1, &[][..]),
        };
        out.extend_from_slice(&(k.len() as u32).to_le_bytes());
        out.extend_from_slice(&vlen.to_le_bytes());
        out.push(t);
        out.extend_from_slice(k);
        out.extend_from_slice(v);
    }
    out
}

pub fn decode(bytes: &[u8]) -> Result<Self, Error> {
    if bytes.len() < 8 { return Err(Error::Short); }
    if &bytes[..4] != b"MMT1" { return Err(Error::BadMagic); }
    let count = u32::from_le_bytes(bytes[4..8].try_into().unwrap()) as usize;
    let mut p = 8usize;
    let mut t = MemTable::new();
    let mut prev: Option<Vec<u8>> = None;
    for _ in 0..count {
        if p + 9 > bytes.len() { return Err(Error::Short); }
        let klen = u32::from_le_bytes(bytes[p..p+4].try_into().unwrap()) as usize;
        let vlen = u32::from_le_bytes(bytes[p+4..p+8].try_into().unwrap()) as usize;
        let ty = bytes[p+8];
        p += 9;
        if p + klen + vlen > bytes.len() { return Err(Error::Short); }
        let key = bytes[p..p+klen].to_vec();
        p += klen;
        let val = bytes[p..p+vlen].to_vec();
        p += vlen;
        if let Some(ref pk) = prev {
            if key.as_slice() <= pk.as_slice() { return Err(Error::Unsorted); }
        }
        let entry = match ty {
            0 => { Entry::Value(val) }
            1 => { if vlen != 0 { return Err(Error::BadTombstone); } Entry::Tombstone }
            _ => return Err(Error::BadType),
        };
        prev = Some(key.clone());
        t.insert_raw(key, entry);
    }
    if p != bytes.len() { return Err(Error::Trailing); }
    Ok(t)
}
}

Go

func (t *MemTable) Encode() []byte {
    out := make([]byte, 0, t.SizeBytes())
    out = append(out, 'M', 'M', 'T', '1')
    out = binary.LittleEndian.AppendUint32(out, uint32(len(t.m)))
    for _, k := range t.sortedKeys() {
        e := t.m[k]
        out = binary.LittleEndian.AppendUint32(out, uint32(len(k)))
        out = binary.LittleEndian.AppendUint32(out, uint32(len(e.Value)))
        out = append(out, byte(e.Type))
        out = append(out, k...)
        out = append(out, e.Value...)
    }
    return out
}

Decode mirrors the Rust shape: read header, then loop reading klen, vlen, type, key, value, validating ascending key order and rejecting trailing bytes.

C++

std::vector<std::uint8_t> MemTable::Encode() const {
    std::vector<std::uint8_t> out;
    out.reserve(SizeBytes());
    static constexpr std::uint8_t magic[4] = {'M','M','T','1'};
    out.insert(out.end(), magic, magic + 4);
    PutU32LE(out, static_cast<std::uint32_t>(map_.size()));
    for (auto const& [k, e] : map_) {
        PutU32LE(out, static_cast<std::uint32_t>(k.size()));
        PutU32LE(out, static_cast<std::uint32_t>(e.value.size()));
        out.push_back(static_cast<std::uint8_t>(e.type));
        out.insert(out.end(), k.begin(), k.end());
        out.insert(out.end(), e.value.begin(), e.value.end());
    }
    return out;
}

What the decoder must reject

How to spot-check

After encoding a 2-entry MemTable (alpha=first, beta tombstoned):

xxd /tmp/m.bin | head
00000000: 4d4d 5431 0200 0000 0500 0000 0500 0000  MMT1............
00000010: 0061 6c70 6861 6669 7273 7404 0000 0000  .alphafirst.....
00000020: 0000 0001 6265 7461                      ....beta

Three things to verify by eye:

1. 4d4d5431 = MMT1.
2. 0200 0000 = count of 2 (LE).
3. The tombstone's vlen is 0000 0000 and the byte before its key is 01.

Test V6 — round-trip 50 entries

Mix puts and deletes:

for i in 0..50:
    if i % 5 == 0: t.delete(format!("key{i}").as_bytes())
    else:          t.put(format!("key{i}").as_bytes(), format!("val{i}").as_bytes())
encoded = t.encode()
roundtrip = MemTable::decode(&encoded).unwrap()
assert_eq!(roundtrip.len(), t.len())
for (k, e) in t.iter() {
    assert_eq!(roundtrip.get(k), Some(e))
}
assert_eq!(roundtrip.encode(), encoded)

The last line is the idempotence check — decoding and re-encoding produces the same bytes. If it doesn't, we have non-determinism in iteration order, which will also break cross-language interop.

Step 03 — CLI + cross-language interop

Wrap the library in a uniform CLI and prove that all three implementations produce byte-identical dumps for the same scripted scenario.

The memtable binary

Every language exposes the same subcommands so the cross-test can drive them uniformly:

memtable new    PATH
memtable put    PATH KEY VALUE
memtable del    PATH KEY
memtable get    PATH KEY
memtable iter   PATH
memtable bulk   PATH N
memtable size   PATH

• KEY and VALUE are passed as raw command-line strings. They may contain printable bytes; for testing we stick to ASCII to avoid shell quoting issues.
• iter and get print hex (lowercase, no separator) so output is shell-safe.

Output formats

# iter
V <hex-key> <hex-value>
T <hex-key>

# get
value: <hex-value>
tombstone
absent

# size
entries=<N> size_bytes=<B>

The scripted scenario

scripts/cross_test.sh drives every language through this sequence:

new                                          # 8 bytes, empty
bulk 100                                     # 100 entries key0..key99 / val0..val99
put  key50  REPLACED                         # overwrite
del  key10                                   # tombstone
put  ""     empty-key-value                  # empty key as a valid key
del  key99                                   # tombstone at the tail

Then it dumps rust.bin, go.bin, cpp.bin and asserts:

shasum -a 256 rust.bin go.bin cpp.bin
# all three hashes must be identical

3×3 reader matrix

For every writer × reader combination, the script runs

$READER iter $WRITER.bin > out.${reader}.${writer}.txt

and diffs pairs of outputs. All nine outputs must agree byte-for-byte.

Why a bulk subcommand

Running 100 separate memtable put PATH key0 val0 … invocations would (a) thrash the disk and (b) test the CLI's argument parsing more than the data structure. bulk exists so the cross-test can build a non-trivial table in one process per language.

Spot-check get results

After the scenario the script also runs

get key50         # expect 'value: 5245504c41434544'   (REPLACED in hex)
get key10         # expect 'tombstone'
get key99         # expect 'tombstone'
get ""            # expect 'value: 656d7074792d6b65792d76616c7565'  (empty-key-value)
get nonexistent   # expect 'absent'

across all three readers.

Failure messages worth designing for

$ memtable get /tmp/m bogus
absent

$ memtable get /tmp/no-such-file foo
error: read /tmp/no-such-file: No such file or directory

$ memtable get /tmp/garbage.bin foo
error: bad magic

A consistent error vocabulary across languages makes the cross-test's grep patterns simpler.

Tying it together

scripts/verify.sh runs:

1. Rust tests (cargo test --release).
2. Go tests (go test ./...).
3. C++ tests (cmake -S . -B build && cmake --build build && ctest).
4. The cross-language script.

Final stdout must end with ALL GREEN.

SSTable Format

1. What Is It

A Sorted String Table (SSTable) is an immutable on-disk file holding key/value entries in byte-lex key order, organised into fixed-size blocks with an index block that maps each block's first key to its byte range inside the file, and a fixed-size footer that locates the index block.

The format in this lab:

+--------------------+   0
| data block 0       |
+--------------------+
| data block 1       |
+--------------------+
| ...                |
+--------------------+
| data block N-1     |
+--------------------+   index_offset
| index block        |
+--------------------+   file_size - 32
| footer (32 bytes)  |
+--------------------+   file_size

The footer always lives in the last 32 bytes and ends with the magic SST1\0\0\0\0, so any reader can validate the file with one pread of the tail and then pread the index block, and only then the relevant data block.

2. Why It Matters

• Read-once, write-never. Each SSTable is written sequentially and then treated as read-only. That eliminates most concurrency hazards: lookups, range scans, and compactions can all share a single immutable file.
• Bounded read amplification. A point lookup is footer → index → one data block. With a 4 KB block and a 16-byte average entry, ≤256 keys are scanned per lookup, regardless of file size.
• Predictable I/O. Blocks are aligned write units; the OS page cache can pin hot blocks. Tail latency is dominated by exactly two I/Os per miss (index + data).
• Foundation for LSM. Compaction merges multiple immutable SSTables into new immutable SSTables. The format is what makes "immutable + sorted + indexed" a usable storage primitive.

3. How It Works

3.1 Data block

A data block is a self-describing run of entries.

[count: u32 LE]
repeat count times (keys ascending byte-lex within the block):
  [klen: u32 LE][vlen: u32 LE][type: u8][key bytes][value bytes]

The writer flushes a block when its accumulated size would exceed a target (default 4096 bytes). The very first key of each block is the index key for that block.

3.2 Index block

[count: u32 LE]
repeat count times:
  [klen: u32 LE][offset: u64 LE][size: u64 LE][first-key bytes]

offset and size locate the data block inside the file. Index entries are listed in ascending block order, which is the same as ascending first-key order.

3.3 Footer (exactly 32 bytes)

[index_offset: u64 LE]
[index_size:   u64 LE]
[num_blocks:   u64 LE]
[magic:        "SST1\0\0\0\0" (8 bytes)]

The fixed size makes the tail trivially locatable: pread(fd, buf, 32, file_size - 32).

3.4 Point lookup

1. Read footer; verify magic.
2. Read index block (index_offset..index_offset+index_size).
3. Binary-search the index for the rightmost index entry whose first key ≤ target. That entry's block is the only one that can contain the target.
4. Read that block; linear-scan within it.

A miss in step 3 (target < first entry's key) means the key is absent without reading any data block.

4. Core Terminology

5. Mental Models

• Phone book. Data blocks are pages; the index is the alphabetical tabs on the side. The footer is the spine label saying "Volume 3 of 3".
• Skiplist with one level. The index is a single coarse "level" above the sorted data; binary search on the index replaces a multi- level skiplist traversal.
• Two-tier B+tree. Conceptually an SSTable is a 2-level B+tree whose leaves are data blocks and whose root is the index block — but built sequentially and frozen.

6. Common Misconceptions

• "You need to scan the whole file to find a key." No — one index lookup pins a single block.
• "The index must be at the start so you can read it first." No — the footer pointer makes the index location flexible, and writing the index last avoids buffering all keys before any data is flushed.
• "Block size = block contents size." The on-disk block includes its own count header; the writer tracks an estimate of accumulated bytes so blocks land roughly on the target.
• "Tombstones can be dropped at write time." Not safely — a tombstone must survive until no older SSTable can shadow it (handled by compaction in db-07).
• "Binary search needs fixed-size index entries." The index entries here are variable-length, but the index block itself is small and fully loaded into RAM, where any search structure is cheap.

7. Interview Talking Points

• Why is the footer at the end? ("So the writer can stream data blocks then index without two passes; one pread of the tail finds everything.")
• What changes if you target 64 KB blocks instead of 4 KB? (Fewer index entries → smaller index → faster directory lookups; larger read amplification per miss; better compression ratios.)
• How does this format become durable? (fsync after the footer is written, and a parent directory fsync so the dirent is recoverable. Without it a crash can leave the magic visible but data missing.)
• What is bsearch looking for inside the index? (The floor — the largest first-key ≤ target — not equality.)
• What stops a corrupt footer from poisoning the reader? (Magic check
  • length plausibility checks. Real systems add CRCs per block.)

8. Connections to Other Labs

• db-05 MemTable supplies the sorted, in-memory K/V stream that this writer drains into blocks.
• db-04 Bloom Filters can be attached per SSTable to skip the index lookup on negative queries (added in db-08 / db-09).
• db-07 LSM Compaction consumes many SSTables and produces new ones using exactly this format.
• db-08 Block Cache and Iterators caches the parsed data block rather than re-decoding on each lookup, and turns intra-block scans into iterators.
• db-09 LevelDB Complete stitches MemTable + WAL + SSTable + compaction + bloom into a working engine.

References — SSTable Format

Papers

• O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. "The Log-Structured Merge-Tree (LSM-Tree)." Acta Informatica 33(4), 1996. — Original description of the immutable run / multi-level merge architecture.
• Chang, F. et al. "Bigtable: A Distributed Storage System for Structured Data." OSDI 2006. — Introduces the SSTable term and the blocks-plus-index layout this lab mirrors.

Open-source implementations

• LevelDB table/format.h, table/table_builder.cc, table/block_builder.cc, table/block.cc — canonical reference for this lab. The data block format here is the LevelDB block format with restart-point compression removed for clarity.
• RocksDB table/block_based/block_based_table_builder.cc — adds bloom-filter blocks, compression, and partitioned indices on top of the same skeleton.
• CockroachDB Pebble sstable/writer.go and sstable/reader.go — Go implementation in idiomatic style.

Articles

• LevelDB design doc: https://github.com/google/leveldb/blob/main/doc/table_format.md
• RocksDB BlockBasedTable: https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
• "Building an LSM Storage Engine: SSTables" — Mini-LSM tutorial, Chen et al.: https://skyzh.github.io/mini-lsm/

Analysis — SSTable Format

Problem

Take a sorted stream of K/V (and tombstone) entries — exactly what db-05 produces — and persist it as an immutable, randomly-readable file:

• writing is one sequential pass (no re-reads, no buffering all keys);
• a point lookup costs O(log N) on the index plus one block read;
• the file is self-describing: a reader can validate and navigate it using only the file itself.

Constraints

• 4 KB target data-block size (close to a page; tunable).
• Little-endian integers throughout (matches db-03 / db-05).
• No per-block CRCs in this lab — added in db-21 ("Storage Engine Advanced"). The footer magic is the only integrity gate.
• No compression, no delta-encoded keys: the goal is a format simple enough to compare byte-for-byte across three languages.
• Cross-language interop: Rust, Go, and C++ MUST emit byte-identical SSTables for the same input MemTable.

Design

Stream-once writer

sst_writer.add(key, type, value) -> writes into current data block buffer
sst_writer.finish() -> flushes the current block, writes index, writes footer

The writer accumulates one block in memory at a time. When adding an entry would push the encoded block size past 4096 bytes, the current block is flushed and a new one started. The first key of every block is captured into an IndexEntry { key, offset, size }.

Index sizing

Index entries are ~ (4 + 8 + 8 + k̄) = 20 + k̄ bytes; for k̄ = 16 and ~250 entries per 4 KB block, a 1 GB SSTable carries ~262 144 blocks × 36 B ≈ 9 MB of index — small enough to keep in RAM per open SSTable.

Lookup

fn get(key) -> Option<Entry>:
    footer = read_tail(32)
    assert footer.magic == "SST1\0\0\0\0"
    index = read(footer.index_offset, footer.index_size)
    blk = bsearch_floor(index, key)?                # None => below smallest
    block = read(blk.offset, blk.size)
    return linear_scan(block, key)

bsearch_floor is the rightmost index entry whose first key ≤ target. Returning None (target precedes the smallest first-key) is a fast miss without reading any data block.

Per-language container choice

IndexEntry is (Vec<u8> key, u64 offset, u64 size) in all three.

Build-from-memtable bridge

For cross-test friendliness, the writer's input source is a decoded MemTable dump (the output of db-05 encode). The CLI command build reads IN.mt, iterates in sorted order, and emits OUT.sst.

What could break

• Block boundary drift. If two implementations disagree on when to flush a block (e.g. > 4096 vs >= 4096), the data blocks land at different offsets, the index differs, and the footer hashes differ. We pin the rule: *flush when `current_block_size + next_entry_size

  4096ANDcurrent_block_size > 0`*.

• Index encoding for the very first block. Its first key may be the empty string ""; the index entry then has klen=0. The reader must still treat it as the floor for any non-empty target.
• Footer alignment. Anything other than exactly 32 bytes after the index block invalidates the magic offset.

Execution — SSTable Format

Library API (uniform across Rust / Go / C++)

struct Entry { type: 0|1; value: bytes }     // tombstone => value == empty
struct IndexEntry { key: bytes; offset: u64; size: u64 }
struct Footer { index_offset: u64; index_size: u64; num_blocks: u64; magic: "SST1\0\0\0\0" }

const BLOCK_TARGET: usize = 4096
const FOOTER_LEN:   usize = 32
const MAGIC:        &[u8; 8] = b"SST1\0\0\0\0"

// ---- writer ----
SstWriter::new(target_block_size = BLOCK_TARGET)
SstWriter::add(&mut self, key: &[u8], entry: Entry)   // keys MUST be strictly ascending
SstWriter::finish(&mut self) -> Vec<u8>               // returns full SSTable bytes

// ---- reader ----
SstReader::open(bytes: &[u8]) -> Result<Self, Error>
SstReader::len(&self) -> usize                         // num entries
SstReader::num_blocks(&self) -> usize
SstReader::get(&self, key: &[u8]) -> Option<Entry>     // None if absent OR tombstone is not skipped
SstReader::iter(&self) -> impl Iterator<Item=(&[u8], Entry)>  // full file scan

Error variants: Short, BadMagic, BadBlock, Unsorted, BadTombstone, BadType, IndexOutOfRange.

CLI

The binary is named sstable in every language and dispatches on the first arg:

sstable build  IN.mt OUT.sst         # read MemTable dump, write SSTable
sstable footer FILE.sst              # print: index_offset=... index_size=... num_blocks=... magic_ok=...
sstable get    FILE.sst KEY          # prints: value: <hex> | tombstone | absent
sstable iter   FILE.sst              # prints lines: V <hex-key> <hex-value> | T <hex-key>
sstable size   FILE.sst              # prints: file_bytes=B entries=N num_blocks=K

Output formats match db-05 deliberately so the same cross-test helpers (hex iter, value:/tombstone/absent get) apply.

Worked example

Given memtable bulk M.mt 100 && memtable put M.mt key50 REPLACED && memtable del M.mt key10, calling sstable build M.mt OUT.sst does:

1. Decode M.mt (MemTable format from db-05).
2. Iterate in sorted order; for each entry, call writer.add.
3. The writer accumulates entries into a 4096-byte data-block buffer. When the next entry would overflow, it flushes the buffer:
   • records IndexEntry { key = first_key_of_block, offset, size },
   • appends the encoded block to the output stream,
   • resets the buffer with the just-added entry.
4. After the last add, finish flushes the final block, then writes the index block, then a 32-byte footer ending in SST1\0\0\0\0.

The output file is then self-validating: sstable footer OUT.sst prints the footer values, sstable iter OUT.sst reproduces every entry in sorted order, and sstable get OUT.sst key50 returns value: 5245504c41434544.

Observation — SSTable Format

Smallest possible SSTable

Build from an empty MemTable: zero entries, zero data blocks, an empty index, and just the footer.

file size: 0 + 4 (index count=0) + 32 (footer) = 36 bytes

Hex (annotated):

offset
0000:  00 00 00 00                                          # index block: count=0
0004:  00 00 00 00 00 00 00 00   index_offset = 0
000c:  04 00 00 00 00 00 00 00   index_size   = 4
0014:  00 00 00 00 00 00 00 00   num_blocks   = 0
001c:  53 53 54 31 00 00 00 00   magic        = "SST1\0\0\0\0"

File-size formula

For a build with N entries spread across K data blocks where the sum of key sizes is Σk and the sum of value sizes (only for non-tombstone entries) is Σv:

data_bytes  = Σ_blocks ( 4 + Σ_entries_in_block (9 + k + v) )
            = 4·K + N·9 + Σk + Σv
index_bytes = 4 + Σ_blocks ( 4 + 8 + 8 + first_key_len )
            = 4 + K·20 + Σ_block_first_key_lens
file_bytes  = data_bytes + index_bytes + 32

(The 4-byte per-block header is the entry count. The 20-byte per-index-entry overhead is klen u32 + offset u64 + size u64.)

Hex walkthrough of a 3-entry SSTable

Three small entries forced into one block by the small block target — e.g. put a 1, put bb 22, del ccc:

00000000  03 00 00 00                       count=3
00000004  01 00 00 00 01 00 00 00 00 'a' '1'              # entry 1: klen=1 vlen=1 type=0 "a" "1"
00000011  02 00 00 00 02 00 00 00 00 'b' 'b' '2' '2'      # entry 2: klen=2 vlen=2 type=0 "bb" "22"
0000001e  03 00 00 00 00 00 00 00 01 'c' 'c' 'c'          # entry 3: klen=3 vlen=0 type=1 "ccc"

00000028  01 00 00 00                       # index count=1
0000002c  01 00 00 00 00 00 00 00 00 00 00 00 28 00 00 00 00 00 00 00 'a'   # klen=1 offset=0 size=0x28 "a"

00000048  00 00 00 00 00 00 00 00           # footer.index_offset = 0x28
00000050  19 00 00 00 00 00 00 00           # footer.index_size   = 0x19
00000058  01 00 00 00 00 00 00 00           # footer.num_blocks   = 1
00000060  53 53 54 31 00 00 00 00           # magic "SST1\0\0\0\0"
                                            #   (file size = 0x68 = 104 bytes)

Note that the first key of the single block is "a", so the index entry copies that key.

What broken looks like

Verification — SSTable Format

V1: empty build

build from an empty MemTable produces a 36-byte file ending in SST1\0\0\0\0 with index_offset=0, index_size=4, num_blocks=0.

V2: single-entry build

add("k", Value("v")) → finish yields a file that:

• contains exactly one data block,
• has one index entry with key "k",
• round-trips: iter returns [("k", Value("v"))], get("k") returns the value, get("missing") returns None.

V3: tombstones survive

A tombstone added during build is reported as Some(Entry::Tombstone) by get and as T <hex-key> by iter.

V4: ascending-key precondition

Calling add with a key that is not strictly greater than the previous added key MUST return Unsorted and leave no partial output.

V5: block-boundary rule

With target_block_size = 64 and inputs whose encoded sizes are known, the writer flushes the running block as soon as adding the next entry would push its size strictly greater than 64 bytes. A test inserts entries crafted so that the second insert is the boundary-crossing one and asserts the resulting file has exactly two data blocks and two index entries.

V6: footer location and magic

For any file produced by finish:

• the last 32 bytes parse as a Footer,
• magic == "SST1\0\0\0\0",
• index_offset + index_size + 32 == file_size,
• num_blocks matches the count of index entries.

V7: bulk round-trip vs MemTable

Take a MemTable populated by bulk 100 + put key50 REPLACED + del key10 + put "" empty-key-value + del key99, build an SSTable from it, then verify that iter-over-SSTable returns the exact same (key, entry) sequence as iter-over-MemTable. Per-key get agrees too.

V8: floor lookup correctness

For a multi-block SSTable, get(target) returns the matching entry when present and None when the target falls between blocks, even though the index entry it lands on belongs to the preceding block.

V9: reader rejects bad magic

A file with the last 8 bytes mutated away from SST1\0\0\0\0 MUST return BadMagic on open.

V10: reader rejects out-of-range index pointer

A file whose footer claims index_offset >= file_size - 32 MUST return IndexOutOfRange on open (caught before any block read).

Broader Ideas — SSTable Format

• Restart points and prefix compression. LevelDB stores keys as (shared_prefix_len, unshared_suffix, value) and resets the prefix every N entries (a "restart point"). The block trailer lists the restart offsets so binary search inside a block is still O(log N_restarts). Halves on-disk size for sorted key sets but couples decode to encode order.
• Two-level / partitioned index. A 1 TB SSTable would have ~10 GB of index entries. Partitioning the index into "index blocks of index blocks" keeps the resident index small at the cost of one extra pread per miss. RocksDB uses this above ~2 GB SSTables.
• Per-block bloom filters. Attaching a small Bloom (db-04) to each data block lets the reader skip the entire block on a miss without decoding it. Trades index/Bloom RAM for fewer block reads.
• Block CRCs / per-block compression. Real engines write [data][type byte: compression][crc32c] per block; the writer computes the CRC over compressed bytes. Detects bit-rot at read time but adds CPU cost per block.
• Streaming writer to disk. This lab returns Vec<u8>; production writers stream blocks into an os.File and only buffer the index in RAM. With a 4 KB block target and 250 entries/block, peak RAM is ~4 KB + the growing index.
• Min/max keys per block in the index. Index entries can carry the last key too, so a query strictly between two blocks short-circuits without reading either. Costs ~2× index size.
• Splitting hot blocks. Some engines (e.g. CockroachDB) measure read frequency per block and adaptively shrink hot blocks to reduce read amplification on small lookups.
• Versioned magic. A future format change (e.g. adding bloom blocks) bumps the magic to SST2; readers can keep both code paths and choose at open time. Cheap, common practice.

Step 01 — Data Block Writer

Goal

Implement the smallest unit of an SSTable: a data block builder that accumulates entries and emits the on-disk block bytes.

Block format (recap)

[count: u32 LE]
repeat count times (keys ascending within the block):
  [klen: u32 LE][vlen: u32 LE][type: u8][key][value]

The block does not carry its own size — the index entry that points to it does.

Encoded entry size

entry_size(klen, vlen) = 9 + klen + vlen   # 4 + 4 + 1 + key + value

A block that holds N entries occupies 4 + Σ entry_size.

Flush rule

Track current_size = 4 (the block header) and the buffer separately. For each candidate entry (k, v):

sz = entry_size(len(k), len(v))
if buffer_non_empty AND current_size + sz > BLOCK_TARGET:
    flush()                # emit block, capture index entry, reset
push entry
current_size += sz

This rule allows the block to grow up to and including BLOCK_TARGET bytes but never beyond. A single oversized entry is emitted alone in its own block (block size grows past the target only when one entry already exceeds it).

Side-by-side: Rust / Go / C++

Rust

#![allow(unused)]
fn main() {
const HEADER: usize = 4;
fn entry_size(k: usize, v: usize) -> usize { 9 + k + v }

struct BlockBuilder {
    buf: Vec<u8>,
    count: u32,
    first_key: Option<Vec<u8>>,
}

impl BlockBuilder {
    fn new() -> Self {
        let mut buf = Vec::with_capacity(BLOCK_TARGET);
        buf.extend_from_slice(&0u32.to_le_bytes()); // placeholder for count
        Self { buf, count: 0, first_key: None }
    }
    fn current_size(&self) -> usize { self.buf.len() }
    fn add(&mut self, key: &[u8], ty: u8, value: &[u8]) {
        if self.count == 0 { self.first_key = Some(key.to_vec()); }
        self.buf.extend_from_slice(&(key.len() as u32).to_le_bytes());
        self.buf.extend_from_slice(&(value.len() as u32).to_le_bytes());
        self.buf.push(ty);
        self.buf.extend_from_slice(key);
        self.buf.extend_from_slice(value);
        self.count += 1;
    }
    fn finish(mut self) -> (Vec<u8>, Vec<u8>) {
        self.buf[0..4].copy_from_slice(&self.count.to_le_bytes());
        (self.buf, self.first_key.unwrap_or_default())
    }
}
}

Go

type blockBuilder struct {
    buf      []byte
    count    uint32
    firstKey []byte
}

func newBlock() *blockBuilder {
    b := &blockBuilder{buf: make([]byte, 0, blockTarget)}
    b.buf = binary.LittleEndian.AppendUint32(b.buf, 0) // placeholder
    return b
}
func (b *blockBuilder) currentSize() int { return len(b.buf) }
func (b *blockBuilder) add(key []byte, ty byte, value []byte) {
    if b.count == 0 { b.firstKey = append([]byte(nil), key...) }
    b.buf = binary.LittleEndian.AppendUint32(b.buf, uint32(len(key)))
    b.buf = binary.LittleEndian.AppendUint32(b.buf, uint32(len(value)))
    b.buf = append(b.buf, ty)
    b.buf = append(b.buf, key...)
    b.buf = append(b.buf, value...)
    b.count++
}
func (b *blockBuilder) finish() (block, firstKey []byte) {
    binary.LittleEndian.PutUint32(b.buf[0:4], b.count)
    return b.buf, b.firstKey
}

C++

struct BlockBuilder {
    std::vector<uint8_t> buf;
    uint32_t count = 0;
    std::vector<uint8_t> first_key;

    BlockBuilder() {
        buf.reserve(kBlockTarget);
        put_u32_le(buf, 0);                // placeholder
    }
    size_t current_size() const { return buf.size(); }
    void add(const uint8_t* k, size_t klen,
             uint8_t ty,
             const uint8_t* v, size_t vlen) {
        if (count == 0) first_key.assign(k, k + klen);
        put_u32_le(buf, uint32_t(klen));
        put_u32_le(buf, uint32_t(vlen));
        buf.push_back(ty);
        buf.insert(buf.end(), k, k + klen);
        buf.insert(buf.end(), v, v + vlen);
        ++count;
    }
    std::pair<std::vector<uint8_t>, std::vector<uint8_t>> finish() {
        std::memcpy(buf.data(), &count, 4); // LE on the platforms we target
        return {std::move(buf), std::move(first_key)};
    }
};

(For portability, the C++ version uses put_u32_le to patch the count header too in the real implementation; the memcpy shortcut works on little-endian hosts but the lab uses the helper.)

Self-check

• Empty finish returns (b"\x00\x00\x00\x00", b"").
• After three adds the buffer length equals 4 + Σ entry_size.
• first_key is captured on the first add and never overwritten.

Step 02 — Writer, Index, Footer

Goal

Wire the data-block builder into a full SstWriter that emits [blocks...][index][footer].

Writer state

SstWriter {
    out: Vec<u8>,            // file bytes accumulated so far
    block: BlockBuilder,     // current data block
    index: Vec<IndexEntry>,  // one entry per flushed block
    target: usize,           // BLOCK_TARGET (default 4096)
    last_key: Option<Vec<u8>>,
}

add

fn add(&mut self, key: &[u8], ty: u8, value: &[u8]) -> Result<(), Error> {
    if let Some(prev) = &self.last_key {
        if key <= prev.as_slice() { return Err(Error::Unsorted); }
    }
    if ty == 1 && !value.is_empty() { return Err(Error::BadTombstone); }
    let sz = entry_size(key.len(), value.len());
    if self.block.count > 0 && self.block.current_size() + sz > self.target {
        self.flush_block();
    }
    self.block.add(key, ty, value);
    self.last_key = Some(key.to_vec());
    Ok(())
}

flush_block

fn flush_block(&mut self) {
    let mut blk = std::mem::replace(&mut self.block, BlockBuilder::new());
    let (bytes, first_key) = blk.finish();
    let offset = self.out.len() as u64;
    let size   = bytes.len() as u64;
    self.out.extend_from_slice(&bytes);
    self.index.push(IndexEntry { key: first_key, offset, size });
}

finish

fn finish(mut self) -> Vec<u8> {
    if self.block.count > 0 { self.flush_block(); }
    let index_offset = self.out.len() as u64;
    self.out.extend_from_slice(&(self.index.len() as u32).to_le_bytes());
    for e in &self.index {
        self.out.extend_from_slice(&(e.key.len() as u32).to_le_bytes());
        self.out.extend_from_slice(&e.offset.to_le_bytes());
        self.out.extend_from_slice(&e.size.to_le_bytes());
        self.out.extend_from_slice(&e.key);
    }
    let index_size = self.out.len() as u64 - index_offset;
    let num_blocks = self.index.len() as u64;
    self.out.extend_from_slice(&index_offset.to_le_bytes());
    self.out.extend_from_slice(&index_size.to_le_bytes());
    self.out.extend_from_slice(&num_blocks.to_le_bytes());
    self.out.extend_from_slice(b"SST1\0\0\0\0");
    debug_assert_eq!(self.out.len() as u64,
                     index_offset + index_size + FOOTER_LEN as u64);
    self.out
}

Footer parse

fn parse_footer(file: &[u8]) -> Result<Footer, Error> {
    if file.len() < FOOTER_LEN { return Err(Error::Short); }
    let tail = &file[file.len() - FOOTER_LEN..];
    if &tail[24..32] != b"SST1\0\0\0\0" { return Err(Error::BadMagic); }
    Ok(Footer {
        index_offset: u64::from_le_bytes(tail[ 0.. 8].try_into().unwrap()),
        index_size:   u64::from_le_bytes(tail[ 8..16].try_into().unwrap()),
        num_blocks:   u64::from_le_bytes(tail[16..24].try_into().unwrap()),
    })
}

The reader then verifies footer.index_offset + footer.index_size + 32 == file.len() (returns IndexOutOfRange otherwise) and parses the index block.

Index block parse

Identical structure to write:

let mut p = footer.index_offset as usize;
let count = read_u32_le(&file[p..]); p += 4;
let mut idx = Vec::with_capacity(count as usize);
for _ in 0..count {
    let klen = read_u32_le(&file[p..]) as usize;            p += 4;
    let off  = read_u64_le(&file[p..]);                     p += 8;
    let sz   = read_u64_le(&file[p..]);                     p += 8;
    let key  = file[p..p+klen].to_vec();                    p += klen;
    if off + sz > footer.index_offset {                     // beyond data region
        return Err(Error::IndexOutOfRange);
    }
    idx.push(IndexEntry { key, offset: off, size: sz });
}

get with floor binary search

fn get(&self, key: &[u8]) -> Option<Entry> {
    // Floor = rightmost index entry whose first_key <= key.
    let pos = match self.index.binary_search_by(|e| e.key.as_slice().cmp(key)) {
        Ok(i)  => i,                  // exact first-key match
        Err(0) => return None,        // key precedes the smallest block
        Err(i) => i - 1,
    };
    let blk = &self.index[pos];
    let block_bytes = &self.file[blk.offset as usize
                                .. (blk.offset + blk.size) as usize];
    scan_block(block_bytes, key)
}

scan_block decodes entries in order and returns the matching one when found, None otherwise (a hit on a tombstone returns Some(Entry::Tombstone) — the engine layer decides what tombstones mean).

Self-check

• An empty writer: finish() length is exactly 36 (4-byte empty index
  • 32-byte footer).
• After one add, file length = 4 + 9 + |k| + |v| (block) + 4 + 4 + 8 + 8 + |k| (index) + 32 (footer).
• For a target of 64 and entries crafted with sizes 30, 30, 30: the first add fits (4+30=34 ≤ 64), the second triggers flush (34+30=64? — equals target, no flush; 34+30=64 ≤ 64), then the third (64+30=94 > 64) → flush; result: two data blocks.

Step 03 — CLI and Cross-Language Test

CLI surface

sstable build  IN.mt OUT.sst        # MemTable dump in → SSTable out
sstable footer FILE.sst              # prints footer values + magic_ok
sstable get    FILE.sst KEY          # value: <hex> | tombstone | absent
sstable iter   FILE.sst              # V <hex-key> <hex-value> | T <hex-key>
sstable size   FILE.sst              # file_bytes=B entries=N num_blocks=K

The hex-encoding and value: / tombstone / absent strings match db-05 so the cross-test reuses the same comparison logic.

Cross-test scenario

Identical input across all three languages:

memtable new        M.mt
memtable bulk       M.mt 100
memtable put        M.mt key50 REPLACED
memtable del        M.mt key10
memtable put        M.mt ""     empty-key-value
memtable del        M.mt key99
sstable  build      M.mt OUT.sst

Cross-test checks:

1. Byte identity. sha256 of OUT.sst matches across rust / go / c++. (Same input MemTable dump + same writer rules ⇒ same bytes.)
2. 3×3 iter matrix. Every reader can iterate every writer's output, producing identical line-by-line dumps.
3. 3×3 footer parse. sstable footer OUT.sst from every reader on every writer's output reports the same index_offset / index_size / num_blocks and magic_ok=true.
4. Spot-check get. For each language: get key50 → value: 5245504c41434544, get key10 → tombstone, get "" → value: 656d7074792d6b65792d76616c7565, get nope → absent.
5. Iter equivalence vs MemTable. sstable iter OUT.sst matches memtable iter M.mt byte-for-byte (the SSTable preserves the sorted entry stream, including tombstones).

Block-boundary check

With 100 small entries (key0..key99 → val0..val99, encoded ≈ 16 bytes each), a 4096-byte block target produces roughly 100 / (4096 / 16) ≈ 1 data blocks but with the +9 overhead per entry it lands at 1 or 2 blocks. The cross-test asserts only that num_blocks ≥ 1 and that every reader agrees on the count.

A separate sub-test forces a small block target (64 bytes) on identical input across the three languages and asserts the resulting num_blocks value matches; this is the precise boundary-rule check.

Output formats (exact strings)

The cross-test scripts diff these as plain text.

db-07: LSM Compaction

0. Why compaction at all?

The LSM write path (db-05 MemTable + db-06 SSTable) is intentionally append-only. When a key is updated, the new version is written to a fresh MemTable and later flushed to a fresh SSTable; the old version is still sitting in some older SSTable. When a key is deleted, a tombstone is written, not a removal.

Without compaction, three pathologies grow without bound:

Compaction merges N input SSTables into M output SSTables, applying newest wins semantics and (eventually) purging tombstones. It trades extra write I/O (write amplification) for bounded read and space amplification.

1. The two strategies (one sentence each)

• Leveled (LevelDB, RocksDB default): level L holds at most ~10× the bytes of level L-1. When a level is full, you pick one file and compact it against the overlapping files in L+1. Read amp ≈ #levels; space amp ≈ 1.1×.
• Tiered (Cassandra default, Pebble's "level 0"): when level L has K files, merge all of them into a single L+1 file. Read amp ≈ #levels × K; space amp can be 2–3×; write amp is much lower.

This lab implements neither policy. It implements the mechanism they both need: a correct K-way merge that respects recency ordering and tombstones. Picking the policy is a separate problem (and a configurable one).

2. The mechanism: K-way merge

Inputs: an ordered list of SSTables [A, B, C, ...], where A is the newest (most recently written) and the rest follow in age order.

Output: a single SSTable whose entries are the sorted union of all input keys, where for any key k the entry is taken from the first input that contains it. Tombstones are entries — they win against older values just like a put.

The merge is a textbook K-way merge:

1. Open all inputs and produce per-input cursors that iterate in key order.
2. Push each cursor's current key into a min-heap keyed by (key, source_index). source_index is the recency tiebreaker — smaller index = newer.
3. Pop the smallest. This is the next unique key and its winning entry.
4. Emit it (subject to the tombstone-drop rule below).
5. Advance the popped cursor. Also advance every other cursor whose current key equals the just-emitted key (they are stale duplicates).
6. Repeat until the heap is empty.

In a min-heap with K cursors and N total entries the merge is O(N log K).

3. Newest-wins semantics

The contract:

• Inputs are ordered by recency. Index 0 is newest.
• For each distinct key, the first input that contains it wins.
• The winning entry's type (Value or Tombstone) is preserved.
• All other versions of that key are discarded.

This matches what a layered reader would do on a get() query if it walked the levels top-down and short-circuited on the first hit.

4. Tombstone purging

A tombstone exists to hide an older version of a key. It is safe to drop a tombstone if and only if there is no older version anywhere that the tombstone could be hiding.

Two cases:

• Compacting the bottom level. There is nothing older. Every tombstone whose only remaining copy is in the output is safe to drop. Callers signal this with drop_tombstones=true.
• Compacting a non-bottom level. Even if no input has an older version of the key, a deeper level still might. Tombstones must be kept. Callers leave drop_tombstones=false.

This lab exposes the flag and trusts the caller. A real engine wires it from the level metadata.

5. What this lab does NOT do (and why)

• No splitting: the output is a single SSTable. Production engines cap output file size to keep per-file work bounded. The merge logic is the same; splitting is an output-side concern handled by switching SstWriter targets.
• No level metadata: there is no notion of "this output belongs to level N". That belongs to a manifest / version-edit log, which is db-09 territory.
• No deletion of obsolete inputs: the caller is responsible for unlinking the input files once the output is durable. We just return bytes.
• No checksums or atomic rename: writing-then-renaming and checksumming blocks belong in db-08+.

6. Cross-language contract

The output is a db-06 SSTable. Two implementations that compact the same inputs in the same order with the same drop_tombstones flag must produce byte-identical outputs. We verify this with sha256 across rust/go/cpp.

7. Failure modes worth recognizing

8. Hand-trace template (the smallest interesting example)

Inputs (newest first):

A: [("a",V,"1"), ("b",T)]
B: [("a",V,"0"), ("c",V,"9")]

Step-by-step heap state and emit:

Output: [("a",V,"1"), ("b",T), ("c",V,"9")] — 3 distinct keys, A's versions of a and b win, c comes from B.

db-07 references

Foundational

• O'Neil, P. et al. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996. The original. Read sections 3–4 for the merge/rolling-merge mechanism.
• Chang, F. et al. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006. Section 5.3 ("compactions") frames minor vs. major compactions on top of SSTables.

Engineering, read these

• LevelDB: https://github.com/google/leveldb/blob/main/db/version_set.cc See Compaction::IsBaseLevelForKey for the tombstone-purge rule and PickCompaction for the leveled-policy choice.
• LevelDB design notes: https://github.com/google/leveldb/blob/main/doc/impl.md
• RocksDB compaction overview: https://github.com/facebook/rocksdb/wiki/Compaction
• Pebble (CockroachDB's Go LSM) compaction notes: https://github.com/cockroachdb/pebble/blob/master/docs/range_deletions.md Pebble's range-tombstone treatment is what you graduate to after this lab.
• Universal (tiered) vs leveled, with numbers: https://github.com/facebook/rocksdb/wiki/Universal-Compaction

Curriculum companions

• mini-LSM Chapter 2.6 "Compaction Strategies": https://skyzh.github.io/mini-lsm/week2-06-task-types.html
• Designing Data-Intensive Applications, Ch. 3 — strikes the right level of abstraction for explaining write amp / read amp trade-offs.

Algorithm

• K-way merge with a min-heap: any algorithms textbook. The pattern here is identical to "merge K sorted lists" with an extra rule for duplicate keys.

db-07 Analysis

Surface area

The lab exposes one library function and one CLI:

compact(inputs: ordered list of SSTable bytes, drop_tombstones: bool) -> SSTable bytes

inputs[0] is the newest. Empty input list returns an empty SSTable (36 bytes, identical to SstWriter::new().finish() from db-06).

CLI:

compact [--drop-tombstones] OUT.sst IN1.sst IN2.sst ...

State machine of the merge

The merger holds K cursors, one per input. Each cursor is a sequence of (key, entry) pairs in sorted key order, produced by iterating the input SSTable's blocks in order.

A min-heap holds at most K entries, each (current_key, source_index). source_index is the position in inputs (smaller = newer).

State transitions:

init:    push each non-empty cursor's first (key, src) into heap
step:    pop top (key=k, src=i)
         take entry from cursor i, advance cursor i
         for every other cursor j whose current key == k: advance cursor j
         re-push any cursor that still has items (only those that advanced past k)
         emit (k, entry) unless (entry is Tombstone AND drop_tombstones)
done:    when heap is empty

The "advance every cursor whose current key == k" rule is what makes the merge deduplicating. It is the only subtle bit. Forget it and SstWriter rejects the output with Unsorted because the same key reappears.

Containers per language

• Rust: BinaryHeap<Reverse<(Vec<u8>, usize)>> — pop smallest by key, ties broken by source index (smaller = newer = wins). Cursors are IntoIter over pre-materialized Vec<(Vec<u8>, Entry)> from SstReader::entries().
• Go: container/heap with a struct slice. Same ordering. Cursors are index counters into []Entry.
• C++: std::priority_queue with custom comparator that flips to min-heap. Cursors are std::vector<...>::const_iterator pairs.

Materializing all entries up front is wasteful for huge SSTables but is fine for this lab and keeps the three implementations symmetric. A streaming reader is the next step (db-08 block-cache and iterators).

What's intentionally not optimized

• We materialize entries instead of streaming blocks. This avoids needing a block-by-block iterator API on db-06's SstReader, which would couple the two labs more tightly than the curriculum wants at this stage.
• We use a single output SSTable. Output splitting is one if-statement in the emit step (flush + start new SstWriter when size exceeds N). Doing it here would force a "list of outputs" API that doesn't matter for byte-identity.
• We do not parallelize. K-way merge is trivially serial; partitioning is a policy concern that belongs above this layer.

What could break the cross-language byte-identity

1. Tiebreaker inconsistency between heap implementations. Pin it: for two equal keys, the cursor with the smaller source index wins. All three implementations must agree on this exactly.
2. Comparing keys as language-native strings (UTF-8 ordering). All three must compare as byte slices (Vec<u8> / []byte / std::vector<uint8_t>).
3. Forgetting to advance non-winning duplicates. Output will contain repeats; SstWriter from db-06 will reject with Unsorted. Good — fail loud.
4. Different block-target sizes. We always use the db-06 default (4096) so the output is a single block for the canonical scenario.

Verification plan in one line

Build two distinct memtables (newer + older), promote each to an SSTable using db-06, run compact [newer, older] in all three languages, then assert sha256 equality and spot-check that newest-wins applied correctly.

db-07 Execution

Library API (per language, same shape)

fn compact(inputs: &[SstReader], drop_tombstones: bool) -> Vec<u8>

• inputs[0] is newest.
• Returns the bytes of a db-06 SSTable.
• Empty inputs → 36-byte empty SSTable.

CLI

compact [--drop-tombstones] OUT.sst IN1.sst IN2.sst ...

• IN1 is newest.
• Output OUT.sst is byte-identical across rust/go/cpp for the same arguments.

Algorithm (pseudocode)

function compact(inputs, drop_tombstones):
  cursors = [iter(input) for input in inputs]   # each iter yields (key, entry) in key order
  heap = empty min-heap                          # entries: (key, src)
  for i, c in enumerate(cursors):
    k = c.peek()
    if k is not None: heap.push((k, i))

  out = SstWriter()
  while heap not empty:
    (k, i_win) = heap.pop()
    entry = cursors[i_win].next()                # consume winner
    if cursors[i_win].peek() is not None:
      heap.push((cursors[i_win].peek(), i_win))

    # Drain all older duplicates of the same key
    while heap not empty and heap.peek().key == k:
      (_, j) = heap.pop()
      cursors[j].next()
      if cursors[j].peek() is not None:
        heap.push((cursors[j].peek(), j))

    if entry.is_tombstone and drop_tombstones:
      continue
    out.add(k, entry)

  return out.finish()

Heap ordering: lexicographic on key; tiebreak by source index ascending (smaller index = newer = wins on equal keys).

How to wire it (per language)

All three "peek a cursor's current key" is cursors[i].keys[idx_i] (or equivalent) — there is no I/O during peek; entries are materialized once.

db-07 Observation

The canonical scenario

We build two SSTables (call them newer.sst and older.sst) and compact them in the order [newer, older].

newer.sst — produced from this MemTable scenario

memtable new
memtable bulk 50            # key0..key49 -> val0..val49
memtable put  "key10" "NEW-10"
memtable del  "key5"

So newer.sst contains 50 distinct keys, of which key10 has value "NEW-10", key5 is a tombstone, and the other 48 are val<i>.

older.sst — produced from this MemTable scenario

memtable new
memtable bulk 100           # key0..key99 -> val0..val99
memtable put  "key50" "OLD-50"

So older.sst contains 100 distinct keys, of which key50 is "OLD-50" and the others are val<i>.

Expected merged output

For every key the table picks the first input that contains it:

Total distinct keys: 100. Tombstones: 1 (key5). Values: 99.

"What broken looks like"

With drop_tombstones=true

Same inputs, run as bottom-level compaction:

• key5 disappears entirely (newer's only entry for key5 was a tombstone).
• 99 keys total, all values.

Hex of the absolute simplest compaction

Compacting [A, B] where A = [("k", T)] and B = [("k", V, "v")]:

• drop_tombstones=false: output is an SSTable with one entry ("k", T). File size = 4 (block hdr) + 4+4+1 (entry hdr) + 1 (key) + 0 (value) + 4 (index count) + 4+8+8+1 (one index entry) + 32 (footer) = 79 bytes. This is the same as sstable build of a MemTable containing only ("k", T).
• drop_tombstones=true: output is the empty SSTable, exactly 36 bytes.

Cross-language sha256 must match for both cases.

db-07 Verification

Ten properties, three implementations each.

V1 — Empty inputs

compact([], drop=false) → exactly 36 bytes, identical to SstWriter::new().finish() from db-06. Same for drop=true.

V2 — Single input passthrough

compact([A], drop=false) reproduces A's logical contents (same entries in same order). The bytes are not necessarily identical to A (block boundaries may differ if A had unusual block-target settings), but the output's entries() matches A's entries() exactly.

V3 — Newest wins on overlap

Inputs A = [("k", V, "new")], B = [("k", V, "old")]. Output contains ("k", V, "new") only. Output entry count = 1.

V4 — Tombstones win over older values

Inputs A = [("k", T)], B = [("k", V, "v")]. With drop=false, output contains ("k", T). With drop=true, output is empty.

V5 — Disjoint keys interleave correctly

Inputs A = [("b", V, "x"), ("d", V, "x")], B = [("a", V, "y"), ("c", V, "y")]. Output: ("a", V, "y"), ("b", V, "x"), ("c", V, "y"), ("d", V, "x") — sorted, no duplicates, every entry from its sole source.

V6 — Three-way merge handles transitive dedupe

Inputs (newest → oldest):

A: [("k", V, "v1")]
B: [("k", V, "v2"), ("z", V, "Z")]
C: [("k", V, "v3"), ("a", V, "A")]

Output: [("a", V, "A"), ("k", V, "v1"), ("z", V, "Z")]. K resolves to A's. Both B and C must advance past their "k" entries even though neither wins.

V7 — Canonical scenario byte-identity

Build newer.sst and older.sst as described in observation.md. Compact in each language with drop=false. Assert sha256 equality across all three languages.

V8 — SstWriter rejects an internally broken merge

If the merger forgets to drain duplicate cursors and tries to call SstWriter::add with the same key twice, the writer returns Error::Unsorted. The test for this constructs two inputs with overlapping keys and verifies that a correct compaction succeeds (i.e., we never see that error during a valid compaction).

V9 — Output is a valid db-06 SSTable

The bytes returned by compact open cleanly via SstReader::open and get(key) returns the merged version. This is the round-trip test.

V10 — Idempotent re-compaction

compact([compact([A, B])]) is byte-identical to compact([A, B]). Compaction of an already-compacted file is a no-op modulo metadata.

Cross-test (scripts/cross_test.sh)

Goes beyond V7 to also run a 3×3 reader/writer matrix on the merged file (byte-identity already implies this, but it confirms the output is portable):

1. Build newer.sst and older.sst via db-05 → db-06 (Rust binaries; db-06 already proved byte-identity).
2. Each language runs compact OUT.sst newer.sst older.sst.
3. Assert sha256 match across the three OUT files.
4. Each language reads each OUT file with sstable iter (from db-06) and asserts the iter output equals a reference (the Rust read of its own OUT).
5. Spot-check sstable get OUT.sst key10 → value: 4e45572d3130 ("NEW-10") in all three.
6. Spot-check sstable get OUT.sst key5 → tombstone.
7. Spot-check sstable get OUT.sst key50 → value: 4f4c442d3530 ("OLD-50").

db-07 Broader Ideas

What you'd add next, in order of payoff

1. Output splitting. Add compact_to_files(inputs, drop, target_bytes) -> Vec<Vec<u8>>. Implementation: switch SstWriter when the in-flight writer exceeds target_bytes. You must finalize at a key boundary (between two emitted entries), never inside a logical key, otherwise readers that depend on per-file key ranges will see overlaps.

2. Streaming block iterator on SstReader. db-06's entries() materializes everything; the compaction loop should pull one entry at a time per cursor. This is db-08 territory (block cache + iterators).

3. Range tombstones. A "delete all keys in [lo, hi)" record. Compaction has to track a set of active range tombstones during the merge and apply them to subsequent entries. Pebble's range-deletions doc is the reference.

4. Snapshot-aware tombstone purging. "Drop tombstones at bottom" becomes "drop tombstones older than the oldest live snapshot". Compaction takes a sequence-number floor and drops anything below it that has been superseded.

5. Leveled policy. A scheduler that picks N input files to compact based on per-level byte budgets and overlap. This is where Compaction::PickFile and IsBaseLevelForKey live in LevelDB.

6. Subcompactions. Splitting one logical compaction into K parallel ones by key range. Requires that the index of each input lets you cheaply find the byte range covering a key span — partitioned index helps.

7. Compaction throttling. When compaction can't keep up, foreground writes must stall. RocksDB exposes level0_slowdown_writes_trigger and level0_stop_writes_trigger. Without this, write bursts cause unbounded read amplification.

8. Universal/tiered compaction. A different scheduler; same merge mechanism. Worth implementing once leveled is in to feel the trade-off.

9. Per-key sequence numbers. Every key gets a monotonically-increasing seqnum; compaction picks the highest-seqnum entry for each key. This makes the merge correct under concurrent writes and snapshots. Required for MVCC (db-13).

10. Compaction filter callbacks. RocksDB lets the user inspect/transform every key during compaction (garbage collection of TTL'd values, schema migration). It's just a hook in the emit step.

What this lab deliberately leaves un-clean for later

• No async I/O. The merge is CPU-bound on materialized vectors.
• No CRCs on blocks. Bad bytes in an input produce corrupt output silently.
• No fsync / atomic rename. The CLI writes the output and the script renames.
• No metrics. Production engines export bytes-read, bytes-written, files-in, files-out, duration per compaction.

These are intentional. The point of this lab is the merge, not the operational surface.

db-07 Step 1 — K-way merge core

The whole lab is one algorithm. We build it in three languages, then expose it through a tiny CLI.

Cursor

A cursor is an iterator over (key, entry) pairs from one input SSTable, in key order. The simplest representation: materialize via SstReader::entries() and index into the resulting vector.

#![allow(unused)]
fn main() {
struct Cursor {
    items: Vec<(Vec<u8>, Entry)>,
    pos: usize,
}
impl Cursor {
    fn peek(&self) -> Option<&[u8]> { self.items.get(self.pos).map(|(k,_)| k.as_slice()) }
    fn take(&mut self) -> (Vec<u8>, Entry) { let i = self.pos; self.pos += 1; std::mem::take_or_clone(&self.items[i]) }
}
}

type cursor struct {
    items []entry // entry = {Key []byte; E sstable.Entry}
    pos   int
}
func (c *cursor) peek() []byte { if c.pos >= len(c.items) { return nil }; return c.items[c.pos].Key }
func (c *cursor) take() entry  { x := c.items[c.pos]; c.pos++; return x }

struct Cursor {
    std::vector<std::pair<std::vector<uint8_t>, sstable::Entry>> items;
    std::size_t pos = 0;
    const std::vector<uint8_t>* peek() const {
        return pos < items.size() ? &items[pos].first : nullptr;
    }
};

Heap entry

(key bytes, source_index)

Min-heap ordered by key ascending, ties broken by source_index ascending (smaller index = newer = wins). All three implementations must use this exact ordering for byte-identity.

Emit loop

Pseudocode is in docs/execution.md. The crucial bit is the inner drain loop:

# After emitting (k, entry):
while heap.peek().key == k:
    (_, j) = heap.pop()
    cursors[j].take()  # discard the older duplicate
    if cursors[j].peek() is not None:
        heap.push((cursors[j].peek(), j))

That loop is the only difference between "K-way merge of disjoint inputs" and "K-way merge with newest-wins dedupe".

Why the tiebreaker direction matters

Inputs are passed newest first (index 0 newest). On a tie, the smaller index must come out of the heap first. So when you build a (key, src) tuple, the smaller src is the smaller tuple, and a min-heap pops it first. No need to invert; the natural lexicographic order on the tuple does the right thing.

If you ever flip the input convention (oldest first), invert the tiebreaker. Do not do both — pick one and document it. We picked: index 0 = newest.

Try this before reading step 2

Without looking at the implementation, on paper, trace this:

A: [("a",V,"1"), ("c",V,"3")]
B: [("a",V,"old"), ("b",V,"2")]

Write out the heap after each pop. You should get four pops and three emits.

The expected output: [("a",V,"1"), ("b",V,"2"), ("c",V,"3")].

db-07 Step 2 — Tombstone purging and the bottom-level rule

A tombstone in an SSTable says: "this key was deleted; do not return any older version of it". Tombstones cost space and slow down reads (you still have to walk past them). Eventually you want to drop them.

The rule

A tombstone for key k is safe to drop during a compaction if and only if there is no older version of k anywhere in the database that the tombstone could be hiding.

Equivalently: if this compaction is over the bottom-most level and the tombstone's input is part of it, you can drop the tombstone.

For non-bottom compactions, keep all tombstones. A deeper level still has data the tombstone is suppressing.

API

compact(inputs, drop_tombstones: bool) -> bytes

The flag is the caller's promise. We do not inspect it; we trust it. In a real engine, the scheduler sets drop_tombstones = (target_level == bottom).

Implementation: one if-statement

In the emit loop, after picking the winner (k, entry):

if entry.type == Tombstone and drop_tombstones:
    continue   # skip; do not write to output
out.add(k, entry)

That's the entire change versus the basic merge.

What's still wrong (and why it's OK for this lab)

The "drop tombstones at bottom" rule is a snapshot-unaware simplification. A correct engine keeps a tombstone alive until every read snapshot older than the tombstone's sequence number has been released. Implementing that requires per-entry sequence numbers, which we add in db-13.

For this lab, "bottom" means "the caller swears nothing older exists". That is enough to demonstrate the mechanism and to write a meaningful cross-test.

Test scenarios this enables

These are V4 in the verification table and the drop_tombstones=true arm of the cross-test.

db-07 Step 3 — CLI and cross-language byte-identity

CLI shape (all three languages emit and accept the same)

compact [--drop-tombstones] OUT.sst IN1.sst IN2.sst ...

Arguments:

• --drop-tombstones: optional first flag. If present, tombstones are dropped (use when this is the bottom-level compaction).
• OUT.sst: output file path.
• IN1.sst ...: one or more input SSTable paths. IN1 is the newest.

Exit codes:

• 0: success.
• 1: any error (open failure, malformed SSTable, write failure).
• 2: usage error.

The CLI is intentionally minimal. There is no JSON, no stats, no progress. Stats live in db-22 (performance + benchmarking).

The cross-test scenario

The script in scripts/cross_test.sh:

1. Builds feed_newer.mt (memtable scenario from observation.md, 50 keys with key10 replaced and key5 deleted).
2. Builds feed_older.mt (100 keys with key50 = "OLD-50").
3. Promotes both to SSTables using the db-06 Rust binary (sstable build feed_newer.mt newer.sst).
4. For each language, runs compact OUT.sst newer.sst older.sst.
5. Asserts sha256(rust.OUT) == sha256(go.OUT) == sha256(cpp.OUT).
6. Runs the 3×3 read matrix using db-06's sstable iter over each OUT.
7. Spot-checks sstable get OUT.sst <key> for key5, key10, key50, key99, nope.

The spot-checks use db-06's sstable CLI (not db-07's compact), which is why steps 5–7 don't need a separate db-07 reader: the output is a db-06 SSTable.

Why this proves the merge

Two SSTables with overlapping keys, where some overlaps prefer the newer version and one (key50) is unique to the older. If your merge logic gets the recency tiebreaker wrong, you read val10 instead of NEW-10. If you forget to drain duplicates, you write the same key twice and SstWriter::add throws. If you drop tombstones by mistake, key5 disappears.

If all three languages get the same sha256, the algorithm and its translation to three runtimes are pinned down.

db-08 — Block Cache and Iterators

What is it?

Two small, foundational read-path components that every LSM (and most B-tree engines) need:

1. Block cache — a bounded, in-memory map from (file_id, block_offset) to the decoded block bytes, evicting the least-recently-used entry when full. Sits between the SSTable reader and the OS page cache so that a hot index block or hot data block does not have to be decoded on every query.
2. Merging iterator — a streaming K-way merge over N pre-sorted sources (memtable, level-0 SSTables, level-1 SSTables, …) that yields each key exactly once, preferring the newest source on ties, and optionally drops tombstones. This is the engine of every LSM read: point lookups, range scans, compaction, and snapshot iteration.

Why does it matter?

In an LSM, a single user get("k") may have to consult the memtable plus 1–10 SSTables. Without a cache, every miss re-reads (and re-checksums, and re-decodes) blocks from disk; without a merging iterator, range scans cannot present a single ordered view of the live keyspace. Together these two components turn the LSM's "many small sorted runs" representation into the illusion of "one big sorted map" — and they do it without unbounded memory.

These primitives also appear far outside databases:

• OS page cache is a block cache for files.
• CPU L1/L2/L3 are hardware block caches keyed on physical address.
• sort -m and most stream-join operators are merging iterators.
• Kafka log compaction, Bigtable scans, and DynamoDB streams all do tournament-style merges across sorted inputs.

How does it work?

            ┌─────────────── BlockCache (cap = N entries) ───────────────┐
get(k)  ──► │  HashMap<(file_id, off), Node*>  +  DoublyLinkedList<Node> │
            │  hit:  splice node to front, return value                  │
            │  miss: insert at front; if full, drop the back node        │
            └────────────────────────────────────────────────────────────┘
                              │
                              ▼
            ┌─────────────── MergingIterator(sources) ───────────────────┐
            │  min-heap of (current_key, src_idx)                        │
            │  Next():                                                   │
            │    pop heap → winner                                       │
            │    advance winner src, push its next key (if any)          │
            │    while heap.top().key == winner.key:                     │
            │       pop & advance older (they are shadowed by winner)    │
            │    if drop_tombstones and winner is tombstone: continue    │
            │    yield (winner.key, winner.entry)                        │
            └────────────────────────────────────────────────────────────┘

Two invariants make this correct:

• Per-source sort. Within one source, keys are strictly ascending. The heap therefore needs only the front of each source — never the full set.
• Tie-break by source index. Source 0 is newest; on a tie, the newest entry wins and the older copies are drained without being yielded. This is how a put in the memtable shadows an old value in L1, and how a tombstone shadows a value of the same key in any older source.

Terminology

• Block — a fixed-ish-size chunk of an SSTable (typically 4 KiB) that is the unit of disk I/O and the unit of block-cache eviction.
• Cache hit / miss — was the requested key present in the cache?
• Eviction — removing an entry to make room. LRU picks the entry least-recently touched (read or written).
• MRU / LRU — most/least recently used end of the list.
• K-way merge — merging K already-sorted sequences into one sorted sequence. Optimal comparison cost is O(N log K) for N total entries.
• Tournament tree / min-heap — the data structure used to pick the next source to advance in O(log K).
• Tombstone — a marker that says "this key has been deleted"; it shadows any older value for the same key until it is dropped during compaction.
• Newest-wins — the LSM tie-break rule: source i < j means i is newer.

Mental models

• The cache is a bounded hash map with a freshness order. The hash gives you O(1) lookup, the list gives you O(1) eviction of the stalest entry.
• The merging iterator is a tournament. K runners, each in their own lane; the heap is the leaderboard; every Next() advances the current leader by one step and re-runs the comparison between the new front of that lane and the rest of the heap.
• Tombstones are entries, not absences. They occupy a slot in the stream and only disappear during a compaction that is guaranteed to have seen all older versions of the same key.

Common misconceptions

• "LRU is just a list." No — a list alone is O(N) per lookup. The hash map is what makes both operations O(1); the list only encodes the order.
• "A merging iterator deduplicates by buffering everything." No. It inspects only the front of each source. Total memory is O(K), regardless of how many entries flow through.
• "Newest-wins requires timestamps." Not in an LSM: source ordering already encodes recency (memtable > L0 > L1 > …). Timestamps are a separate concern for MVCC (db-13).
• "A block cache replaces the OS page cache." It complements it. The OS caches raw file bytes; the block cache caches decoded/decompressed blocks and shortcuts the verification step (CRC checks, decompression).
• "Tombstones can be dropped any time." Only during a compaction that includes the bottom level — otherwise an older live value could re-surface. See db-07 for the rule; db-08 lets the caller decide via a flag.

Talking points (interview-grade)

• Why bound the cache by entries vs bytes? Entry-bounded is simpler and fine when blocks are roughly uniform (e.g., RocksDB's default 4 KiB blocks). Production systems bound by bytes (block_cache_size_mb) because compressed block sizes vary widely; we use entry count here to keep the data structure the focus of the lab.
• Why a doubly-linked list and not a VecDeque? O(1) removal of an arbitrary node on hit-promotion. VecDeque only gives O(1) at the ends.
• Why heap of (key, src) and not heap of full entries? Comparator cost: keys are small and comparable; entries (which may hold large values) are not. Also lets us move the entry out of the source vector with a single std::move / mem::take, avoiding copies.
• Why does newest-wins also drain all older entries with that key? Otherwise the iterator would emit duplicates downstream, breaking the "exactly one entry per live key" contract that compaction and range scans depend on.
• What about thread safety? Our block cache is single-writer-single-reader by design. Real systems use sharded caches (RocksDB: 64 shards) so each shard has its own mutex and contention is 1/Nth.

Connections to the rest of the curriculum

• db-05 (memtable) is the newest source in every read-path merge.
• db-06 (SSTable format) produces the sorted entries the merger consumes, and the blocks the cache caches.
• db-07 (compaction) is itself a merging iterator with drop_tombstones=true whose output is fed to an SSTable writer. db-08 generalizes that machinery so the read path can use it for point lookups and scans as well.
• db-09 (LevelDB-complete) wires this into a full Get/Scan path.
• db-13 (MVCC) layers per-key snapshot filtering on top of a merging iterator like this one.

db-08 — References

Block cache / LRU

• O'Neil, O'Neil, Weikum — "The LRU-K Page Replacement Algorithm For Database Disk Buffering" (SIGMOD 1993). The canonical "LRU is not the whole story" paper; explains why LRU under-performs LRU-K on database workloads.
• LevelDB util/cache.cc — the reference shardless LRU used by LevelDB. Doubly-linked list + hash table; reads update recency on hit. Worth reading end-to-end; ~300 lines. https://github.com/google/leveldb/blob/main/util/cache.cc
• RocksDB cache/lru_cache.{h,cc} and cache/clock_cache.{h,cc} — production-grade sharded LRU plus a clock-based variant. Demonstrates the shard-by-key-hash technique. https://github.com/facebook/rocksdb/tree/main/cache
• CockroachDB Pebble internal/cache/ — a Go implementation with a modern API; useful for comparing language ergonomics. https://github.com/cockroachdb/pebble/tree/master/internal/cache
• Postgres src/backend/storage/buffer/ — the canonical relational buffer pool: clock-sweep replacement with usage counts. Different policy, same role.

Merging iterators

• Knuth, TAOCP Vol. 3 §5.4.1 — "Multiway Merging and Replacement Selection". The original analysis of K-way merge using a tournament tree and a loser tree.
• LevelDB table/merger.cc and table/iterator.h — the canonical read-path merging iterator interface, plus the heap-based merger that combines memtable + level-0 + level-N+ iterators. https://github.com/google/leveldb/blob/main/table/merger.cc
• RocksDB table/merging_iterator.{h,cc} — extended with range tombstones and pinned iterators. Shows how the interface evolves under production pressure.
• Pebble internal/manifest/level_iter.go + merging_iter.go — a Go flavor with explicit handling of range deletes.

Background reading

• Designing Data-Intensive Applications, Ch. 3 ("Storage and Retrieval"), pp. 70-89. Kleppmann's tour of LSM read amplification, bloom filters, and the role of the block cache.
• Petrov, "Database Internals", Ch. 7 ("Log-Structured Storage"). Covers caching, iterators, and tombstone semantics at the level we implement.

Lab-specific notes

• The canonical byte layout used by merge_iter is documented in src/rust/src/lib.rs on SerializeStream. It is deliberately minimal — its only job is to give us a byte-identical cross-language fingerprint for the sha256 check.
• The cross-test reuses the same newer.mt/older.mt feedstock as db-07 so the two labs can be compared side-by-side. Their sha256s will differ because db-07 emits a full SSTable (with index, footer, padding) while db-08 emits a flat entry-stream, but the underlying ordering is identical.

db-08 — Analysis

Problem statement

We need two read-path primitives that the rest of the LSM stack assumes exist:

1. A bounded in-memory cache that lets us amortize the cost of decoding SSTable blocks across many lookups, with predictable memory usage and O(1) operations.
2. A streaming K-way merging iterator that exposes N pre-sorted sources as a single sorted, deduplicated stream — newest-wins on tie — without buffering all entries in memory.

Both must be small, dependency-light, and byte-deterministic when serialized (so the cross-language cross-test can detect any divergence).

Constraints

• Determinism. Given identical inputs, the merge stream's serialized bytes must be identical across Rust, Go, and C++. This is the cross-test's only gate.
• Bounded memory. The cache must cap at a user-supplied entry count; the iterator must use O(K) working set regardless of the number of entries.
• No backtracking. The iterator is streaming: it must work on inputs that arrive lazily.
• Newest-wins is strict. Source index 0 always wins. There are no timestamps, generations, or sequence numbers — that complexity is deferred to db-13 (MVCC).

Decisions

• Cache eviction policy: LRU. Simple, predictable, well-understood. Not the best policy for all workloads (LRU-K, ARC, and CLOCK-Pro all beat it on scan-heavy workloads), but the correct teaching baseline.
• Cache capacity unit: entries. Production systems bound by bytes; we use entries to keep the data structure (rather than the accounting) the focus.
• Heap element shape: (key, source_index). Small and cheap to compare. Pulling the full entry into the heap would inflate comparator cost and force copies.
• No timestamps / sequence numbers. Newest-wins is by source index alone.
• Tombstone drop is opt-in. Callers pass drop_tombstones=true only when they have proven (via compaction rules — see db-07) that no older source could resurrect the deleted key.

Trade-offs