Distributed Key-Value Store

In plain words

A key-value store is the simplest database there is — put(key, value) and get(key) — spread across many machines so it survives any one of them dying. The hard part is not storing bytes; it is deciding what a reader is promised when the copies disagree. This problem is where "consistency", "replication" and "quorum" stop being vocabulary and become dials you set.

Four decisions, in order:

1. Placement — which node owns a key?
2. Replication — how many copies, and where?
3. Consistency — what does a read guarantee?
4. Failure — what happens when a replica or the network is gone?

1. Placement: a ring, not a modulo

The naive rule, hash(key) % N, is a trap: go from 10 nodes to 11 and about 90% of keys move to a different node. Consistent hashing puts nodes and keys on a ring; a key belongs to the first node clockwise from its hash. Adding a node moves only about 1/N of keys, all from one neighbour.

The refinement that makes it work is virtual nodes: each physical node sits at 100–200 points on the ring. Without them, random placement leaves some nodes with huge arcs and others with slivers, and a node leaving dumps its whole load on a single neighbour.

2. Replication: the next N nodes clockwise

Store each key on the next N distinct physical nodes clockwise (distinct matters — with virtual nodes the next three ring positions could be the same machine). N = 3 is the usual choice.

3. Consistency: two dials, W and R

A quorum is the minimum number of copies that must agree before an operation counts as done. The trick is to make it a setting:

• W — replicas that must acknowledge a write.
• R — replicas that must respond to a read.

This is the CAP trade-off turned into two numbers the caller chooses per request, instead of a fixed property of the system.

def put(key, value, W=2):
    version = clock.next(key)                     # vector clock or timestamp
    acks = 0
    for node in ring.replicas(key, N=3):          # send to all three
        if node.write(key, value, version): acks += 1
        if acks >= W: return True                 # answer as soon as W have it
    raise WriteFailed                             # fewer than W alive: refuse

def get(key, R=2):
    answers = [n.read(key) for n in ring.replicas(key, N=3)][:R]  # wait for R
    newest = max(answers, key=lambda a: a.version)
    for a in answers:
        if a.version < newest.version: a.node.write(key, newest.value, newest.version)  # read repair
    return newest.value

Conflicts: when two copies both think they are right

With W=2 and two clients writing the same key at the same moment through different coordinators, two replicas can hold different values with no "newer" between them. Three ways to settle it:

4. Failure handling

• Hinted handoff (in the diagram): a healthy node accepts writes meant for a down node and replays them when it recovers.
• Anti-entropy with Merkle trees: replicas compare hash trees of their key ranges (a hash per chunk, then a hash of the hashes, up to one root) to find where they differ without streaming the whole dataset, then repair.
• Gossip: nodes swap membership and health with a few random peers every second. Failure detection with no central monitor and no single point of failure.

Where this design breaks

• Hot keys. The ring spreads keys evenly, not traffic. One viral key still lands on N nodes and can saturate them. Cache it in front.
• Large values. The design assumes small values. Multi-megabyte values make replication bandwidth, not storage, the binding constraint.
• Range scans. Hash placement destroys key order, so "all keys between X and Y" means asking every node. If you need ranges, you want range partitioning and its hot-spot problem instead.
• Cross-key transactions. Two keys can live on disjoint node sets, so there is no atomic multi-key write without a coordination protocol this design does not have.
• Clock skew. Any last-write-wins scheme is only as trustworthy as NTP, the protocol that keeps clocks in sync — good to milliseconds, not microseconds.

Take this with you

• The one idea: placement, replication, consistency and failure are four separate decisions. Make each one on purpose.
• In an interview, draw the ring, say "N copies, W to write, R to read, R + W > N for fresh reads", and name one way to settle conflicts.
• At work, check what W and R your store actually runs with. The default is often the fast one, and "we read our own write back" is not guaranteed there.