Adding a server moved almost everything

A hypothetical service routes keys with hash(key) % N. You add a fifth server to a four-server fleet. The new server should take roughly one fifth of the data. Instead, most keys change owners.

More capacity arrived with a migration large enough to consume it.

Test the routing function with small numbers

Take hashes 0 through 19. Under modulo four, owners repeat 0,1,2,3. Under modulo five, they repeat 0,1,2,3,4. Only hashes 0,1,2,3 keep the same numbered owner: 80% move.

Separate key placement from machine count

A consistent-hash ring places node tokens and keys in one ordered hash space. A key belongs to the first token at or clockwise after its hash, wrapping at the end. Adding a token transfers its preceding interval to the new owner.

pythonCopy
# Lookup sketch: tokens is sorted; owners has the same length.
from bisect import bisect_left

def owner(key_hash, tokens, owners):
    if not tokens:
        raise ValueError("empty ring")
    return owners[bisect_left(tokens, key_hash) % len(tokens)]

Lookup is $O(\log M)$ for $M$ sorted tokens. Define collision handling, a stable cross-language hash/encoding, and a versioned membership view. A randomized evenly weighted ring with enough tokens moves an expected share near $1/(N+1)$ when adding one node to $N$; that is not a worst-case traffic guarantee.

Multiple virtual nodes per physical host reduce random ownership imbalance and permit weighting. In a simple random-allocation model, relative spread improves on the order of $1/\sqrt V$ as virtual-node count $V$ grows. More tokens cost metadata and movement complexity. Deliberate token allocators have different behavior. When selecting replicas, choose distinct physical failure domains, not merely the next few virtual tokens.

A directory makes movement explicit

Another design hashes keys into many fixed logical buckets, then looks up each bucket's physical owner. You can move selected buckets by size or traffic without redefining the key hash. A range partitioner makes ordered scans local but can concentrate monotonically increasing writes in the newest range. Rendezvous hashing scores candidate nodes and chooses the highest score; the straightforward lookup costs $O(N)$ and has different metadata trade-offs.

Client-side routing avoids a proxy hop but distributes topology logic to clients. Proxy routing centralizes it but adds another tier and pool budget. In either case, the data owner must validate ownership; a stale router cannot be trusted to enforce a write boundary.

Mental model: hashing decides a location. Indirection decides how expensive it is to change that location.

Transfer: the largest tenant

---

Source trail: 01-consistent-hashing, 08-database-sharding-and-partition-keys, 08-sharding-hot-keys-and-rebalancing. See the source map for consolidation and reference-retained material.