Consistent Hashing Explained With a Momo Shop Analogy

My aunt runs a momo shop with four cooks. Orders get assigned by ticket number mod four. Works great until cook number four calls in sick, and suddenly every ticket has to be reassigned because mod three gives different answers for almost everything. Chaos. Cold momos. Angry customers.

That is exactly what happens when you shard a cache with hash(key) % N and then change N. I ran the numbers on a toy ring to show a coworker who didn't believe me:

With naive modulo, removing one node out of four moved almost 75 percent of keys. Every one of those is a cache miss hitting your database at the same time. With consistent hashing, removing a node moved 25 percent, which is the theoretical minimum since a quarter of the keys genuinely lived there.

The trick is to stop mapping keys to node numbers and start mapping both keys and nodes onto the same circle. Hash each node onto the ring, hash each key onto the ring, and a key belongs to the first node you hit walking clockwise. When a node leaves, only its arc of the circle gets reassigned to its clockwise neighbor. Everyone else stays put.

The wrinkle nobody tells you about is hot spots. With one point per node, your arcs are lumpy, so one node can own way more of the circle than its fair share. The fix is virtual nodes. Hash each physical node 100 to 200 times onto the ring under different names, and the lumps average out. My demo uses 160 vnodes per node and the distribution lands within about one percent of even.

If you use Redis Cluster, Cassandra, or DynamoDB, you are already sitting on some version of this idea. Worth understanding it before the day a node dies and you have to explain to someone why the database fell over too.