System design · Question 48 of 50
What is consistent hashing?
Distributed caches and sharding.
The answer
With hash(key) % N servers, adding or removing one server changes N, so almost every key maps somewhere new: a cache cluster loses nearly all its hits at once.
Consistent hashing puts servers and keys on a ring (0 to 2³²); each key belongs to the first server clockwise from it. A new server takes over only the keys between it and its neighbour, about 1/N of them; a removed one hands its keys to the next server. Virtual nodes (each server at many points on the ring) even out the load and spread a failed server's keys across all the others. DynamoDB, Cassandra and many distributed caches use it.
The picture
S1
● ● key k1 → the next server clockwise: S2
S4 ring S2
● ●
S3
add S5 between S1 and S2: only the keys on that arc moveWhy virtual nodes?
Show the answer
With few servers the arcs are uneven. Many virtual points per server even out the load and spread a failed server's keys across everyone.