Design a Distributed Key-Value Store

Requirements

Functional: put(key, value) and get(key), nothing fancier — no queries, no joins. Non-functional: must survive individual node failure with no data loss; must scale horizontally (adding nodes increases capacity); tunable consistency (this is the classic CAP-theorem discussion question).

Core ideas to walk through

1. Partitioning (sharding): consistent hashing maps both keys and nodes onto a hash ring, so each key's owning node is a lookup, not a lookup table — and adding/removing a node only reshuffles the keys near it on the ring, not the whole keyspace.
2. Replication: each key is stored on N nodes (its owner plus the next N-1 nodes clockwise on the ring), so losing any single node doesn't lose data.
3. Consistency knobs: a write can require acknowledgment from W replicas before returning success; a read can query R replicas and merge. If W + R > N, every read is guaranteed to see the latest write (strong consistency) — if not, you get eventual consistency but lower latency.

Architecture

Handling node failure

Hinted handoff: if a replica node is temporarily down during a write, another node stores the write on its behalf with a "hint" to forward it once the original node recovers — keeps writes succeeding without waiting for the failed node. Read repair / anti-entropy: on reads, if replicas disagree, the newest version (by timestamp or vector clock) is returned and the stale replicas are updated in the background — this is how the system heals inconsistencies over time without a separate repair process.

Follow-up: how do you detect a node is actually down vs. just slow?

Gossip-based failure detection: nodes periodically exchange "I'm alive" heartbeats with a few random peers, and a node is marked suspect after missing enough heartbeats, then dead after a further timeout — this avoids a single point of failure in the failure-detection mechanism itself (no central health-check service to go down).