Adding a server remaps everything

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

Scene 03 · Adding a server remaps everything

When N changes from 4 to 5, almost every key's home changes — a cluster-wide migration.

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

Watch

Diagram

The same four-bin layout from scene 2, plus space for new bins as N grows. A migration counter at the top tallies how many of the 12 key dots changed home when N flipped. Migrating dots animate as orange streaks toward their NEW bin; stationary dots stay grey. **rebalance** = the bulk movement of keys when a cluster's membership or routing scheme changes.

0 / 12 keys re-homed — steady state

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.

Implementation

migrationFraction

what fraction of keys change home when N changes

1def migrationFraction(oldN, newN):
2    moved = 0
3    for key in keys:
4        if hash(key) mod oldN != hash(key) mod newN:
5            moved += 1
6    return moved / len(keys)
7 
8# closed form for oldN -> oldN+1: ~ (oldN - 1) / oldN
9# 4 -> 5 ~ 80% ; 8 -> 9 ~ 88% ; never small.

Cluster.rebalance

the actual per-key migration loop that runs when N changes

1def rebalance(oldN, newN):
2    for key in all_keys:
3        oldOwner = servers[hash(key) mod oldN]
4        newOwner = servers[hash(key) mod newN]
5        if oldOwner != newOwner:
6            stream(key, oldOwner -> newOwner)
7            # cache miss on read until copy lands
8    flip_routing(newN)

PreviousSplit keys with hash mod N NextThe ring — keys and nodes on a circle