When nodes are added to or removed from a partitioned cluster, walk through how rebalancing actually moves data. What are the main strategies (e.g., a fixed number of partitions per node vs. dynamically splitting partitions by size), and what can go wrong during the process?

## What rebalancing is Rebalancing is the process of moving data between nodes so that each node in a partitioned cluster ends up with a proportionate share after the cluster's membership changes: - a node is added to relieve load, - a node is removed for maintenance, - or a node fails and needs its data reconstructed elsewhere. It has two logically separate parts worth pulling apart: 1. **The assignment decision** — which partitions should live on which nodes now? 2. **The data-movement mechanism** — how do bytes actually get from the old owner to the new owner without breaking availability or correctness along the way? ## The two assignment strategies The assignment decision is where the two dominant strategies diverge. **The fixed-partition-count approach** decides, at cluster creation time, on a partition count well above the number of nodes ever expected — a common rule of thumb is roughly 10x the eventual maximum node count — so each node initially owns many partitions, and as nodes are added, whole partitions get reassigned from existing nodes to the new one. Because partitions are moved as indivisible units and never split further, the assignment algorithm is comparatively simple: essentially a load-balancing/bin-packing problem over a fixed set of items. The real risk is choosing the wrong partition count upfront — too few, and you can't spread data thin enough across a cluster that grows much larger than expected; too many, and each partition carries fixed overhead (metadata, compaction bookkeeping, replication streams) that adds up needlessly at low node counts. This strategy is common in hash-partitioned systems like Cassandra and Riak, both descended from the Dynamo design. **The dynamic-partitioning approach** instead lets the number of partitions grow and shrink with the data itself: a partition exceeding a configured size or request-rate threshold gets split in two, each half potentially migrating to a different node to spread load, and partitions that shrink can be merged back together. This adapts naturally to unpredictable or highly skewed growth without needing to guess a partition count in advance, but requires an active coordinator continuously deciding when and how to split/merge, plus bookkeeping to track changing partition boundaries over time — meaningfully more operational and implementation complexity. This is the model used by range-partitioned, LSM-tree-based systems like HBase and Bigtable, where region splitting (HBase's term) is a well-known, automatic background process. | Strategy | Partition count | Assignment | Seen in | |---|---|---|---| | **fixed-partition-count** | decides at cluster creation time; partitions move as indivisible units | comparatively simple — a load-balancing/bin-packing problem | Cassandra and Riak | | **dynamic-partitioning** | grows and shrinks with the data itself | an active coordinator continuously deciding when and how to split/merge | HBase and Bigtable | ## Stream, then cut over The data-movement mechanism matters independently of which assignment strategy is used. The safe pattern most systems converge on is: 1. the destination node begins streaming a copy of the partition's data from the source (often a snapshot plus a stream of subsequent changes, to avoid losing writes that happen during the copy), 2. the source keeps serving reads and writes throughout, 3. and only once the destination has fully caught up does the system perform an **atomic cutover** — updating routing metadata so new requests go to the destination, while in-flight requests against the source complete. Getting this ordering wrong is the source of most rebalancing correctness bugs: cut over routing before the destination has all the data, and reads against the new owner return incomplete results; forget to keep capturing writes that land on the source during the copy, and those writes are silently lost from the destination's copy. ## Failure modes in production Several concrete failure modes show up in production. - **Thundering-herd rebalancing** happens when a node addition or removal triggers many partitions to move simultaneously, saturating network bandwidth and disk I/O across the cluster and causing latency spikes on totally unrelated partitions that happen to share the same physical links or disks — well-designed systems throttle the rate of concurrent partition moves for exactly this reason, trading a slower rebalance for a stable one. - **Stale-routing windows** happen when clients or coordinators haven't yet learned about a completed cutover and keep sending requests to the old owner, which must either reject, forward, or (worse, if not handled) silently serve now-outdated local data — this is why many systems keep the old owner able to forward or redirect for a grace period after cutover. - **Compounding movement plans.** A related risk during simultaneous multi-node changes is those plans conflicting with each other if the coordinator doesn't serialize or carefully merge them, which some systems handle by allowing only one rebalance operation in flight per partition at a time. ## Where it shows up in real systems A concrete real-world illustration: - **Cassandra's bootstrap process** streams token-range data to a newly joining node using its consistent-hashing-with-vnodes assignment, and operators are explicitly advised to add nodes one at a time and let streaming complete before adding the next, precisely to avoid the thundering-herd and conflicting-rebalance-plan failure modes described above. - **HBase's automatic region splitting** is the dynamic-partitioning counterpart, splitting a region once it exceeds a configured size and letting the master reassign the resulting two regions across region servers as a separate load-balancing step.