Consistent hashing

Distributed systems Mid-level Python 3.13+ PostgreSQL 17+ Reviewed By Best Latest Apps

Predict the output

Our simulation hashes 1,000 keys with MD5. How many change node with plain modulo when going from 4 to 5 nodes?

Python 3.13
import bisect
import hashlib


def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")


class Ring:
    def __init__(self, nodes: list[str], vnodes: int) -> None:
        self.points = sorted(
            (h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes)
        )
        self.hashes = [p for p, _ in self.points]

    def owner(self, key: str) -> str:
        i = bisect.bisect(self.hashes, h(key)) % len(self.points)
        return self.points[i][1]


keys = [f"user:{i}" for i in range(1000)]
mod_before = {k: h(k) % 4 for k in keys}
mod_after = {k: h(k) % 5 for k in keys}
print(
    "modulo, 4 -> 5 nodes:",
    sum(mod_before[k] != mod_after[k] for k in keys),
)

Options
Hint 1 of 1

For a key to stay, h % 4 must equal h % 5.

Choose an answer, then open Show answer below to check it.

Twelve keys on a ring of three nodes with one point each: A owns 4 keys, B 7 and C 1. Adding node D moves only the keys between D and the point before it (2 of 12); hash mod N (3 → 4) would move 11 of 12. Step through with 3 points per node to see how extra points change the split; real rings use 100 or more points per node.

Illustrative; not a load test

Text version
Add node D, 1 point per node: 2 of 12 keys move
KeyBeforeAfterMoved?
item:1BBNo
item:2BBNo
item:3ADYes, to D
item:4AANo
item:5ADYes, to D
item:6AANo
item:7BBNo
item:8BBNo
item:9CCNo
item:10BBNo
item:11BBNo
item:12BBNo

Keys per node: A 2, B 7, C 1, D 2.

Remove node B, 1 point per node: 7 of 12 keys move
KeyBeforeAfterMoved?
item:1BAYes, to A
item:2BAYes, to A
item:3AANo
item:4AANo
item:5AANo
item:6AANo
item:7BAYes, to A
item:8BAYes, to A
item:9CCNo
item:10BAYes, to A
item:11BAYes, to A
item:12BAYes, to A

Keys per node: A 11, C 1.

Add node D, 3 points per node: 3 of 12 keys move
KeyBeforeAfterMoved?
item:1AANo
item:2AANo
item:3ADYes, to D
item:4AANo
item:5ADYes, to D
item:6AANo
item:7BDYes, to D
item:8BBNo
item:9CCNo
item:10BBNo
item:11BBNo
item:12BBNo

Keys per node: A 4, B 4, C 1, D 3.

Remove node B, 3 points per node: 5 of 12 keys move
KeyBeforeAfterMoved?
item:1AANo
item:2AANo
item:3AANo
item:4AANo
item:5AANo
item:6AANo
item:7BAYes, to A
item:8BAYes, to A
item:9CCNo
item:10BAYes, to A
item:11BAYes, to A
item:12BAYes, to A

Keys per node: A 11, C 1.

11 of 12 would move with hash mod N (3 → 4).

Show answer

Answer: A modulo, 4 -> 5 nodes: 807

Correct. Roughly 4 in 5 keys move, because the remainder changes for most hashes.

With hash % n, changing n changes the remainder for most hashes, so most keys move. In this run 807 of 1,000 move, while a ring would move only the share the new node takes over, about 1 in 5.

Why not the others?
  • B modulo, 4 -> 5 nodes: 200. That's about what an ideal ring moves, not modulo.
  • C modulo, 4 -> 5 nodes: 0. Changing the divisor reshuffles most keys.
  • D modulo, 4 -> 5 nodes: 1000. Keys whose hash gives the same remainder for 4 and 5 stay put.

30-second answer

With modulo, changing N changes almost every key's node: in our simulation of 1,000 keys going from 4 to 5 nodes, 807 keys moved, which empties most of a cache at once. Consistent hashing places nodes and keys on a ring and gives each key to the next node clockwise, so adding a node only takes keys from its neighbours: 176 of 1,000 moved with 100 virtual nodes each, close to the ideal 1/5.

Practise saying it · 35 s. No recording, just a timer

Explain consistent hashing.

Say your answer out loud, then check which of these points you covered:

  • Modulo moves most keys
  • Ring: next node clockwise
  • Adding a node moves about 1/N
  • Virtual nodes even the load
  • Hot keys still need care

Deep dive

Virtual nodes (many points per server) even out the load; with 1 point per node our ring gave one node 551 keys and another 12.

Removing a node moves only that node's keys to its successor.

Rendezvous (highest random weight) hashing gives the same property without a ring.

Used by Dynamo-style stores, Cassandra, and client-side cache sharding.

Modulo vs ring on 1,000 keys Ran on Python 3.13.5 · mypy --strict
Python 3.13
import bisect
import hashlib


def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")


class Ring:
    def __init__(self, nodes: list[str], vnodes: int) -> None:
        self.points = sorted(
            (h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes)
        )
        self.hashes = [p for p, _ in self.points]

    def owner(self, key: str) -> str:
        i = bisect.bisect(self.hashes, h(key)) % len(self.points)
        return self.points[i][1]


keys = [f"user:{i}" for i in range(1000)]
mod_before = {k: h(k) % 4 for k in keys}
mod_after = {k: h(k) % 5 for k in keys}
print(
    "modulo, 4 -> 5 nodes:",
    sum(mod_before[k] != mod_after[k] for k in keys),
)
before, after = Ring(list("ABCD"), 100), Ring(list("ABCDE"), 100)
print(
    "ring, 4 -> 5 nodes:",
    sum(before.owner(k) != after.owner(k) for k in keys),
)

Common mistakes

  • Using modulo sharding for a cache cluster that scales up and down.
  • Using one point per node and getting badly uneven load.
  • Forgetting that hot keys still land on one node; consistent hashing balances key counts, not traffic.

Senior take & follow-ups

Contrast modulo and ring with numbers, then explain virtual nodes.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you handle a hot key?

    Show hint

    Replicate it to several nodes or add a random suffix and fan out reads.

  2. Why weight virtual nodes?

    Show hint

    Give bigger machines more points so they take more keys.

Related questions

Suggest a fix if something here is wrong or out of date.