Write-Ahead Log, fsync & Group Commit

Part 0. Start here

The problem: 100,000 acknowledged writes a second

Our storage node is the one the LSM-Trees & Compaction loop primitive builds (we call that page "the LSM page" below). It takes 100,000 small writes a second, about 100 bytes each, on an EBS gp3 volume (AWS's general-purpose SSD block volume, attached to the instance over the network). The key-value store loop promises that "OK" means the write survives a crash. So before we reply, each write's log record must be synced: forced out of memory onto the disk itself.

How long does one sync take? AWS describes gp3 latency only as "single-digit millisecond". We assume about 1 ms per sync of the log. That is an assumption, and real values can be higher; Part 2 shows how to measure yours.

The big picture

A write-ahead log (WAL) is an append-only file that records every change before the change is applied anywhere else. Here is the whole write path this page takes apart:

Synthesizing vector architecture diagram...

What you'll be able to do after this page

1. Say exactly what an "OK" promises, and against which failure (Part 1).
2. Explain what fsync and its relatives guarantee, and what a sync costs (Part 2).
3. Handle a failed fsync correctly (Part 3).
4. Write a log record's format and the append procedure (Part 4).
5. Size group commit: batch size, syncs per second, the wait (Part 5).
6. Choose a durability mode for a kind of data (Part 6).
7. Recover a log after a power loss that tore a write (Part 7).
8. Decide when a log segment may be deleted (Part 8).
9. Explain the WAL in a B-tree engine: PostgreSQL, InnoDB, SQLite (Part 9).
10. Say what replication adds to durability, and trace one write through every layer (Part 10).
11. Map all of it onto AWS (Part 11).

You may have arrived from step 1.1 of the key-value store loop ("WAL, fsync, group commit"), step 1.1 of the message queue loop (the broker's append-only log) or step 1.4 of the stock exchange matching engine loop (journal every input before releasing it). All three rest on this page.

Part 1. What "acknowledged" has to mean

"OK" is a promise, and a promise needs terms: survive what? Before any mechanism, we pin down the rule every engine follows and the failures it has to survive.

The WAL rule

The rule has two halves:

1. Log the change before applying it. The record goes into the log before the MemTable (the LSM tree's in-memory table of recent writes), the page or anything else changes.
2. Make the log durable before acknowledging. "Durable" means the record survives the failures the promise covers.

The section Writes, step by step of the LSM-Trees & Compaction loop primitive already walks one write through this order: WAL (durable), then MemTable, then visible, then OK. This page is about the word "durable": what it costs and what it really guarantees.

Four ways to fail

A write that survives one class may not survive the next. An "OK" is only meaningful when we say which class it covers.

The durability chain

A record passes through several places on its way to safety. Each one survives a different set of failures:

Synthesizing vector architecture diagram...

The tiny store, now watching the log

The tiny store is a small key-value store that we follow through the whole page. It takes 24 writes, puts and deletes on keys such as user:1 and order:9, which is few enough to show every byte and every sync. Its MemTable holds 4 writes; when it is full, the MemTable is flushed to a sorted file on disk (numbered F1, F2 and so on, such as F11 for writes 17 to 20), and a new log segment starts. The LSM page follows the same store as its tree grows; this page watches its log. The settings:

The same 24 writes as the LSM page; Part 5 gives each an arrival time.

Part 2. What fsync really guarantees

Everyone says "we fsync the log". But there are several calls, each with a different promise, and a cache inside the drive that can break all of them without reporting an error. This Part shows what each call really guarantees, and what a sync costs.

The calls

O_DIRECT is not durability. It skips the kernel's cache, but the drive's own cache can still hold the bytes, and the file's metadata may not be written. An engine using direct I/O still needs fdatasync (or O_DSYNC). PostgreSQL uses fdatasync for its WAL by default on Linux; RocksDB uses fdatasync where it is available.

The device's own cache

A drive with a volatile write cache can report a write as done while the bytes are only in its own RAM. So a sync has two jobs: get the pages to the device, then make the device put them on stable media.

Synthesizing vector architecture diagram...

A cloud volume adds a network: on EBS, a sync becomes a round trip from the instance to the volume, which AWS replicates within its Availability Zone. AWS does not publish how EBS handles flushes internally, so we claim nothing more than its latency figures.

Creating and growing the log file

A sync of the file is not the whole story:

• A new file's name lives in its directory. fsync on the file "does not necessarily ensure that the entry in the directory containing the file has also reached disk" (fsync(2)). So after creating a segment (or renaming one), the engine syncs the directory too. Otherwise a power loss can leave a perfectly synced file that no directory lists.
• A growing file changes its size. Each sync of an append that extends the file must also write the new size (metadata). So engines give the log its space up front: PostgreSQL zero-fills each new segment and recycles old ones; RocksDB can recycle log files. Reserving space with fallocate alone is usually not enough: on common Linux file systems the reserved space starts as unwritten extents, and the first write into each one still has to update file-system metadata. RocksDB's documentation gives the same reason for recycling log files: then "fdatasync does not need to update the inode after each write".
• The same is true of the LSM tree's flushed files; the LSM page's section The safe order syncs "the file and its directory" for the same reason.

Trace: the first write

When the tiny store opens, it creates wal-1, fills it with zeros, syncs it and syncs its directory. Then write 1 arrives at 0.0 ms. Only the steps that the LSM page's write trace (its section A write, traced down to the device) does not show are drawn here:

Synthesizing vector architecture diagram...

What a sync costs

One log syncs one batch at a time, and a sync takes L. So:

The LSM page counted the log as sequential bytes; with a sync per batch, each sync is also one I/O against the IOPS budget. EBS counts an I/O of up to 256 KiB on SSD volumes as one, and "attempts to merge" small sequential I/Os into one, so one sync of a batch of up to 256 KiB costs about one I/O.

Measure, don't assume. Run a test with a sync after every write on the actual volume and instance type, and read the engine's own sync-latency metric in production. Three literal command lines:

bashCopy
fio --name=walsync --filename=/data/fio.test --size=256m --rw=write --bs=4k --ioengine=sync --fdatasync=1
pg_test_fsync -f /data/pg_test_fsync.out
cat /sys/block/nvme1n1/queue/write_cache

fio with --fdatasync=1 syncs after every write and reports the latency distribution; pg_test_fsync times each sync method PostgreSQL can use; the last line shows whether the kernel sees a volatile cache on that device (write back) or not (write through).

Go deeper: layers that ignore flushes. Every guarantee above assumes each layer honours the flush: the file system passes it on, the virtualization layer passes it on, the drive obeys it. A layer that acknowledges a flush without doing it (a misconfigured hypervisor, a RAID card with a failed battery still in write-back mode, a consumer drive that reports a flush as done while the data is still in its volatile cache) breaks every promise above it without any error, and nothing shows until a power loss. Treat it as a risk to test for: pull the power (or the virtual equivalent) under load on the exact stack you run, then check that every acknowledged write is there.

Part 3. When fsync fails

A sync can return an error: an I/O error (EIO) from a failing device or a lost network volume, or ENOSPC when the disk is full. The natural reaction, "try again", is exactly the wrong one. This Part shows why, with two branches of the tiny store.

What a failed sync means

When the kernel fails to write dirty pages back, Linux may mark those pages clean anyway and report the error once, to the next sync that asks. The bytes may never have reached the disk, but the kernel no longer considers them waiting to be written. So:

• the failed sync means the data may already be gone, and
• a retried sync finds nothing dirty and returns success.

This behaviour hit PostgreSQL in 2018 (the incident is often called "fsyncgate"). PostgreSQL's fix was to stop retrying: by default it now raises a PANIC on a failed data sync (data_sync_retry = off), crashes and recovers from its WAL. It was not alone: a 2020 USENIX study of five widely used applications (PostgreSQL, LMDB, LevelDB, SQLite and Redis) found that none of their failure-handling strategies was sufficient, and that a failed fsync could still cause data loss or corruption.

Trace: the log's sync fails (branch E1)

Rewind to batch B11 (writes 18, 19 and 20, Part 5). Their records are in wal-5's page cache, and the fdatasync of wal-5 returns EIO. The reference implementation's kernel marks the pages clean without writing them.

Why "before F11": on the wrong path, the MemTable still holds 18 to 20, so if the flush writing F11 completes first, their data reaches disk that way. So after the retry, the outcome depends on timing: if power fails before F11 is written, three acknowledged writes are lost; if F11 is written first, nothing is lost. On the right path, no timing loses an acknowledged write.

Trace: the flush's sync fails (branch E2)

This is the classic case. After write 20, the flush writes F11 and calls fsync on it. If the fsync succeeded, the next steps would record F11 in the manifest (the file in which the LSM tree records which data files are live) as edit 9, and then delete wal-5. Here the fsync fails:

Synthesizing vector architecture diagram...

The rule

1. A failed sync is fatal. Never retry it and carry on.
2. Fail every write waiting on that sync. None of them was acknowledged.
3. Stop taking writes, restart, and recover from what is on disk.
4. A client that got an error does not know the outcome. The bytes may or may not be on the disk, and after recovery the write may or may not exist. So an error means "unknown", not "failed", and the client's retry must be idempotent: safe to apply twice (the Idempotency & Effectively-Once Processing loop primitive covers how).

Go deeper: the page cache can still hold what the disk lacks. After a write-back error the kernel marks the pages clean, but it may keep their contents in memory. A process that restarts without a reboot and reads the log through the page cache can then see records the disk does not have: in branch E1, the reference implementation's restarted process reads records 17 to 20 back from the cache, although only 17 is on the disk. It would replay them as if they were durable, and the next power loss would take them away. The 2020 USENIX study found exactly this on ext4 and XFS: after a failed fsync the newest data stays in the page cache, so applications "seemingly work correctly" until the pages are evicted or the machine restarts. Reading the log with direct I/O, or recovering after a reboot, prevents the engine from replaying records that exist only in memory.

Part 4. The log record and the append

Recovery reads the log back after a crash, possibly with half a record at the end. So every record has to describe itself: how long it is, and whether its bytes are the ones that were written.

What a record holds

The header layout is LevelDB's and RocksDB's. The payload layout is the tiny store's own choice (real engines use variable-length integers and put a whole batch in one payload).

That last point matters: LevelDB and RocksDB write a whole commit group as one record. The leader of a group commit (Part 5) merges its group's write batches and writes them as a single record (LevelDB's BuildBatchGroup, RocksDB's MergeBatch), then syncs once. The tiny store writes one record per write, so a torn write shows up record by record; in those engines, a torn group is lost or kept as a unit.

The sequence number has two forms in real engines: RocksDB counts entries (a batch carries the number of its first entry, and the entries in it follow on), while PostgreSQL and InnoDB number log positions by byte offset in the log. Either way, it only goes up, so it orders every change.

Trace: wal-1after write 4

The reference implementation's bytes for the first segment (seq as 8 bytes little-endian, PUT = 1, DEL = 0, FULL = 1; checksums shown unmasked):

Each record starts where the previous one ends: 0 + 29 = 29, 29 + 27 = 56, 56 + 29 = 85, and wal-1 holds 85 + 29 = 114 bytes. The header is 7 bytes on every record, so on 100-byte writes the log is about 7% larger than the data.

The append

pseudocodeCopy
APPEND(op, key, value)                              -- run by every client write
    1. seq = next sequence number
    2. payload = (seq, op, key, value)
       record  = checksum(type + payload), length, type, payload
    3. join the group-commit queue with record
       wait until it is durable                     -- Part 5
       if the sync failed:
           return an error (outcome unknown)        -- Part 3
    4. apply: insert into the MemTable (or change the page)
    5. make seq visible to readers
    6. acknowledge the client

APPEND is the path every client write takes, and its job is to make the write durable in the log before anyone is told it succeeded. Its inputs come from the client: op is PUT or DEL, key is the key being written (for example user:1), and value is the new value (for example alice), empty for a delete. Step 1 takes seq, the next sequence number, which only goes up, orders every change and becomes the entry's version. Step 2 builds payload from seq, op, key and value, and wraps it in record: a 4-byte checksum (CRC32C of the type byte and the payload), a 2-byte length and a 1-byte type (FULL for a whole record), as the "What a record holds" table lists. Step 3 hands record to group commit and waits until a sync has made it durable; if the sync failed, APPEND returns an error whose meaning is "outcome unknown", because the record may or may not be on the disk. Only after a successful sync does it change the in-memory state (step 4, the MemTable or the page), make seq visible to readers (step 5), and return the acknowledgement to the client (step 6).

The order of steps 3 and 6 is the whole promise. Compare the right order with the one that produces the "acknowledged but lost" bug:

Go deeper: blocks, fragments and recycled files. LevelDB and RocksDB split the log into 32 KB blocks. A record never starts in a block's last 6 bytes (too little room for a 7-byte header), so those bytes are filled with zeros. A record too long for the rest of a block is cut into pieces typed FIRST, MIDDLE and LAST, each with its own header and checksum, and the reader glues them back together. Blocks let a reader resynchronise at the next 32 KB boundary after damage. RocksDB's recyclable record format adds a 4-byte log number to every header, so that the old records still sitting in a reused file are not mistaken for new ones (Part 7).

Part 5. Group commit

One sync per write caps a log at 1 ÷ L writes a second, however fast the rest of the engine is. Group commit removes that cap without weakening the promise. This Part is the algorithm, the 24-write trace and the arithmetic.

One sync, many writers

A sync of the log file makes every byte written to the file before it durable. So if three writers have each written a record, one sync covers all three. The only question is how to gather them. The naive answer is a timer ("a background thread syncs every millisecond"); real engines such as LevelDB, RocksDB and PostgreSQL do something simpler with no timer at all. PostgreSQL's source describes it: a backend waiting for the WAL write lock rechecks "if the backend that held the lock did it for us already".

The algorithm

pseudocodeCopy
GROUP_COMMIT_WRITE(record)
    1. lock the queue
       append record
    2. while a sync is running and record is not durable:
           wait
    3. if record is durable:                        -- a leader carried it
           unlock
           return OK
    4. become the leader:
           batch = the whole queue
           empty the queue
           unlock
    5. one write of the whole batch to the log file
    6. one fdatasync of the log file
    7. lock
       mark every record in batch durable (or failed)
       wake every waiter
       -- a waiter whose record is still queued becomes the next leader
    8. unlock
       return OK (or the error)

GROUP_COMMIT_WRITE lets many writers share one fdatasync, so the log is no longer limited to one write per sync latency. Its input record is the record that APPEND built. The queue is shared by all writers and holds the records that are written but not yet part of a sync; the lock protects it. A writer first adds its record to the queue (step 1), then waits while another writer's sync is running (step 2). If that sync already covered its record, the writer simply returns OK (step 3). Otherwise it becomes the leader: it takes every queued record as batch, empties the queue (step 4), writes the whole batch to the log file in one write (step 5) and runs one fdatasync (step 6), which takes the sync latency L, 1.0 ms in the trace below. It then marks every record in batch durable, or failed if the sync failed, and wakes the waiters (step 7); a waiter whose record arrived too late for this batch becomes the next leader. The function returns OK to each writer in the batch, or the sync's error, and the change it makes is that every record in the batch is on stable media.

Batches form by themselves: the next batch is whoever queued during the last sync. At low load a writer finds nothing running and leads a batch of one, with no added wait. At high load the queue fills while each sync runs, and batches grow. Tie rule (the tiny store's choice, needed because its times are exact): a write that arrives at the very instant a sync completes joins the next batch.

Batch B4 of the tiny store, as the reference implementation ran it:

Synthesizing vector architecture diagram...

Trace: 24 writes, 14 syncs

The same 24 writes as the LSM page, now with the time each reaches the engine. Sync latency L = 1.0 ms. Every result below comes from the reference implementation:

14 syncs for 24 writes. The average wait is 33.2 ÷ 24 ≈ 1.4 ms, the worst 1.9 ms (write 4), the best 1.0 ms: always between L and 2L. No batch crosses a segment boundary (B1 to B3 are all in wal-1, and so on); a new segment starts only between batches.

The same arrivals with one sync per write: 24 writes arrive in 12.7 ms, about 24 ÷ 0.0127 ≈ 1,900 a second, above the 1,000-a-second ceiling. So the queue grows: write n is acknowledged at n ms, the last at 24.0 ms. By 12.7 ms, 12 writes are waiting. Write 24 waits 24.0 − 12.7 = 11.3 ms, and the average wait is 6.4 ms.

Synthesizing vector architecture diagram...

The math

An approximate rule for the batch size:

Worked for the opening problem (Part 0): 100,000 writes a second × 0.001 s = 100 writes per batch, so 100,000 ÷ 100 = 1,000 syncs a second, each carrying about 10 KB. A writer waits for the rest of the sync in progress (between 0 and L, L ÷ 2 on average) plus its own sync (L): between L and 2L, about 1.5 ms on average. The reference implementation's steady-load run (100,000 writes a second, both evenly spaced and random arrivals) gives exactly that: 1,000 syncs a second, 100 writes per batch, 1.50 ms average wait, 2.0 ms worst.

Three consequences:

• It needs concurrency. Writes in flight = 100,000 × 0.0015 ≈ 150. One client writing one record at a time never gets a batch bigger than one.
• It adapts by itself. At low load, batches of one and a wait of exactly L; at high load, bigger batches and a wait approaching 2L, while syncs a second stay at about 1 ÷ L.
• It stops helping only at the bandwidth limit, when a batch takes longer to write than to sync; above 256 KiB, one sync also costs EBS more than one I/O.

The window variant

Instead of syncing as soon as the previous sync ends, some designs wait on purpose: collect writes until a window W has passed or the batch reaches a size, then write and sync once. The message queue loop uses "2 ms or 64 KB, whichever comes first". Real examples: Cassandra's commitlog_sync: group (acknowledges after a sync of each group window) and PostgreSQL's commit_delay, which waits before flushing only when at least commit_siblings other transactions are active (defaults: 0 µs and 5, so off by default).

Both on equal terms, on the same inputs, from the reference implementation (the window opens when the first write reaches an empty batch; a write arriving exactly as a window closes joins the next one):

The window halves the syncs at high load and costs up to W of extra latency at every load, even when the disk is idle.

"Group commit" is also used loosely for any batching of durable writes; the distributed email loop "group-commits" messages into an S3 spool. The idea is the same: one expensive durable step shared by many writes.

Go deeper: pipelining and one shared journal. RocksDB's optional pipelined writes (enable_pipelined_write, off by default) let the next group start its WAL write while the previous group is still inserting into the MemTable, so the log and the MemTable work in parallel. At the other extreme, a broker with many partitions can give them one shared journal, so one sync covers every partition's writes instead of one sync per partition log; the message queue loop does this in Round 2 (step R2.5). The whole broker then shares one sync budget.

Part 6. Durability modes: what "acknowledged" means

Not all data deserves a sync before OK. Metrics can lose a second; a payment cannot. Every engine lets you choose, and the classic mistake is to choose a mode without stating what it can lose.

The ladder

A quorum is the number of replicas that must hold a record before the write counts as committed, for example 2 of 3 (Part 10).

Trace: one power loss, four modes

The same 24 arrivals, and power fails at the same wall-clock instant, 13.5 ms, under four modes. Flushed files are synced in every mode (the LSM page's flush order). Two things the reference implementation derives rather than assumes: under the no-sync modes, the flush of writes 21 to 24 (F12) starts when write 24 arrives at 12.7 ms and needs its own 1 ms file sync, so it cannot be durable before 13.7 ms; and we assume the kernel has not written wal-6's pages back by 13.5 ms.

Group commit acknowledged 22 writes by the instant of the power loss and lost none of them; sync per write acknowledged only 13; the fast modes acknowledged all 24 and lost four of them.

How engines name it

With InnoDB's 2, the log reaches the OS at every commit, so by Part 2's rules a crash of the MySQL process alone should not lose it; an OS crash or power loss can lose up to about the last second.

Losing writes vs corrupting data

PostgreSQL shows the difference in two settings:

• synchronous_commit = off acknowledges before the WAL flush. A crash can lose the last few commits (up to three times wal_writer_delay), but the database comes back consistent: the WAL is still written in order and still protects every page.
• fsync = off stops syncing altogether, including the data pages and checkpoints. A crash can leave pages and log out of step, and the database may be corrupt, not just behind. PostgreSQL's documentation puts it plainly: fsync = off "can result in unrecoverable data corruption"; synchronous_commit = off "does not create any risk of database inconsistency".

Losing the last second of metrics can be a sound business choice. Corrupting the database never is.

Part 7. Power loss and torn writes

A sync writes many bytes, and a power loss can stop it anywhere. Recovery must find exactly the records that are whole, and nothing else.

What a torn write is

A device persists data in atomic units (sectors): each unit is written completely or not at all. A write larger than one unit is not atomic. If power fails in the middle, some units have the new bytes and some the old, and the units may have reached the media in any order. That is a torn write.

The tiny store uses 32-byte units so the effect shows up in a small example. At real scale the unit is 512 bytes or 4 KiB; two small records then usually share one unit and cannot tear apart, and a torn tail is cut at unit boundaries, not record boundaries.

Trace: power fails during B14 (branch P)

wal-6 holds records 21 to 24. The reference implementation places them at these byte ranges: record 21 at 0 to 27, record 22 at 27 to 55, record 23 at 55 to 82, record 24 at 82 to 109. Units 0 and 1 were already on the media after B13. B14 writes records 23 and 24, which dirties units 1, 2 and 3 (unit 1 is rewritten whole, record 22's tail included), and the fdatasync is running when the power fails:

Synthesizing vector architecture diagram...

This is case 1 of branch P, unit by unit. "Unit 0, bytes 0 to 31" holds record 21 and the head of record 22, and has been on the media since B13. B14's sync then had to store units 1, 2 and 3, and the power failed while it ran. "Unit 1, bytes 32 to 63" (the tail of 22 and the head of 23) and "Unit 2, bytes 64 to 95" (the tail of 23 and the head of 24) reached the media. "Unit 3, bytes 96 to 127" (the tail of 24) did not, so the disk still holds zeros there. The result: record 23 is complete on disk; record 24 has its header and its first 7 payload bytes, then zeros. Because each unit is atomic, rewriting unit 1 could not damage record 22's tail: that unit holds either its old bytes or its new ones.

The recovery scan

pseudocodeCopy
RECOVER_SCAN(segments still needed, oldest first)
    for each segment:
        offset = 0
        loop:
            1. read 7 header bytes at offset
               if fewer than 7, or all zero:
                   stop                             -- end of what was ever written
            2. read length payload bytes
               if fewer than length:
                   stop                             -- torn
            3. if checksum(type + payload) != the stored checksum:
                   stop                             -- torn or damaged
            4. if seq is already in a flushed file:   -- safe to repeat
                   skip it
               else:
                   apply it
            5. offset = offset + 7 + length
    "stop" ends the whole replay, not just this segment
    cut the log after the last good record
    next seq = last good seq + 1

RECOVER_SCAN runs once when the engine starts after a crash, and its job is to find every complete record in the log and stop at the first one that is not complete. Its input is the list of log segments that have not been deleted yet, read oldest first. offset is the byte position of the next record inside the current segment and starts at 0. Each record begins with a 7-byte header, which holds the stored checksum, length (the number of payload bytes) and type; the payload holds seq, the record's sequence number. A record is accepted only if all 7 header bytes are there and not all zero, all length payload bytes are there, and the checksum computed over type and the payload equals the stored one. An accepted record is applied unless its seq is already in a file flushed earlier, which makes the scan safe to run twice, and then offset moves forward by 7 + length bytes. The first failed check ends the whole replay, because records after a bad one cannot be trusted. The scan changes two things: it cuts the log after the last good record, and it sets the next sequence number to the last good seq + 1.

Synthesizing vector architecture diagram...

This is the log side of the LSM page's boot sequence (its section The boot sequence), which surrounds this scan with reading the manifest and flushing the rebuilt MemTable; the LSM page's section A damaged WAL lists RocksDB's recovery modes for damage found here.

Case 1 depends on the tiny store's one-record-per-write format; in LevelDB or RocksDB, 23 and 24 would be one record and would be lost or kept together. Case 2 happens in every engine: the sync can finish a moment before the power goes, and nobody is told.

Writes that survived without their OK

In a sync-before-OK mode, the torn tail is always safe to cut: nothing in it was acknowledged. The surprise runs the other way: a write can survive without its OK. Clients 23 and 24 saw a timeout or a dropped connection, not an error, and their writes may exist after recovery (both do in case 2). So a timeout is an unknown outcome, like the error in Part 3. The client must retry with an idempotency key, so the write applies once whether or not the first attempt survived (the Idempotency & Effectively-Once Processing loop primitive).

Go deeper: recycled segments. An engine that reuses old log files (to avoid growing a file, Part 2) leaves old records in them. After a crash, the bytes just past the new tail may be an old record with a perfectly valid checksum, which the scan would apply. The fix is to put the log file's number in each record (RocksDB's recyclable format, Part 4), or a position the old record cannot match (PostgreSQL's WAL pages carry their own log address in a header), so the scan stops at the first record left over from the file's earlier use.

Part 8. Segments, rotation and truncation

The log records every write forever unless something deletes it. It cannot simply be deleted by age: a segment may still hold the only durable copy of a write, or data a reader has not consumed yet.

Why segments

One endless file cannot be shortened from the front. So the log is a series of segments, separate files, and old ones are deleted, recycled or archived whole. A new segment starts:

• at a MemTable switch (RocksDB, and the tiny store: one segment per MemTable, so a segment becomes useless exactly when its MemTable is flushed);
• at a size (PostgreSQL's 16 MB segments); or
• at a size or a time (Kafka).

When a segment may go

A segment may be deleted only when both are true:

1. Every record in it is durable elsewhere: in a flushed file (LSM), or in data pages written back by a checkpoint (B-tree, Part 9).
2. No consumer still needs it: every replica, backup shipper and change-data-capture reader has confirmed a position past its last record.

The LSM page's section The safe order gives the order for the first condition: sync the flushed file and its directory, record it in the manifest, and only then delete the segment. Its crash-at-each-step table shows why that order loses nothing.

Synthesizing vector architecture diagram...

Trace: after write 24, with and without a stuck reader (branch T)

Fork the main timeline after write 24 is acknowledged and before F12's manifest edit. Manifest edit 9 (F11) has made writes 1 to 20 durable in flushed files, so wal-1 to wal-5 pass the first gate and wal-6 does not. Now add a change-data-capture (CDC) reader, a program that reads the log to copy each change to another system, which has confirmed only up to seq 10:

Without the reader, one segment is kept; with it, four. Every new write adds to the retained segments until the reader moves or the disk fills.

The log as a change stream

Replicas, backup shippers and change-data-capture tools all read the log, and each one pins it:

• Replication: a follower that falls behind needs every segment since its position (or must be rebuilt from a snapshot).
• Backup shipping: the key-value store loop ships sealed segments to S3 every 60 s; a segment may go only after its upload is confirmed.
• Change data capture: PostgreSQL's replication slots make the server keep WAL until the slot's consumer confirms it. The transactional outbox loop (step R2.7, "a stalled slot retains WAL") and the payments loop (step R3.9) alarm on exactly this. The Change Streams & the Transactional Outbox loop primitive covers the readers themselves.
• RocksDB can archive WAL files for such readers instead of deleting them, bounded by WAL_ttl_seconds and WAL_size_limit_MB (both 0 by default: no archive).

Part 9. The WAL in B-tree engines

PostgreSQL, InnoDB and SQLite are not LSM trees: they keep data in fixed-size pages (8 KB in PostgreSQL, 16 KB in InnoDB) and change them in place. They log first too, but a page adds two problems: replay must be safe to repeat, and a half-written page cannot be repaired from a small log record.

Log first in a page-based engine

A change modifies a page in memory, logs a record describing it, and the dirty page is written back to its place in the data file later, possibly much later. The WAL rule adds one constraint: a page may be written back only after the log is durable up to that page's last change. The log's commit record is what makes a transaction durable; the page write-back is just catching up.

The words to know: this is ARIES-style recovery, a steal / no-force design. "No-force": commit does not wait for the pages to be written. "Steal": a page may be written back before its transaction commits (so the log also needs undo information; that is beyond this page).

pageLSN makes redo safe to repeat

Each page stores the LSN of the last log record applied to it, its pageLSN. Redo applies a record to a page only if the record's LSN is greater than the pageLSN; otherwise that change is already on the page. That makes replay idempotent: a crash during recovery just runs it again.

pseudocodeCopy
REDO(from the checkpoint's redo point)
    for each log record r, in LSN order:
        page = read r's page from the data file
        if r carries a full-page image:
            page = the image                        -- the image already includes r's change
            page.LSN = r.LSN
        else if r.LSN <= page.LSN:
            skip                                    -- already on the page
        else:
            apply r
            page.LSN = r.LSN

REDO rebuilds the data pages after a crash in a page-based engine. It starts at the checkpoint's redo point, the log position before which every change is already on the data pages, and reads each log record r in LSN order; r.LSN is the record's log sequence number. page is the page that r changes, read from the data file, and page.LSN is that page's pageLSN, the LSN of the last record applied to it. When r carries a full-page image (a whole copy of the page logged with the first change after a checkpoint), REDO replaces the page with the image, even if the page on disk looks newer, because a torn page cannot be recognised by its LSN. Otherwise it skips r when r.LSN is less than or equal to page.LSN, because that change is already on the page, and applies r when r.LSN is greater. Each applied record also sets page.LSN to r.LSN. REDO returns nothing; it changes the data pages until each one holds every logged change, as in the branch B trace below, which ends with P1 at pageLSN 7 and P2 at pageLSN 8.

Checkpoints bound replay

A checkpoint writes dirty pages back and records a redo point: every change before it is on the data pages. Recovery starts there, not at the beginning of the log, and segments before it can go (Part 8's first gate). Checkpoints trade steady background writes for shorter recovery.

Torn pages

A page is 8 or 16 KB, much larger than the device's 512-byte or 4 KiB atomic unit, so a power loss during write-back can leave a page half old and half new. A log record says something like "put order:7 pen in this page"; applied to a page that is half garbage, it cannot rebuild the rest. The page needs a whole good copy from somewhere:

Synthesizing vector architecture diagram...

Full-page images and doublewrite are the B-tree's extra write cost; the LSM page's section B-tree vs LSM tree compares the totals.

Trace: the tiny store on two pages (branch B)

Put writes 1 to 8 on a B-tree with two leaf pages: P1 holds the order: keys, P2 the user: keys. A checkpoint after write 4 writes both pages (P1 pageLSN 3, P2 pageLSN 4); redo will start at LSN 5. Write 5 is P2's first change after the checkpoint, so its record carries P2's full-page image; write 7 is P1's first, so it carries P1's image. P2 is written back after write 6 (pageLSN 6). After write 8, P1's write-back is torn by a power loss.

Synthesizing vector architecture diagram...

The reference implementation runs recovery both ways. Both end with P1 = order:7 pen, order:9 book (pageLSN 7) and P2 = user:1 alicia, user:3 carol, user:4 dave (pageLSN 8), exactly the state before the power loss:

Without either protection, P1 is lost: record 7 only says "put order:7 pen", and order:9 book was written before the checkpoint, so nothing in the log since the redo point holds it.

SQLite's WAL mode

The mobile news feed and mobile chat loops run SQLite in WAL mode. Its log holds whole pages, not change records:

Part 10. Replication as a durability level

Everything so far survives a power loss on one machine. A dead volume, a lost instance or a zone outage still takes the only copy. The next step up is more copies on other machines, and the question becomes: which copies must have the record before we say OK?

What each promise means

The shared mechanism in two sentences: the leader appends the record to its own log and sends it to the followers in parallel; it commits (and acknowledges) once W of the N replicas, itself included, have the record, each by its own sync policy. How a leader is elected and how a lagging follower catches up belong to the Replication, Quorums & Read-Your-Writes loop primitive and Distributed Consensus (Raft & Paxos).

The latency rule

The leader's local sync and the followers' round trips run at the same time, so commit latency is the slowest leg we must wait for, not the sum: max(local sync, the (W − 1)-th fastest follower's acknowledgement). At W = 2 of 3 that is the faster of the two followers. The slow follower does not count. This is how Raft-style logs work (the Raft paper, etcd, DynamoDB): the leader sends to followers in parallel with its own sync. PostgreSQL is different: it ships only WAL it has already flushed locally, so a synchronous commit costs the local flush plus the standby's round trip (with this branch's numbers, 1.0 + 1.4 = 2.4 ms).

Trace: three replicas take writes 21 to 24 (branch R)

Fork the main timeline after write 20. Replica A leads in AZ a; B (AZ b) and C (AZ c) follow; commit at W = 2 of 3. Assumptions, all labelled: A's local sync takes 1.0 ms, B acknowledges 1.4 ms after A sends (network plus its own sync), and C is slow at 6.0 ms. One batch is in flight at a time, as in Part 5, so each batch now takes max(1.0, 1.4) = 1.4 ms, and the batches regroup. From the reference implementation:

Synthesizing vector architecture diagram...

When the leader is cut off, when everyone loses power

Local sync vs quorum, on equal terms

Neither column alone covers everything: replication covers the lost disk and zone, local syncs cover the correlated power loss. Systems that promise both do both.

One acknowledged write through every layer

Synthesizing vector architecture diagram...

Write 23's budget in branch R, with max() for parallel legs and a sum for dependent ones:

The naive sum of every leg, 1.3 + 1.0 + 1.4 + 6.0 = 9.7 ms, is more than three times too high. And requiring all three replicas (W = 3) would make the commit max(1.0, 1.4, 6.0) = 6.0 ms per batch. The client's own network round trip adds to all of these.

Part 11. On AWS

Every AWS database and log service has a write-ahead log or a replicated log inside it; the question for a design is what each one publishes about when it says OK. And if you run your own engine, the log's sync budget comes out of the same volume as everything else.

Managed services that use a log

Stated only from AWS's public documentation and papers:

Running it yourself on EC2

Not the same thing

Part 12. What you've learned

Back to the 100,000 writes a second

Our node had to acknowledge 100,000 writes a second, each surviving a crash, when one sync of its log takes about 1 ms and so caps it at 1,000 syncs a second:

• The WAL rule said what OK must mean: logged before applied, durable before acknowledged, against a named failure class (Part 1).
• A sync, not a write, makes a record durable, through the device's cache, with the directory and file size made durable too (Part 2), and a failed sync stops the engine instead of being retried (Part 3).
• Group commit shares each sync: about 100 writes per batch, about 1,000 syncs a second, waits of 1 to 2 ms, with about 150 writes in flight (Part 5). It keeps the same guarantee as a sync per write (Part 6).
• The shared budget holds: about 1,000 IOPS of syncs plus about 760 for the LSM tree's flushes and compaction is about 1,800 of gp3's 3,000 baseline, and the log's 12 to 16 MB/s adds to the LSM tree's 200 MB/s of flushes and compaction, already above gp3's 125 MiB/s baseline, so we provision more gp3 throughput (or move the log to its own volume).
• Checksums and the stop-at-first-bad-record scan make a torn tail harmless (Part 7); truncation keeps the log small unless a reader pins it (Part 8).
• Replicas in other AZs cover what one disk cannot, the lost volume and the lost zone, with commit latency set by the fastest follower (Part 10).

The cheat card

Failure checklist

• Does every "OK" in the design name the failure class it survives?
• Is the sync before the acknowledgement in the code path that actually answers?
• Do sync errors stop the engine, never get retried?
• Are log files zero-filled or recycled, and the directory synced on create?
• Are sync latency and batch size metrics with alarms?
• Is consumer lag on every log reader alarmed before disk space?
• Is torn-page protection on, or are atomic writes proven for this instance and block size?
• Are replicas in separate AZs, with a sync policy that covers a power event they all share?

Think-first drills

Interview questions

Follow-ups an interviewer may add:

Where to go next

• LSM-Trees & Compaction: what the tree does with each record once the log has made it durable.
• Loop primitives: Idempotency & Effectively-Once Processing (retries after unknown outcomes), Change Streams & the Transactional Outbox (the readers that pin the log), Replication, Quorums & Read-Your-Writes (elections and catch-up).
• Distributed Consensus (Raft & Paxos), Change Data Capture (CDC) & Outbox Pattern, Database Isolation Levels, ACID & Concurrency Anomalies.
• Loops: the key-value store (steps 1.1, 1.6, R2.5, R2.10), the message queue (steps 1.1, 1.3, R2.5, R2.7), the matching engine (steps 1.4, 2.3), S3-like object storage (step 1.2), metrics (steps 1.1, 2.2), the mobile news feed (steps 1.3, R2.8), mobile chat (step 1.1), the transactional outbox ledger (steps R2.7, 3.2) and payments (step R3.9).