# Commentary: wal-kv
The study guide for [`wal_kv.py`](wal_kv.py), and the only documentation
this toy has. Read it with the source open beside you.
```
cd wal-kv
python3 demo.py # the aha (§6)
python3 test_wal_kv.py # 7 tests, including a real SIGKILL
```
Stdlib only, no dependencies, no setup. **Environment for every transcript
below:** macOS (Darwin 25.5.0, arm64), APFS, `Python 3.15.0a8 (main, Apr 14
2026, 14:20:41) [Clang 22.1.3]`.
**The files:** [`wal_kv.py`](wal_kv.py) is the toy (146 lines);
[`demo.py`](demo.py) crashes it three ways; [`test_wal_kv.py`](test_wal_kv.py)
pins the behaviour this page describes.
---
## Contents
1. [Orientation](#1-orientation)
2. [The problem this mechanism exists to solve](#2-the-problem-this-mechanism-exists-to-solve)
3. [Background you need](#3-background-you-need)
4. [The mental model](#4-the-mental-model)
5. [Reading the source](#5-reading-the-source)
6. [The demo, and what it proves](#6-the-demo-and-what-it-proves)
7. [Design decisions and roads not taken](#7-design-decisions-and-roads-not-taken)
8. [What's simplified vs. the real thing](#8-whats-simplified-vs-the-real-thing)
9. [Check yourself](#9-check-yourself)
10. [Further reading](#10-further-reading)
---
## 1. Orientation
This toy is a key-value store that survives crashes by appending every
mutation to a log *before* touching its in-memory map, and recovering by
replaying that log from byte zero. That's write-ahead logging, and it is the
durability mechanism underneath Postgres, SQLite, etcd, Kafka and every
LSM-tree storage engine.
But the toy exists to make one specific point, and it is not "the log
replays." It is this: **the experiment you would run to check that your WAL
works cannot fail.**
By the end you should be able to:
- name the three buffers a write passes through before it is safe, and say
which crash empties each one;
- explain why `kill -9` is not a durability test, and what it *does* test;
- read a record framing format and say what each field defends against;
- explain why recovery **stops** at damage rather than skipping past it, and
why the version that recovers *more* data is worse.
---
## 2. The problem this mechanism exists to solve
A store that keeps its data in memory is fast and loses everything when the
process dies. A store that writes every update straight to its on-disk
structure is durable and slow, because those updates land in scattered
places and each one costs a seek.
Write-ahead logging is the trick that gets both. Before touching the real
data structure, append a record describing what you're about to do to a
single sequential file. Appends are the cheapest thing a disk does. Once that
record is safe, the actual update can happen lazily, in memory, batched, out
of order — because if the process dies, replaying the log rebuilds it.
The log inverts what counts as the truth. The in-memory map is no longer the
database; it is a **cache of the log**, and it can be thrown away and rebuilt
at any time. Postgres puts this plainly: only the WAL file needs flushing to
commit a transaction, not every data file the transaction touched.
That's the *what*. The reason this toy exists is the *when*: "once that
record is safe" is doing enormous work in that paragraph, and almost nobody
can say precisely when it becomes true.
---
## 3. Background you need
| Concept | Where it's used here | One source |
|---|---|---|
| **Buffered I/O and the page cache** | The whole aha — `write()` returning does not mean the disk has anything | [Files are hard](https://danluu.com/file-consistency/) |
| **`fsync` and what it does not promise** | `_append`, and the macOS caveat in §8 | `man 2 fsync` |
| **Checksums for corruption detection** | The `crc32` in the record frame; §5.4 | [CRC-32](https://en.wikipedia.org/wiki/Cyclic_redundancy_check) |
| **Signals: SIGKILL vs. SIGTERM** | Why the demo can crash deterministically without cleanup running | [`signal(7)`](https://man7.org/linux/man-pages/man7/signal.7.html) |
**The two that carry the result** are the first two. If you take one idea
from this page, take the distinction between *your process's* buffer, *the
kernel's* buffer, and *the disk*. Everything else here is consequence.
---
## 4. The mental model
A `put()` does not write to disk. It starts a value on a journey through
buffers, and each one is emptied by a different disaster.
```
kv.put(k, v)
│
▼
┌───────────────┐
│ Python buffer │ f.write() stopped here
└───────────────┘ ✗ SIGKILL destroys this — it dies with the process
│
│ f.flush()
▼
┌───────────────┐
│ page cache │ the KERNEL holds it now
└───────────────┘ ✓ survives SIGKILL — killing a process
│ ✗ power cut destroys this doesn't touch the kernel
│ os.fsync()
▼
┌───────────────┐
│ the drive │ ✓ survives a power cut
└───────────────┘ ...mostly. See §8 — on macOS the drive may still be
holding it in a volatile cache of its own.
```
The single most useful thing on this page: **`kill -9` only empties the top
box.** It cannot reach the kernel's buffer, because the kernel is not the
thing that died. So a `kill -9` test tells you your process-crash story is
fine and tells you *nothing at all* about power loss — which is the failure
a WAL is fundamentally there to survive.
---
## 5. Reading the source
146 lines. Read them in this order.
### 5.1 The record frame
```python
_HEADER = struct.Struct(">II")
```
`wal_kv.py:25`
Every record is `length | crc32 | payload`. Two fields, two entirely
different jobs, and it's worth being precise about which defends against
what:
- **`length`** makes the log *parseable*. Without it there's no way to know
where one record ends and the next begins, so you couldn't even find
record two.
- **`crc32`** makes the log *trustworthy*. A crash can leave a record whose
length field is intact and whose payload is garbage. Framing alone can't
see that; the checksum can.
The payload itself is `op | keylen | key | value`, which is why the key needs
an explicit length and the value doesn't — the value is "whatever is left,"
so it costs zero bytes to delimit.
### 5.2 `_append` — the three lines that decide everything
```python
def _append(self, payload):
# Log first, mutate second. The reverse order would let a crash
# land between them and leave the map ahead of its own log.
self._f.write(_frame(payload))
if self.flush:
self._f.flush() # Python's buffer -> kernel page cache
if self.fsync:
os.fsync(self._f.fileno()) # kernel page cache -> disk
```
`wal_kv.py:84-91`
This is the toy. Three writes to three different places, and each `if` is a
policy decision about which crash you're willing to lose data to.
Note what `put` does *around* this call: it appends, and only then assigns to
`self.data`. That ordering is the "write-ahead" in the name. Flip it and the
map can hold a value the log has never heard of — I flip it in §6.4 and watch
them disagree.
### 5.3 `flush` is not optional when you asked for `fsync`
```python
self.flush = flush or fsync
```
`wal_kv.py:58`
One line, easy to read past, and it is a trap with teeth. `os.fsync` takes a
**file descriptor**. It tells the kernel to push its own buffers for that
descriptor to the drive. It knows nothing whatsoever about Python's buffer
sitting above it — bytes still in userspace have not reached the kernel, so
`fsync` cannot push what it cannot see.
Remove the `or fsync` and you get a store that calls `fsync` on every single
write and loses everything anyway. I ran it (§6.3). It loses all five
records, and the file is zero bytes.
### 5.4 `_recover` — stop at the first lie
```python
while off + _HEADER.size <= len(blob):
length, crc = _HEADER.unpack_from(blob, off)
start = off + _HEADER.size
payload = blob[start:start + length]
if len(payload) < length: # truncated mid-record
break
if zlib.crc32(payload) != crc: # framing intact, bytes rotten
break
self._apply(payload)
off = start + length
self.replayed += 1
```
`wal_kv.py:110-122`
Two guards, two different failures, and **both are `break`, not `raise` and
not `continue`.**
Not `raise`, because a ragged tail is the *normal* state of a log after a
crash — the process died mid-append, so of course the last record is half
written. Refusing to start because of it would throw away a perfectly healthy
database over the one record that was never acknowledged anyway.
Not `continue`, and this is the subtle one. Skipping a damaged record and
carrying on recovers *more* data, which sounds strictly better and isn't.
§6.4 shows the variant recovering `alpha` and `gamma` while dropping the
corrupt `beta` in the middle — a state the database **never actually was
in**. A log must replay to a *prefix* of history. `break` guarantees that;
`continue` produces a plausible-looking store assembled from surviving
fragments, which is a far worse thing to hand someone than an honest short
read.
### 5.5 The tombstone
```python
def delete(self, key):
# A delete is a record too -- a tombstone.
self._append(_encode(_DELETE, key))
self.data.pop(key, None)
```
`wal_kv.py:75-79`
Deletion has to be *written down*. The log is append-only, so the `put` that
created the key is still sitting there and replay will faithfully re-apply
it. If deleting only mutated memory, every key you ever removed would rise
from the dead on the next restart.
---
## 6. The demo, and what it proves
A child process performs 5 puts and then SIGKILLs itself:
```python
os.kill(os.getpid(), signal.SIGKILL)
```
`demo.py:35`
A real SIGKILL — no handlers, no `atexit`, no flush on the way out — but at a
fixed point, so the output is identical on every run. For each buffering
policy the demo then asks the log two questions: what survives a process
crash, and what survives a power cut.
```
$ python3 demo.py
5 puts, then the writer SIGKILLs itself mid-run.
policy signal bytes after SIGKILL after power loss
flush=off fsync=off 9 0 0 / 5 0 / 5
flush=on fsync=off 9 115 5 / 5 0 / 5
flush=on fsync=on 9 115 5 / 5 5 / 5
```
### 6.1 Where 115 bytes comes from
Never leave a number underived. Each record is `8` bytes of header
(two 4-byte big-endian ints) plus a payload of `1` op byte + `2` key-length
bytes + the key + the value. The demo writes `key00`…`key04` (5 bytes) and
`value00`…`value04` (7 bytes):
```
8 + (1 + 2 + 5 + 7) = 23 bytes per record
23 × 5 = 115 bytes
```
Row 1 shows `0` because those 115 bytes never left Python's buffer.
### 6.2 The aha: rows 2 and 3 are indistinguishable
Look at the `after SIGKILL` column. `fsync=off` recovers **5 / 5**. Not
most — all of them. Turning fsync on changes the outcome not at all: same
115 bytes, same 5/5, same everything.
So if your durability test is "kill -9 the process and check the data came
back," **you cannot fail it**, and you learn nothing. You'd conclude the
store is crash-safe having exercised only the buffer that was never at risk
from the disaster you're worried about.
Why: `f.flush()` hands the bytes to the kernel. The kernel is not the process
you killed. `SIGKILL` removes a process; the page cache belongs to the
operating system and doesn't notice. The data is sitting in RAM that outlives
your program, and the next process to open the file reads it back happily.
The `after power loss` column is where the two rows finally separate — 0/5
against 5/5, total loss against no loss. That's the entire value of `fsync`,
and it is invisible to the test everyone runs.
### 6.3 The trap: calling `fsync` and losing everything anyway
`flush or fsync` (§5.3) looks like a convenience. Remove it, so `fsync=True`
no longer implies flushing, and run the same crash:
```
=== CF2: you called fsync(). Without flush(), does it help? ===
fsync implies flush (as written): signal=9 bytes= 85 recovered=5/5
fsync alone : signal=9 bytes= 0 recovered=0/5
```
Zero bytes. Every put called `os.fsync` and every put was lost, because the
bytes were still in userspace where `fsync` cannot see them. (85 rather than
115 because this variant uses shorter keys: `8 + 1 + 2 + 3 + 3 = 17`, times
5.)
This is the failure mode worth carrying away from the toy: the call that is
supposed to guarantee durability succeeded, returned zero, and guaranteed
nothing.
### 6.4 The other two load-bearing lines
**Drop the checksum** and corruption stops being an error and becomes an
*answer*:
```
=== CF1: drop the checksum check -- is corruption silent? ===
with crc (as written): replayed=1 beta=None
without crc : replayed=2 beta=b'twX'
```
`b'twX'`. Not a crash, not an exception — a wrong value, returned confidently
as though it were real. The length field was intact so the framing parsed
fine; only the checksum knew. Silent corruption is strictly worse than a
short read, which is why the crc costs 4 bytes on every record forever.
**Skip damaged records instead of stopping**, and recovery invents a state
that never existed:
```
=== CF3: replay stops at damage vs. skips past it ===
break (as written): replayed=1 keys=['alpha']
continue : replayed=2 keys=['alpha', 'gamma']
```
The corrupt record is `beta`, in the middle. `continue` recovers *more* rows
and produces a database containing `alpha` and `gamma` but not `beta` — a
combination that was never true at any instant. `break` stops at `alpha`,
which is a real historical state.
**Flip the write-ahead ordering** so the map is updated before the log, and
make the disk fill up mid-`put`:
```
=== CF4: write-ahead ordering -- log first vs map first ===
log first (as written): in memory= None in log= None
map first : in memory= b'two' in log= None <-- map and log disagree
```
With the ordering as written, a failed append means the write simply didn't
happen — memory and log agree. Reversed, the store now serves a value from
memory that has no record behind it: reads succeed until the moment of a
restart, and then the data is gone. The word "ahead" is the whole design.
### 6.5 The boundary condition — when none of this matters
Worth naming so you can place your own system. If your process only ever
dies by `SIGKILL`, `SIGSEGV`, an uncaught exception, an OOM kill, or a
`docker stop` — anything that kills *the process on a running machine* — then
`fsync` buys you **nothing at all**, and the difference this whole toy is
about does not exist for you. Row 2 and row 3 are genuinely identical.
`fsync` starts to matter exactly when the *kernel* stops running: power loss,
a kernel panic, a yanked cable, a hypervisor dying, a cloud instance being
hard-stopped. If your deployment cannot experience those, you are paying for
insurance against a fire that cannot start. Most real deployments can.
---
## 7. Design decisions and roads not taken
### 7.1 Why the power-loss column is a model, and what it models
You cannot stage a power cut from inside a program, so
`simulate_power_loss(path, fsynced_bytes)` truncates the log to what `fsync`
had already pushed and calls that the disk's contents. Everything else in
this commentary is measured; **this one column is a simulation**, and it
would be dishonest not to say so in the same breath as the result.
What justifies it: a power cut empties the page cache and keeps what reached
the drive. With `fsync` off, exactly zero bytes ever reached the drive, so
the durable prefix is zero. The truncation isn't approximating that — it's
the definition of it.
The alternative was to drop the column and ship a toy about only the two
tiers I can crash for real. That's fully measured and much less useful: the
reader would leave knowing `kill -9` proves nothing, without ever seeing what
the thing it fails to prove actually looks like.
### 7.2 Why the process kills itself
`os.kill(os.getpid(), signal.SIGKILL)` rather than a parent killing the child
after a delay. A parent-side `sleep` then kill would crash at a
nondeterministic point — sometimes 3 records in, sometimes 5 — and the demo's
byte counts would change every run. Self-killing at a fixed point keeps the
signal completely real (SIGKILL cannot be caught, so nothing gets a chance to
flush) while making the crash reproducible.
### 7.3 Why replay is O(everything), forever
Recovery reads the log from byte zero every single time, and nothing ever
removes records. A key written a million times replays a million times. Real
systems fix this with **checkpointing**: periodically write the current state
somewhere durable, record that the log is safe up to offset N, and start
replay from there. That is genuinely the next mechanism to learn — and it's
deliberately absent, because it is a second idea and this toy is about the
first.
### 7.4 Why not `O_APPEND` and raw `os.write`?
Using a raw file descriptor would remove Python's buffer entirely and make
`flush` meaningless. Which would delete the most interesting failure in the
toy — §6.3 only exists because there is a userspace buffer to forget about.
Real systems do often use raw descriptors, and correspondingly have no
equivalent of that particular trap.
---
## 8. What's simplified vs. the real thing
- **`os.fsync` does not reach the platter on macOS.** This is not a nitpick;
it undercuts the toy's third tier on the machine it was verified on. From
`man 2 fsync` here: fsync flushes "from the host to the drive," but "the
drive itself may not physically write the data to the platters for quite
some time," and — the man page's own words — "this is not a theoretical
edge case." macOS provides `fcntl(F_FULLFSYNC)` for real durability, which
SQLite and Postgres use and this toy does not. So the ladder in §4 really
has a fourth rung, and `os.fsync` only climbs to the third.
- **No directory fsync.** Making a *file's* bytes durable does not make the
file's **existence** durable. The directory entry lives in its own metadata
that also needs syncing. A real system fsyncs the parent directory after
creating a log file, or a crash can leave you with a perfectly durable file
that nothing points at.
- **No checkpointing or log rotation** — see §7.3. The log grows without
bound and recovery time grows with it.
- **No transactions.** Each `put` is its own record; there is no way to say
"these three writes commit together or not at all." Real WALs carry
transaction ids and commit records, and replay discards records belonging
to transactions that never committed.
- **No group commit.** Every put with `fsync=True` pays a full sync. Real
systems batch concurrent commits into one sync — Postgres notes that a
single WAL flush can commit many transactions, which is most of why WAL is
fast rather than merely safe.
- **Single-threaded, single-process.** No locking on the log or the map. Two
writers would interleave partial records and produce a file neither could
recover.
- **`fsync` can fail, and the error may be unreportable.** The toy ignores
the return value. In the real world a failed writeback can mark pages clean
and discard them, so a later `fsync` returns success having lost data — the
2018 "fsyncgate" problem in Postgres. See §10.
---
## 9. Check yourself
Answer before expanding. Each answer is derivable from the source.
**Q1.** You run the store with `fsync=True` and `kill -9` it mid-write. Then
you run it with `fsync=False` and `kill -9` it the same way. What differs?
Answer
Nothing observable. Both recover every record, and the log is byte-identical
(115 bytes in the demo). That's rows 2 and 3 of §6.2, and it's the whole
point: `kill -9` exercises only Python's buffer, which `flush` already
emptied. The `fsync` call did real work — it just protected against a
disaster you didn't stage.
**Q2.** A colleague "optimises" the store by removing `self._f.flush()` and
keeping `os.fsync()`, reasoning that fsync is the stronger of the two and
therefore sufficient. How much data do they lose to a `kill -9`?
Answer
All of it. `os.fsync` operates on a file descriptor and cannot see bytes
still sitting in Python's userspace buffer, so there is nothing in the kernel
for it to push. Measured in §6.3: **0 bytes on disk, 0/5 recovered**, despite
an `fsync` call on every put. fsync isn't "stronger" than flush — they move
data between two *different* pairs of places, and skipping the first makes
the second a no-op.
**Q3.** Recovery hits a corrupt record in the middle of the log with 500 good
records after it. Stopping loses those 500. Why is stopping still right?
Answer
Because a database must be a state it actually passed through. Skipping the
bad record yields the state "everything except record 300," which was never
true at any instant — §6.4 shows exactly this, recovering `alpha` and
`gamma` while `beta` silently vanishes. Handing someone a store assembled
from surviving fragments is worse than handing them an honest short read,
because the fragments look completely fine.
Real systems avoid the dilemma rather than resolving it: checkpoints bound
how much a single corruption can cost, and replicas provide another copy of
the tail.
**Q4.** Why does `delete` write a record at all? Deleting from a dict is free.
Answer
Because the log is append-only and the original `put` is still in it. Replay
walks the whole file and would re-apply that `put`, resurrecting the key on
the next restart. The tombstone is a record whose only job is to be replayed
*after* the put and undo it — which is why order matters, and why
`test_delete_is_a_tombstone_that_survives_replay` asserts `replayed == 2`
for a single surviving absence.
**Q5.** You deploy this on a cloud VM. Ops assures you the instance is never
hard-stopped and always drains gracefully. Do you still need `fsync`?
Answer
By the argument in §6.5, if the *kernel* genuinely never stops abruptly then
`fsync` buys nothing — every crash mode left is a process crash, which the
page cache survives.
The catch is that the claim is nearly always false. Hypervisors fail, hosts
get rebooted for security patches, spot instances are reclaimed with seconds
of notice, and "graceful drain" describes intent rather than the power
supply. The honest version is that you're choosing a probability, not
avoiding a mode — and §8 adds that on macOS even `os.fsync` doesn't fully buy
you out of it.
---
## 10. Further reading
Every link below was fetched and confirmed live when this was written.
- **[Dan Luu: Files are hard](https://danluu.com/file-consistency/)** — the
best single piece on why crash-safe file I/O is harder than it looks, with
the research showing that real systems (LevelDB, git) got it wrong by
assuming ordering between syscalls. Read this one.
- **[SQLite: Atomic Commit in SQLite](https://www.sqlite.org/atomiccommit.html)**
— a production database explaining its durability protocol step by step,
including why it flushes twice and where the actual commit point is. Also
candid that drives lie about having written data.
- **[PostgreSQL: Write-Ahead Logging](https://www.postgresql.org/docs/current/wal-intro.html)**
— the canonical statement of the rule this toy implements, plus the
performance argument: only the WAL needs flushing to commit, and one flush
can commit many transactions.
- **[LWN: PostgreSQL's fsync() surprise](https://lwn.net/Articles/752063/)**
— the 2018 discovery that a failed writeback could be reported once and
then forgotten, so a later `fsync` returns success having lost your data.
The §8 caveat, as a real incident.
- **`man 2 fsync`** — on macOS, worth reading in full for the `F_FULLFSYNC`
discussion. It is unusually blunt about its own guarantees.