Design Consistent Hashing
To scale horizontally, we need to spread requests and data evenly across servers. Consistent hashing is the go-to technique, used by DynamoDB, Cassandra, Discord, Akamai's CDN and Google's Maglev load balancer. First, let's see the problem it solves.
- 5.1The rehashing problemWith n cache servers, a common way to balance load is: serverIndex = hash(key) % N // N = number of servers This works well while the…
- 5.2The hash ringConsistent hashing is a special kind of hashing where, when the table is resized, only k/n keys need to move on average (k = number of…
- 5.3Adding and removing serversAdd a server: only the keys between the new server and the server before it (anticlockwise) move to the new server. Everyone else stays…
- 5.4Two problems, and virtual nodesThe basic approach has two problems: Uneven partitions: the range between neighboring servers can be very different in size. After removing…
- 5.5Finding affected keys, and wrap upWhen a server is added or removed, which keys must be redistributed? Server added: move the keys between the new server and the first…