Skip to main content

Storage log recovery and compaction contracts

This required 24–36-hour package develops the format/replay core of guided Lab 1: lessons and predictions 6–8, implementation and experiments 12–20, assessment and repair 6–8. Reuse this work in the existing append-only store rather than building a second one. The disk adapter and offset index, B+ tree invariants, LSM policy comparison, Bloom filters and query-plan work remain required. These are author estimates awaiting pilots; see the reconciled semester workload.

Prerequisite bridge​

Use Semester 05's distinction between volatile bytes, durable state and observed acknowledgment. Use Module 1's distinction between valid data and a valid operation. Here a complete record is replayable, but no separate transaction or acknowledgment marker exists. The lab cannot determine which client operations were acknowledged.

Sequence​

  1. Bounded records and recovery policy.
  2. Tombstones and compaction scope.
  3. Publishing replacement files and measuring cost.
  4. Prediction practice, runnable implementation, then all ST1–ST6 gates.

Runnable format/replay lab​

Download storage-log-contracts.zip. Python 3 standard library only. Read README, predict a trace, implement starter.py, then run python3 -B check.py starter. Use python3 -B check.py reference for calibration after attempting independently.

The original binary format has a four-byte header, bounded key/value payload and CRC32. Keys are 1–32 bytes; values are 0–256 bytes. None means delete; empty bytes is a stored value. Recover returns state, valid-prefix length and incomplete tail. Append and compact refuse a torn tail until an explicit repair decision. Full-history compaction emits sorted live keys and is byte-idempotent.

The checker covers 625 four-operation histories, all 327 byte prefixes of a representative log, malformed headers, selected corruption, bounds and a temporary-file reopen. It rejects five seeded faults. These finite tests do not prove all corruption detection, concurrent correctness, durable publication or power-loss safety. The implementation holds the whole log in memory and scans it on append; it is a teaching model, not a performance design.

Complete the original storage lab​

Reuse encode/recover to build the file adapter and key-to-offset index. Check that each index entry points to the latest complete put and no deleted key remains. Define whether an incomplete tail may be discarded, preserve a copy before repair, and rebuild the index after compaction because offsets change. Record before/after file bytes, lookups and recovery results. Write a separate replacement-file crash matrix as specified in the third lesson; do not equate the supplied file-reopen test with durable compaction.