Articles

Key-Value Store System Design Interview: Partitioning, Replication, Compaction, and Consistency

Design a distributed key-value store for interviews: partitioning, replication, WALs, SSTables, compaction, consistency, recovery, and trade-offs.

A strong key-value store system design answer connects a distributed service with a durable storage engine. Route each key to an owning shard, replicate across failure domains, state the client-visible consistency contract, and persist accepted mutations through a log, memtable, immutable SSTables, and controlled compaction.

The key is which guarantees the product needs and how components preserve them during crashes, rebalancing, lag, and compaction. This 45-minute walkthrough uses interview assumptions, not vendor claims.

Start with the API and an Explicit Consistency Contract

Clarify whether the store serves opaque values by exact key or must support ordered scans. Hash partitioning balances point lookups; range partitioning preserves order. Supporting both changes routing and storage, so do not promise scans casually.

A useful baseline API is:

Get(key, consistency?) -> value, version | NOT_FOUND
Put(key, value, expected_version?, idempotency_key?) -> version
Delete(key, expected_version?) -> tombstone_version

Define key and value limits, TTLs, conditional writes, durability acknowledgement, and tombstones. State consistency in client terms: linearizable, read-after-write, bounded-stale, or eventual.

Assume point lookups dominate, each virtual shard is a three-node Raft group across three availability zones, and successful writes survive one machine loss. The default is linearizable operation within one region; stale reads may trade freshness for latency. Multi-key transactions and cross-region active-active conflict resolution remain out of scope unless asked.

Quantify the Workload Before Choosing Components

State assumptions aloud. These numbers are an interview exercise, not measured product limits.

Input or result	Interview assumption
Stored keys	10 billion
Average key plus value	1 KB
Logical data	About 10 TB
Replication factor	3; about 30 TB before indexes and compaction headroom
Peak traffic	About 93,000 reads/sec and 18,500 writes/sec
Latency target	In-region p99 under 10 ms for ordinary point operations
Growth and maintenance headroom	Keep roughly 30% free disk plus compaction I/O capacity

Also budget for indexes, Bloom filters, WAL retention, compaction output, repair, snapshots, and skew. Average-safe capacity can still fail under one celebrity key or increasing prefix.

Partition Keys, Route Requests, and Rebalance Safely

For point-heavy access, hash each logical key into a large token space and assign token ranges to virtual shards. A small strongly consistent metadata service stores each shard's replicas, leader, epoch, and migration state; routers cache that map, and any contacted node can reject a stale epoch. Consistent hashing or many fixed logical shards reduces the amount of data moved when capacity changes, but neither eliminates hot keys. FoundationDB's architecture illustrates the broader pattern of clients caching key-range locations and refreshing after a wrong-server response.

AWS documents the practical reason in its DynamoDB partition-key guidance: poor key distribution creates hot partitions even when the table has unused aggregate capacity. Mitigations include high-cardinality keys, write sharding for splittable workloads, per-key rate limits, replica-aware reads, and a cache for immutable hot values. A single indivisible hot key may require application-level decomposition rather than another hash function.

Treat rebalancing as a state machine: copy a consistent snapshot to target replicas, stream newer mutations, verify checksums and lag, publish a new routing generation, forward stale requests briefly, and retire old copies only after a safety window. Throttle migration so it cannot starve foreground disk or network traffic. If scans are required, use range shards with split and merge boundaries instead; this preserves order but makes skew harder.

Choose Per-Shard Consensus, Then Compare Leaderless Quorums

Use one leader and two followers for each virtual shard. The leader proposes a mutation, a majority durably records it, and every replica applies committed entries in the same order. This makes per-key ordering, compare-and-set, and linearizable reads clear. Leader election and fencing still matter: an old leader must reject writes after a newer term becomes active. The Raft paper is the primary reference for this replicated-state-machine model.

A Dynamo-style leaderless design sends writes to several replicas and lets coordinators collect W acknowledgements and reads collect R responses. The original Amazon Dynamo paper prioritizes availability and uses versioning plus conflict reconciliation. Quorum intersection such as R + W > N increases the chance a read overlaps a successful write, but it is not automatically linearizability. Sloppy quorums, concurrent writes, clock-based conflict resolution, coordinator failure, or an acknowledgement before durable persistence can still weaken the contract.

The trade-off is that writes and linearizable reads depend on a live majority and network round trips. etcd’s API guarantees make this cost visible: linearizable reads consult consensus state, while cheaper serializable reads may be stale. If no majority is reachable, this design rejects writes rather than claiming both consistency and availability.

Trace the Durable Write Path

On the shard leader, validate the request and propose a checksummed record through the replicated log. In this design that consensus log is also the recovery WAL; do not add a second log without an implementation reason. After a majority durably records and commits the entry, each replica applies it to its in-memory memtable and the leader returns the assigned version. Group commit can amortize fsync, but the acknowledgement contract must still say when a successful write is stable.

When a memtable fills, freeze it, create a new mutable one, and flush the immutable data as a sorted SSTable. RocksDB’s memtable documentation describes this pattern. On restart, load the manifest and replay log records newer than the last durable flush.

