Storage & Durability

A delete must remain a delete after a crash, a read, and compaction. Keeping the newest value is only half the problem: keeping enough evidence that an older value was deleted is the other half.

You should already be comfortable with maps, sorted arrays, and binary search. By the end, you should be able to replay a persisted history, trace a lookup, separate logical deletion from physical reclamation, and justify why compaction cannot expose a shadowed value.

Persisted history and crash recovery

A simplified write path is: append a WAL record, make the required log prefix durable, apply it to the memtable, and acknowledge the write. A successful buffered append alone does not establish crash durability. Later, a flush writes an immutable SSTable; compaction replaces several tables with merged tables. Recovery also needs durable metadata identifying which tables are installed. The exercises model records and entries, not filesystem synchronization or atomic installation of files.

Replay complete persisted records in append order:

Record	Visible state after replay
set a=1	{a:1}
set b=2	{a:1,b:2}
delete a	{b:2}
set a=3	{a:3,b:2}

A crash after persisting record 3 but before applying it in memory still recovers {b:2}. Record 4 is recovered only if it belongs to the durable prefix. An unacknowledged operation can appear after recovery if it was already persisted. ReplayWAL receives that complete prefix; torn records and transaction commits are outside its contract. Sort final keys to make its output deterministic.

A tombstone is a stored fact, not an expiring delete

SSTables are immutable. Deleting k cannot simply remove its newest in-memory value, because an older table may still hold k=old. Write a tombstone instead. A read selects the winning version across all sources, then returns absent when that winner is a tombstone.

gcBefore is a reclamation threshold. It never tells a read to ignore a stored tombstone. Age alone cannot prove that no older copy remains. LevelDB retains deletion markers to hide older values and drops markers only when overlap with older levels permits it. LevelDB implementation notes.

A distributed store must also account for replicas that missed the delete: removing all evidence too early can let an old replica reintroduce the value. This module assumes that an externally established GC horizon accounts for those copies; computing that horizon is outside the exercises. Apache Cassandra tombstone documentation.

Trace the read path before implementing it

LSMGet and MultiWayCompaction share one rule: greatest timestamp wins; on a tie, the earlier source wins. Read sources are memory followed by tables in input order. Within memory, the first equal-timestamp occurrence wins. Each table has at most one entry per key. Table creation order need not match every entry's timestamp, so a read must compare candidates from every possible table.

Query k, with gcBefore=10:

Location	Entries or metadata	Decision
memtable	k@4=old, x@11=x, k@8=delete	Scan all entries; k@8 wins
first SSTable	k@6=stored	Candidate is older than the current winner
second SSTable	k@1=ancient	Candidate is older; keep the tombstone winner

The result is absent even though 8 < 10. The marker still exists and still covers those older values. Changing only the threshold cannot change a read. If a later memtable write k@12=new is added, that write wins: recreating a key with a newer write is legitimate, unlike exposing its pre-delete value.

With no matching memtable entry, a Bloom-negative table can be skipped. A Bloom-positive table only might contain the key; binary search must confirm an exact match. For example, a positive table containing [a,c] does not answer query b, so continue. In valid inputs, a negative flag guarantees absence for this query. The flag is supplied; building a Bloom filter is not required.

Compaction: choose the winner before reclaiming anything

The first merge exercise, CompactRuns, is a complete two-run materialization: there are no other versions, replicas, or snapshots to preserve. Newer-run entries override older-run entries and deleted keys are omitted. This makes its value-only output safe under that narrow assumption. It is not a routine for compacting an arbitrary pair while leaving overlapping older tables outside.

MultiWayCompaction returns a stored run, which may contain tombstones. For each key, rank versions by timestamp descending, then run index ascending. This is the same priority as LSMGet across its tables. All runs are sorted by key, with at most one entry per key per run.

The exercises serve current reads only: no historical snapshot requires any losing version. The caller guarantees full coverage of older local versions for these keys and that stale replicas cannot reintroduce values shadowed by markers below gcBefore. The cutoff certifies that external safety condition; time alone is not evidence of it. Under those assumptions:

1. Select exactly one winner, including tombstones in the ranking.
2. A value winner is emitted unchanged.
3. A tombstone winner at or above gcBefore is retained unchanged.
4. A tombstone winner below gcBefore is omitted together with all its older versions. Never fall back to a losing value.

Worked compaction trace

Inputs, newest run first:

run0: k@7=delete, x@5=v5
run1: k@6=v6,     x@4=v4
run2: k@2=v2

Cutoff	Winning versions	Stored output	Visible values
gcBefore=5	k@7=delete, x@5=v5	k@7=delete, x@5=v5	x=v5
gcBefore=7	same	same; equality retains the marker	x=v5
gcBefore=8	same	x@5=v5; all versions of k removed	x=v5

To integrate the components, query these runs as SSTables with an empty memtable, compact them, then query the single output table. k must remain absent and x must remain v5 at every cutoff. Repeat with a later table holding a greater timestamp: both read and compaction must choose it. A reader that stops at the first match would fail that test.

Physical storage changes, but the visible answer does not. If another older run containing k@1 were outside this compaction, the full-coverage assumption would fail; keep the marker instead. A production API needs that coverage information rather than inferring it from a clock.

A map holding each key's current winner uses O(N) scanning, then sorting K keys costs O(K log K), with O(K) extra storage. Grouping and sorting all candidates is also acceptable, but sorting must never discard tombstones before selecting the winner.

Predict, explain, then implement

1. A table's winning delete is at timestamp 9 and the cutoff becomes 100. Can a read return an older value without any write or compaction?
2. A compaction winner is z@9=delete, cutoff 10, with all older versions and required GC guarantees covered. What is emitted for z?
3. At timestamp 12, run 0 has a value and run 1 a tombstone. Which wins? What if their positions are swapped?
4. What information is missing if someone proposes dropping a marker simply because it is a week old?

Check your reasoning

1. No. Reads honor stored tombstones regardless of cutoff.
2. Nothing for z; none of its older values survives either.
3. The run-0 entry wins each tie. A newer equal-timestamp tombstone deletes; a newer equal-timestamp value recreates the key under this exercise's tie rule.
4. Whether overlapping older versions remain, historical snapshots are served, or replicas can return stale data. Elapsed time alone supplies none of these.

Implement the four exercises in module order, then use the checkpoint to test new crash and version histories. If a question about reclamation is missed, retrace both the stored output and the visible value columns above.