Consistent hashing and virtual nodes

01What is consistent hashing, and why not modulo N?

The common ring version hashes both keys and machine positions into the same circular number space. A key belongs to the next machine position clockwise. A virtual node, or token, is an additional ring position assigned to a physical machine, not another server. We will compute the placement before discussing migration and balance.

A distributed hash table associates keys with values and uses a deterministic rule to locate their owners. In a metadata-cache example, keys P12 and P35 identify records; a hash function maps each key to a numeric placement position. Placement stability determines how much cached or durable data must move when membership changes.

One cache is easy to address but eventually runs out of memory or throughput. With three caches, the application must decide where P35 lives. A common first rule is hash(key) mod 3. Everyone can calculate the same owner without a lookup table for every object.

Here mod means the remainder after integer division. Number the three destinations 0, 1 and 2; dividing a key’s hash by 3 produces one of those remainders, which selects its destination. All clients using the same hash and machine numbering therefore agree where to send that key.

The difficulty appears when a fourth machine joins. Changing the rule to mod 4 moves many keys. For a numeric hash of 35, the remainder changes from 2 to 3; for 12, it stays 0. Some mappings remain, but widespread movement can create cache misses or durable-data migration. We want a placement rule that changes fewer existing assignments when capacity changes.

02The hash ring: clockwise ownership with five keys

For a small worked example, let hashes range from 0 through 99. Connect 99 back to 0 to form a circle. Put cache A at position 20, B at 50, and C at 80. Real systems use a much larger space; the tiny range lets us compute every step by hand.

To locate a key, hash it and move clockwise until reaching the first cache position, including an exact match. That cache owns the key under our convention. P35 hashes to 35, so it reaches B50. P90 reaches the end of the range, wraps through zero, and reaches A20.

Each position owns the interval after its predecessor and through itself. B therefore owns (20,50]: positions greater than 20 and less than or equal to 50. The round bracket excludes 20; the square bracket includes 50.

Hash collisions are expected in a placement space: two different object keys may map to the same number and therefore the same machine. Store and compare their full keys so they remain different records. Consistent hashing chooses an owner; it does not make a key unique. Clients must also use the same hash function, key encoding, token order, and membership version to calculate the same owner.

03Adding and removing a node: which keys move?

Add D at position 40. It becomes the first clockwise owner for hashes in (20,40]. B’s old interval splits: D takes (20,40], while B keeps (40,50]. Key P35 moves from B to D; P45 stays with B. Other intervals are unchanged.

Next remove B. Its remaining interval moves to the next position, C80. P45 now moves to C. This removal does not require moving P12, P35, P65, or P90.

Consistent hashing tries to preserve existing assignments where membership change does not require a new owner. The ring is a placement mechanism, not a promise that the new machine already contains the object. We still need to move or rebuild data and coordinate routing.

04Virtual nodes, balance, and physical failure domains

Our original intervals are unequal: A owns the wraparound interval (80,20], B owns (20,50], and C owns (50,80]. With uniformly distributed hashes, A owns about 40% of the space while B and C own about 30% each. Randomly choosing one position per machine can produce even larger imbalances.

Virtual nodes assign several positions to each physical machine. For example, A can own tokens A1 and A2 in separate parts of the ring. It then receives several smaller intervals rather than one possibly large interval. More well-distributed positions tend to smooth random imbalance and permit capacity-aware allocation.

To make virtual nodes concrete, use a separate six-token example with A at 10 and 60, B at 30 and 80, and C at 45 and 95. A owns (95,10] and (45,60]: 15 + 15 = 30 positions. B owns two 20-position intervals, totaling 40; C owns two 15-position intervals, totaling 30. Two tokens per host do not guarantee perfect balance. The benefit appears statistically or through deliberate token allocation across many smaller ranges.

A production example is Cassandra's token-based placement: multiple tokens may belong to one node, while replica selection must skip duplicate physical owners. Increasing token count also adds placement metadata and more ranges to manage; choose it from operational needs rather than assuming the largest possible value is best.

A ring is not the only way to keep most assignments stable when membership changes. Another approach ranks the eligible machines separately for each key. A newly added machine takes that key only if it outranks the existing winner, avoiding the need for token positions.

Rendezvous hashing, also called highest-random-weight hashing, is another placement algorithm. Compute a deterministic score hash(key, nodeId) for each eligible node and choose the highest, using a stable tie-breaker. With illustrative scores A=.31, B=.86 and C=.54, the key belongs to B. Adding D with .70 leaves it on B; adding D with .93 moves it to D. Removing a node changes only keys that selected it. All routers need the same membership and scoring rules.

Unlike a token ring, the simple implementation evaluates all N nodes per lookup. It avoids virtual-node metadata but pays O(N) scoring cost, meaning the number of scores grows in proportion to the number of nodes; optimized variants and weighting require their own analysis. Neither placement method fixes a single hot key or performs safe data migration.

Interview check: Does adding a node move every key? No. A key moves only if the new node outranks its previous owner; moving durable bytes and changing write authority are separate steps.

05Estimate movement and recognize hot-key limits

Assume 1.2 million equal-sized metadata objects, equal-capacity machines, and balanced placement. Adding a fourth machine to three should move about one quarter of the keys, roughly 300,000, to the new machine on average. At an assumed 500 bytes per object, that is about 150 MB of payload before indexes, protocol overhead, or redundant copies.

More generally, adding one machine to N existing balanced owners moves an expected fraction near 1/(N+1); removing one of N owners moves near 1/N. These are distribution-based estimates. Our fixed D40 example takes a 20-position interval, not exactly 25% of the ring.

Fixed logical buckets offer another way to separate keys from physical machines. A bucket is a stable group of keys; a routing map records which machine currently owns each group. Changing that map can move selected groups without changing every key’s grouping rule.

A logical bucket is a stable group of keys, such as bucket 17 of 1,024, that a routing map assigns to a physical machine. Moving bucket 17 changes its physical host without changing the hash modulus for every key. A ring is one good placement strategy, not a prerequisite for every sharded system.

06Data migration: copying, catch-up, and routing cutover

For an ordinary cache, D can start empty and fetch P35 from the authoritative database on a miss. But a sudden transfer of many hot keys can overwhelm that database. Warm selected keys, limit concurrent refills, and keep origin protection active during the change.

For durable storage, keep B’s copy until D is ready. Copy a consistent snapshot of the moving range, record and apply updates made during copying, then verify D’s data before making it the writer. Give the routing change a version so clients can detect old routes. During the move, keep one writer or use a protocol that explicitly coordinates the handover.

Suppose a write updates P35 while copying occurs. The destination must receive the newer version before it becomes authoritative, or the old owner must forward/reject according to the migration protocol. A stale client sending to B needs a safe redirect or forwarding path. Retain rollback information until verification completes. Ownership math says where P35 belongs; it does not implement this data-transfer protocol.

07Interview answer: draw the ring and explain the tradeoff

Interviewer: “What does consistent hashing solve when we add a cache?”

Candidate: “It reduces placement changes. On our 0–99 ring, P35 belongs to B50. Adding D40 transfers only the interval (20,40], so P35 moves to D while P45 stays with B. That can avoid the broad remapping from changing a modulo divisor.

“I would add virtual positions to improve placement balance, but I would still check object sizes and hot-key traffic. For a cache I need controlled refill; for durable storage I need snapshot transfer, concurrent-update catch-up, and safe routing cutover. The ring also does not provide read consistency or replication automatically.”

This explanation can be replayed on a whiteboard with five keys. It shows why the technique helps, when its balancing assumptions fail, and which essential migration decisions remain outside the hashing algorithm.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.