# DDIA Ch. 12: a compacted changelog rebuilds the exact database from 0.1% of the records

## Concept

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.

## Provenance

*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.

## Prerequisites

The surprise is that discarding history is *lossless for state*. These four ideas
carry it; each line notes where it shows up.

1. **Append-only log / changelog** — every update is appended as a `(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.
2. **Log compaction (keep latest per key, drop tombstones)** — a background pass
   that keeps only each key's most recent record and deletes keys whose latest
   record is a *tombstone* (a delete marker). It shows up as `compact()` collapsing
   1,000,000 records to 937.
3. **Rebuilding state by replay** — the database is not stored separately; it is
   *derived* by folding the log left-to-right, last write per key winning,
   tombstones removing. It shows up as `replay()`, run over both the full and the
   compacted log.
4. **Size ∝ distinct live keys** — because only the latest record per key
   survives, the compacted log has exactly one record per live key, so its size
   tracks the *key space*, not the write count. It shows up as `compacted size ==
   live key count : True`.

### Where to learn the prerequisites

- **Log compaction and the log-as-snapshot idea (#1–#3):** DDIA §"Log compaction"
  and §"State, Streams, and Immutability"; Kafka's own docs on log compaction
  (the "compacted topic" and its use for bootstrapping consumers).
- **State as a fold over the log (#3):** DDIA §"Deriving current state from the
  event log" — the database is a *materialized view* of the log, `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.

## Environment

Seeded, so the counts reproduce exactly:

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Python 3.15.0a8, standard library only — no Docker, no deps
- Deterministic: `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

## Mental model

There is one source of truth — the **log** — and everything else is derived from it.

- **The log is the source of truth.** An append-only sequence of `(key, value)`
  records (a delete is a record too: a *tombstone*). Nothing overwrites anything;
  new writes are appended.
- **The database is a materialized view = `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.
- **Compaction keeps only what's needed to reproduce the current view.** Since the
  current value of a key is its *last* record, every earlier record for that key
  is dead weight for reconstructing state. Compaction discards exactly those,
  leaving one record per live key. Replaying the compacted log therefore folds to
  the *same* dict — it rebuilds the exact state.

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.

## Setup

```
cd study/ddia/ch12/code
python3 log_compaction_rebuild.py
```

Do **not** read the output yet — make each prediction first.

## Steps

### Step 1 — the workload

**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?

**Observe.**

```
append-only changelog -> compact -> rebuild a fresh consumer from offset 0
    writes appended        = 1,000,000
    distinct key space     = 1,000
    deletes (tombstones)   ~ 5% of writes

full log records           = 1,000,000
live database (distinct live keys) = 937
```

**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.

### Step 2 — compact the log

**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?

**Observe.**

```
compacted log records      = 937
compression ratio          = 1,067.2x  (full / compacted)
records discarded          = 999,063  (99.9% of the log)
```

**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).

### Step 3 — rebuild a fresh consumer from the compacted log

**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?

**Observe.**

```
rebuilt database records   = 937
rebuilt == live            : True

compacted size == live key count : True
    the compacted log is a complete backup, sized by distinct keys -- not the 1,000,000 writes.
```

**`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.

## What you should see

- The full log is **1,000,000** records; folding it yields **937** live keys.
- Compaction collapses the log to **937** records — a **1,067.2×** shrink,
  **99.9%** of records discarded.
- A fresh consumer replaying only the compacted log rebuilds a database that is
  **exactly equal** to the live one: **`rebuilt == live: True`**.
- The compacted size **equals the live key count** — size is set by distinct
  keys, not by the number of writes.

## Why

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.*

**The boundary — compaction preserves state, not history.** The compacted log
can rebuild the *current* database exactly, but it has forgotten how the database
got there: the intermediate values, the overwrite order, the deletes. If you need
an **audit trail**, time-travel, or "what did this key hold last Tuesday," a
compacted log cannot answer — you kept the destination and burned the route.
(That is why an event-sourced system that needs history keeps the *raw* log and
compacts only a derived changelog.) A second boundary: compaction only helps a
key that has *stopped* changing; a key written every second keeps just its newest
version, so a workload of all-distinct, never-overwritten keys compacts to
nothing — the compacted size is the live key count, and if every key is live and
unique, that is the whole log. Compaction is for **state reconstruction**, not
event history.

### Go deeper

1. **Kafka log compaction / topic-as-table.** Kafka's compacted topics implement
   exactly this: a topic keyed by primary key, compacted in the background, is a
   durable table you can rebuild from. Read Kafka's compaction docs and map
   `retention=compact` onto this script's `compact()`.
2. **Stream–table duality.** The same log is a *stream* (the sequence of changes)
   and a *table* (the fold of those changes). Compaction is the operation that
   turns the stream's history into just the table. Try emitting the changelog of a
   dict and reconstructing the dict from it — both directions.
3. **Bootstrap a new derived store.** This is how you seed a fresh cache, search
   index, or read replica: point a new consumer at the compacted topic from offset
   0, let it replay to the current state, then switch it to tailing new records.
   Add a "then apply 10 more live writes" phase to the script and watch the
   rebuilt store stay in sync.