Storage & Durability

Persist a history, recover its state, and preserve deletes through compaction.

1 / 8

Crash boundary

  • Durable WAL prefix precedes acknowledgement.
  • Append to a buffer is not the same as durable persistence.
  • Replay set a=1, delete a: absent, even if memory never applied the delete.
  • Exercises assume complete records; no torn-record or file-install protocol.
2 / 8

Delete evidence

  • Old table: k@6=value.
  • Memtable: k@8=delete.
  • Read: absent for cutoff 5, 8, or 100.
  • A GC threshold cannot make an existing marker stop hiding an older value.
3 / 8

Read order

  • Compare matches from memory and every possible SSTable.
  • Greatest timestamp wins; ties prefer memory, then earlier tables.
  • Negative Bloom result skips a table; positive requires exact key lookup.
  • Resolve the final winner once; tombstones mean absence at any cutoff.
4 / 8

Stored output versus visible values

For k@7=delete over k@6=value:

Cutoff Stored compaction output Visible key
5 k@7=delete absent
7 k@7=delete absent
8 none absent

GC drops the winning old marker and its shadowed versions.

5 / 8

Required GC assumptions

  • All older local versions for the compacted keys are included.
  • Only current reads are modeled; no historical snapshot needs a losing version.
  • The supplied horizon accounts for external stale copies.
  • Without those guarantees, keep the marker.
6 / 8

Distinguish exercise contracts

  • CompactRuns: complete two-run visible materialization; omit deletes.
  • LSMGet: timestamp-first lookup; tombstones participate in ranking.
  • MultiWayCompaction: timestamp-first winner, run order breaks ties.
  • Multi-way output retains markers at or above the GC horizon.
  • With empty memory and full coverage, reads agree before/after compaction.
7 / 8

Check yourself

A winning marker is at 15; cutoff is 16. What is emitted under full coverage? What changes if an older overlapping run is excluded?

Explain both before opening the lesson's model answers or taking the checkpoint.

8 / 8
←/→ or click edges to navigate · ? help · N notes · F fullscreen