How does a key-value store survive a crash?

With a write-ahead log (WAL): every update is appended to an on-disk log and fsynced before the write is acknowledged, and only then applied to the in-memory structures. On restart the store replays the WAL to reconstruct the in-memory state it lost, so no acknowledged write is ever forgotten. RocksDB puts it plainly: "write ahead logs can be used to completely recover the data in the memtable."

What is a write-ahead log and why append before apply?

A WAL is an append-only file the store writes to before touching any other structure. Appending is sequential, so it is fast, and because the durable record exists before the in-memory apply, a crash at any point leaves a log you can replay. If you applied first and logged second, a crash between the two would lose the write with no record it happened.

What does fsync do and why is it the durability/latency trade-off?

A write to a file only lands in the OS page cache; fsync forces it to the physical disk. fsync-per-write is the safest (zero writes at risk) but caps you near the disk’s fsync rate (~1,000/s). Group commit fsyncs a batch once per small window (e.g. 5 ms), so the durability window is that batch and latency is roughly half the window — far higher throughput for a bounded, honest risk. Letting the OS flush is fastest but risks tens of seconds of writes.

What happens if the store crashes after the WAL append but before the memtable apply?

The write survives. The WAL is the source of truth, so on recovery the store replays the log and re-applies that record to the memtable — whether or not the in-memory apply happened before the crash. The only writes lost are ones whose WAL record was never fully written and fsynced; a torn tail record fails its checksum and is discarded, and that write was never acknowledged.

What is the difference between an LSM tree and a B-tree storage engine?

An LSM tree (LevelDB, RocksDB, Cassandra) buffers writes in a memtable, flushes them to immutable sorted files (SSTs), and compacts in the background — write-optimized, sequential I/O, higher read/space amplification. A B-tree (InnoDB, most SQL engines) updates pages in place — read-optimized with predictable point lookups, but writes do more random I/O. Both still need a WAL for crash durability.

Design a Durable Key-Value Store

Start with a hash map behind a socket; end with a crash-survivable storage engine. The write-ahead log — append before apply, fsync, and replay-on-recovery — is the whole story, drawn and computed.

System design · Systems. The source ↗

A free, interactive, animated visual explainer of Design a Durable Key-Value Store — built to be understood, not skimmed.

Questions

How does a key-value store survive a crash?: With a write-ahead log (WAL): every update is appended to an on-disk log and fsynced before the write is acknowledged, and only then applied to the in-memory structures. On restart the store replays the WAL to reconstruct the in-memory state it lost, so no acknowledged write is ever forgotten. RocksDB puts it plainly: "write ahead logs can be used to completely recover the data in the memtable."
What is a write-ahead log and why append before apply?: A WAL is an append-only file the store writes to before touching any other structure. Appending is sequential, so it is fast, and because the durable record exists before the in-memory apply, a crash at any point leaves a log you can replay. If you applied first and logged second, a crash between the two would lose the write with no record it happened.
What does fsync do and why is it the durability/latency trade-off?: A write to a file only lands in the OS page cache; fsync forces it to the physical disk. fsync-per-write is the safest (zero writes at risk) but caps you near the disk’s fsync rate (~1,000/s). Group commit fsyncs a batch once per small window (e.g. 5 ms), so the durability window is that batch and latency is roughly half the window — far higher throughput for a bounded, honest risk. Letting the OS flush is fastest but risks tens of seconds of writes.
What happens if the store crashes after the WAL append but before the memtable apply?: The write survives. The WAL is the source of truth, so on recovery the store replays the log and re-applies that record to the memtable — whether or not the in-memory apply happened before the crash. The only writes lost are ones whose WAL record was never fully written and fsynced; a torn tail record fails its checksum and is discarded, and that write was never acknowledged.
What is the difference between an LSM tree and a B-tree storage engine?: An LSM tree (LevelDB, RocksDB, Cassandra) buffers writes in a memtable, flushes them to immutable sorted files (SSTs), and compacts in the background — write-optimized, sequential I/O, higher read/space amplification. A B-tree (InnoDB, most SQL engines) updates pages in place — read-optimized with predictable point lookups, but writes do more random I/O. Both still need a WAL for crash durability.

Design a Durable Key-Value Store

Questions

Related explainers