Design a distributed key-value store

Expected question

"Design a distributed key-value store. How do you partition and replicate data, choose consistency guarantees, handle node failures, and compact storage at scale?"

Variant forms

Same design, different framing:

• "Design a Dynamo/Cassandra-style key-value store for billions of keys."
• "How do you distribute keys when nodes are continuously added and removed?"
• "Design a store that remains writable during a data-center partition."
• "How do quorum reads and writes trade latency for consistency?"
• "What happens when a replica is down during a write?"
• "How do you prevent tombstones from resurrecting deleted values?"
• "Design compaction for an LSM-backed storage engine."
• "Why is this not simply a distributed cache?"

Where this actually gets asked

Foundational infrastructure prompt in databases, storage, and platform interviews. It is deliberately broader than a cache/CDN design: data is durable, replicas recover correctness, and clients need documented consistency semantics. Staff+ depth: partition lifecycle, anti-entropy, conflict policy, tail latency, and operational controls.

Executive summary

30-second thesis

I'd default a Dynamo-style partitioned, replicated store with consistent hashing, quorum R/W you can tune, and anti-entropy — and say out loud this is durable storage, not a cache.

2-minute answer

Clarify latency vs consistency, key/value sizes, and failure domains. Default: virtual nodes on a hash ring, N replicas across zones, client or coordinator quorum (e.g. N=3,R=2,W=2 H), hinted handoff + read repair / anti-entropy for missed replicas. Version with vector clocks or timestamp+actor; conflict policy explicit (LWW vs merge). Deletes are tombstones with GC story so resurrection doesn't bite. LSM + compaction for write-heavy engines; bound read amplification. Membership changes via epoch'd ring; streaming rebalance, not big-bang. Hot keys: cache tier or bucket splitting. Linearizability only for the ops that truly need consensus.

Quantitative trade-offs

What I'd ask them

1. What consistency does the product actually need per API?
2. Value size distribution and range-scan requirement?
3. Multi-DC active-active or primary region?

Requirements

Functional

• Put, get, delete, and optionally range/scan within a partition.
• Persist data across process and node failures.
• Replicate each key to configurable replicas and rebalance when membership changes.
• Expose consistency levels (eventual, quorum, or linearizable for selected operations).

Non-functional

• Scale horizontally to billions of keys and high mixed read/write throughput.
• Remain available through individual node failures; survive zone failure with appropriate placement.
• Bound data loss and stale-read behavior explicitly, not by implication.
• Recover disk space and read performance through compaction without halting writes.

Core entities

• Partition token: hash range / virtual-node identifier and current replica set.
• Record: key, value or tombstone, version/vector clock, TTL, checksum.
• Replica state: node, partition, epoch, log/SSTable position, health.
• Hint: intended replica, mutation, expiry, delivery status.
• Membership epoch: immutable ring/configuration version.
• Repair digest: key-range hash tree used for anti-entropy.

API / interface

PUT /v1/kv/orders/o_491?consistency=QUORUM
If-Version: 18
{ "value":{"status":"paid"}, "ttl_seconds":86400 }
→ 200 { "version":"19:us-east-1a" }
→ 409 version_conflict | 503 insufficient_replicas

GET /v1/kv/orders/o_491?consistency=ONE
→ 200 { "value":{"status":"paid"}, "version":"19:us-east-1a" }

DELETE /v1/kv/orders/o_491?consistency=QUORUM
→ 204

Staff+ callout: document whether QUORUM means R + W > N for a single stable replica set, and that it does not alone make multi-key operations serializable or protect against sloppy routing.

Data Flow

A coordinator routes the key to the current virtual-node replica set, writes a durable local log at each replica, and returns once the requested acknowledgements arrive. Reads consult enough replicas for the requested consistency and repair stale copies asynchronously or inline.

Rendering architecture diagram…

High-level design

routing/membership selects replicas, the storage engine persists local data, and background services converge replicas. The system is not a cache: disk durability, repair, tombstones, and backup are first-class.

Rendering architecture diagram…

Deep dive 1: partitioning and replica placement

Hash the key onto a consistent-hash ring with many virtual nodes per physical node, so adding a node moves only adjacent token ranges and smooths skew. Rendezvous hashing is a credible alternative when membership is modest and weighted placement matters. Keep a versioned membership epoch; coordinators must not write blindly to a stale ring during rebalance.

Replicate N=3 across distinct zones where possible. A hot key still concentrates on one logical partition, so use application-level bucketing or a different data model for unbounded hot counters. During streaming, read/write from both old and new owners or use a handoff epoch; do not declare the move complete until data is copied and repairs verify it.

Deep dive 2: CAP, quorum, and conflicts

Under a network partition, a Dynamo-style store chooses availability and partition tolerance for eventual-consistency writes; it may return divergent siblings. With N=3, W=2, R=2, R + W > N normally overlaps one replica and reduces stale reads, but tail latency rises and failures can make the request unavailable. Linearizable operations need a leader/consensus group per shard, sacrificing some availability during leader election.

Use version vectors or conditional versions for writes that cannot safely resolve by timestamp. Do not claim CAP means "choose two"; partitions are unavoidable and the real decision is behavior then.

Deep dive 3: storage engine and compaction

Writes append to a WAL then a memtable; flush produces sorted immutable SSTables. Reads check memtables, bloom filters, indexes, and a bounded number of SSTables. Size-tiered compaction minimizes write amplification for write-heavy workloads; leveled compaction controls read amplification at more rewrite cost. Throttle compaction so it cannot starve foreground IO, but monitor backlog because unbounded SSTables destroy tail reads.

Deletes are tombstones replicated like values. Retain them longer than maximum replica/hint outage; otherwise an old replica can resurrect deleted data during repair. TTL expiry also yields tombstones, so a high TTL churn workload needs capacity planning and compaction observability.

Deep dive 4: hinted handoff, repair, and failure modes

When an intended replica is down, a healthy node stores a bounded hint and later delivers it. Hints improve short-outage availability but are not a substitute for anti-entropy. Periodic Merkle-tree repair compares ranges and streams missing records; run incrementally to avoid saturating the cluster. Backups/snapshots protect against logical bugs and correlated deletion, which replication does not.

If a coordinator times out, the write may have reached some replicas; retry with a mutation id so replicas deduplicate. Apply overload shedding before queueing unbounded writes. In 45 minutes, state the desired consistency per use case, then explain repair; do not conflate this durable store with the cache/CDN in entry 07.

What's expected at each level

• Mid-level: hash keys, replicate, read from a replica.
• Senior: consistent hashing, replication factor, quorum arithmetic, failure detection.
• Staff+: membership epochs/rebalance, consistency contract, conflict resolution, LSM compaction, tombstones, hinted handoff versus repair, backup and overload behavior.
• Principal: product-wide data classification, multi-region consistency tiers, migration strategy, operator experience, and cost/SLO governance.

Follow-up questions to expect

• "Why isn't this just Redis?" — Durability, recovery, and documented consistency. Cache can evaporate; this can't pretend to.
• "Replica down during write?" — Hinted handoff / retry; repair later. Say what W you chose and what that means for ack.
• "Tombstones forever?" — Bounded GC with a resurrection story you can explain; "delete" without tombstones comes back wrong.

Related

• 07 Distributed cache / CDN
• 05 Distributed unique ID generator
• 04 Distributed job scheduler
• 01 Distributed rate limiter