← CatZep/Engineering Guides/System Design/Foundations

Consistent Hashing & Designing a Key-Value Store

A system-design interview guide to the one idea that makes distributed storage tractable: how to spread keys across a changing set of servers without reshuffling everything, and how that single technique becomes the backbone of a partitioned, replicated, tunable key-value store.

Almost every distributed data system has to answer the same question first: given a key, which machine holds it? When there is exactly one machine the answer is trivial, but the moment you have several — and especially when that number changes as machines come and go — the mapping becomes the whole game. Consistent hashing is the technique that keeps that mapping stable under change, and it turns out to be the foundation that the rest of a key-value store is built on. This guide starts from the naive approach, shows why it falls apart, develops consistent hashing and virtual nodes, and then uses it as the partitioning layer of a complete distributed key-value store — replication, the CAP tradeoff, tunable quorums, conflict resolution, and the background machinery that keeps replicas honest.

Concepts to understand first

Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.

1. The Problem Setting: A Distributed Key-Value Store

Consistent hashing is usually asked inside a bigger question: design a distributed key-value store (think Amazon Dynamo, Apache Cassandra or Riak). Start with the requirements, because they explain why each later mechanism exists.

Clarifying questions worth asking: How big is the data? What is the read/write ratio? Is stale data ever acceptable, and for how long? Must a write never be lost? Single data center or several?

2. Back-of-the-Envelope Estimation

Practice numbers (assumptions): 10 billion keys, 1 KB average value, replication factor N = 3, 100,000 reads/s and 20,000 writes/s at peak. Each node has 2 TB of disk and we fill it to 70%.

3. API and Data Model

get(key)                  -> (value(s), context)   # may return several siblings on conflict
put(key, context, value)  -> ok                    # context carries the version (vector clock)
delete(key, context)      -> ok                    # usually writes a tombstone

Deletes write versioned tombstones so replicas can learn the deletion. Safe garbage collection must wait for the required repair/offline horizon; collecting too early can resurrect an old value.

4. The Problem with Naive Hashing

Suppose you have N servers and you want to spread keys evenly across them. The obvious scheme is to hash the key to an integer and take it modulo the server count:

server_index = hash(key) % N

While N stays fixed this works beautifully. The hash spreads keys uniformly, the modulo folds them into the range 0 .. N-1, and every server gets roughly the same share. The trouble is the N in that formula. The instant the server count changes — a machine is added to grow capacity, or one fails and drops out — N becomes a different number, and the modulo of nearly every key changes with it.

Concretely, suppose you have 4 servers and add a 5th. A key that hashed to 1000 maps to 1000 % 4 = 0 before and 1000 % 5 = 0 after, so it happens to stay. But 1005 moves from server 1 to server 0, 1006 moves from 2 to 1, and 1004 moves from 0 to 4. A key stays put only when h % N == h % (N+1), which happens for just 1/(N+1) of hash values. So going from N to N+1 servers remaps about N/(N+1) of all keys. With 10 servers growing to 11, a simulation over 100,000 keys moved 90.8% of them (the formula says 10/11 = 90.9%). Almost everything moves.

5. Consistent Hashing

Hash tokens and keys into a compatible common ordered space. Their hash algorithms need not literally be identical, but every participant must use the same placement rules and membership version. Sort tokens; a key belongs to the first token at or clockwise after its hash, wrapping to the first token if necessary. A token at t owns the interval (previous counterclockwise token, t].

from bisect import bisect_left

def owner(tokens, owners, position):
    if not tokens or len(tokens) != len(owners):
        raise ValueError('nonempty, aligned ring required')
    # Precondition: tokens are unique and sorted; position is in their hash space.
    return owners[bisect_left(tokens, position) % len(tokens)]

Adding a token transfers its new owned interval from its clockwise successor. With equally weighted physical nodes and good token allocation, adding a node to n nodes moves about 1/(n+1) of primary ownership in expectation; removing one moves about 1/n. Real token intervals, weights, replica placement, and migration state determine actual bytes transferred.

A transient suspected failure does not necessarily remove a member from the ring. Separate stable membership/rebalancing from temporary replica routing, or brief outages can trigger unnecessary mass migrations.

6. Virtual Nodes

