Consistent Hashing Virtual Nodes and Resharding

01 The idea

The problem this lesson solves

The ring has A at 20, B at 50 and C at 80. The six key positions are 5,25,35,55,75,95.

Prerequisite: earlier lessons introduce the vocabulary and shared examples used here. Follow the module order.

02 Worked example

Follow one worked example

Trace the example in order. Follow the same identities, units and state transitions through the diagram and the events below.

Changing the owner function is only one step; live data movement must preserve an explicit read and write ownership protocol.

03 The method

Mechanisms decisions and a guided tutorial

Work through the explanation in order, then apply it in the tutorial. Each comparison names a cost as well as a benefit.

Use logical partitions to make movement manageable

If application code computes hash(key) modulo the physical node count directly, changing that count remaps many keys. Instead, map to a larger stable set of logical partitions and maintain a versioned mapping from partition to physical owner. A migration copies data, catches up concurrent changes, validates the destination, cuts over routing and retains a rollback path. During the transition, reads and writes must follow an explicit ownership protocol. Copying rows alone is not a resharding strategy.

Read a consistent-hash ring

Hash each key to a position on a circle. Starting at the key position, walk clockwise to the first node token, wrapping around if needed. That token's node owns the key. With tokens A at 20, B at 50 and C at 80, key 35 belongs to B and key 95 wraps to A. Adding D at 60 changes only keys in the interval (50,60] to D. The fraction moved depends on token placement and key distribution; the familiar approximate 1/(N+1) result assumes balanced placement and uniformly distributed keys.

Virtual nodes improve balance but do not cure everything

Give each physical node multiple token positions so its ownership consists of several smaller ranges. This often smooths uneven ranges and makes movement more flexible, at the cost of more metadata. One extremely popular key remains hot under simple ownership even with many virtual nodes. Replication, request coalescing and hot-key-specific serving strategies solve different parts of that problem.

Follow the first clockwise owner

Use a ring from 0 to 99 with A at 20, B at 50 and C at 80. A key at 35 belongs to B because B is the first token at or after 35. A key at 95 wraps to A. Adding D at 60 transfers the interval (50,60] from C to D.

The selected keys 5,25,35,55,75,95 originally map to A,B,B,C,C,A. After adding D they map to A,B,B,D,C,A. One of six selected keys moves. The observed 16.7 percent is a property of this sample and placement, not a universal promise. Expected balanced-fraction claims require suitable assumptions about tokens and key distribution.

Separate balance from popularity

Several virtual nodes per physical owner split ownership into smaller ranges and can smooth uneven placement. A stable set of logical partitions can also be mapped through a directory to physical nodes, making movement explicit and manageable. Both add routing metadata and operational work.

Neither automatically divides one extremely popular key. Uniformly distributed key hashes can still produce highly nonuniform request rates. Measure key concentration and per-owner demand, then choose a hot-key serving strategy independently of the partition-count strategy.

Migrate while writes continue

A live move typically copies the affected data, catches up concurrent changes, verifies the new owner, coordinates cutover and retains a recovery or rollback path. Readers and writers must agree which owner is authoritative during each phase.

If clients independently switch routing at different times without a protocol, writes can diverge or reads can miss data still on the old owner. Version routing metadata and define forwarding, dual-read or other transition behavior carefully. The Python tutorial computes placement only; it deliberately does not implement replication, consensus or migration correctness.

Guided tutorial

1. Assign by hand

Use the original tokens and calculate owners of all six sample keys.

2. Add the token

Find the newly owned interval before rerunning the console.

3. Run Python

Compare the printed owners with your trace.

4. Write migration phases

Name the authoritative writer, catch-up condition and rollback behavior at each phase.

# Python 3: a placement model, not a database cluster
from bisect import bisect_left
ring = [(20, 'A'), (50, 'B'), (60, 'D'), (80, 'C')]
positions = [token for token, _ in ring]
for key in [5, 25, 35, 55, 75, 95]:
    owner = ring[bisect_left(positions, key) % len(ring)][1]
    print(key, owner)
# Expected owners: A B B D C A

05 Cheat sheet

Review the decisions

Use this table to explain the mechanism and its limit without memorizing a product name.

06 Where & why

Check the primary references

Use official references for protocol and implementation details. The questions here are teaching prompts.

07 Interview questions

Explain the reasoning out loud

Answer before opening the explanation. The questions progress from vocabulary to decisions and failure behavior.

08 Practice problems

Practice a new case

Solve the new cases before revealing hints. Complete worked solutions follow the set.

Worked solutions