07 - Design a Key-Value Store

📋 Jump to Takeaways

🎁 Just two operations: PUT and GET. The data model is trivial, but distributing it across hundreds of machines without losing data is one of the hardest problems in computing.

A key-value store maps keys to values, the simplest data model possible. Just PUT(key, value) and GET(key). No schemas, no joins, no SQL. Think Redis, DynamoDB, or Memcached.

The data model is trivial, but distributing it across many machines introduces the core challenges of distributed systems: how to split data, how to keep copies, and what to do when machines disagree.

Key-Value Store Requirements

Key-Value Store Functional Requirements

PUT(key, value): store a value (overwrite if key exists)
GET(key): retrieve the value (return null if not found)
DELETE(key): remove a key-value pair
Keys are strings (max 256 bytes), values are blobs (max 10 KB)

Key-Value Store Non-Functional Requirements

Metric	Target
Scale	100 TB of data across many machines
QPS	500K reads/sec, 100K writes/sec
Latency	p99 < 10ms reads
Availability	99.99% (~52 min/year, ~4.3 min/month, ~0.9 sec/day)
Durability	No data loss once a write is acknowledged

Key-Value Store Scope Exclusions

Range queries (that's a sorted store like Cassandra)
Transactions across multiple keys
Complex data types (lists, sets, that's Redis)

Key-Value Store Estimation

Key-Value Store Traffic

600K total ops/sec
A single server handles about 50K ops/sec → need at least 12 servers for throughput
100 TB at 2 TB SSD per server → need about 50 servers for storage
With 3× replication → about 150 nodes total

Storage is the binding constraint, not throughput. 150 nodes easily handle 600K ops/sec.

Key-Value Store High-Level Design

┌─────────────────────────────────────────────────────────────────┐
│                      KEY-VALUE STORE                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌──────────┐     ┌──────────────┐                              │
│  │  Client  │────►│  Coordinator │                              │
│  │          │◄────│  (any node)  │                              │
│  └──────────┘     └──────┬───────┘                              │
│                          │  hash(key) → find node on ring       │
│              ┌───────────┼───────────┐                          │
│              ▼           ▼           ▼                          │
│       ┌──────────┐ ┌──────────┐ ┌──────────┐                    │
│       │ Node A   │ │ Node B   │ │ Node C   │  ...               │
│       │ (primary)│ │ (replica)│ │ (replica)│                    │
│       └──────────┘ └──────────┘ └──────────┘                    │
│                                                                 │
│       Nodes on a hash ring (consistent hashing)                 │
│       Each key → hash → next node clockwise = primary           │
│       Replicated to N-1 additional nodes                        │
└─────────────────────────────────────────────────────────────────┘

Three problems to solve:

Partitioning: which node stores which keys?
Replication: how to keep copies for durability?
Consistency: what happens when replicas disagree?

Key-Value Store Deep Dive

Partitioning: Consistent Hashing

With 50+ nodes, how do you decide where a key lives?

Naive approach: hash(key) % N

Works until you add or remove a node. Changing N remaps almost every key → massive data migration.

Better: Consistent hashing

Arrange nodes on a virtual ring. Hash the key → find the next node clockwise:

        Node A
       /      \
    Node D     Node B
       \      /
        Node C

Key "user:123" → hash → lands between A and B → stored on B
Add Node E between A and B → only keys between A and E move

Why this matters: Adding a node moves only ~1/N of keys (not all of them). Removing a node is the same. Only its keys redistribute to the next neighbor.

Virtual nodes: Each physical node gets 100+ positions on the ring. Without this, some nodes get more keys by chance. Virtual nodes make distribution statistically even.

Replication

One copy = data loss when that node dies. Store each key on N=3 nodes:

Key "user:123" → primary: Node B
                 replica 1: Node C (next clockwise)
                 replica 2: Node D (next after that)

Tradeoff: Every write goes to 3 nodes (write amplification). But any single node can die without data loss or downtime.

Consistency: The Quorum Rule

With 3 replicas, how many must acknowledge a read or write?

W (write ack)	R (read ack)	W+R > N?	Guarantee
2	2	4 > 3 ✓	Strong consistency, always read latest
1	1	2 > 3 ✗	Eventual, may read stale data, but fastest
1	3	4 > 3 ✓	Fast writes, consistent reads
3	1	4 > 3 ✓	Slow writes, fast reads

The rule: W + R > N guarantees you read the latest write. At least one node in the read set must have the latest value because the write and read sets overlap.

What if W + R ≤ N? You might read from nodes that all missed the latest write, returning stale data. This is eventual consistency: fast, but you accept the risk of reading an old value until replicas sync up.

What if replicas disagree? Each value has a timestamp. The coordinator returns the value with the latest timestamp and repairs the stale replica in the background.

Node Failure Recovery

Temporary failure (node comes back in minutes):

Hinted handoff: writes meant for the dead node go to a neighbor with a "hint." When the node recovers, hints are replayed. No data lost.

Permanent failure (disk dead, node replaced):

Anti-entropy: background process compares replicas and copies missing data to the new node.

Network partition (nodes can't talk to each other):

AP choice (DynamoDB): Both sides keep serving. Conflicts resolved later (last-write-wins).
CP choice (ZooKeeper): Minority side stops. Majority continues. No conflicts, but reduced availability.

This is the CAP theorem (Consistency, Availability, Partition tolerance, pick two during a network partition) in practice. During a partition, you choose availability or consistency.

Data Flow

PUT("user:123", "{name: alice}"):
  1. Client → any node (coordinator)
  2. Coordinator hashes key → Node B is primary
  3. Forward write to B, C, D (N=3)
  4. Wait for W=2 acks → respond success to client

GET("user:123"):
  1. Client → coordinator
  2. Coordinator → read from R=2 nodes (B, C)
  3. Both return same value → return to client
  (If they disagree → return latest timestamp, repair stale one)

Key Takeaways

Consistent hashing distributes keys with minimal disruption

Adding or removing a node moves only ~1/N of keys. Virtual nodes ensure even distribution. This is why every distributed database uses it.
Replication (N=3) provides durability and availability

Any single node can die without data loss. The cost is 3× write amplification, every write goes to three nodes.
W + R > N guarantees strong consistency

The quorum overlap ensures at least one read node has the latest write. Tuning W and R lets you trade consistency for speed.
CAP theorem forces a choice during network partitions

AP (keep serving, resolve conflicts later) or CP (stop minority, guarantee consistency). Most key-value stores choose AP because availability matters more for their use cases.
The data model is simple, but distribution is hard

PUT/GET/DELETE is trivial. Partitioning, replication, quorums, and failure handling are where the real complexity lives. This is why it's a popular interview question.

Want to go deeper? The example "Key-Value Store at Scale" covers storage engine internals: LSM Trees, Write-Ahead Logs, compaction, tombstones, and B-Tree vs LSM tradeoffs.

🎁 Your system needs to run a million tasks on schedule, retry failures, and never execute the same job twice. How do you coordinate that?