Plain consistent hashing has a weakness: with only one point per server, the arcs between servers are uneven. A server that happens to land far from its clockwise predecessor owns a large arc and a heavy share of keys; one that lands in a crowded stretch owns almost nothing. With a handful of servers this variance can be severe, and it gets worse when a server leaves — its entire arc dumps onto a single neighbor, which can then become a hotspot.

Virtual nodes fix this by giving each physical server many points on the ring instead of one. A server s0 is hashed under several derived labels — s0_0, s0_1, s0_2, and so on — and each label lands at its own position. A key still belongs to the first point clockwise, but that point now maps back to whichever physical server owns it.

• Smoother load. Scattering many small arcs per server averages out the gaps, so each physical server ends up with a share close to its fair fraction of the ring. More virtual nodes per server means lower variance.
• Graceful failure. When a server leaves, its many small arcs are absorbed by many different neighbors rather than dumped on one. The departing load spreads across the cluster instead of creating a single hotspot.
• Heterogeneous capacity. A more powerful machine can be given proportionally more virtual nodes, so it naturally owns a larger share of the ring without any special-case logic.

function build_ring(servers, vnodes_per_server):
  ring = empty()
  for s in servers:
    for i in range(vnodes_per_server):
      ring.insert(hash(f"{s.id}_{i}"), s)  # many points, one server
  return ring                              # lookup() is unchanged

You can see the effect with a short simulation: 10 servers, 100,000 keys, MD5 as the hash, and a varying number of virtual nodes per server.

import bisect, hashlib

def h(text):
    return int.from_bytes(hashlib.sha256(text.encode()).digest()[:8], "big")

def build(servers, v):
    if not servers or len(servers) != len(set(servers)) or type(v) is not int or v <= 0:
        raise ValueError("unique nonempty servers and positive vnode count required")
    ring = sorted((h(f"{server}#{i}"), server) for server in servers for i in range(v))
    if len({point for point, _ in ring}) != len(ring):
        raise ValueError("token collision: choose a deterministic collision policy")
    return [p for p, _ in ring], [server for _, server in ring]

def owner(points, owners, key):
    if not points or len(points) != len(owners):
        raise ValueError("nonempty aligned ring required")
    return owners[bisect.bisect_left(points, h(key)) % len(points)]

With one point per server, the busiest server carried two and a half times its fair share. The spread shrinks roughly like 1/√v as you add virtual nodes v. (Your exact numbers will vary with the hash and key set.) For reference, Apache Cassandra used 256 tokens per node by default for years, and lowered the default to 16 in version 4.0 with a smarter token allocator.

7. Replication

Up to here a key has exactly one owner, so a single server failure loses data and stalls every request for the keys it held. A real key-value store keeps each key on more than one server. The ring makes the replica set fall out naturally: store each key on the first N servers you meet walking clockwise from the key's position (its owner plus the next N-1), where N is the replication factor.

The one subtlety is virtual nodes. Because a single physical server appears at many points on the ring, naively taking the next N points clockwise might land on several virtual nodes that all belong to the same physical machine — which would defeat the purpose of replicating. So when collecting the replica set you walk clockwise but skip points that map to a physical server already chosen, until you have N distinct physical servers. These N servers are often called the key's preference list.

function replica_set(key, ring, N):
  pos = hash(key)
  chosen = []
  for vnode in ring.points_clockwise_from(pos):
    server = ring.server_at(vnode)
    if server not in chosen:               # skip virtual duplicates
      chosen.append(server)
    if len(chosen) == N:
      break
  return chosen                            # the preference list

N distinct durable copies can retain a key after at most N−1 copy losses, assuming a surviving valid copy and a recovery protocol. That does not guarantee read/write availability: required R/W thresholds may no longer be reachable. Prefer independent failure domains, and reject a replica-set request that exceeds available distinct owners.

8. The CAP Theorem

CAP concerns a service's behavior during a partition, when messages between groups can be lost or delayed indefinitely. C means linearizability: operations behave like one copy and respect real-time order. A means every eligible request to a nonfailed node completes successfully, not merely that it returns an error quickly. You cannot promise both across the partition.

A quorum-based authority can continue on the majority side and reject or block operations on the minority. A locally writable mergeable store can remain available with weaker ordering. Neither choice alone defines durability: an AP event log can preserve both concurrent records, and a CP system can still lose data if its acknowledged state was not durable.

