Dynamic Rebalancing

When the cluster scales up or a node fails, data needs to be migrated from the old distribution to the new one. A good rebalance migrates only the minimum necessary data and does not interrupt reads and writes—virtual nodes in consistent hashing make this decentralized.

Overview

Consistent Hashing and Sharding Strategies solve "how data is distributed across nodes." However, when the cluster scales up (adding nodes) or scales down (node failure/shutdown), data needs to be migrated from the old distribution to the new one—this is rebalancing. A poor rebalancing scheme may migrate far more data than necessary and even cause service outages during migration. A good rebalance migrates only the minimum necessary data and does not interrupt reads and writes.

Three Rebalancing Strategies

Fixed Partitions: Simple but Rough

Pre-create partitions far exceeding the number of nodes (e.g., 100 partitions per node, totaling 1000 partitions for 10 nodes), keeping the partition count constant. When adding a node, some partitions are redistributed from each old node to the new one.

Before adding a node: Node-1: [p1..p100],  Node-2: [p101..p200], ... Node-10: [p901..p1000]
After adding a node:  Node-1: [p1..p90],   Node-2: [p91..p180],  ... Node-11 (new): [p901..p990]

• Migration granularity: Entire partitions (N keys moved together), not key-by-key.
• Disadvantage: Partition size is tightly coupled with the number of nodes—if the initial estimation is off (partitions are too large or too small), it is difficult to adjust later; the partition count is static and cannot split as data volume grows.

Redis Cluster uses this scheme: 16384 fixed slots.

Dynamic Partitions: Partitions Split as Data Grows

Each partition has a size limit (e.g., 10GB); when exceeded, it splits into two new partitions. When the number of nodes changes, partitions are migrated en masse to new nodes—similar to fixed partitions, but the partition count itself is dynamic.

Partition p3 reaches 10GB → splits into p3a and p3b (each ~5GB)
When migration is needed → move p3a entirely to a new node

• Advantage: The number of partitions is proportional to the total data volume, avoiding the "pre-created too many or too few" problem of fixed partitions.
• Cost: Requires a centralized coordinator to track partition metadata (which partition is on which node, which is currently splitting). HBase uses this scheme.

Consistent Hashing + Virtual Nodes: Decentralized Rebalancing

In Consistent Hashing, each physical node corresponds to multiple virtual nodes (vnodes, e.g., ~100 per node), distributed across the hash ring. When adding a node, the new node is inserted into the ring and takes over the token ranges covered by its vnodes (taken from adjacent nodes' vnodes); when removing a node, the ranges corresponding to its vnodes are taken over by neighboring vnodes.

Adding node N11 (with vnodes v1101..v1200) to the ring:
  Previously, token [5000, 5200] was on N3's v303
  Now v1101 covers [5000, 5200] → this range migrates from N3 to N11
  Only keys within the new node's range are migrated; other keys remain unchanged

• Minimal migration volume: Only keys falling within the new vnode's range are migrated, not entire partitions.
• Decentralized: Each node knows the global routing table via the Gossip Protocol, calculates itself which ranges it should take over, and does not rely on a coordinator.
• Cost: Migration granularity is the range covered by a single vnode, which may cause hotspots (a vnode's range contains too much data)—the solution is dynamically adjusting the number of vnodes or splitting vnodes by load (Cassandra's virtual node splitting).

Migration Engineering: How to Move Data Without Interruption

Regardless of the strategy, there are some common practices for the actual data migration process:

Dual-Write Transition

During migration, both old and new nodes simultaneously accept writes for that range:

1. Metadata update: Range [5000, 5200] migrates from N3 to N11
2. Transition period: Reads and writes still go to N3; N3 streams new writes to N11
3. N11 receives completion signal → Metadata update: [5000, 5200] now belongs to N11
4. Subsequent reads and writes go directly to N11

Dual-write ensures no writes are lost during migration: even if the new node is not fully ready, the old node continues to serve. Cassandra's nodetool move / decommission follows this approach.

Rate Limiting and Priority

Data migration consumes network and IO—migrating at full speed during business peak hours will overwhelm normal requests:

• Rate limiting: Limit migration bandwidth (e.g., Cassandra's stream_throughput_outbound_megabits_per_sec).
• Off-peak migration: Manually trigger during low-traffic periods.
• Incremental resync: First transfer the full snapshot, then transfer new writes that occurred during migration (similar to MySQL binlog catch-up).

Consistency Pitfalls

During migration, the N replicas of a single piece of data may span the old and new distributions—some replicas follow the old routing, while others follow the new routing. The solution is to migrate data first, then switch routing metadata (atomic switch, not replica-by-replica). Or, like Cassandra, check both old and new locations during reads (brief dual-routing during the transition).

Trade-offs and Failure Modes

• Full redistribution: Rehashing all keys when adding a single node → migration volume = total data / N, causing massive unnecessary migration. Always use consistent hashing or fixed partitions + partition migration.
• Hotspot vnodes: A vnode's covered range contains too much data, becoming a bottleneck during migration → monitor vnode sizes and split dynamically.
• Data loss during migration: Switching routing before moving data → always move data first, then atomically switch routing.
• Migration storm: Adding a large number of nodes at once, causing simultaneous migrations that may overwhelm the cluster → add nodes one by one, waiting for rebalancing to complete before adding the next (recommended by Cassandra).

References

• Paper: "Dynamo" (Consistent Hashing Rebalancing, 2007)

Keywords: rebalancing, fixed partition, dynamic partition, hash ring, virtual node, vnode, data migration, minimal migration, dual-write transition, progressive migration, rate limiting, atomic routing switch, hotspot vnode