Adding a shard without moving everything

Where does this key live?

Suppose a service stores customer documents on three machines. Every request arrives with a document ID. Before it can read anything, the service needs a cheap answer to one question: which machine owns that ID?

A first attempt is hash(id) % 3. It is easy to calculate and gives three possible destinations. Adding a fourth machine changes the divisor. A key whose hash is 11 moves from bucket 2 to bucket 3 even if neither of those machines is new. Many existing assignments change at once.

Arpit Bhayani’s lesson explains consistent hashing as an ownership lookup. Hello Interview’s explanation adds a useful question: how does that ownership change when machines join or leave? Work through both questions before drawing the database boxes.

A small ring you can calculate by hand

For this exercise, hash values lie between 0 and 99. The real hash space can be much larger; the small range makes the movement visible. Place A at 20, B at 55 and C at 85. A key belongs to the first token at or above its hash value. If there is no such token, wrap around to the smallest token.

D takes the interval (55, 70]. C used to own it. A key at exactly 70 goes to D under our boundary convention; a key at 55 stays with B. A key at 96 wraps to A. Those edge cases are worth checking in an implementation.

The hash function and the other token positions stayed fixed. That is why the unaffected intervals retained their owners. Spreading all the old tokens out again after every membership change would lose this property.

The ring is a sorted list

You do not need an array with a slot for every possible hash value. Store the assigned tokens in sorted order, with an owner beside each token. Find the first token greater than or equal to the key hash using a lower-bound search. Wrap to index zero if the search falls off the end.

tokens = [20, 55, 70, 85]
owners = [ A,  B,  D,  C]
i = lower_bound(tokens, stable_hash(key))
if i == len(tokens): i = 0
return owners[i]

With T tokens, the lookup takes O(log T) comparisons. Every router needs the same hash function, token map and interpretation of boundaries. A fast lookup against a stale map can still send a write to the wrong owner.

More tokens smooth ownership, not every workload

One token per machine can leave uneven intervals. Give each machine several tokens spread through the hash space and it owns several smaller intervals. When that machine leaves, its intervals can pass to several remaining machines instead of one neighbor absorbing everything.

These virtual nodes are routing entries, not extra machines or additional copies of the data. Replication is a separate choice. Nor do virtual nodes split one very popular key: requests for that key still meet at its owner. A hot document may need caching or a change to the data model even when the byte count is evenly distributed.

Ownership changes before bytes finish moving

Return to D at 70. Updating the map is quick; copying the documents in its interval may take minutes. During that interval, a router using the new map can ask D for a document that is still only on C.

A migration therefore needs an explicit handoff: identify the range, copy it, account for writes that arrive during copying, and switch routing only when the new owner can serve the required state. Versioned maps, forwarding and replication are possible ingredients. The right sequence depends on the storage system’s consistency contract.

In an interview, name what the algorithm settles and then finish the handoff story. As an exercise, remove B from the example. Only keys in (20, 55] change owner; with D present they move to D. Now ask how a read of hash 37 behaves halfway through that move.