Consistent Hashing: How It Works and Why It Matters
Consistent hashing maps both data keys and servers onto a hash ring, so adding or removing a node only remaps about 1/N of keys instead of nearly all of them. This makes it ideal for distributed caches and databases that scale dynamically. Virtual nodes spread load evenly and avoid hot spots.
The Problem with Modulo Hashing
A naive way to distribute keys across N servers is hash(key) % N. It works until N changes. Add or remove one server and the modulo changes for almost every key, so nearly all data must be remapped, causing a cache stampede or massive data migration. With 4 servers going to 5, roughly 80% of keys move.
Consistent hashing solves this: when the cluster size changes from N to N+1, only about K/N keys (where K is the total keys) need to move, the ones that were on the now-adjacent node. This minimal disruption is why it underpins elastic distributed systems.
How the Hash Ring Works
Imagine a circular hash space, say 0 to 2^32 - 1, joined end to end. Each server is hashed to a point on this ring. Each key is also hashed to a point; to find its server, you walk clockwise from the key's position to the first server you hit. That server owns the key.
When a server is added, it takes over only the keys between it and the previous server on the ring, everything else stays put. When a server is removed, its keys move to the next clockwise server. No global reshuffle. This is the core mechanism behind Amazon Dynamo and its descendants.
Virtual Nodes (Vnodes)
Plain consistent hashing can distribute load unevenly: with few servers, the gaps between them on the ring vary, so some servers own far more of the ring than others. If a server dies, all its load dumps onto a single neighbor.
Virtual nodes fix this: each physical server is hashed to many points on the ring (e.g., 100-256 vnodes per server). This evens out the distribution and, when a node fails, its load spreads across many neighbors instead of one. Cassandra defaults to 256 vnodes per node; DynamoDB and Riak use similar techniques. Weighted vnodes also let heterogeneous hardware carry proportional load.
| Approach | Keys moved on resize | Load balance |
|---|---|---|
| Modulo (hash % N) | ~All keys | Even (static N only) |
| Consistent hashing | ~K/N keys | Uneven without vnodes |
| Consistent hashing + vnodes | ~K/N keys | Even |
Where It's Used
Consistent hashing powers Amazon DynamoDB and Cassandra (partitioning rows across nodes), Discord's message storage, distributed caches (memcached client libraries like ketama, Redis Cluster uses a related 16,384-slot scheme), CDNs for mapping content to edge servers, and load balancers doing session-affine routing. Maglev (Google's load balancer) uses a consistent-hashing variant optimized for minimal disruption and even spread.
ResuMax tailors your resume to each role, scores it like a recruiter, and preps you for interviews.
Practice with the interview coachFrequently asked questions
Why not just use hash(key) % N?
Because changing N (adding/removing a server) changes the modulo for almost every key, forcing nearly all data to be remapped. That causes massive cache misses or data migration. Consistent hashing remaps only about 1/N of keys when the cluster resizes.
What are virtual nodes and why are they needed?
Virtual nodes hash each physical server to many ring positions (e.g., 256) so load is distributed evenly and a failed node's load spreads across many neighbors instead of one. Without them, the ring gaps are uneven, causing hot spots.
How many keys move when a node is added?
Roughly K/N keys, where K is the total number of keys and N is the number of nodes, only the keys in the arc the new node takes over. This is the minimal-disruption property that makes consistent hashing valuable.
Which real systems use consistent hashing?
Amazon DynamoDB, Apache Cassandra, Riak, Discord, memcached client libraries (ketama), Redis Cluster (a slot-based variant), CDNs, and Google's Maglev load balancer all use consistent hashing or close variants.