Consistent hashing comes up in nearly every distributed systems interview — not as the main question, but as the follow-up that separates candidates who understand data distribution from those who just name databases. This guide explains the problem it solves, how the algorithm works, why virtual nodes exist, and how to deploy the concept in any system design interview.
Before consistent hashing, the standard approach to distributing keys across multiple cache or database nodes was modulo hashing: assign a key to node hash(key) % N, where N is the number of nodes. Simple, uniform, fast. The fatal flaw: it breaks completely whenever N changes.
Imagine a cache cluster with 4 nodes holding 1 million keys. Node 2 fails. N is now 3. Every key that was previously mapped by hash(key) % 4 must be recalculated against hash(key) % 3. Mathematically, approximately 75% of keys will map to a different node — meaning 750,000 cache entries are invalidated simultaneously. Every one of those requests is now a cache miss that falls through to the database. At any significant scale, this is a database-killing thundering herd.
The same problem occurs in reverse when adding a node: you want to scale out by adding a fifth node, so N goes from 4 to 5. Again, approximately 80% of keys remap. Your cache is instantly cold. Adding capacity to handle load causes a load spike that defeats the purpose of adding the node.
Consistent hashing solves this by ensuring that only K/N keys need to remap when the cluster size changes (where K is total key count and N is node count). Adding or removing one node out of 10 remaps approximately 1/10 of keys, not all of them. The rest stay exactly where they were.
Consistent hashing maps both keys and nodes onto a circular hash space — a ring of integer values from 0 to 2³² (or 0 to 2⁶⁴ for larger spaces). Every node is assigned a position on the ring by hashing its identifier (IP address, hostname, UUID). Every key is similarly hashed to a position on the ring.
To find which node owns a key: start at the key's position on the ring and walk clockwise until you hit a node. That node owns the key. Adding a node: place it on the ring and walk clockwise from its position — the keys between its predecessor (the next node counter-clockwise) and its position now belong to the new node. Those keys move from the old successor to the new node. Every other key stays unchanged.
Removing a node: its keys are inherited by its clockwise successor. Keys from all other nodes are unaffected. In both cases, only the keys adjacent to the change point need to move. This is the minimal remapping property.
With N nodes and K keys uniformly distributed, each node owns approximately K/N keys. Adding a node adds one new region to the ring, and the new node inherits approximately K/N keys from its predecessor — exactly what you'd want for balanced distribution. On average, 1/N of all keys remap per node addition or removal.
The basic hash ring has a critical flaw: with a small number of nodes, hash positions are unlikely to be evenly spaced around the ring. One node might own 30% of the key space while another owns only 5%. This creates hot nodes — some nodes hold significantly more data and serve significantly more requests than others, defeating the purpose of distributing load.
Virtual nodes (vnodes) fix this by assigning each physical node multiple positions on the ring. Instead of one hash per node, you hash node_id + ":" + vnode_index for each of V virtual nodes. A physical node with 150 virtual nodes has 150 positions on the ring. The key space is divided into 150 × N segments for N physical nodes, each owning a tiny slice of the ring.
With 150 virtual nodes per physical node and 10 physical nodes, there are 1,500 segments on the ring. The maximum any one physical node can own is not one large chunk but 150 scattered small chunks — statistically, each physical node ends up with approximately 10% of the key space (1/N), with variance proportional to the square root of V rather than the square root of 1. More virtual nodes = more even distribution.
Virtual nodes also make node removal graceful: instead of one node's entire key space landing on a single successor, the 150 virtual positions are scattered around the ring, so 150 different neighbours each absorb a tiny fraction of the removed node's data. Load is spread across the entire cluster rather than piling onto one node.
The tradeoff: virtual nodes add memory overhead (the ring metadata scales with V × N) and increase the complexity of the gossip protocol that maintains ring membership. In practice, 100–200 virtual nodes per physical node is the standard sweet spot, as used by Cassandra.
Cassandra. Uses consistent hashing natively for partition key distribution. Each row's partition key is hashed to a token, and each node owns a set of token ranges corresponding to its virtual node positions. Replication is handled by writing to the next R nodes clockwise from the primary token position (where R is the replication factor). This means Cassandra's partitioning, replication, and routing are all derived from the same ring data structure.
Amazon DynamoDB. Uses consistent hashing internally across its storage nodes. The paper "Dynamo: Amazon's Highly Available Key-Value Store" (2007) is the foundational reference for consistent hashing in production at scale. DynamoDB manages the ring membership and virtual node assignment entirely automatically — users interact only through partition keys.
Redis Cluster. Uses a variant: the key space is divided into 16,384 fixed hash slots, and each node owns a configurable subset of slots. Resharding moves slots between nodes. This is a fixed-slot approach rather than a pure consistent hash ring, but achieves the same minimal remapping property.
Distributed caches (Memcached clients, custom CDNs). Client-side consistent hashing libraries (libketama, twemproxy) distribute keys across Memcached nodes without requiring server-side coordination. The client hashes each key to a ring position and routes to the appropriate server. This is entirely stateless at the server level — Memcached nodes have no knowledge of each other.
Load the Distributed Cache blueprint in SysSimulator to observe consistent hashing in action under load. The blueprint models a sharded cache cluster with consistent hashing for key distribution.
Run traffic at 20,000 RPS and observe load distribution across cache nodes — with virtual nodes configured, each node should handle approximately equal request volume. Note the cache hit rate and per-node utilisation in the Metrics view.
Then simulate a node failure via the Chaos panel. With consistent hashing, watch what happens: only the keys owned by the failed node experience cache misses — approximately 1/N of keys (10% for a 10-node cluster). The remaining 90% of keys continue hitting their correct nodes. Compare this to the full-cache-invalidation scenario that would occur with modulo hashing.
Now add a node (scale out in the blueprint config). Again, only ~1/N of keys move — the new node absorbs its fair share of the key space from its neighbours, and the cache remains warm for the other 90% of keys. This demonstrates the operational value that makes consistent hashing worth the implementation complexity.
Open Distributed Cache blueprint →
Consistent hashing is rarely the topic of a standalone interview question. It appears as a follow-up when you propose a distributed cache or database sharding strategy. The interviewer asks: "How do you distribute keys across your cache nodes?" or "What happens when a cache node goes down?" Your answer to the second question is what reveals whether you know consistent hashing.
The wrong answer: "The other nodes take over." (Vague — no mechanism, no cost.)
The right answer: "I'm using consistent hashing for key distribution. Each node owns a range on the hash ring. When a node fails, only the keys it owned — roughly 1/N of the total — need to be re-routed. The rest of the keys continue hitting their correct nodes without any cache invalidation. With virtual nodes, the failed node's load is spread across multiple successors rather than dumping all of it on one neighbour."
Then add the numbers: "At 1 million cached keys and 10 nodes with 150 virtual nodes each, a node failure remaps approximately 100,000 keys. Those 100,000 keys will be cache misses on first access after the failure, hitting the origin database. At 20,000 RPS with 10% of keys affected, that's 2,000 RPS of extra database load during the warm-up window — our database can handle that." Numbers make the tradeoff concrete.
"Why not just use modulo hashing?" Modulo hashing remaps nearly all keys when cluster size changes, causing cache invalidation at scale. Consistent hashing remaps only 1/N keys. For a 10-node cluster, modulo hashing invalidates 90% of the cache on any membership change; consistent hashing invalidates 10%. At 1 million keys, that's the difference between 900,000 database fallback requests and 100,000.
"How do you handle hot keys?" Consistent hashing distributes keys uniformly, but some keys are accessed far more often than others. A hot key (a viral tweet's like count, a popular product page) can overwhelm its node even with perfect key distribution. Solutions: (1) local in-process cache in front of Redis for the hottest keys; (2) key replication — store popular keys on multiple nodes and distribute reads; (3) key sharding — split a single hot key into multiple sub-keys spread across nodes. The interviewer is checking that you understand consistent hashing handles distribution, not access frequency imbalance.
"What's the difference between consistent hashing and range-based sharding?" Range-based sharding (used by MySQL's RANGE partitioning and some NoSQL databases) assigns contiguous key ranges to nodes. This allows efficient range scans (all keys between A and B are on the same node). The downside: if certain ranges are accessed more than others (a product ID range for popular items), those nodes become hot. Consistent hashing distributes randomly, preventing range hotspots but making range scans require querying multiple nodes.
What problem does consistent hashing solve?
The key remapping problem: with modulo hashing, adding or removing one node causes nearly all keys to remap to different nodes, invalidating an entire cache. Consistent hashing ensures only 1/N of keys remap per membership change — minimal cache invalidation at any scale.
How do virtual nodes improve consistent hashing?
Without virtual nodes, hash positions are unlikely to be evenly spaced, creating uneven load across nodes. Virtual nodes assign each physical node 100–200 ring positions, spreading its ownership evenly. Node removal distributes absorbed load across many neighbours rather than one.
How does Cassandra use consistent hashing?
Partition keys are hashed to token values. Each node owns token ranges corresponding to its virtual node positions. Replication writes to the next R clockwise nodes from the token. The entire partitioning, replication, and routing logic derives from the ring.
What happens when a node is removed from the ring?
Only the removed node's keys remap — to its clockwise successor(s). With virtual nodes, the load is distributed across multiple successors. All other keys remain on their existing nodes unchanged.
What is the difference between consistent hashing and rendezvous hashing?
Both achieve minimal remapping. Consistent hashing uses a ring; rendezvous hashing scores each key against each node and picks the highest. Both are valid answers in interviews. Consistent hashing is more widely referenced and the expected answer.
See consistent hashing in SysSimulator → Browse all blueprints
Next in the series: Design a URL shortener →