P is a failure condition the model permits, not a third feature to switch off. Outside partitions, coordination still trades latency against stronger ordering (the PACELC observation).

9. Tunable Consistency: N, W, R

Let N be the fixed set of replicas for a key, W the durable responses required for a completed write, and R the responses used by a read. R + W > N guarantees each such read set intersects that write set. 2W > N makes write quorums overlap. For N=3 and R=W=2, one unavailable replica still permits both operations.

Overlap is useful only if a replica in the intersection retains the relevant version and the read can identify it. It is not automatically linearizability. A read may observe an in-progress write that a later read misses; a failed write can leave partial state; sloppy quorums use stand-ins outside N; wall-clock LWW can discard a later logical update. Vector clocks expose concurrent siblings rather than defining one globally latest value.

A linearizable atomic-register algorithm such as ABD uses versioned quorum reads and a write-back phase before the read returns. A consensus log instead orders committed commands, and linearizable reads establish current authority and wait for applied state. Do not label a Dynamo-style overlap rule as a consensus implementation.

10. Versioning & Conflict Resolution

Quorums tell you how many replicas to wait for, but not how to decide which value is "newest" when two writes happened without seeing each other — for example on opposite sides of a partition, or with W < N. The store needs a way to attach a version to each value and to detect when two versions are concurrent rather than one being a clean successor of the other.

The difference is what they do with a true conflict. Vector clocks detect it and preserve both versions (called siblings) so nothing is lost until something merges them — a shopping cart, for instance, can union the two carts. Last-write-wins resolves it immediately by picking a winner, which is fine when losing one of two concurrent updates is acceptable and is far easier to operate.

function compare(v_a, v_b):  # illustrative pseudocode
  if v_a == v_b: return EQUAL
  if all(a >= b) and any(a > b): return KEEP_A
  if all(b >= a) and any(b > a): return KEEP_B
  return CONCURRENT  # retain siblings or application-merge

function resolve_lww(a, b):
  # Total deterministic tie-break; selects one, does not preserve both.
  return max([a, b], key=(wall_timestamp, stable_writer_id, operation_id))

11. Anti-Entropy with Merkle Trees

Replicas drift apart over time — a write that only reached W of N nodes, a node that was down during an update, a dropped message. The store needs a background process to find and repair these divergences without comparing every key on every replica, which would be hopelessly expensive for large datasets. This reconciliation is called anti-entropy, and the efficient tool for it is the Merkle tree.

Merkle roots compare canonical key/value/version encodings over compatible ranges and a consistent view. Matching roots imply matching encoded content only under a negligible-collision assumption. Differing branches identify candidates for version-aware repair; concurrent writes and tombstone retention must be handled.

The win is the amount of data exchanged. To find the differences between two replicas you transfer and compare only hashes along the divergent paths. When only a few buckets differ, that is about (number of differing buckets) × (tree depth) hashes, and tree depth is logarithmic in the number of buckets. That is far less than shipping every key across to compare. (If almost everything differs, the tree saves nothing and you end up comparing most of it.) Once the differing buckets are pinpointed, only those keys are exchanged and repaired.

12. Failure Handling

The final pieces keep the cluster coherent as nodes come and go. Two lightweight mechanisms cover the common cases.

• Gossip can disseminate versioned membership/suspect information efficiently when communication resumes, but does not prove one identical view within a fixed number of rounds during a partition. Separate stable membership changes from temporary failure suspicion; a replicated authority may coordinate changes without an unavoidable single point of failure.
• Hinted handoff for temporary failures. When a write's target replica is briefly unreachable, the coordinator does not simply fail. It writes the value to another healthy node along with a hint recording which node the data really belongs to. When the intended replica recovers, the holder replays the hinted writes to it and then discards the hint. This keeps writes available through short outages and lets the cluster heal itself once the node returns. Counting these stand-in writes toward W is called a sloppy quorum: it raises availability but weakens the W + R > N overlap guarantee.

function gossip_round(self, peers):
  peer = random.choice(peers)
  merge(self.membership, peer.membership)  # exchange + reconcile views

function write_with_handoff(key, value, replicas):
  for r in replicas:
    if r.is_up():
      r.store(key, value)
    else:
      backup = pick_healthy_node()
      backup.store_hint(key, value, intended=r)  # replay when r returns

13. Tradeoffs and Alternatives

The ring is not the only way to map keys to nodes. Know at least these, and when each fits.

