Tombstones — deletes that come back

A tombstone is a record stating absence; if merge garbage-collects the tombstone before every older segment containing the key has been merged away, restart will replay the older live record and resurrect the deleted key.

Previously

fsync chose how much of the tail to keep. Merge chose how much of the dead to reclaim. The collision between those two policies is where deleted keys come back from the dead.

Scene 07

Tombstones — deletes that come back

Watch
Try it
Predict
Capture

What to watch for

Naive merge rule. Five steps animate left to right, ~2s each: PUT, DELETE, merge, crash, restart. Step 5 is the punchline — restart rebuilds the keydir from disk and the deleted key reappears with a red WRONG badge.

Implementation

Highlighted lines are the ones running in the diagram right now.

Bitcask.delete

delete is just another append — a tombstone record. Highlight indices are 0-based.

1def delete(key):
2    tomb = Record(
3        key = key,
4        value = TOMBSTONE_MARKER,  # vsz = 0
5        tstamp = now(),
6    )
7    active_file.append(tomb)
8    keydir.pop(key, None)  # RAM only — disk still holds older PUT

Merge.naive

scan a window of immutable files, keep only what keydir points at. Highlight indices are 0-based.

1def merge(window_files, keydir):
2    out = new_data_file()
3    for f in window_files:
4        for rec in f.scan():
5            if rec.is_tombstone:
6                # key already gone from keydir → assume redundant
7                if rec.key not in keydir:
8                    continue  # drop the tombstone
9            elif keydir[rec.key] != (f.id, rec.offset):
10                continue  # stale PUT, shadowed by newer record
11            out.append(rec)
12    atomic_swap(window_files, out)

Merge.tombstone2

riak_kv #925 — re-append the tombstone into the oldest file still mentioning the key. Highlight indices are 0-based.

1def merge(window_files, keydir, all_files):
2    out = new_data_file()
3    for f in window_files:
4        for rec in f.scan():
5            if rec.is_tombstone:
6                older = oldest_file_with(rec.key, all_files)
7                if older and older not in window_files:
8                    older.append(rec)  # carry tombstone backwards
9                    continue
10                # safe to drop: no older file mentions this key
11                continue
12            elif keydir[rec.key] != (f.id, rec.offset):
13                continue
14            out.append(rec)
15    atomic_swap(window_files, out)

Bitcask.startup_replay

rebuild the keydir by scanning every immutable file in tstamp order. Highlight indices are 0-based.

1def open(dir):
2    keydir = {}
3    for f in sorted(dir.data_files(), key=lambda f: f.tstamp):
4        for rec in f.scan():
5            if rec.is_tombstone:
6                keydir.pop(rec.key, None)
7            else:
8                keydir[rec.key] = (f.id, rec.offset, rec.tstamp)
9    return keydir  # whichever record wins by tstamp wins on disk

Sources

Where this sits in Build a Bitcask-style KV store

Scene 07 of 9, in the Sharp edges act — Tombstone resurrection and the design ceiling.. If merge GCs a tombstone before every older segment containing the key has been merged away, restart resurrects the deleted key. The riak_kv #925 fix.

Up next. Tombstones must outlive every older segment that mentions the key — the rule is nontrivial because every log-structured store ships some version of this trap. Now zoom all the way out and design.

All 9 scenes in Build a Bitcask-style KV store · Every curriculum

Designs that use this

Built with Arqly

Every scene in Build a Bitcask-style KV store builds on the one before it.All 9 Build a Bitcask-style KV store scenes