· SWE Editorial · System Design · 6 min read
Design a Key-Value Store: Architecture and Data Flow
Tracing a single write and read through a distributed key-value store: write-ahead log, memtable, SSTable flush, and how the read/write paths differ, plus replication data flow.
Naming “LSM tree” in a system design interview earns partial credit. Tracing exactly what happens to a byte of data from the moment a client calls put() to the moment it’s durably queryable — and what happens differently on get() — is what separates a candidate who has read about LSM trees from one who understands them. This article walks the write path and read path step by step through the write-ahead log, memtable, and SSTables, then extends the data flow across replicas.
The Write Path, Step by Step
When a client issues put(key, value) to a node responsible for that key:
- Write-ahead log (WAL) append: the operation is serialized and appended to an on-disk, sequential log file. This is a pure append — no seeking, no read-before-write — which is why this step is fast even on spinning disk. The write is
fsync’d (or batched-fsync’d) before acknowledgment, guaranteeing durability: if the process crashes immediately after, the WAL can replay this write on restart. - Memtable insert: concurrently (or immediately after WAL append), the key-value pair is inserted into an in-memory sorted structure — typically a skip list or balanced tree — called the memtable. This is what makes subsequent reads of very recent writes fast, without touching disk.
- Acknowledgment: once both the WAL append is durable and the memtable insert completes, the node acknowledges the write to the client (or to the coordinator, in a replicated setup — see below).
- Memtable flush (asynchronous, later): once the memtable reaches a size threshold, it is frozen, a new empty memtable takes over new writes, and the frozen memtable is serialized to disk as an SSTable (Sorted String Table) — an immutable, sorted, indexed file. The corresponding WAL segment can then be truncated, since the data is now durably represented in the SSTable.
The critical data-flow insight: durability comes from the WAL (step 1), not from the memtable or the eventual SSTable flush. This is why systems can acknowledge writes in single-digit milliseconds despite disk-based storage — the expensive, multi-level SSTable structure is built lazily in the background.
The Read Path, Step by Step
When a client issues get(key):
- Check the active memtable — if the key was written recently and hasn’t been flushed yet, it’s found here immediately, in memory.
- Check bloom filters for each SSTable, newest first — for each SSTable that might contain the key (per its bloom filter), check its sparse index to locate the approximate disk block.
- Binary search / index lookup within the candidate SSTable — SSTables store an index (often a sparse index, one entry per N keys) allowing a near-direct seek rather than scanning the whole file.
- Return the first match found, newest SSTable wins — because SSTables are immutable and ordered newest-to-oldest in the search order, the first version of the key encountered is the most recent, correctly handling overwrites without needing to scan every SSTable.
- Merge with tombstone check — if the newest version found is a tombstone (delete marker), the key is reported as not-found even if older SSTables contain a value.
This is why read latency in an LSM-based store is variable and workload-dependent: a key updated once and read once might resolve at the memtable in microseconds, while a key with no recent writes might require checking several SSTables’ bloom filters and indexes before resolving — precisely the read amplification trade-off named in the storage-engine decision.
Data Flow Comparison: Write Path vs. Read Path
| Stage | Write Path | Read Path |
|---|---|---|
| First touchpoint | WAL (sequential append, disk) | Memtable (in-memory, sorted) |
| Durability guarantee established | After WAL fsync | N/A (reads don’t need durability) |
| Structures consulted | WAL + memtable only | Memtable, then each SSTable (newest-first) via bloom filter + index |
| I/O pattern | Sequential (WAL append + eventual SSTable flush) | Potentially random (SSTable index seeks), mitigated by bloom filters |
| Background work triggered | Memtable flush when size threshold hit | None directly, but frequent misses across many SSTables signal a compaction need |
| Latency driver | fsync latency + memtable insert (fast, predictable) | Number of SSTables checked before a hit (variable, workload-dependent) |
Replication Data Flow
Extend this single-node picture to a replicated cluster with replication factor N (commonly 3). On put(key, value):
- The client (or a coordinator node) hashes the key to find its position on the consistent-hashing ring and identifies the N nodes responsible for it (the coordinator plus its N-1 clockwise neighbors).
- The write is sent to all N replicas in parallel.
- The coordinator waits for W acknowledgments (a tunable write-quorum, e.g., W=2 of N=3) before returning success to the client — each acknowledging replica has independently completed its own WAL-append + memtable-insert sequence described above.
- Replicas that missed the write (network partition, temporary outage) are reconciled later via read repair (detected during a subsequent read when replicas disagree) or hinted handoff (a temporarily-unreachable replica’s write is held by another node and delivered once it recovers).
On get(key), the coordinator queries R replicas (read-quorum, e.g., R=2) and returns the value with the latest timestamp or vector clock, triggering read repair on any replicas found to be stale. The classic tunable consistency relationship is W + R > N, which guarantees at least one overlapping replica between any write and any subsequent read, giving strong consistency at the cost of latency (waiting on more replicas) — a trade-off worth stating explicitly when asked to justify quorum values.
Compaction’s Place in the Data Flow
Compaction runs as a background process reading multiple SSTables and writing a merged, smaller set — it doesn’t sit in either the write or read path directly, but it determines how many SSTables a read must check (fewer, larger, well-organized SSTables after compaction mean fewer bloom-filter checks per read) and reclaims space from overwritten or tombstoned keys. Because compaction is I/O- and CPU-intensive, production systems throttle it against foreground traffic — a detail worth naming when discussing the full data flow’s operational behavior, not just its steady-state correctness.
Bringing It Together
The full data flow is: writes land sequentially in a WAL for durability and immediately in a memtable for fast subsequent reads, memtables flush asynchronously into immutable, bloom-filter-indexed SSTables, reads check memtable then SSTables newest-first, and replication overlays a quorum-based fan-out on top of this per-node behavior. Tracing this sequence out loud, rather than stopping at “it uses an LSM tree,” is what interviewers are listening for.
For a fully diagrammed version of this write/read path with a worked capacity-estimation exercise, see The 0-to-1 SWE Interview Playbook (Amazon: https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20), which includes this exact data-flow trace as a whiteboard-ready template for 2026 interview loops.
Practice Prompt
Walk through what happens, step by step, when a node crashes immediately after acknowledging a write but before the memtable is flushed to an SSTable — and explain how the WAL recovers the correct state on restart. Being able to answer this without hesitation is a strong signal you actually understand the architecture rather than having memorized its component names.