beginnerintermediateadvanced

System Design · Section 39

Consistent Hashing

Level: intermediate
Read: 15 min
Concepts: 3

Consistent hashing maps both nodes and keys onto a circular hash space (a ring) so that each key belongs to the next node found walking clockwise — used to route keys in distributed caches, partitioned datastores, and load balancers. Virtual nodes hash each physical node to many ring positions instead of one, evening out load that would otherwise depend on the luck of a few raw hash values. The payoff is minimal key movement: adding or removing a node changes only the arc(s) adjacent to it, moving roughly 1/N of all keys instead of the near-total reshuffle plain hash(key) % N causes on every membership change.

This section

Consistent Hashing - System DesignPiyush Garg

What is true here

Nodes and keys are hashed into the same circular space; a key's owner is the next node clockwise.
This is what distributed caches, partitioned datastores and load balancers use to route the same key to the same node consistently as membership changes.
Virtual nodes (~100-200 ring points per physical node) even out load that a single hash point per node would leave unbalanced.
Adding or removing a node only moves the keys on the arc(s) touching that node — about 1/N of all keys, not nearly all of them.

What you will be able to do

Explain why a ring routes keys more stably than hash(key) % N as nodes join or leave
Explain why virtual nodes are needed for even load distribution, not just correctness
Trace exactly which keys move (and to which node) when a node is added or removed
Recognize when a fixed shard count makes consistent hashing unnecessary overhead

The ring and what it is used for

How consistent hashing routes keys to nodes, and the three problem areas — caching, partitioning, routing — that rely on it.

What consistent hashing is for, and the ring concept

coreintermediate

Consistent hashing is a way to map both data (keys) and servers (nodes) onto the same circular hash space, called a ring, so that each key belongs to whichever node comes next on the ring in clockwise order. It solves a specific problem with plain "hash(key) % N" routing: with modulo hashing, adding or removing a single server changes the result of the modulo for almost every key, so almost every key gets remapped to a different server at once. On a ring, only the keys that fall between the changed node and its neighbor move — everyone else keeps pointing at the same node they always did. That is why it shows up anywhere a distributed cache, a partitioned datastore, or a load balancer needs to route the same key to the same node consistently, even as nodes come and go.

Think of it as

Picture a circular parking garage with numbered spots running 0 to 359 all the way around, and imagine security guards posted at fixed spots around that circle. Every car (a key) drives to its assigned spot number and then walks clockwise to the nearest guard — that guard owns it. If one guard goes home sick, only the cars between that guard's spot and the previous guard's spot need to walk further, to the next guard around the circle; every other car's nearest guard hasn't changed at all. Compare that to a system where cars are assigned to guards by "spot number mod number-of-guards" — remove one guard and that division changes for almost every car, so almost everyone has to find a new guard.

text

ring = sorted positions of hash(node_id) for every node
key's owner = first node position >= hash(key), walking
              clockwise (wrap around to the smallest
              position if none is found before 360°/2^32)

What we're doing: Place three nodes and one key on a ring, and find which node owns the key.

ring-lookup.txttext

Ring space: 0 to 359 (a circle, using degrees for readability)

