When Shards Must Move
Over time shards grow unevenly or a cluster simply needs more nodes. Rebalancing moves data so load and storage spread fairly. Doing this without downtime is one of the trickiest operations in a sharded system.
The Naive Trap
A tempting scheme is to assign a key to shard number hash mod N, where N is the node count. But adding one node changes N, so almost every key maps to a new shard. Nearly all data must move at once. This is unacceptable at scale.
Better Approaches
- Consistent hashing places nodes and keys on a ring so adding a node moves only the keys near it, roughly one over N of the data.
- Fixed virtual partitions split data into many small partitions up front, far more than nodes. Rebalancing just reassigns whole partitions between nodes, never resplitting keys.
Doing It Live
Rebalancing online means copying a partition to its new home while the old copy still serves traffic, then cutting over routing once the copy is caught up. The system tracks in flight moves so reads and writes follow the data. Throttling limits the copy rate so migration does not starve normal queries.
Key idea
Rebalancing should move minimal data; consistent hashing or fixed virtual partitions avoid the mod N trap of remapping almost every key.