The write-ahead log, byte by byte

A write-ahead log is the smallest interesting thing in a database: an append-only file that makes a promise. Here is the format, and the trick that lets a file with no delete operation record a delete.

Everything a database promises about durability comes down to one file that only ever gets appended to. Before a write is acknowledged, it goes in the log. If the process dies, the log is replayed on startup and the world comes back.

The format is deliberately boring:

[key_len: u32 LE][key bytes][val_len: u32 LE][value bytes]

Little-endian length prefixes, then the bytes. No framing headers, no field names, no schema. Replay reads four bytes, reads that many bytes, reads four more, reads that many. When the read comes up short, the log is done.

How do you append a delete?

This is the part that is actually interesting. The file only supports appending, so you cannot go back and remove the record you wrote earlier. A delete has to be written forward — a new record that says "whatever you saw before, that key is gone now".

So a delete writes the key exactly like a write does, then writes u32::MAX where the value length would be:

// uses u32::MAX as a tombstone marker so replay knows this was a delete
pub fn delete(&mut self, key: &str) -> io::Result<()> {
    let key_bytes = key.as_bytes();
    self.writer.write_all(&(key_bytes.len() as u32).to_le_bytes())?;
    self.writer.write_all(key_bytes)?;
    self.writer.write_all(&u32::MAX.to_le_bytes())?;
    self.sync()
}

A value length of 4,294,967,295 is not a value anyone is storing, so it is free to mean something else. Replay sees it and knows the record is a tombstone — a deliberate marker that this key was removed, as opposed to simply never having been there.

That distinction sounds academic right now, with one layer and nothing under it. It stops being academic the moment there is an older file that still has the key. Then "deleted" and "not here" are completely different answers, and a log that cannot tell them apart will happily resurrect data you deleted.

Replay

Replay is a loop over the file returning a vector of entries, each one either a put or a tombstone, in the order they were written. Order is the whole guarantee: apply them front to back and the last word on any key wins.