Write-ahead log
On the roadmap:Advanced · step 3: Storage engines
Record every change in an append-only file before applying it, so a crash can be replayed, and a half-written last record is detected and ignored.
In plain words
Before changing anything, write down what you are about to do in a file that is only ever added to. After a crash, read the file and redo the work.
Why it matters
This is how databases survive power loss without losing a committed change, and how they notice a half-written record at the end of the file.
Where you meet it
- PostgreSQL, MySQL and SQLite
- Kafka's log idea and replication
- Any system that must not lose acknowledged writes
You will be able to
- Log before you apply
- Detect a corrupt last record with a checksum
- Explain what fsync costs and what group commit does
In interviews
Comes up in 'how does a database stay durable?' and 'design a key-value store'.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Append-only file with one JSON record per line
- A checksum on every record to detect corruption
- A replay that stops at the first bad record
- A tiny key-value store that logs first, then updates memory
This lab reads and writes files, so it runs on your own computer. Copy the code and the check, then use the commands below.
import fs from "node:fs";
import { createHash } from "node:crypto";
type Op = { op: "set"; key: string; value: string } | { op: "del"; key: string };
const sum = (s: string) => createHash("sha1").update(s).digest("hex").slice(0, 8);
export class Wal {
constructor(private path: string) {}
append(op: Op): void {
const body = JSON.stringify(op);
fs.appendFileSync(this.path, `${sum(body)} ${body}\n`); // ponytail: no fsync; add one where durability matters
}
/** Valid records in order. Stops at the first line that is incomplete or fails its checksum. */
replay(): Op[] {
if (!fs.existsSync(this.path)) return [];
const ops: Op[] = [];
for (const line of fs.readFileSync(this.path, "utf8").split("\n")) {
if (line === "") continue;
const i = line.indexOf(" ");
const body = line.slice(i + 1);
if (i !== 8 || sum(body) !== line.slice(0, 8)) break;
ops.push(JSON.parse(body));
}
return ops;
}
}
/** Log first, then apply. After a crash, rebuild by replaying the log. */
export class DurableMap {
private data = new Map<string, string>();
private wal: Wal;
constructor(path: string) {
this.wal = new Wal(path);
for (const o of this.wal.replay()) this.apply(o);
}
private apply(o: Op) { if (o.op === "set") this.data.set(o.key, o.value); else this.data.delete(o.key); }
set(key: string, value: string) { const o: Op = { op: "set", key, value }; this.wal.append(o); this.apply(o); }
delete(key: string) { const o: Op = { op: "del", key }; this.wal.append(o); this.apply(o); }
get(key: string) { return this.data.get(key); }
}
How to run it on your computer
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints write-ahead-log ok when everything passes. You need Node.js installed.
mkdir write-ahead-log && cd write-ahead-log
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Real logs call fsync to force data onto the disk, which is slow. Group commit batches many writes into one fsync to recover the speed.
- Every record gets a sequence number (an LSN) as well as a checksum, and the log is split into segment files that are deleted once a checkpoint makes them unnecessary.
- The same log is used to copy data to other machines: PostgreSQL's streaming replication, for example, ships its log.
Ways to survive a crash
| How it works | Cost | After a crash | Pick it when | |
|---|---|---|---|---|
| Write-ahead log | Log the change first, then apply it | A fast sequential append | Replay the log to rebuild the state | Most databases and storage engines |
| Write in place only | Overwrite the data directly | Cheap | A write cut off halfway can corrupt data | The data is disposable |
| Copy-on-write | Write a new copy, then switch a pointer | Extra writing | The old copy is intact, no replay needed | Some storage engines and file systems |
| Replication only | Copy changes to another machine | Network and lag | Fail over to the copy | Use it together with a log, not instead of one |
What it cannot do
Forcing data to disk is slow
fsync is what makes a write really durable. Group commit batches several writes to share the cost.
The log grows
Until a checkpoint lets old records go, it keeps getting bigger.
Replay takes time
A very long log makes recovery after a crash slow.
It needs checksums
Without them, a half-written or corrupted record could be applied as if it were real.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add fsync after each write and measure the cost
- Batch several records per fsync (group commit)
- Truncate the log after taking a snapshot (checkpoint)