System design · Question 48 of 50

What is consistent hashing?

What they're checking

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 move
The follow-up they'll ask

Why 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.

Your progress stays on this device.