Node positions (from hashing each node's id):
  Node A -> 40
  Node B -> 160
  Node C -> 300

Key positions (from hashing each key):
  key "user:42"   -> hash = 75
  key "user:99"   -> hash = 310

Lookup for "user:42" (75):
  walk clockwise from 75 -> first node found is B (160)
  owner = Node B

Lookup for "user:99" (310):
  walk clockwise from 310 -> wraps past 360/0 -> first node
  found is A (40)
  owner = Node A

9: "user:42" hashes to 75, which is not a node position — the lookup keeps walking clockwise.
13: The first node reached clockwise from 75 is Node B at 160, so Node B owns this key.
17: "user:99" at 310 wraps around past the 360/0 boundary before reaching Node A at 40 — the ring is circular, so lookups wrap.

Why this works: The mechanical lookup — hash the key, walk clockwise, wrap at the boundary — is the entire algorithm; everything else (virtual nodes, rebalancing) builds on this one operation.

Forgetting the ring wraps around, and stopping the clockwise walk at the highest hash value

Wrong

text

def find_owner(key_hash, node_positions):
    for pos in sorted(node_positions):
        if pos >= key_hash:
            return pos
    return None  # key_hash was past the last node

Better

text

def find_owner(key_hash, node_positions):
    for pos in sorted(node_positions):
        if pos >= key_hash:
            return pos
    return sorted(node_positions)[0]  # wrap to the
    # smallest position — the ring has no highest point

What you see: Keys that hash above the last node's position on the ring get no owner at all (a None/null result) instead of wrapping to the first node.

Why: A ring has no start or end — position 359 is adjacent to position 0, not a dead end — so a correct implementation must wrap the search back to the smallest node position instead of returning nothing.

Modulo hashing vs. ring-based consistent hashing

hash(key) % N

+Routing depends on the current node count N
+Adding/removing a node remaps nearly all keys
+Every lookup needs to know N upfront

Consistent hashing (ring)

−Routing depends only on ring position
−Only keys near the changed node remap
−Lookup only needs the ring, not N

Modulo hashing vs. ring-based consistent hashing

Modulo hashing vs. ring-based consistent hashing
Property	hash(key) % N	Consistent hashing (ring)
Where a key routes	Depends on the current node count N	Depends only on ring position, not N
Effect of adding/removing a node	Nearly all keys remap	Only the keys near the changed node remap
Needs to know total node count upfront	Yes — every lookup uses N	No — lookup only needs the ring
Typical use	Fixed-size shard counts decided in advance	Caches/stores that scale nodes up or down

Remember: Ring-based lookup (hash the key, walk clockwise to the next node) means only the keys near a changed node move when that node joins or leaves — unlike hash(key) % N, where changing N remaps nearly everything.

Even load and minimal movement on membership changes

Virtual nodes fix uneven load on the ring; node addition and removal show why only a small slice of keys ever needs to move.

Virtual nodes and why they even out load

coreintermediate

A plain ring with one point per physical node has an uneven-load problem: hashing a handful of node IDs onto a large circular space produces gaps of very different sizes, purely by chance, so some nodes end up owning far more of the ring — and far more keys — than others. Virtual nodes fix this by hashing each physical node to many points on the ring (commonly on the order of 100-200 per node) instead of one. Each of those points is a separate "virtual" node that maps back to the same physical machine, so a physical node's total share of the ring is the sum of many small, scattered arcs rather than one large-or-small arc decided by a single unlucky or lucky hash.

Think of it as

It is like handing out raffle tickets instead of one lottery ball per contestant. If each of 5 contestants gets exactly one ball dropped into a drum at a random position, pure chance can easily put two balls close together and leave a big empty stretch elsewhere — one contestant's "territory" ends up much bigger than another's. Give each contestant 150 tickets scattered throughout the drum instead, and the law of averages takes over: every contestant's tickets add up to roughly the same total territory, even though any single ticket is still placed at random.

text

for physical_node in cluster:
    for i in range(virtual_nodes_per_node):   # e.g. 150
        ring_position = hash(f"{physical_node.id}-{i}")
        ring[ring_position] = physical_node

What we're doing: Show a 3-node ring with only 1 point each landing unevenly, then the same 3 nodes with virtual nodes landing much more evenly.

virtual-nodes.txttext

Without virtual nodes (1 hash point per node, ring 0-359):
  Node A -> 10
  Node B -> 40
  Node C -> 300
  Arc owned clockwise from each point to the next:
    A owns 300->10   = 70 degrees  (arc wraps 0)
    B owns 10->40     = 30 degrees
    C owns 40->300    = 260 degrees  <- C owns most of the ring

With virtual nodes (3 per physical node, same 3 nodes):
  A-0 -> 10    B-0 -> 40    C-0 -> 300
  A-1 -> 130   B-1 -> 170   C-1 -> 210
  A-2 -> 250   B-2 -> 90    C-2 -> 350
  Sorted ring: 10(A) 40(B) 90(B) 130(A) 170(B)
               210(C) 250(A) 300(C) 350(C)
  Arcs now alternate between owners all the way
  around, instead of one node owning a 260-degree arc.

8: With one point each, Node C happens to own a 260-degree arc out of 360 — pure chance from where three random hashes landed.
11: The same three physical nodes each get 3 virtual points (9 total), scattered around the same ring.
14: Sorted, the 9 virtual points alternate ownership around the ring instead of leaving one huge unbroken arc — each physical node's total share is now much closer to 360/3 = 120 degrees.

Why this works: This is the concrete mechanism, not just the claim — a small number of raw hash points can land arbitrarily unevenly, and scattering many points per node is what pulls the distribution back toward the fair 1/N share each node should get.

Using only one virtual node per physical node and being surprised by an unbalanced cluster

Wrong

text

# 8-node cache cluster, 1 ring point per node
ring = {hash(node.id): node for node in nodes}
# observed: one node handling 3x the traffic
# of another, despite "identical" hardware

Better

text

# same 8-node cluster, ~150 virtual points per node
ring = {}
for node in nodes:
    for i in range(150):
        ring[hash(f"{node.id}-{i}")] = node
# load now varies by only a few percent between nodes

What you see: A small cluster (fewer than a few dozen physical nodes) shows persistently uneven request or memory load across nodes that are otherwise identical, even though the hashing itself is not biased toward any particular key pattern.

Why: With few raw hash points, the gaps between them on the ring are governed by chance and can differ by several times over — the imbalance is a property of how few random points were placed, not a bug in the hash function, and it only goes away by adding more points per node.

1 ring point per node vs. ~150 virtual nodes each

1 point per node

+Load distribution is uneven — pure chance
+A node leaving dumps its whole arc on one neighbor
+Every node gets one equal-ish arc, no tuning

Virtual nodes

−Load distribution averages out and is even
−A leaving node's keys spread thinly across many
−Bigger nodes can get proportionally more points

One point per node vs. virtual nodes

One point per node vs. virtual nodes
Property	1 point per physical node	Many virtual nodes per physical node
Load distribution	Uneven — depends on luck of a few hash values	Even — averages out over many hash values
Effect of a node leaving	Its entire arc dumps onto one neighbor	Its keys spread thinly across many nodes
Supports unequal node capacity	No — every node gets one equal-ish arc	Yes — give bigger nodes more virtual nodes
Ring metadata size	O(number of physical nodes)	O(number of physical nodes x virtual nodes each)

Remember: One hash point per physical node lets chance create big, uneven arcs; ~100-200 virtual points per physical node averages that out, spreads a leaving node's keys across many neighbors instead of one, and lets unequal-capacity nodes get proportionally more points.

Adding or removing a node moves about 1/N of the keys

coreintermediate

This is the payoff of the whole ring design: when a node joins or leaves an N-node ring, only the keys that fall on the arc immediately owned by that node need to move — everyone else's owner is unaffected, because everyone else's "next node clockwise" hasn't changed. For a roughly balanced ring that works out to about a 1/N fraction of all keys moving per membership change, compared to hash(key) % N remapping close to (N-1)/N of all keys — nearly everything — for the same change. That difference is the entire practical reason distributed caches and partitioned stores use a ring instead of modulo hashing: adding capacity, or losing a node to a crash, costs a small, roughly predictable amount of data movement instead of a near-total reshuffle.

Think of it as

Think of a relay race where runners are stationed at fixed points around a circular track and each runner is responsible for carrying the baton from wherever the previous runner dropped off to their own station. If one runner is pulled from the race, only the ground between that runner's station and the next runner's station needs a new runner assigned to it — every other handoff on the track is untouched. Compare that to a system that renumbers every runner's station from scratch whenever the total runner count changes: pulling one runner would mean re-briefing almost the entire track on their new positions.

text

add node X at ring position P:
    only keys between P and the previous node
    (walking counter-clockwise from P) move to X

remove node Y at ring position Q:
    all keys Y owned move to the next node
    clockwise from Q

What we're doing: Walk through a concrete 4-node ring, add a 5th node, and show exactly which keys move.

node-add.txttext

Before: 4 nodes on a 0-99 ring
  Node A -> 10   Node B -> 35   Node C -> 60   Node D -> 85
  (each owns the arc from the previous node up to itself)
  A owns (85, 10]   B owns (10, 35]
  C owns (35, 60]   D owns (60, 85]

8 keys and their current owners:
  k1=5->A  k2=20->B  k3=30->B  k4=45->C
  k5=55->C k6=70->D  k7=80->D  k8=95->A

Add Node E at position 50:
  E's arc is carved out of C's old arc (35, 60]:
    new: C owns (35, 50]   E owns (50, 60]
  Every other node's arc is untouched.

Re-check the 8 keys after adding E:
  k1=5->A  (unchanged)   k2=20->B  (unchanged)
  k3=30->B (unchanged)   k4=45->C  (unchanged, still <=50)
  k5=55->E (MOVED, was C, now between 50 and 60)
  k6=70->D (unchanged)   k7=80->D  (unchanged)
  k8=95->A (unchanged)

Result: 1 of 8 keys moved (k5), and only between C and E.
Expected fraction for 8 keys / 5 nodes is close to 1/5 = 20%;
1/8 = 12.5% here is within the range one small worked
example can land on.

11: Node E is added at position 50, which falls inside Node C's old arc (35, 60] — that is the only arc that gets split.
13: Only C's arc changes shape (split into (35, 50] and (50, 60]); A, B and D's arcs are completely untouched by adding E.
19: Of the 8 keys, only k5 (hash 55) falls in the newly carved-out (50, 60] slice — it is the only key that moves, and it moves from C to E specifically, not to a random node.

Why this works: A worked example with real hash positions makes the "about 1/N keys move" claim checkable rather than an assertion — every key that does not fall inside the changed arc is verifiably unaffected.

Rebuilding the whole ring assignment from scratch on every node join instead of doing a local update

Wrong

text

def add_node(new_node, all_keys, ring):
    ring.add(new_node)
    # recompute every key's owner from scratch
    for key in all_keys:
        reassign(key, ring)

Better

text

def add_node(new_node, ring):
    prev_node = ring.node_before(new_node.position)
    # only touch keys currently owned by prev_node that
    # fall between prev_node's old start and new_node
    for key in prev_node.keys_in_range(new_node.position):
        reassign(key, new_node)

What you see: Adding one node to a large cluster triggers a full data-copy pass across every existing node instead of a targeted transfer from a single neighbor — the operation takes far longer and uses far more bandwidth than the ring design should require.

Why: Recomputing every key's owner from scratch throws away the entire benefit of consistent hashing and reproduces the "nearly everything moves" behavior of modulo hashing, even though the ring itself only actually changed ownership for one arc.

Adding node E splits only C's arc — 1 of 8 keys moves

C owns (35, 60]

before: k4, k5

C owns (35, 50]

after: k4 stays

E owns (50, 60]

after: k5 moves here

A, B, D

6 other keys, untouched

Key movement on a membership change, ring vs. modulo

Key movement on a membership change, ring vs. modulo
Change	hash(key) % N	Ring-based consistent hashing
Add 1 node (N -> N+1)	Nearly all keys remap (N/(N+1) of them)	About 1/(N+1) of keys move, to the new node
Remove 1 node (N -> N-1)	Nearly all keys remap	About 1/N of keys move, to one clockwise neighbor
Keys unaffected by the change	Very few	All keys not on the changed arc(s)

Remember: Adding or removing one node only changes the arc(s) adjacent to that node — roughly 1/N of keys move, versus nearly all of them under hash(key) % N — and virtual nodes spread even that movement across many physical neighbors instead of dumping it on one.