Design a Key-Value Store

Design a Key-Value Store

Step 1 of 11

N3

The key is hashed to a partition, and that partition lives on three machines, not one.

The Idea

Store a value on three machines and still answer correctly while one of them is unreachable. Keys are hashed into partitions, each partition is replicated, and a quorum decides what counts as done.

Real-World Example

Three copies of the same register kept in three offices. Reading two of them is safe as long as every change also reached two, because then no pair of offices can both be out of date.

N = 3 replicas    W = 2 acks    R = 2 reads
put(k, v): send to 3, return once 2 acknowledge
get(k):    read 2, take the higher version,
           repair the stale replica in the background

The Tradeoff

Raising W buys durability and costs write availability; lowering it makes writes cheap and hands you two versions to reconcile later. Quorum is a dial between those, not an escape from them.

Your turn

Put the steps in the right order.

1. 1Return the higher version to the caller↑↓
2. 2Hash the key to its partition and find the three replicas↑↓
3. 3Repair the stale replica in the background↑↓
4. 4Read from two replicas and compare their versions↑↓

Check order

Mini quiz

1 / 3

R + W > N guarantees that:

• AWrites are faster
• BReplicas never disagree
• CThe read set and the write set share at least one replica
• DNodes cannot fail