Append 1,000,000 updates over only 1,000 keys to a changelog, then compact it — keep the latest record per key, drop tombstoned keys — and it shrinks to 937 records, a 1,067× reduction. A fresh consumer replaying only that compacted log rebuilds a database exactly equal to the live one: rebuilt == live: True, from 0.1% of the records.
Append 1,000,000 updates — spread over only 1,000 distinct keys, with some deletes mixed in — to an append-only changelog. Then compact it: keep only the latest record per key and drop keys whose latest record is a tombstone. The compacted log holds 937 records — its size is set by the number of distinct live keys, not the million writes. Now start a fresh consumer at offset 0, replay only the compacted log into a new dict, and assert it equals the live database. It does — rebuilt == live: True — even though compaction threw away 99.9% of the records. You kept 0.1% of the log and it is still a complete backup: no separate snapshot needed.
Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 12 — Stream Processing, §"Log compaction" (and §"State, Streams, and Immutability"):
The size of the log depends only on the current contents of the database, not the number of writes.
The book presents log compaction as the mechanism that lets a log double as a durable snapshot: throw away every record that is later overwritten, keep one record per live key, and the compacted log can rebuild the full database state. Here you watch it do exactly that — reconstruct the database bit for bit from a log that is a thousand times smaller than the write stream that produced it.
The surprise is that discarding history is lossless for state. These four ideas carry it; each line notes where it shows up.
(key, value) record; nothing is edited in place, so the log is an ordered history of writes. It shows up as the 1,000,000-record log list build_log() produces.compact() collapsing 1,000,000 records to 937.replay(), run over both the full and the compacted log.compacted size == live key count : True.state = fold(log). If only one is new, make it #3: "state is a fold over the log" is the idea that carries the whole result — once the current state is a pure function of the records, any log that yields the same fold is an equivalent backup.
random.Random(42) seeds the workload, so the log, the live database, and every count are fixed every run. Fixed workload: 1,000,000 writes over 1,000 keys, ~5% of them deletes.
There is one source of truth — the log — and everything else is derived from it.
(key, value) records (a delete is a record too: a tombstone). Nothing overwrites anything; new writes are appended.fold(log). To read the current state you replay the log: for each record, last write per key wins, a tombstone removes the key. The dict you end with is the database — it is not stored separately.The whole thing is one script, code/log_compaction_rebuild.py: it builds the log, folds it into the live database, compacts it, and folds the compacted log into a fresh dict to check equality.
cd study/ddia/ch12/code
python3 log_compaction_rebuild.pyDo not read the output yet — make each prediction first.
Predict. A million updates are appended over a key space of 1,000 keys, with about 5% of writes being deletes. After folding the entire log, how many distinct keys are live in the database — closer to 1,000,000, or 1,000?
937 live keys out of 1,000,000 records. The million writes pile up on only a thousand keys, so the state is tiny — and 63 keys ended their history on a tombstone, so they are gone entirely, leaving 937.
Predict. Compaction keeps only the latest record per key and drops tombstoned keys. How many records does the compacted log hold — and what's the compression ratio against the million-record original?
937 records — a 1,067× shrink, 99.9% discarded. The compacted log has exactly one record per live key. Its size is the key count, not the write count: the 999,063 records it dropped were all superseded by a later write to the same key (or erased by a tombstone).
Predict. A brand-new consumer starts at offset 0 and replays only the compacted log — it never sees the 999,063 discarded records. Does the dict it rebuilds equal the live database exactly, or is it lossy because history was thrown away?
rebuilt == live: True — exactly equal, from 0.1% of the records. The fresh consumer never saw the discarded writes and did not need them: every discarded record was already overwritten, so it could not have changed the final fold. Same keys, same values — no separate snapshot required.
Start from what "the current state" means for a log. The database is a fold: you replay the records left to right, and for each key the value you end with is whatever its last record said (an update sets it; a tombstone removes it). That single fact — the current value of a key is its last write — is the whole lever. It means every record for a key except its last is invisible to the final state: it was overwritten before the fold ended, so deleting it cannot change where the fold lands. Compaction is exactly the operation that deletes all those provably-redundant records. What survives is one record per key that still has a live value — nothing more, nothing less — which is why the compacted log is both a complete backup and sized by distinct keys.
Now the arithmetic. 1,000,000 writes spread over 1,000 keys is, on average, 1,000 writes per key; all but the last are superseded, so ~999 of every 1,000 records are redundant — a ~1,000× reduction. The run measures 1,067.2× (and 937, not 1,000, live keys) because ~5% of writes are deletes: tombstones both add records that compaction later removes and kill 63 keys outright, nudging the ratio up and the live-key count down. The reduction is not a lucky constant — it is writes / distinct-live-keys. Pour ten million writes onto the same thousand keys and the compacted log stays ~1,000 records while the ratio climbs to ~10,000×. That is the book's claim made mechanical: the size of the compacted log depends only on the current contents of the database, not the number of writes.
retention=compact onto this script's compact().Sources: DDIA 2e, Ch. 12, §"Log compaction", §"State, Streams, and Immutability", §"Deriving current state from the event log".