Free sample lesson · Consistent Hashing 完全指南：從問題到 Virtual Node 實務
Naive hashing 的搬遷問題
Lesson 1 of the Wondering course Consistent Hashing 完全指南：從問題到 Virtual Node 實務
The rule: hash(key) % N
You have N cache servers and millions of keys. You need a fast way to decide which server owns a key.
Naive hashing answers in one line: hash the key, take the remainder modulo N, and route there.
- Hash the key: A hash function turns the key into a large integer.
- Take remainder: Compute hash(key) % N, where N is the current node count.
- Route request: Send the key to the node holding that index.
It is cheap, stateless, and spreads keys evenly. Every client computes the same answer without asking anyone.
Change N, reshuffle everything
The trouble hides in the divisor. N is baked into the formula.
Add one node and every key is divided by a new number. Remainders shift almost everywhere at once.
Notice that almost every ball ends up in a different bucket even though the balls themselves never changed.
The key did not change. Its hash did not change. Only the divisor did, and that alone moves the key.
A six-key example
Take keys 7 through 12 with four nodes. Their targets are 3, 0, 1, 2, 3, 0.
Now add a fifth node. The same keys map to 2, 3, 4, 0, 1, 2.
Every single one moved. Not one key stayed home.
How bad it gets at scale
Bigger clusters make this worse, not better.
Moving from 4 nodes to 5 relocates about 80% of keys. From 10 to 11, about 91%. From 100 to 101, about 99%.
- 4 to 5: 80
- 10 to 11: 91
- 100 to 101: 99
One extra machine can invalidate nearly your whole cache.
Compare with the minimum
How much movement is actually necessary? Growing from 4 nodes to 5, a fair layout needs only 20% of keys to move.
Naive hashing moves about 80%. That is four times the necessary traffic.
- Fair minimum
- Naive hashing
The gap is pure waste.
What breaks in production
The remapping is not only bookkeeping. Requests start missing the cache in bulk.
Misses fall through to the database, latency climbs, and the cluster shuffles data around while already under load.
- Most keys remap: One node change relocates nearly every key.
- Bulk cache misses: Requests no longer find their key on the node they ask.
- Database overload: Misses fall through to the database.
- Rising latency: Response times climb while the cache refills.
- Data shuffling: The cluster moves data around while already under load.
Adding capacity becomes a risky operation instead of a routine one.
The takeaway
Remember the diagnosis: the divisor is shared state. Change N and you change almost every key's address.
Watch for it in cache routing, shard selection, and partition assignment.
Any scheme worth using should move keys in proportion to the capacity you added, closer to that 20% figure than to 80%.
Check yourself
Naive hashing routes a key to the server identified by hash(key) % N.
- True
- False
Answer: True
Correct. The hash value is divided by N, and the remainder identifies the target server.
To route a key with naive hashing, first compute its _____, then take the _____ modulo the server count N.
Answer: To route a key with naive hashing, first compute its hash, then take the remainder modulo the server count N.
The procedure first transforms the key into a hash value, then uses division by N and routes according to the resulting remainder.
Under naive hashing, a cluster grows from 10 servers to 11. Approximately what percentage of keys is expected to relocate?
- 9%
- 50%
- 91%
- 99%
Answer: 91%
The approximate relocation fraction is 10/11, or about 91%. The larger the original cluster, the closer this fraction gets to 100%.
Keep going
This is lesson 1 of 6 in Consistent Hashing 完全指南：從問題到 Virtual Node 實務. Next up:
- Consistent hashing 環狀結構原理
- Virtual node 如何解決負載不均
- Amazon Dynamo 與 Cassandra 的實作案例
- Consistent hashing 不等於自動均匀
- 複寫與持久性是別一層問題
Wondering turns any topic into short lessons you can read, watch, or listen to, with practice questions and an AI tutor.