Worked example: adding one token and reading replicas

Use a toy ring numbered 0–99. These are hash positions, not literal key names.

Run a small, testable model

Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:

python3 concepts.py hashing
python3 concepts.py test

The model checks clockwise ownership at exact token boundaries and demonstrates that only the inserted token's interval changes.

The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.

14. A 45-Minute Interview Walkthrough

15. Common Mistakes

• Forgetting virtual nodes. A ring with one point per server is badly unbalanced (2.5× overload in the simulation above).
• Picking replicas by ring points, not machines. Two virtual nodes of the same machine are not two replicas. Real systems also spread replicas across racks or zones.
• Claiming W + R > N means perfect consistency. Sloppy quorums and concurrent writes still cause anomalies.
• Using last-write-wins for data you cannot lose. LWW silently drops one of two concurrent writes.
• Deleting without tombstones. A replica that missed the delete will “repair” the value back to life.
• Treating a temporary failure as permanent. Moving all of a node's data after a 30-second blip causes a huge, needless data transfer. Use hinted handoff for short outages; rebalance only when a node is declared dead.

16. Summary

A distributed key-value store is consistent hashing plus a series of deliberate tradeoffs layered on top of it:

17. Check Yourself

1. A cache cluster grows from 9 to 10 servers using hash % N. Roughly what fraction of keys now miss?
   Answer

   About 9/10 = 90%. Only keys where h % 9 == h % 10 stay, which is 1/10 of them.

2. Same growth with a consistent hashing ring. About what fraction of keys move?
   Answer

   About 1/10. Only the keys on the arc the new server takes over move, and they all come from its neighbors.

3. Why can't the replica set just be “the next 3 points on the ring” when you use virtual nodes?
   Answer

   Several consecutive points may belong to the same physical machine. Losing that machine would lose all “replicas” at once. Skip points whose machine is already chosen.

4. N = 5. You want reads and writes to each survive two replicas being down, and reads to always overlap the latest write. Pick W and R.
   Answer

   W = 3, R = 3. Each needs 3 of 5, so each survives 5 - 3 = 2 failures, and 3 + 3 = 6 > 5 guarantees overlap.

5. Two clients update the same shopping cart on opposite sides of a partition. What does a vector-clock store do, and what does an LWW store do?
   Answer

   The vector-clock store sees the versions are concurrent and keeps both as siblings, so the app can merge the carts. LWW keeps the one with the later timestamp and silently drops the other.

6. Two replicas each hold 1 million keys split into 1,024 buckets, and exactly one bucket differs. About how many hashes must they compare with a binary Merkle tree?
   Answer

   About 2 × log₂(1024) = 2 × 10 = 20 hashes along one path (plus the root), instead of 1 million keys.

18. Key Terms

Hash ring

The hash output space treated as a circle, holding both keys and servers.

Virtual node (vnode / token)

One of many ring points owned by a single physical server.

Preference list

The N distinct servers that hold copies of a key.

Quorum (N, W, R)

Replication factor, write acks needed, and read replies needed.

Sloppy quorum

Counting stand-in nodes toward W or R when real replicas are down.

Hinted handoff

A stand-in node keeps a write plus a note, then hands it to the real owner later.

Vector clock

Per-node counters attached to a value that detect concurrent writes.

Siblings

Conflicting versions of one key kept side by side until merged.

Tombstone

A marker that records a delete so repair does not resurrect old data.

Anti-entropy

Background repair that finds and fixes replica differences, often with Merkle trees.

Gossip

Nodes swap membership info with random peers until everyone agrees.

19. Further Reading

• Karger et al., “Consistent Hashing and Random Trees” (STOC 1997), the original paper.
• DeCandia et al., “Dynamo: Amazon's Highly Available Key-value Store” (SOSP 2007). Most of this page follows its design.
• Martin Kleppmann, Designing Data-Intensive Applications, chapters 5 (Replication) and 6 (Partitioning).
• Lamping and Veach, “A Fast, Minimal Memory, Consistent Hash Algorithm” (2014), jump consistent hash.
• Thaler and Ravishankar, “Using Name-Based Mappings to Increase Hit Rates” (1998), rendezvous hashing.
• Alex Xu, System Design Interview, Vol. 1, chapters “Design Consistent Hashing” and “Design a Key-Value Store”.