Why every database is secretly a log

Every write you’ve ever made to a database landed in a log first. Not a table, not a B-tree: a file you can only add to. That one constraint gets you durability, ordering and replication.

PostgreSQL calls it the write-ahead log. MySQL’s InnoDB calls it the redo log. SQLite has a WAL mode. Kafka skips the pretence and calls the whole product a log. Different names, same idea: before anything clever happens, the change is appended to the end of a file and forced to disk.

The smallest durable thing

Strip a database down until it barely works. What’s left is append(record) and fsync(). If the machine dies after fsync returns, the record is safe. That promise is the whole job.

def append(f, key, value):
    rec = f"{key}\t{value}".encode()
    f.write(len(rec).to_bytes(4, "big") + rec)
    f.flush(); os.fsync(f.fileno())   # durable from here

Four lines, and each one is doing real work.

The record is turned into bytes. A disk does not store strings or dicts. It stores bytes, so you pick an encoding and stick to it.

Each record is length-prefixed: 4 bytes that say how long the record is, then the record. That is how a reader finds where one record ends and the next begins, without scanning for a separator that might also appear inside the data.

Then the bytes go to disk. Appending is the cheapest write a disk can do. There is no seeking to the middle of a file, no rewriting a page in place, no reading before writing. The head of the file never moves. Only the tail grows.

After flush(), your bytes are in the operating system’s page cache: memory. A power cut loses them. After fsync(), the OS has told the disk to persist them and waited for the answer. That wait is the real cost of durability. A consumer SSD can take anywhere from tens of microseconds to a few milliseconds per fsync, and that sets the ceiling on how many durable writes per second one log can take. It is also why real databases batch: they collect many transactions and fsync them together, a trick called group commit.

Reading it back

Writing the log is half of it. The other half is replay: reading every record from the start and rebuilding state from it. Here is replay for the format above, with one twist: the last record was cut off halfway, the way it would be if the power failed mid-write.

import io

def encode(key, value):
  rec = f"{key}={value}".encode()
  return len(rec).to_bytes(4, "big") + rec

log = io.BytesIO()
for k, v in [("a", 1), ("b", 2), ("a", 3)]:
  log.write(encode(k, v))
log.write(encode("c", 4)[:6])            # a torn write: only 6 of 7 bytes landed

def replay(f):
  state = {}
  f.seek(0)
  while True:
      head = f.read(4)
      if len(head) < 4:
          break                        # clean end, or a torn length prefix
      n = int.from_bytes(head, "big")
      body = f.read(n)
      if len(body) < n:
          print("torn tail detected, stopping")
          break
      key, value = body.decode().split("=")
      state[key] = int(value)          # later records win
  return state

print(replay(log))

The state comes back as a=3, b=2. Record a was written twice, and the later write wins, because replay applies records in the order they were appended. That ordering is free: it is just the position in the file. The torn record for c is detected because its length prefix promises 3 bytes and the file only has 2. Replay stops cleanly instead of reading garbage.

Where it breaks

The first version I shipped ran out of memory replaying 2M rows, because it read the whole file into a list. The fix is boring and correct:

• Stream records instead of loading them all at once. Replay only ever needs the current record and the state it is building. Read one record, apply it, move on.
• Length-prefix each record so a torn tail is detectable. Without the prefix, a half-written record looks like a valid one with strange content. With it, the reader knows exactly how many bytes to expect.
• Checkpoint so replay doesn’t start from byte zero forever. Every so often, write the current state to a separate file and note the log position it covers. On restart, load the checkpoint and replay only what came after. Once a checkpoint is safe, the log before it can be deleted.

Real systems add a checksum per record too, usually a CRC32. The length prefix catches a record that is too short. The checksum catches one that is the right length but has the wrong bytes.

Durability isn’t a feature you add later. It’s the order in which you do things.

Why tables come second

Once the log exists, everything else in the database is a cache of the log. The table, the B-tree index, the materialised view: each is a faster-to-read copy of what the log already says. If they are lost or corrupted, you can rebuild them by replaying.

That is what crash recovery is. On startup, PostgreSQL finds the last checkpoint and replays the write-ahead log from there, re-applying every change that might not have reached the table files. Nothing magic. It is the replay function above, with more record types.

And that is what replication is. A replica is a second machine running the same replay, on a copy of the same log, a few milliseconds behind. Ship the log bytes over the network, apply them in order, and the replica ends up in the same state. Because the log is ordered, both machines agree on what happened first. Change data capture tools read the same stream to feed warehouses and search indexes.

Seen this way, a database is two parts: a log that is the truth, and a set of structures that make the truth fast to query. The rest of this series is about the second part. But it all sits on the first.

Ship it

You’ve read enough. Build it, break it with a torn write, and watch the replay catch it.

1. Write append(path, key, value) with a length prefix and an fsync.
2. Write replay(path) that streams records and stops cleanly at a torn tail.
3. Append 3 records, then chop the last 3 bytes off the file and replay.

You have shipped it when replay returns the first two records and does not crash. Then read Rows, pages and files to see what a database builds on top of the log.