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.”

Required storage-log extension

Complete Storage log recovery and compaction contracts, prediction practice and all ST1–ST6 gates. Budget 24–36 hours for this implementation core of guided Lab 1, reusing artifacts. The disk adapter/offset index and original B+ tree, LSM, Bloom and plan work remain required.