Build a wide-column store (Cassandra / DynamoDB family) (13 scenes)
Scene 03

Adding a server remaps everything — hash-mod-N and the cluster-wide rebalance

Hash-mod-N has a catastrophic property: when N changes from N to N+1, roughly (N-1)/N of all keys change home — a cluster-wide rebalance, not a gentle nudge.

Previously

Hash mod N looked perfect — let's stress-test it by doing the most ordinary operational thing: adding one server.

Scene 03

Adding a server remaps everything

  1. Watch
  2. Try it
  3. Predict
  4. Capture
INCOMING KEYSu-7u-13u-22u-5u-29u-30u-23u-6u-14u-39u-28u-11hash(k) mod 4evenly-spread routingMIGRATION0 / 12keys re-homed (0%)N: oldN → newN4 → 4SERVERS1S03S14S24S3N: 4 → 4 — steady state. 0 of 12 keys move.
0 / 12 keys re-homed — steady state
What to watch for

Same 12 keys you saw last scene, same 4-server cluster. After a beat, watch what happens when one server is added — the migration counter spikes and most dots turn orange. That's a rebalance.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

migrationFraction
what fraction of keys change home when N changes
def migrationFraction(oldN, newN):
    moved = 0
    for key in keys:
        if hash(key) mod oldN != hash(key) mod newN:
            moved += 1
    return moved / len(keys)
 
# closed form for oldN -> oldN+1: ~ (oldN - 1) / oldN
# 4 -> 5 ~ 80% ; 8 -> 9 ~ 88% ; never small.
Cluster.rebalance
the actual per-key migration loop that runs when N changes
def rebalance(oldN, newN):
    for key in all_keys:
        oldOwner = servers[hash(key) mod oldN]
        newOwner = servers[hash(key) mod newN]
        if oldOwner != newOwner:
            stream(key, oldOwner -> newOwner)
            # cache miss on read until copy lands
    flip_routing(newN)

Where this sits in Build a wide-column store (Cassandra / DynamoDB family)

Scene 03 of 13, in the Sharding act — Hash mod N spreads load — until adding a server reshuffles 80% of keys.. When N changes from 4 to 5, almost every key's home changes — a cluster-wide migration.

Up next. Hash mod N reshuffled 80% of keys when N changed; we need a geometry where servers live in the same space as the keys, so adding one only nudges its neighborhood.

All 13 scenes in Build a wide-column store (Cassandra / DynamoDB family) · Every curriculum

Built with Arqly
Every scene in Build a wide-column store (Cassandra / DynamoDB family) builds on the one before it.All 13 Build a wide-column store (Cassandra / DynamoDB family) scenes