System Design: Build a Distributed Key-Value Store

A distributed key-value store maps keys to values across a cluster of machines, providing fast reads and writes at massive scale. DynamoDB, Cassandra, and Redis Cluster all follow this pattern. It’s one of the most commonly asked system design problems because it touches every fundamental distributed systems concept.

Functional Requirements

• put(key, value) — store a key-value pair.
• get(key) — retrieve the value for a given key.
• delete(key) — remove a key-value pair.
• Support keys up to 256 bytes and values up to 1 MB.
• Automatic data partitioning across nodes.
• Configurable replication for durability.

Non-Functional Requirements

• High availability — the system should serve reads and writes even during node failures.
• Horizontal scalability — adding nodes increases capacity linearly.
• Tunable consistency — let clients choose between strong and eventual consistency per request.
• Low latency — p99 under 10ms for single-key operations.
• Durability — no data loss once a write is acknowledged.

High-Level Architecture

Client
│
▼
Coordinator Node (any node can coordinate)
│
├──► Partition Map (consistent hash ring)
│
├──► Node A (partition 0-63)
├──► Node B (partition 64-127)
├──► Node C (partition 128-191)
└──► Node D (partition 192-255)
│
Each partition replicated to N nodes
(e.g., N=3: primary + 2 replicas)

Every node in the cluster can serve as a coordinator for any request. The coordinator uses the partition map to route the request to the correct nodes.

Data Partitioning

Consistent hashing distributes keys across nodes. Each node owns a range of the hash space. When a node is added or removed, only adjacent ranges are affected.

To avoid hotspots from uneven hash distribution, use virtual nodes: each physical node appears at multiple points on the ring. A node with more capacity gets more virtual nodes.

Partition map is the mapping from hash ranges to physical nodes. Every node holds a copy and updates are propagated via gossip protocol.

Replication

Each key is replicated to N nodes (typically 3). The coordinator writes to the primary node and N-1 replicas. Replicas are chosen as the next N-1 distinct physical nodes clockwise on the hash ring.

Write path:

1. Client sends put(key, value) to the coordinator.
2. Coordinator hashes the key, identifies N responsible nodes.
3. Coordinator sends the write to all N nodes in parallel.
4. Waits for W acknowledgments before responding to the client.

Read path:

1. Client sends get(key) to the coordinator.
2. Coordinator sends read requests to all N nodes.
3. Waits for R responses, returns the value with the highest version.

Consistency with Quorum

The values of N, W (write quorum), and R (read quorum) control the consistency-availability tradeoff:

A common setup: N=3, W=2, R=2 — tolerates one node failure while maintaining strong consistency.

Conflict Resolution

With W + R ≤ N, concurrent writes to the same key can produce conflicts. Two approaches:

Last-write-wins (LWW): attach a timestamp to each write; the latest timestamp wins. Simple but can lose data silently.

Vector clocks: each write carries a vector of logical clocks per node. On read, if versions are concurrent (neither dominates), the client receives both and resolves the conflict. DynamoDB and Riak use this approach.

Version 1: {A: 1, B: 0}  — written by node A
Version 2: {A: 0, B: 1}  — written by node B concurrently

These are concurrent → client must merge

Handling Failures

Failure detection: nodes monitor each other via gossip protocol. If a node doesn’t respond to heartbeats within a timeout, it’s marked as temporarily down.

Hinted handoff: when a target node is down, the coordinator writes to a healthy stand-in node with a “hint” indicating the intended recipient. When the target recovers, the stand-in forwards the data.

Anti-entropy with Merkle trees: nodes periodically compare Merkle trees of their data. A Merkle tree hashes ranges of keys hierarchically — differing branches pinpoint exactly which keys are out of sync, minimizing data transfer.

Permanent failure: if a node is permanently lost, a new node joins and copies data from replicas. The partition map is updated and gossiped to the cluster.

Storage Engine

Each node stores data locally using a Log-Structured Merge Tree (LSM) or a B-Tree:

• LSM Tree (used by Cassandra, RocksDB): writes go to an in-memory memtable, then flush to sorted SSTables on disk. Great for write-heavy workloads.
• B-Tree (used by traditional databases): in-place updates on disk pages. Better for read-heavy workloads with random access.

For a key-value store optimized for high write throughput, LSM is the standard choice.

Interview Talking Points

• Start with single-server, then explain why you need partitioning (data doesn’t fit on one machine) and replication (fault tolerance).
• Draw the consistent hash ring and explain virtual nodes.
• Show the quorum formula W + R > N and let the interviewer choose the tradeoff.
• Mention vector clocks for conflict resolution — it shows depth.
• Discuss the gossip protocol for failure detection and cluster membership.
• If time permits, mention read repair: when a read finds stale data on a replica, the coordinator pushes the latest version to it.