Why consistent hashing instead of hash mod N?
“You shard a cache across 10 nodes with `hash(key) mod 10`. You add an eleventh node. What happens, and how does consistent hashing fix it?”
What this tests
- The remapping cost of mod N (almost every key moves)
- The ring, clockwise assignment, and only K/N keys moving
- Virtual nodes for balance and heterogeneous capacity
- Where the pattern appears: caches, partitioning, LB affinity, DynamoDB/Cassandra
Answers by level
Read the beginner answer first and notice what is missing.
With mod 10 → mod 11, a key stays on its node only if h mod 10 == h mod 11, which is true for about 1/11 of keys. Roughly 91% of keys move, so nearly the whole cache misses at once and the database takes the full read load — a self-inflicted stampede, exactly when you added capacity to reduce load.
Consistent hashing places both nodes and keys on a ring (hash space 0 to 2³²); a key belongs to the first node clockwise. Adding node K+1 takes over only the arc between it and its predecessor: about 1/(N+1) of the keys move, and every other key stays where it was. Removing a node moves only its keys, to its successor. With plain single points, arcs are uneven, so each physical node gets 100–200 virtual nodes on the ring, which evens the load and lets a bigger machine get more points — see Consistent Hashing.
Green flags · Red flags
- Quantifies the mod-N remap (~91% of keys for 10 → 11)
- Describes the ring and clockwise ownership precisely
- Virtual nodes for balance and for weighted capacity
- Mentions the binary search on the sorted ring
- Names replication along the ring and the hot-key limit
- "Consistent hashing is just a better hash function that spreads keys evenly."
- Thinks adding a node under mod N moves only 1/11 of keys
- Never mentions virtual nodes
- Cannot say how a client learns the ring membership changed
Follow-up questions
Scenario
crc32(key) mod 8 in the client library. Scaling to 12 nodes for Black Friday caused a 10-minute database overload with 88% cache miss rate; scaling back caused another one. Explain the math and specify the replacement scheme, including how many virtual nodes and how replicas would be placed.