Commentary: wal-kv

Write-ahead logging, and the discovery that the experiment you would run to prove your WAL is durable cannot fail — it exercises the one buffer that was never at risk.

cd wal-kv
python3 demo.py           # the aha (§6)
python3 test_wal_kv.py    # 7 tests, including a real SIGKILL

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.

3. Background you need

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.

5. Reading the source

146 lines. Read them in this order.

5.1 The record frame

_HEADER = struct.Struct(">II")

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

    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

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

        self.flush = flush or fsync

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

        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

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

    def delete(self, key):
        # A delete is a record too -- a tombstone. Without one, replaying
        # the log would faithfully resurrect every key you ever removed.
        self._append(_encode(_DELETE, key))
        self.data.pop(key, None)

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:

    os.kill(os.getpid(), signal.SIGKILL)

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

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):

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:

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

6.4 The other two load-bearing lines

Drop the checksum and corruption stops being an error and becomes an answer:

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:

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:

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

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.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Dan Luu: Files are hard — 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 — 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 — 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 — 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.