Consistent Hashing
Place keys and servers on a ring so adding or removing a server moves only a small share of the keys.
The problem with mod N
Suppose a cache cluster of servers picks a server with hash(key) mod N. It works until changes, because a server is added, or one crashes.
Predict the output
12 keys are numbered 0 to 11. Count how many land on a different server when the cluster grows from 3 servers to 4 (key mod 3 versus key mod 4).
print(sum(k % 3 != k % 4 for k in range(12)))For a cache that means a sudden wave of cache misses: almost every key now looks for its data on the wrong server, and the database behind it gets flooded. For a sharded database it means moving almost all data.
1 of 8