Consistent Hashing Virtual Nodes and Resharding

01 The idea

The problem this lesson solves

With hash(key) modulo the server count, adding a server changes the divisor and can move a large fraction of keys. Consistent hashing uses stable positions on a ring so a new position captures a limited interval. We will calculate ownership by hand, compare it with modulo placement, and then separate the placement algorithm from the much harder job of moving live data safely.

Use the API, database, capacity and cache concepts from earlier modules. These lessons add distributed ownership and failure trade-offs.

02 Worked example

Add D without moving every key

03 The method

Understand the mechanism

See why modulo placement changes broadly

Suppose keys are represented by integers and the owner is key modulo N. With three owners, key 5 maps to remainder 2; with four, it maps to remainder 1. Many keys change owners because the entire arithmetic function changed.

For keys 0 through 11, compare modulo 3 and modulo 4. Only 0,1,2 retain the same numeric owner label; nine of twelve move. This is a finite worked example, not a measurement of a production hash distribution.

Broad remapping can create a cache-miss storm or require moving a large amount of durable data. The cost depends on whether old placement is merely a disposable cache copy or the authoritative storage location.

A placement strategy should make membership changes manageable while preserving the routing contract. That is the problem consistent hashing addresses. It does not itself copy records, elect leaders or define a consistency model.

Assign keys to the first clockwise token

Use a circular space from 0 to 99. Place A at token 20, B at 50 and C at 80. A key belongs to the first token at or after its position, wrapping to the beginning when needed.

For keys 5,25,35,55,75,95, the owners are A,B,B,C,C,A. Key 95 wraps past 99 to A at 20. Under this convention, B owns the interval (20,50], C owns (50,80], and A owns the remaining wraparound interval.

The boundary convention matters. A key exactly at 50 belongs to B in this model because the comparison is greater than or equal. An implementation using a different convention must use it consistently for routing and movement.

In real systems, a stable hash maps application keys into a large numeric space. Clients and servers must agree on the hash, token set, encoding and metadata version. Different interpretations can route the same key to different owners.

Add a token and calculate the moved range

Add D at token 60. D captures (50,60], which previously belonged to C. Keys outside that interval retain their owner under this ring change.

Our six sample keys now map to A,B,B,D,C,A. Only key 55 moves, so one of six observed keys, approximately 16.7%, changes owner. The interval itself spans ten of the hundred numeric positions under this toy space; the sampled keys are not uniformly spaced enough to make their observed percentage identical to the interval fraction.

Expected balanced fractions require assumptions about token placement, hash distribution and node weights. Do not promise that every newly added node moves exactly 1/N of every real dataset. A small sample or uneven tokens can differ substantially.

Removing a token also changes ownership of a defined interval. If D disappears from this placement model, its interval returns to the next clockwise owner C. Serving durable data after a real failure still requires a surviving copy or recovery protocol.

Use virtual nodes or stable logical partitions for finer placement

One token per physical machine can produce uneven intervals. Giving each physical owner multiple token positions divides its ownership into smaller pieces and can smooth placement under suitable distribution assumptions.

When a new physical owner receives several virtual positions, it can acquire smaller ranges from several existing owners rather than one large contiguous range from a single neighbor. More tokens also mean more metadata, movement units and bookkeeping.

A stable logical-partition design offers a related alternative: hash keys into many fixed partition ids, then map those ids to physical servers through a directory. Adding a server moves selected partitions without changing the key-to-logical-partition function.

Weight placement by measured capacity where needed, and distinguish balanced bytes from balanced request load. One viral key remains one key even if the ring has thousands of virtual nodes. Placement refinement does not automatically split that key’s traffic.

Move live data with a protocol

For a durable partition move, begin with the old owner authoritative. Copy the relevant data to the new owner while recording or streaming changes that happen during the copy. Catch up those changes and verify that the new owner is ready under the migration’s consistency rules.

At cutover, establish which owner may accept writes and update routing metadata. Delayed clients still using an old map need explicit behavior, such as forwarding through the old owner or receiving a route-version error and retrying safely. Avoid a period where both independently accept conflicting authoritative writes.

Rollback is not merely changing a pointer back after the new owner has accepted writes. The old owner must receive those changes or another recovery procedure must preserve them. State which phases can be rolled back easily and which require additional synchronization.

Test failures during copy, catch-up, authority switch and cleanup. Keep old data until the retention and verification policy permits removal. A successful placement calculation is only evidence that routing chooses an owner, not evidence that the owner has the right data.

Implement and inspect the small model

The Python model stores sorted token-owner pairs. bisect_left finds the first token not less than the key. Taking the resulting index modulo the number of tokens wraps an insertion point at the end back to the first token.

The model assumes a nonempty ring and numeric key positions already in the ring’s space. It deliberately omits hashing arbitrary strings, persistence, replication and concurrent membership changes. Those omissions make the placement rule easy to inspect, but they must remain visible.

Compare output before and after adding D, and list moved keys rather than reporting only a percentage. Then include a key exactly at a token and one beyond the last token to test boundary behavior.

Use the model as one component of a design argument: it explains locality of placement changes. Combine it with a separate ownership and migration protocol before claiming that a distributed database can be resharded safely.

# 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