Distributed Key-Value Store · Approach · designlab

Distributed Key-Value Store · Approach · designlab

Analysis

Reason about the problem

Approach

Turn it into a plan

Solution

The complete design

01 · Develop the design

Plan the design

Place keys on a consistent-hash ring, replicate each to N nodes, and let a coordinator succeed a write after W acknowledgements and a read after R answers, repairing divergent replicas in the background.

Stage 1

Hash keys onto a ring

Consistent hashing with virtual nodes spreads keys evenly and moves only a small share when nodes join or leave. A key's N replicas are the next N distinct nodes on the ring.

Stage 2

Pick W and R deliberately

R + W > N gives read-your-writes overlap. W = N makes every node failure a write outage.

Stage 3

Repair what the quorum missed

Use hinted handoff while a node is down, then read repair and anti-entropy to converge replicas.

02 · Work through the method

Step-by-step approach

Each node owns many virtual-node tokens on a hash ring; a key's preference list is the next N distinct physical nodes clockwise from its hash.
Any node can coordinate: it sends a write to all N replicas and acknowledges the client once W have persisted it, tagging the value with a version vector.
A read asks R replicas, returns the newest version, and repairs replicas that answered with older versions.
When a replica is unreachable, another node stores a hint and replays it on recovery; periodic Merkle-tree comparison fixes remaining drift.

03 · Justify the choices

Why this approach works

With N = 3, which setting guarantees a read sees the latest acknowledged write?

W = 2, R = 2

R + W > N means every read quorum overlaps every write quorum in at least one replica.

What happens to a W = 3 write when one of three replicas is down?

It fails, because three acknowledgements are impossible

Requiring every replica makes writes unavailable during any single failure. W = 2 tolerates one.

How does a replica that missed writes catch up?

Read repair, hinted handoff and background anti-entropy

Hints replay writes held for a dead node; read repair and Merkle-tree anti-entropy fix anything still divergent.

04 · Plan the evidence

Validation strategy

With N = 3, W = 2, R = 2, reads and writes succeed while one replica is down.
With W = 3, writes fail while one replica is down.
A replica that missed writes converges after it returns.
Adding a node moves only the keys adjacent to its tokens.

Trade-offs to explain

Higher W and R improve consistency but add latency and reduce availability.
W = 1 is fast but can lose acknowledged writes if that node dies before replicating.
Version vectors expose conflicts to the client instead of hiding them with last-writer-wins.

Read the detailed solution Build my design