Compaction

Goal

Measure the garbage in a log, compact it, and see why the swap at the end is crash-safe.

The log only grows

In chapter 03 you wrote 100,000 values over 20 keys. Check it again:

uv run python -m stash stats data/garden.stash

keys      20
size      5,049,235 bytes
garbage   5,048,208 bytes (100%)
opened in 0.152 s

Five megabytes on disk for about one kilobyte of live data, and every open replays all of it.

Compact it

uv run python -m stash compact data/garden.stash
uv run python -m stash stats data/garden.stash

compacted data/garden.stash: 5,049,235 -> 1,027 bytes
keys      20
size      1,027 bytes
garbage   0 bytes (0%)
opened in 0.001 s

From 5 MB to 1 KB, and opening is 150 times faster. Tombstones are gone too: a deleted key simply has no record in the new file.

The safe swap

From lab/stash/store.py:

    def compact(self) -> tuple[int, int]:
        """Copy only the live records to a new file, then swap it in with one atomic rename."""
        before = self.size
        fresh = self.path.with_name(self.path.name + ".compacting")
        with open(fresh, "wb") as out:
            for key in self.keys():
                out.write(record.encode(key.encode(), self.get(key).encode()))
            out.flush()
            os.fsync(out.fileno())
        self.file.close()
        os.replace(fresh, self.path)  # readers see the old file or the new one, never half
        self._open()
        return before, self.size

Three steps, each one crash-safe:

1. Write a new file beside the old one. A crash here leaves the old log untouched, plus a half-written .compacting file nobody reads.
2. fsync it, so the new file is really on disk before it replaces anything.
3. Rename it over the old one. os.replace is atomic: after a crash, the name points at the old file or the new one, never a mix.

This is the same trick as the exercise in chapter 01. There it cost a full rewrite on every write; here it runs once in a while.

Check it works

• compact shrinks data/garden.stash to about 1 KB, with the same 20 keys.
• You can say what is on disk after a crash at each of the three steps.

Exercise

A crash during step 1 leaves a stale nuts.stash.compacting file. Make _open delete it if it exists. Test it by creating that file by hand, then opening the store.

More to try

• Compaction blocks writes while it runs. Bitcask avoids that by writing to a new log segment during compaction and merging only closed segments. Sketch how Stash would split its log into segments.
• Add compact_when to Stash: compact automatically when garbage is over 50% and the file is over 1 MB. Where would you check it?