Module 2: Storage Engines & Indexing: Guided Labs

Lab 1: Append-Only Key-Value Store

Implement put, get, delete, restart recovery, and compaction using an append-only data file and an in-memory key-to-offset index. Define a binary or unambiguous text record format with length bounds and integrity checking.

Evidence: format note, implementation, and tests for overwrite, tombstone, restart, corrupt checksum, and torn final record.

Lab 2: Page and B+ Tree Trace

Choose a page size and calculate approximate fanout for two key widths. Hand-trace inserts that force a leaf split and propagation into an internal node. Then implement either a small page-backed B+ tree or a faithful simulator that checks sorted keys, occupancy bounds, parent separators, and leaf links after every insert.

Evidence: trace, invariant checker, and randomized insertion test.

Lab 3: LSM Compaction Experiment

Model a memtable plus immutable sorted runs. Compare size-tiered and leveled compaction on the same write/read sequence. Measure bytes rewritten, runs consulted per read, tombstones retained, and peak disk space.

Evidence: reproducible workload, results table, and a decision for a write-heavy telemetry service.

Lab 4: Cache and Bloom-Filter Tradeoff

Place a Bloom filter in front of immutable runs. Select m and k from expected item count and target false-positive rate, then measure observed false positives. Explain why false negatives would be a correctness bug.

Exit check: results distinguish latency, read amplification, write amplification, and space amplification rather than collapsing them into “faster.”