STANDARDwalkthrough
Write-Ahead Log (WAL)
The counter service crashes at counter value 1,000,042. On restart, it reads its last checkpoint at 1,000,038.
Users who received those codes now share URLs with strangers. The constraint: we need crash recovery without sacrificing write throughput.
“Without durability, it reissues IDs 1,000,039 through 1,000,042, creating four short codes that already exist in the database.”
We chose a Write-Ahead Log (WAL) (not periodic checkpointing alone) because WAL persists every counter increment to an append-only log on disk before applying it to the in-memory counter. On crash recovery, the service replays the log to restore the exact counter state, so no ID is ever issued twice.
Why not checkpoint after every write instead? Because checkpointing updates a data structure in place, requiring random I/O.
WAL writes are sequential I/O, which is roughly 10x faster than the random I/O required to update a B-tree index or a hash table on disk. Implication: at 29K writes per second, the WAL adds roughly 0.1ms of latency per write (one sequential disk append), while a checkpoint-per-write approach would add 1ms+ of random I/O, cutting our throughput by 10x.
Trade-off: we accept the operational complexity of log compaction (the WAL grows indefinitely without periodic truncation) in exchange for both durability and high throughput. MySQL InnoDB and PostgreSQL both use WAL internally for crash recovery. Every INSERT first goes to the WAL (called the redo log in InnoDB), and only later gets flushed to the actual data pages.
We apply the same principle to our counter service: durability comes from the log, not from the data structure itself. What if the interviewer asks: what if the disk holding the WAL fails?
We replicate the WAL to a standby node using synchronous replication. The counter service only acknowledges a write after both the local and remote WAL confirm the append.
Formula & tradeoffs
Formula
Related concepts