Retries need idempotency. A client timeout does not reveal whether the write committed, so use an idempotency key or a compare-and-set version instead of blindly creating a second logical mutation. For deletes, append a versioned tombstone. Do not physically remove the older value until compaction knows that every relevant replica and snapshot has passed the tombstone’s safety horizon.

Trace the Read Path from Memtable to SSTables

A read first resolves the shard and consistency level. A linearizable read goes through the leader or a quorum-confirmed read path; an explicitly stale read may use an eligible follower. The node rejects obsolete routing generations. Locally, the engine checks the mutable memtable, immutable memtables, and then SSTables from newest to oldest.

Bloom filters skip SSTables that definitely lack a key; sparse indexes locate the likely block, and a block cache serves hot blocks. Bloom filters may return false positives but not false negatives, so they reduce I/O without proving presence.

Return the newest visible value or tombstone. Followers catch up from the committed log, while rebuilt replicas use a snapshot plus the later log suffix. A stale read reduces latency but can return an older committed version, so label that contract instead of calling every read “strongly consistent.”

Explain Compaction as Correctness Plus Resource Control

Compaction merges SSTables, keeps the newest visible version, discards obsolete versions when safe, and eventually reclaims tombstones and expired values. It also trades write amplification for lower read amplification and bounded file counts.

Leveled compaction reduces overlapping ranges and favors predictable reads but rewrites data more often. Size-tiered compaction favors ingest by grouping similar files, but reads may inspect more files and temporary space rises. Choose for the workload; neither is universally best.

The operational point is compaction debt. If flushes create files faster than compaction consumes them, read amplification, disk use, and latency rise together. Monitor pending bytes, level-zero files, stalls, bandwidth, and free space. Apply backpressure before exhaustion. RocksDB’s tuning guidance notes that rate-limiting background I/O can reduce latency outliers.

Recover from Replica, Zone, and Data Divergence Failures

Separate fast repair from guaranteed convergence. During a brief replica outage, hinted handoff can temporarily retain missed mutations. Read repair fixes versions discovered on the foreground path. Neither proves that cold keys are consistent.

Run anti-entropy in the background by comparing hashes over matching token ranges and streaming only divergent ranges. Apache Cassandra’s repair documentation describes Merkle-tree comparison and the I/O cost of repair. Schedule and throttle it; a repair storm can harm the healthy serving path. In the leaderless alternative, hints and foreground read repair reduce divergence but remain best effort rather than replacements for anti-entropy.

For permanent loss, rebuild from a verified snapshot plus the log suffix, then route traffic only after catch-up. Test torn log records, corruption, full disks, partitions, stale leaders, zone loss, and crashes during compaction. Checksums detect damage; replicas enable recovery.

Define Observability and the Failure Matrix

Track p50/p95/p99 latency and errors by operation and consistency level, plus per-shard QPS, skew, replica lag, elections, fsync, flushes, SSTables per read, cache and Bloom-filter usefulness, compaction debt, stalls, repair age, checksum failures, disk headroom, and rebalance progress.

Then narrate failure behavior instead of saying “the system is highly available”:

Replica or zone fails: continue only while a durable majority remains; spare capacity must absorb the load.
Network partitions: only the majority side accepts linearizable writes.
Hot shard: split or move it; for one indivisible key, cache safe reads, rate-limit, or redesign.
Compaction lags: throttle writes before disk space and latency collapse.
Request times out: retry idempotently because the commit result may be unknown.

Key-Value Store System Design Interview FAQ

Is consistent hashing required for a distributed key-value store?

No. Consistent hashing is useful for point-heavy workloads because it limits movement when membership changes. Fixed logical shards also work, and range partitioning is better when ordered scans matter. The requirement determines the partitioner; rebalancing safety and hot-key handling matter more than naming the algorithm.

Does `R + W > N` guarantee linearizable reads?

Not by itself. It creates quorum intersection, but linearizability also requires well-defined version ordering, durable acknowledgements, correct handling of concurrent writes, and rules that prevent stale or sloppy replicas from satisfying the wrong contract. Consensus is the clearer choice when a single real-time order is mandatory.

Why use both a WAL and SSTables?

The WAL makes recent acknowledged mutations recoverable before their in-memory memtable is flushed. SSTables store sorted, immutable data efficiently for reads, compaction, and snapshots. After a crash, the engine loads durable SSTables and replays the unflushed WAL suffix.

Why can tombstones not be deleted immediately?

An unavailable replica may still contain the old value. If the tombstone disappears before that replica is repaired, the old value can reappear. Reclaim tombstones only after the system’s repair, replica, and snapshot rules establish that no relevant reader or replica needs them.

What is compaction debt?

Compaction debt is the queued work required to merge accumulated SSTables and reclaim obsolete data. Rising debt increases file counts, read amplification, temporary space needs, and tail latency. It needs explicit metrics, I/O budgets, disk headroom, and write backpressure.

Final Takeaway

The strongest answer follows one key through routing, replication, durable acknowledgement, memtables, SSTables, compaction, repair, and rebalance. Make consistency a client contract, not a CAP slogan, and budget compaction and repair as real capacity.

Sources and Further Reading

Research note: This guide was checked on August 31, 2026. Capacity figures are interview assumptions, while implementation details and guarantees should be verified against the cited primary documentation for the system being discussed.