Write-Ahead Log, fsync & Group Commit

Part 0. Start here

The problem: 100,000 acknowledged writes a second

We go back to the storage node from the LSM-Trees & Compaction page. It takes 100,000 small writes a second, about 100 bytes each, on an EBS gp3 volume. 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 to notice: many writers, one write, one sync, many acknowledgements. The dotted branch is replication (Part 10): when the promise includes losing a machine or a zone, the OK also waits for other machines.

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 page or anything else changes.
2. Make the log durable before acknowledging. "Durable" means the record survives the failures the promise covers.

The LSM page (Part 2) 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...

What to notice: write() only moves a record from the "Application buffer" box to the "Page cache" box. Getting it to "Stable media" takes a sync, which also has to get through the "Device cache". Only "Other machines" survive losing the disk.

The tiny store, now watching the log

The LSM page followed a tiny store as its tree grew; this page watches its log. The settings are the same, plus the log's own:

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 quietly break all of them. This Part is what each call really buys, 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...

What to notice: the kernel sends a flush (write everything in your cache to media) or uses FUA (force unit access: this write completes only once it is on non-volatile storage). If the device reports no volatile cache, the Linux block layer simply drops these requests. A power-loss-protected drive treats its cache as stable: it reports no volatile cache, or completes a flush almost at once; the sync still has to reach that cache, and no drive protects against its own loss or the zone's.

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 Part 3 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 Part 8) does not show are drawn here:

Synthesizing vector architecture diagram...

What to notice: the directory sync happens once per file, at creation; the data sync happens once per batch. Because wal-1 was zero-filled in advance, the sync at 1.0 ms has no file size to change.

What a sync costs

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

$$\text{syncs per second} \le \frac{1}{L}, \qquad \text{writes per second} \approx \frac{n}{L} \text{ with } n \text{ writes per batch}$$

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:

textCopy
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 lies) breaks every promise above it silently, 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. The retry turns a crash that loses nothing into a timing lottery.

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, and the fsync fails:

Synthesizing vector architecture diagram...

What to notice: every step after the retry follows the LSM page's safe flush order (its Part 3), and it still loses data, because the order assumed the sync told the truth. F11's blocks never reached the disk, and wal-5, the only other copy of writes 17 to 20, is gone. Nothing complains until a read or a compaction touches F11, which could be days later.

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, avoids being fooled.

---

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

textCopy
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

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

textCopy
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: unlock; return OK                -- a leader carried it
  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)

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

What to notice: writers 5, 6 and 7 arrived during B3's sync, so they became one batch; writer 5 was first in the queue and led it. One sync, three acknowledgements, all at 4.0 ms.

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

What to notice: both rows sync back to back, one sync per millisecond: the disk is equally busy. The "Group commit" row finishes all 24 writes at 14 ms because several of its syncs carry two or three writes; the "One per write" row needs 24 ms, and every write that arrives after 1 ms waits in a queue that keeps growing until the arrivals stop at 12.7 ms.

The math

The rule of thumb for the batch size:

$$\text{batch size} \;\approx\; \text{arrival rate} \times L$$

Worked for the hook: 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

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

Case 1 of branch P: units 1 and 2 reached the media, unit 3 did not. 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

textCopy
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: skip it; else apply it   -- safe to repeat
      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

Synthesizing vector architecture diagram...

What to notice: there is only one way forward and three ways to stop. The scan never skips a bad record to look for good ones after it.

This is the log side of the LSM page's boot sequence (its Part 9), which surrounds this scan with reading the manifest and flushing the rebuilt MemTable; the LSM page's Part 10 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 happily 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 from a previous life.

---

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 Part 3 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...

What to notice: a sealed segment has two gates to pass, and the slowest one decides. A flush can release it in milliseconds; a stuck reader can hold it forever.

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 reader that has confirmed only up to seq 10:

Without the reader, one segment is kept; with it, four. Every new write adds to the pile 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.

textCopy
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; page.LSN = r.LSN        -- the image already includes r's change
    else if r.LSN <= page.LSN:
        skip                                      -- already on the page
    else:
        apply r; page.LSN = r.LSN

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

What to notice: in "Full-page image" the good copy lives in the log (PostgreSQL, full_page_writes = on by default); in "Doublewrite" it lives in a separate area written before the page (InnoDB, on by default); with "Atomic device write" no copy is needed, which is what AWS's torn-write prevention and RDS Optimized Writes provide (Part 11).

Full-page images and doublewrite are the B-tree's extra write cost; the LSM page's Part 7 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...

What to notice: record 7's image is the only thing that can rebuild P1; record 8 is newer than P2's pageLSN, so it must be applied.

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 Primitive #09: Raft and 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...

What to notice: the OK waits for the slower of A's own sync (1.0 ms) and B, the fastest follower (1.4 ms), so R3 commits 1.4 ms after it starts. C's 6.0 ms never enters the client's latency.

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

What to notice: the local path runs down the middle and the replicas run beside it; the OK waits at the commit check for whichever legs W requires.

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 throughput the LSM page had already pushed above the 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.
• Coming as 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).
• Primitive #09: Raft and Paxos, Primitive #12: Change Data Capture and the Outbox Pattern, Primitive #21: Isolation Levels.
• 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).