Consistent Hashing

You're distributing data across nodes. Naive hashing means adding or removing a node reshuffles almost everything. Consistent hashing is the technique that makes distributed caches and databases possible, and it's a top interview topic.

---

The Concept Explained

You have a set of keys and a set of nodes, and you need a rule that maps each key to exactly one node. The rule has to be deterministic so any client can compute it without asking anyone, and it should spread keys evenly so no node is overloaded.

The obvious answer is to hash the key and take the remainder modulo the node count. It is one line of code, it distributes keys evenly, and any client can compute it independently. For a fixed set of nodes it is genuinely the right answer.

The problem appears the moment the node count changes, and in a distributed system the node count changes constantly: a machine fails, a machine is added, a deploy replaces a node. When N becomes N+1, the modulus changes, and almost every key maps somewhere new.

The magnitude is worth being precise about, because "some keys move" undersells it badly. Going from 10 nodes to 11, roughly 91% of keys change owner. From 100 to 101, about 99% move. The fraction that stays put is roughly one over the new node count, so the disruption gets worse as the cluster grows.

Consistent hashing exists to make that number small and, critically, to keep it small as the cluster grows.

---

How It Works

Instead of mapping keys directly to nodes, map both keys and nodes into the same abstract space, then assign each key to the nearest node in that space.

Picture the output range of the hash function bent into a circle, from zero round to the maximum hash value and back to zero. Hash each node's identifier and place it on the circle. Hash each key and place it on the circle too. A key belongs to the first node encountered walking clockwise from the key's position.

The insight is that node positions no longer depend on the node count. Each node sits wherever its own hash puts it, and adding a node does not move any existing node.

The arithmetic that makes this worth doing: adding one node to a cluster of N moves roughly one over N+1 of the keys. Ten nodes going to eleven moves about 9% of keys, where modulo hashing moved 91%. At a hundred nodes it moves about 1%, where modulo moved 99%. The larger the cluster, the better consistent hashing looks and the worse modulo looks.

The Problem Consistent Hashing Creates

Placing each node at a single random point produces uneven arcs. Hash values are uniformly distributed, but uniformly distributed points on a circle do not produce equal gaps. Some nodes land close together and own tiny slices, others land far apart and own large ones. With a handful of nodes the imbalance is severe, and one node routinely owns several times the average share.

It gets worse on failure. When a node dies, its entire arc transfers to exactly one neighbour, which now owns roughly double its previous share. That neighbour is already under whatever load caused the first failure, and now it gets a step change in traffic. This is a cascading failure waiting to happen.

Virtual Nodes Fix Both Problems

Instead of placing each physical node once, place it many times, at positions derived from hashing the node identity together with a replica index.

With, say, 200 virtual nodes per physical node, the circle is divided into many more, much smaller arcs, and each physical node owns a scattered collection of them. Two things improve immediately.

Balance. Averaging over 200 small random arcs produces a far tighter distribution than one large random arc. The relative spread narrows as the square root of the number of virtual nodes, so a few hundred is generally enough to bring imbalance down to a few percent.

Failure spreading. A failed node's virtual positions are scattered around the circle, so their arcs are inherited by many different neighbours rather than one. The load from a lost node spreads across the surviving cluster instead of landing entirely on the node next door.

Virtual nodes also give you weighting for free. A machine with twice the capacity gets twice the virtual nodes and receives roughly twice the keys, which is how heterogeneous clusters are handled without a separate mechanism.

---

System Design Implications

Consistent hashing shows up wherever a keyspace is spread over a changing set of machines, which is most distributed data systems: partitioning in Dynamo-style databases and Cassandra, key distribution in memcached and Redis client libraries, shard placement in search clusters, and session or connection affinity in load balancers.

Several design consequences follow from choosing it.

Routing needs no coordinator. Any client that knows the membership list and the hash function computes ownership locally. That removes a lookup service from the request path, which removes a SPOF and a network hop. The cost is that every client must agree on membership, which is why these systems pair the ring with a gossip protocol or a consensus-backed membership store.

Replication is a walk, not a separate scheme. To keep R copies, store the key on the first R distinct physical nodes clockwise from its position. Skipping virtual nodes belonging to a physical node already holding a copy is essential, and forgetting that check is a real bug that produces multiple replicas on one machine.

Rebalancing is bounded but not free. The keys that move must actually be transferred, and during the transfer both the old and new owner may be serving requests for them. Systems handle this with handoff protocols and by serving reads from the old owner until the new one confirms it has the data.

Hot keys are not solved. Consistent hashing distributes keys evenly. It does nothing about one key receiving a million requests per second, because that key still maps to one node. That needs a different tool: replicating the hot key to several nodes, or adding a random suffix and fanning reads across the variants.

---

Tradeoffs and Decision Framework

Approach	Keys moved when N changes	Distribution evenness	Lookup cost	Complexity
Modulo N	Nearly all	Excellent	Constant	Trivial
Consistent hashing, 1 point per node	About 1/N	Poor at small N	Log of node count	Moderate
Consistent hashing with virtual nodes	About 1/N	Good, tunable	Log of total positions	Moderate
Fixed shard count with a lookup table	Only reassigned shards	Excellent	Table lookup	Needs a directory service

Choose modulo hashing when the node set genuinely does not change, such as a fixed set of partitions in a batch job. It is simpler and there is no reason to pay for machinery you will not use.

Choose consistent hashing with virtual nodes when membership changes at runtime and clients need to route without a coordinator. This is the default for caches and for peer-to-peer style datastores. Use a few hundred virtual nodes per physical node as a starting point.

Choose a fixed large shard count with an explicit shard-to-node table when you want precise control over placement, for example to satisfy data residency or to move a specific hot shard deliberately. Create many more shards than nodes at the outset and reassign whole shards. Kafka partitions and many sharded relational setups work this way. The cost is that you now run a directory service and must keep it available and consistent.

---

Common Mistakes

Explaining the ring without quantifying the problem it solves. The 91% versus 9% comparison is the whole point, and an answer that omits it has described a mechanism without a motive.

Omitting virtual nodes. A plain ring is badly unbalanced at realistic cluster sizes and dumps a failed node's entire load onto one neighbour. Interviewers ask about virtual nodes specifically because it separates recall from understanding.

Believing it solves hot keys. It balances the number of keys, not the traffic to any individual key. A single hot key still lands on a single node.

Forgetting distinct physical nodes when replicating. Walking clockwise for R replicas without skipping virtual nodes of the same machine puts multiple copies on one box, so a single failure loses several replicas at once.

Assuming rebalancing is instant. Keys have to be copied, and the system needs a defined behaviour for reads and writes during the transfer.

Using a poor hash function. Anything with clustering or weak avalanche properties produces uneven arcs no amount of virtual nodes will rescue. MD5 and murmur are the usual choices here for distribution quality, not for security.

Letting clients disagree on membership. Two clients with different views of the ring will route the same key to different nodes, producing what looks like data loss but is really two consistent answers to different questions.

---