Skip to main content

“Wait… Why Are We Modding by the Number of Nodes?”

A Quick Developer’s Journey to Consistent Hashing​

1. The Naive Starting Point​

You’re building a distributed cache or key-value store. You need to decide: which node holds which key?

First thought (and it sounds perfectly reasonable):​

“We just need relatively balanced buckets… each bucket is one node… so we’ll hash the key and mod by the number of nodes.”

# Naive hashing
def get_node(key: str, nodes: list[str]) -> str:
    return nodes[hash(key) % len(nodes)]

Boom, done, right? Keys are evenly spread across all nodes. No central lookup table. No coordination. It feels elegant.

2. The First Pain Point​

Everything is fine until one day: a node dies (or you add a new one). Suddenly:

node = hash(key) % (node_count ± 1)

And you realize… Almost every key just moved to a new node.

  • Node A didn’t just get a few new keys.
  • Node B didn’t just lose a small slice.
  • The entire dataset just shuffled like a deck of cards.

Statistically:

  • Adding/removing a node moves ~(N-1)/N of all keys.
  • That’s basically all of them for big clusters.

3. The First Hacky Fix: Buckets​

Your inner monologue kicks in:

“Wait, what if each node didn’t equal one bucket? What if we had lots of buckets and just mapped those to nodes?”

Example:

  • Use 500 buckets (a constant).
  • Assign them to your 5 nodes (100 buckets each).
# Fixed number of slots
SLOT_COUNT = 500
slot_to_node = {}

# Assign buckets to nodes (e.g., round-robin)
for slot in range(SLOT_COUNT):
    slot_to_node[slot] = nodes[slot % len(nodes)]

def get_node(key: str) -> str:
    slot = hash(key) % SLOT_COUNT
    return slot_to_node[slot]

Now, when a node fails:

  • You only reassign its buckets.
  • The other buckets (and their keys) stay put.

4. Buckets Need to Be Scattered, Not Clumped​

But wait: there’s a subtlety here. If all of Node 1’s buckets are adjacent (say 0–20, 21–40, 41–60, etc.), then when Node 1 fails:

  • All those adjacent buckets move together → effectively one big chunk.
  • You haven’t actually solved the load-balancing problem.

The Fix: Scatter the Buckets​

Assign each node multiple randomly distributed buckets across the hash space:

  • Node A: [0–20, 100–120, 300–320]
  • Node B: [20–40, 120–140, 320–340]
  • Node C: [40–60, 140–160, 340–360]
  • …

Now, when Node A fails:

  • Its buckets are spread out.
  • All other nodes share the load instead of one unlucky neighbor.

5. The “Ohhh…” Moment: Consistent Hashing​

Congratulations, you’ve basically discovered:

  • Consistent Hashing → deterministic key-to-range mapping.
  • Virtual Nodes → fancy term for “a node owns multiple scattered ranges.”

The “hash ring” people draw is just a prettier visualization of this:

  • Nodes (or virtual nodes) are points on the ring.
  • Keys land somewhere on the ring.
  • Each key goes to the next node clockwise.

6. Picking the Constant​

One subtle detail:

What do we mod by?

  • In naive hashing, it was node_count → bad.
  • In bucketized hashing, it’s a fixed constant (like 500 or 10,000).
  • Nodes can change, but your hash space doesn’t.

That’s why consistent hashing is called consistent:

  • Adding/removing nodes only shifts keys in those affected ranges.
  • Everything else stays consistent.

7. Bonus: Jump Consistent Hash​

If you’re feeling fancy, check out Jump Consistent Hash (from Google):

  • No big slot table.
  • O(1) time to compute which node a key belongs to.
  • Still only remaps ~1/N keys when node count changes.

Takeaway​

The whole point of consistent hashing is to break free from the naive thought:

“We’ll just mod by the number of nodes.”

Instead:

  • Use a fixed hash space (lots of small buckets).
  • Scatter buckets among nodes.
  • Remap only the affected buckets when nodes change.

That’s how you get scalable, fault-tolerant, load-balanced key distribution.