· SWE Editorial · System Design · 6 min read
Design a Key-Value Store: System Design Interview Guide
A complete interview framework for designing a distributed key-value store: LSM tree vs. B-tree trade-offs, compaction strategy, bloom filters, and consistent hashing for partitioning.
The key-value store question is a staple of senior and staff-level system design interviews because it compresses nearly every distributed systems concept — storage engines, replication, consistency, and partitioning — into a single, well-scoped problem. Unlike vaguer questions (“design Twitter”), a key-value store has a crisp API (get(key), put(key, value), sometimes delete(key)) which forces the conversation quickly toward the interesting parts: how data is stored on disk, how it’s distributed across nodes, and what consistency guarantees the system makes. This guide covers the storage-engine decision (LSM tree vs. B-tree), compaction, bloom filters, and consistent hashing — the four sub-topics that determine whether an interview goes deep enough to differentiate a candidate.
Scoping the Problem
Before designing anything, pin down:
- Read/write ratio: write-heavy (logging, metrics) vs. read-heavy (session cache, config store)?
- Value size: small values (session tokens, counters) or large blobs (documents, serialized objects)?
- Consistency requirements: strong consistency per key, or eventual consistency acceptable?
- Durability: can we lose recent writes on a crash, or must every acknowledged write survive?
A common interview default: assume a write-heavy workload (think DynamoDB or Cassandra’s original use case), values under 1MB, tunable consistency, and durability required post-acknowledgment. State this and move to architecture — this scoping step should take under five minutes.
Core API and High-Level Architecture
The API is deliberately minimal: put(key, value), get(key), optionally delete(key) (implemented as a tombstone write, not a physical delete — critical for LSM-based designs). The high-level architecture has four layers:
- Client with a partitioning-aware routing layer (or a coordinator node)
- Partitioning/replication layer — consistent hashing ring, N replicas per key
- Storage engine per node — LSM tree or B-tree
- Coordination for consistency — quorum reads/writes, vector clocks or last-write-wins for conflict resolution
LSM Tree vs. B-Tree: The Central Trade-off
This is the single most consequential decision in the interview, and interviewers expect you to justify it with workload reasoning, not just name-drop RocksDB.
| Dimension | LSM Tree | B-Tree |
|---|---|---|
| Write path | Append-only to WAL + in-memory memtable — O(1) amortized, sequential disk I/O | In-place update requiring page read-modify-write — random disk I/O |
| Write throughput | High — writes are batched and flushed sequentially | Lower — random writes are expensive on spinning disk, moderate on SSD |
| Read path | May check memtable + multiple SSTable levels — needs bloom filters to stay fast | Direct O(log n) tree traversal — consistently fast, no multi-level check |
| Read amplification | Higher (multiple SSTables to check without bloom filters) | Low — single tree structure |
| Write amplification | Higher (compaction rewrites data multiple times) | Lower — updates happen in place |
| Space efficiency | Requires compaction to reclaim space from overwrites/deletes | Reclaims space immediately on update |
| Best fit | Write-heavy workloads (logging, time-series, event stores) | Read-heavy or balanced workloads needing consistent low-latency reads |
| Real-world examples | Cassandra, RocksDB, LevelDB, HBase | InnoDB (MySQL default), PostgreSQL (heap + B-tree indexes) |
The interview-winning explanation: LSM trees trade read amplification and background compaction cost for dramatically better write throughput by converting random writes into sequential ones. B-trees keep reads uniformly fast at the cost of random-write I/O. If asked “which would you pick,” answer conditionally on the workload you scoped earlier rather than picking one universally.
Compaction: Why LSM Trees Need It
Because LSM writes are append-only, a key updated ten times exists as ten separate entries across memtable and SSTables until compaction runs. Compaction merges SSTables, keeping only the newest version of each key (and physically removing tombstoned/deleted keys after a grace period).
Two common compaction strategies to name:
- Size-tiered compaction: merge SSTables of similar size together as they accumulate; simpler, but can cause large space amplification temporarily.
- Leveled compaction: organize SSTables into levels of exponentially increasing size (L0, L1, L2…); each level is compacted into the next when it exceeds a size threshold, bounding read amplification more tightly at the cost of more total compaction I/O.
A senior-level detail: compaction competes with foreground read/write traffic for disk I/O and CPU, so production systems throttle compaction rate and schedule it to avoid latency spikes — mentioning this “compaction storm” risk shows operational maturity.
Bloom Filters: Making LSM Reads Fast
Without a bloom filter, a get(key) on an LSM tree might need to check every SSTable on disk to confirm a key’s absence — expensive when there are dozens of SSTables. A bloom filter per SSTable gives a fast, memory-resident, probabilistic “definitely not present” or “maybe present” answer:
- False negatives are impossible — if the filter says “not present,” the key is guaranteed absent, so that SSTable is skipped entirely.
- False positives are possible and tunable — a larger filter (more bits per key) reduces the false-positive rate at the cost of memory.
- A typical production setting uses ~10 bits per key for roughly a 1% false-positive rate, which is why bloom filters are described as a memory-for-I/O trade: a small amount of RAM avoids most unnecessary disk seeks.
Consistent Hashing for Partitioning
To distribute keys across N nodes without a full remap on every node addition/removal, map both nodes and keys onto a hash ring (e.g., via SHA-1 or MurmurHash), and assign each key to the first node clockwise from its hash position. Adding or removing a node only reshuffles the keys between it and its immediate neighbor on the ring, not the entire keyspace — this is the property that makes horizontal scaling operationally cheap.
Two refinements worth naming:
- Virtual nodes: each physical node is assigned multiple positions on the ring, smoothing out load distribution that a small number of physical nodes would otherwise skew.
- Replication via the ring: for a replication factor of N, a key’s data is stored on the N nodes immediately clockwise from its hash position — a natural extension of the same structure used for partitioning.
Putting It Together in the Interview
A strong answer sequences the trade-offs: scope the workload, justify LSM vs. B-tree against that workload, explain how compaction reclaims space and its operational cost, show bloom filters as the fix for LSM read amplification, and use consistent hashing with virtual nodes to explain how the system scales horizontally without full reshuffles. This sequence mirrors how a real distributed key-value store is actually built, which is exactly the signal interviewers are calibrating for.
For a fully worked transcript of this question at staff level, including the follow-up questions on replication quorums and conflict resolution, The 0-to-1 SWE Interview Playbook (Amazon: https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20) covers this exact question with annotated interviewer expectations, updated for 2026 loops.
Common Follow-Ups to Prepare
Expect extensions into “how do you handle hot keys” (covered separately as a scaling-bottleneck topic), “how do you achieve strong consistency” (quorum reads/writes with W + R > N), and “how would you support range queries” (a B-tree-friendly requirement that pushes the design away from pure LSM, or requires a secondary sorted index). Have a one-sentence answer ready for each rather than reasoning from scratch under time pressure.