Build your own mini table format · Stage 7 of 7
Compaction + snapshot expiration
Many small appends and delete files make reads slow. Maintenance fixes that without breaking readers pinned to old snapshots.
Implement
table.compact() -> snapshot_id— read all live rows of the current snapshot (data minus deletes), write them into one new data file, and commit a snapshot whose manifest is that single file with no delete files. Do not physically remove the old data/delete files yet — a reader time-traveling to an earlier snapshot still needs them.table.expire(older_than_ms) -> int— drop snapshots whosetimestamp_msis< older_than_ms(always keep the current one), then garbage-collect any data or delete file that no retained snapshot references. Return the number of files physically deleted.
The invariants the tests enforce
- After
compact(), the current scan is unchanged (same rows) but the current manifest is a single file with no deletes. - A reader pinned to a pre-compaction snapshot still reads the correct old rows — because compaction only adds; it never deletes the old files.
expiremust never delete a file still referenced by a snapshot it kept. Expiring old snapshots first makes their now-unreferenced files collectible; the live snapshot's files are always retained.
Keep stages 1–6 green.
Hints
Hint 1
compact(): materialize the current live rows (scan with deletes applied), write ONE new data file with fresh stats, and commit a snapshot whose manifest is just that file and whose deletes list is empty. Don't delete old files.
Hint 2
expire(older_than_ms): keep snapshots with timestamp_ms >= older_than_ms (plus always the latest). Delete the metadata of the rest.
Hint 3
GC: collect the set of data/delete keys referenced by any RETAINED snapshot; delete only store keys not in that set. Never delete a file a retained snapshot still points to.
Run it locally
uv run de start LKH-BYO/07-compaction-expiration
uv run de test