Merge — GC without stopping writes

Merge scans only immutable files, writes a deduplicated copy with just the live record per key, then atomically retargets keydir pointers — the active file is never touched and writes never block.

Previously

RAM held one entry per live key. Disk held every record ever written. Merge is what makes the disk remember its dead — without ever asking the writer to slow down.

Scene 05

Merge — GC without stopping writes

Watch
Try it
Predict
Capture

What to watch for

Three immutable files at ~60% dead bytes — overwrites and tombstones marked dead in red. Below them, the active file is still accepting appends (the 'live writes during merge' counter ticks throughout). AFTER will hold a single merged data file with its hint sibling — only the latest record per key. Watch merge walk idle → scanning → emitting → swap → done; every keydir row flips at the swap tick, never half.

Implementation

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

Bitcask.should_merge

the trigger — operator-tunable, OR of two conditions

1def should_merge(stats, cfg, clock):
2    if not within_window(clock, cfg.merge_window):
3        return False
4    frag = stats.dead_bytes / stats.total_bytes
5    if frag >= cfg.frag_merge_trigger:
6        return True            # default 60%
7    if stats.dead_bytes >= cfg.dead_bytes_merge_trigger:
8        return True            # default 512 MB
9    return False

Bitcask.merge

scan immutables, emit deduped copy + hint, swap, delete

1def merge(files, keydir, active_file):
2    # scope: immutable files only — active file excluded
3    inputs = [f for f in files if f is not active_file]
4    out = open_new_data_file()
5    hint = open_new_hint_file()
6    new_pointers = {}
7    for f in inputs:
8        for rec in f.scan():
9            if live_record(rec, keydir):
10                pos = out.append(rec)
11                hint.append(rec.key, pos, rec.vsz)
12                new_pointers[rec.key] = (out.id, pos, rec.vsz)
13    fsync(out); fsync(hint)
14    atomic_keydir_swap(keydir, new_pointers)
15    for f in inputs: delete(f)

Bitcask.live_record

a record is live iff the keydir still points at exactly it

1def live_record(rec, keydir):
2    entry = keydir.get(rec.key)
3    if entry is None:
4        return False           # tombstoned or never existed
5    # newer write would have moved the pointer elsewhere
6    return (
7        entry.file_id == rec.file_id
8        and entry.value_pos == rec.value_pos
9    )

Bitcask.atomic_keydir_swap

every key flips at one tick — never half

1def atomic_keydir_swap(keydir, new_pointers):
2    with keydir.write_lock:        # held only for the swap
3        for key, ptr in new_pointers.items():
4            current = keydir.get(key)
5            # a concurrent put may have moved the key into the
6            # active file while we were emitting — keep that.
7            if current is None:
8                continue
9            if current.file_id == new_pointers_origin(key):
10                keydir[key] = ptr
11    # writers were never blocked from appending to active_file

Sources

Where this sits in Build a Bitcask-style KV store

Scene 05 of 9, in the Limits act — RAM is paid per key; merge gives back what's dead.. Merge scans only immutable files, writes a deduplicated copy, then atomically retargets keydir pointers. The active file is never touched.

Up next. Merge is the GC and it's safe across crashes. But if the process dies, the in-memory keydir is gone — and the GC's other side product, the hint file, is the only thing that makes restart fast.

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