System Design: consistent hashing
Consistent hashing decides which of N servers holds a key, so that every participant computes the same answer with no coordination. The course separates hashing for identity from hashing for placement, measures how modulo placement moves most keys when a cluster resizes, and builds the ring with virtual nodes. It covers replication on the first R distinct nodes, rack and zone awareness, and hot keys. It looks at memcached, Dynamo, Cassandra, Redis Cluster and load balancers, compares rendezvous and jump hashing, and ends with a rendezvous hashing challenge.
What you'll learn
- ✓The difference between hashing for identity and hashing for placement
- ✓Why modulo placement moves almost every key when a node is added
- ✓How the ring and virtual nodes limit movement and even out distribution
- ✓Replication on distinct nodes, rack and zone awareness, and hot keys
- ✓Where memcached, Dynamo, Cassandra, Redis Cluster and load balancers use these ideas
- ✓When rendezvous hashing, jump consistent hash or a single node fits better
Hashing for identity versus placement
This application hashes things in three places, and none of them is what consistent hashing is for. Seeing the difference is the fastest way into the topic.
Read the full lesson free →Curriculum
7 lessonsHashing for identity versus placement
Three identity hashes in this application show how naming a thing differs from deciding which server holds it.
Why modulo breaks
Measured on a hundred thousand keys, hash modulo N moves up to 99% of keys when one node joins.
The ring
Nodes and keys share one circular hash space, and virtual nodes cut the uneven spread of random arcs.
Replication and hot keys
Replicas go on the first R distinct nodes clockwise, and hot keys need read replicas, splitting or caching.
Where you already rely on it
memcached clients, Dynamo, Cassandra, Redis Cluster slots and load balancers all solve this same placement problem.
The simpler alternatives
Rendezvous hashing, jump consistent hash and a single node compared with the ring on cost, balance and limits.
Putting it together
A summary of the measurements and two general ideas, followed by implementing a rendezvous hash called place.