Compare

Consistent hashing vs Modulo hashing

Consistent hashingNext server clockwise on a ring

each key → the next server clockwise

ABC31117263442525865758596
Databaseno misses
Modulo hashingHash divided by the number of servers

server = hash % 3

A0 keys
B0 keys
C0 keys
Doff
31117263442525865758596
Databaseno misses

Twelve keys in a cache, over three servers: add a server, lose one, and see how many keys move. Every key that moves is a cache miss.

Compare next

Monolith vs MicroservicesHorizontal vs Vertical scaling

Consistent hashing or Modulo hashing?

Modulo is fine while the number of servers never changes. When servers come and go, use consistent hashing — and give each server many points on the ring (virtual nodes) so the load stays even.

Compare next

Monolith vs MicroservicesHorizontal vs Vertical scaling
DifferenceConsistent hashingModulo hashing
A key’s serverThe next server clockwise on a ringhash % N: the remainder picks it
Add a serverOnly the keys before it move: about 1 in NAlmost every key moves
A server diesOnly its keys move, to the next serverAlmost every key moves again
The cache after a changeA few missesMostly misses: the database takes the load
Even spreadUneven with few servers; virtual nodes even it outEven, as long as N never changes
Used inDynamoDB, Cassandra, Memcached clients, load balancersA fixed set of shards that never changes

Consistent hashing vs Modulo hashing, explained step by step

1. Spread the keys

Twelve keys in a cache, spread over three servers. On the left, consistent hashing: servers and keys sit on a ring, and each key belongs to the next server clockwise. On the right, modulo hashing: the key’s hash is divided by the number of servers, and the remainder picks the server. Let’s put both through three situations.

First, spreading the keys. On the ring, a key walks clockwise until it meets a server: key eleven walks to server B. Every key does the same, and each server ends up with four.

On the right, each key’s hash is divided by three, and the remainder, zero, one or two, picks server A, B or C. Four keys each here too.

2. Add a server

Next, traffic grows, so we add server D. It lands on the ring between A and B, and takes over only the keys in between. Three of twelve move; the other nine stay where they were.

On the right, dividing by four instead of three changes almost every remainder. Nine of twelve keys move to another server. Each one is a cache miss, so the database takes all those requests at once.

3. A server dies

Finally, server C dies. Only its four keys move, to the next server clockwise: A. The rest of the ring doesn’t notice.

On the right, C dies too, and modulo divides by three again. The keys reshuffle a second time, nine of twelve, and the database is flooded again.

In short

So which should you pick? Modulo is fine while the number of servers never changes. When servers come and go, use consistent hashing: only a slice of the keys moves. Real systems also give each server many points on the ring, called virtual nodes, so the load stays even.