Compaction

The unit

The unit of compaction is one sealed log file plus its small data files. A day holds several numbered log files, and each is compacted on its own schedule.

Large data files hold one value each and are deleted individually, with no rewriting at all. That case is covered in its own section below.

Today's files are never compacted. Today is append-only and carries no day index, which keeps the writing path simple and keeps every reader's view of today consistent. See Storage for the file layout.

Garbage accounting

Each machine keeps counts for its own files:

log file    live records / total records
small .dat  live bytes   / total bytes
large .dat  live or dead (one value per file)

A record is live until one of these becomes true:

A value follows its record. A value counts as garbage exactly when the record that points at it does, and the two are removed together.

The counts live in memory and in a local cache outside the shared folder. Losing the cache costs a rebuild from the machine's own indexes and its merged view, and nothing else. The counts stay private: other machines never read them, so keeping them out of the published day index avoids rewriting index files whenever a number changes.

The node index already records where every record sits, so when a machine learns that a record has been superseded or that an entry is gone, it decrements the count for the file holding it.

Triggers

The sequence

1. Copy forward. Append the file's live records, and their values, to today's log. Each copy is byte-identical to the original: same version, same hash. Merging a copy changes nothing, so other machines see no effect.
2. Wait for today to seal. When the day ends, today's logs are complete, its day index is written, and the month, year and root indexes follow.
3. Rewrite the old file. Keep its live entry container records, compacted to the front. Rewrite or delete its small data files.
4. Update the day index for the rewritten file: the new record count, the new hash, the copied_into day, and any marks for deleted values. Then update the month, year and root indexes.

Between steps 1 and 3 both copies exist, which costs at most one day of duplicated live records from the files being compacted.

Why container records stay

An entry's container record stays in the log file it was written to, moving only within that file when the file is rewritten. Everything else moves forward to today.

Deletion depends on it. An entry's name carries its birth day, so a reader knows exactly which day index answers the question "does the creator still hold this entry?". If container records moved forward, a reader would have to hold every later day of that machine before it could trust an absence, and a missing day would make the answer wrong. See Deleting.

A log file whose live records are all entry container records shrinks to those records alone and needs no data files.

When a rewritten file takes effect

A reader that receives the rewritten file sees records disappear from it. The copies are in the day named by copied_into.

Reader rule: a rewritten file's day index entry takes effect once the reader holds a verified index for its copied_into day. Until then the reader keeps answering from its cached copy of the old contents, and reports that machine's data as still syncing.

Step 2 puts the copies in a sealed, indexed day before the rewrite exists, so the pointer always names a day that is complete on the writer's side. Arrival order then stops mattering: the rewrite cannot take effect before the copies are verifiably present.

Records move more than once over time. Day D is compacted into C1, and later C1 is compacted into C2. D's index names C1, and C1's index names C2. A rewritten day takes effect once the day it names takes effect, and the chain ends at a day that exists, because each rewrite waited for its own target to be sealed.

Large values

A large data file holds a single value, so it can be deleted on its own.

Delete a large data file once its record is:

• gone — the entry it belongs to, or an ancestor entry, is verified gone; or
• superseded — a higher (version, hash) for that node sits in a verified day index on any machine. Any reader synced with that machine already holds the newer record.

Then rewrite that day's index to mark the record's value as deleted, and update the month, year and root indexes. The logs stay untouched, so this costs one small file write and three small index writes.

The mark matters to readers. Without it, a reader whose winning record points at a missing file cannot tell a value still in transit from a value deleted as garbage, and would wait for a file that will never arrive. With the mark, the reader shows the node as superseded and waits only for the newer record.

Crash recovery

A machine writes a local marker, outside the shared folder, naming the file it is rewriting. At startup, any file still marked has its day index and the indexes above it rebuilt from the logs on disk.

Files that are not marked need no checking. Nothing else writes them.

Before compacting a file, a machine can hash its logs against the day index. That catches damage from outside the system, such as a restored backup, and it costs nothing extra because compaction reads those logs anyway.

Related