Q34 — What is consistent hashing — why does naive hashing break in distributed systems?

What problem does hashing solve in distributed systems?

When you have multiple servers (cache nodes, database shards, storage nodes), you need a rule for deciding which server a given key belongs to. The rule must be deterministic — the same key must always map to the same server — and it must distribute keys roughly evenly across all servers.

The natural answer is hashing: compute hash(key) % N, where N is the number of servers. Server index 0 through N-1. Every key maps to exactly one server. The hash function distributes keys uniformly, so the load is approximately even.

This works perfectly — until N changes.

Why does naive modulo hashing break when servers are added or removed?

Suppose you have 4 servers and key "user:42" hashes to hash("user:42") % 4 = 2. It lives on server 2.

You add a 5th server. Now the formula is hash("user:42") % 5 = ?. Let's say it gives 3. The key now belongs on server 3, not server 2.

This isn't just one key. When you change N from 4 to 5, almost every key remaps to a different server. Specifically, approximately (N-1)/N = 80% of all keys change their assigned server. For a distributed cache, this means 80% of cached data is suddenly on the wrong server — effectively a full cache flush. Every request misses until the cache warms again. The database gets hit with full traffic. If the cache was absorbing significant load, this triggers the cold start problem we discussed in Q17.

Removing a server is equally catastrophic. Go from 4 servers to 3, and again ~75% of keys remap. Scaling a distributed cache or sharded database up or down becomes a dangerous operation that causes a thundering herd on your backend.

This is why hash(key) % N fails for distributed systems — it's not stable under topology changes.

What is the core idea of consistent hashing?

Consistent hashing makes only the minimum necessary remapping when nodes are added or removed. Instead of remapping proportionally to the total number of keys, it remaps only the keys that belonged to the added or removed node — approximately 1/N of all keys.

The mechanism: imagine a ring — a circle with values from 0 to 2^32-1 (the full range of a 32-bit hash). Both keys and servers are placed on this ring using a hash function:

Each server is hashed to a position on the ring: hash(server_id) → position
Each key is hashed to a position on the ring: hash(key) → position
A key is assigned to the first server encountered when moving clockwise from the key's position

code

         Server A (pos 100)
              |
  Key "x"    |    Key "y"
  (pos 80)   |    (pos 120) → Server B (pos 200)
      ↑             ↑
  Goes to A       Goes to B

Key "x" at position 80 looks clockwise and finds Server A at position 100. Key "y" at position 120 looks clockwise and finds Server B at position 200.

Why does only 1/N of keys remap when a server is added or removed?

Adding a server: A new server C is placed at position 150 (between A at 100 and B at 200). The only keys that need to move are those that were previously assigned to B but are now closer to C — keys with positions between 100 and 150. That's a fraction of the ring owned by C, approximately 1/N of all keys. All other keys are unaffected.

Removing a server: Server B at position 200 is removed. The keys that were assigned to B (positions 150–200) now flow past B's (now empty) position to the next server clockwise. Only B's keys move — approximately 1/N of all keys. All other assignments are unchanged.

This is the key property: consistent hashing minimizes disruption. Adding a server steals keys from its neighbor; removing a server donates keys to its neighbor. The rest of the ring is stable.

What is the virtual nodes problem — and how does it fix uneven distribution?

With a small number of physical servers, the hash function might not place them evenly around the ring. If Server A lands at position 10 and Server B at position 12 (very close together), then Server A owns the arc from ~2^32-6 to 10 (a tiny slice) while Server B owns the arc from 10 to 12 (also tiny) and everything else wraps around to Server C — an enormous slice. Load distribution is wildly uneven despite using a hash function.

The fix: virtual nodes. Instead of placing each physical server once on the ring, place it many times — say, 150 virtual nodes per physical server — at positions generated by hashing different identifiers (hash("serverA-1"), hash("serverA-2"), ..., hash("serverA-150")). All 150 virtual nodes for Server A map back to the same physical machine.

With 150 virtual nodes per server and 3 servers, there are 450 points on the ring. The arcs between consecutive points are small and numerous. The physical servers' slices are many small arcs spread across the ring rather than one large arc — statistically they sum to approximately 1/3 of the ring each. The more virtual nodes, the more even the distribution.

Virtual nodes also make server removal more graceful: when a server with 150 virtual nodes is removed, its keys don't all flow to one neighbor — they flow to 150 different neighbors (whichever server follows each of the 150 virtual node positions clockwise). The load distributes across all remaining servers rather than crushing one.

Where is consistent hashing used in real systems?

Distributed caches: Memcached uses consistent hashing (via the Ketama algorithm) to distribute cache keys across cluster nodes. Adding or removing cache nodes doesn't invalidate the entire cache.

Cassandra: uses consistent hashing on a ring to determine which nodes own which partition key ranges. The vnodes feature in Cassandra is virtual nodes — each physical node owns multiple small token ranges.

DynamoDB: Amazon's original Dynamo paper (2007) describes consistent hashing as the core of its data distribution strategy.

CDNs: Edge node selection for content routing uses consistent hashing to ensure a given URL consistently routes to the same edge cluster (maximizing cache hit rate), while gracefully handling edge node additions and removals.

The mental model

code

Naive hashing: hash(key) % N
  Add/remove server → N changes → ~80% of keys remap → cache flush → thundering herd

Consistent hashing: ring from 0 to 2^32-1
  Servers and keys both placed on ring via hash function
  Key → next server clockwise

Add server: steals keys from clockwise neighbor → ~1/N keys move
Remove server: donates keys to clockwise neighbor → ~1/N keys move

Virtual nodes: each physical server appears 100-150x on ring
  → Even distribution (statistically ~1/N of ring per server)
  → Removal spreads load across all remaining servers, not just one neighbor

Real systems: Memcached (Ketama), Cassandra (vnodes), DynamoDB (original Dynamo), CDNs

Consistent hashing exists because systems that distribute load across nodes must be able to change their topology — add capacity, handle failures, replace hardware — without catastrophic remapping. The ring turns a global disruption into a local one: only the keys nearest the changed node are affected.