Rebalancing Partitions

How a partitioned database moves data when machines join or leave: fixed, dynamic and per-node partitioning, moving a partition without downtime, and how clients find the new owner.

Overview

A partitioned database does not stay the same size. Data grows, traffic grows, machines fail and get replaced. Rebalancing is moving partitions between machines so that data and load are even again. It has three goals: after the move, load is spread fairly; during the move, reads and writes keep working; and no more data moves than necessary, because every byte copied competes with real traffic for disk and network.

The main design choice is how keys map to partitions, and how partitions map to machines. If you keep the first mapping stable and only change the second, a rebalance is just copying whole partitions. That idea underlies all three strategies below.

Keep the key-to-partition map stable

The rule to avoid is hash(key) % number_of_nodes. It mixes the two mappings, so changing the node count changes the partition of almost every key: going from 10 to 11 nodes moves about 91% of keys (see Partitioning Strategies).

Strategy 1: a fixed number of partitions

Create many more partitions than you have machines, and never change that number. Each machine holds many partitions. A new machine takes a few whole partitions from each existing machine; a leaving machine hands its partitions out.

1,000 partitions on 10 nodes — 100
Same partitions on 11 nodes — About 91 (1,000 / 11); the new node receives about 9 from each old node
Same partitions on 1,000 nodes — 1: the partition count is now the ceiling on cluster size

This is simple and moves the minimum, and the move comes from many machines in parallel. Amazon's Dynamo paper reports switching to this design (equal-sized fixed partitions) because it balanced load best and let a partition move as one file, where the earlier random-token scheme had to scan data to hand it off. Redis Cluster uses 16,384 fixed hash slots. Elasticsearch fixes an index's primary shard count when the index is created (the default is 1).

The catch is choosing the number up front. Too few, and partitions become huge and the cluster cannot grow past the partition count. Too many, and each carries fixed overhead. Elasticsearch softens this with split and shrink operations that create a new index with a multiple or factor of the old shard count.

Strategy 2: dynamic partitioning

The idea is to let partitions follow the data. When a partition grows past a size limit, split it in two; when partitions shrink, they can be merged. Split halves can then move to other machines. This fits key-range partitioning, where good boundaries cannot be known in advance.

HBase — A region splits when its files pass hbase.hregion.max.filesize, 10 GiB by default — The master assigns regions to region servers
MongoDB (6.0.3 and later) — Chunks are split only when they must be migrated — The balancer moves data when shards differ by at least 3 times the range size (128 MB default, so 384 MB)
Bigtable — Tablets split as they grow; the paper cites about 100 to 200 MB by default — The master assigns tablets to tablet servers

The weak spot is a new, empty table: it starts as one partition on one machine, and every write goes there until it splits. The fix is pre-splitting: create the table with split points chosen from the expected keys. The HBase reference guide recommends starting with a modest number of pre-split regions per server and splitting further as data grows.

Strategy 3: partitions proportional to nodes

Give each machine a fixed number of partitions, so the partition count grows with the cluster. This is how Cassandra works: each node owns num_tokens positions on the hash ring (16 by default since Cassandra 4.0, 256 before). A new node picks its tokens, which splits some existing ranges, and it streams the data for those ranges from the current replicas. Afterward, operators run nodetool cleanup on the old owners, which keep the moved data until then.

Fixed number — Set once — Grows with the data — Hash partitioning with a known growth range
Dynamic — Follows the data size — Kept near a target — Key-range partitioning
Proportional to nodes — Follows the node count — Grows with data, shrinks as nodes join — Hash rings with virtual nodes

Moving a partition without downtime

Every system that rebalances online uses the same shape: copy first, switch ownership second, delete last.

Elasticsearch calls this peer recovery: the new shard copy syncs from the primary, and the copy rate is throttled by indices.recovery.max_bytes_per_sec (40 MiB/s by default on most nodes). Redis Cluster moves one hash slot at a time; while a slot is migrating, a client asking the old node for a key that has already moved gets an ASK redirect for that one request, and once the move completes it gets MOVED and updates its slot map.

Automatic or with a human in the loop

Fully automatic rebalancing is convenient, but moving data is expensive and competes with normal traffic. The danger is a feedback loop: a node that is only slow gets treated as dead, the cluster starts moving its data, the extra copying loads that node and its neighbors further, and more nodes start to look slow.

The Dynamo paper gives a real sense of the cost: under its original scheme, handing data to a new node had to run at low priority so customers were not affected, and during busy periods a node's bootstrap took almost a day. Real systems add brakes: MongoDB lets you restrict the balancer to a time window; Elasticsearch throttles recovery bandwidth; Cassandra adds nodes only when an operator starts one. A common middle ground is to let the system propose moves and have an operator approve them.

Finding the owner after a move

Once partitions move, a client must still find the right machine. There are three designs, and all need an up-to-date map of partition to node.

Any node forwards — The client talks to any node; that node forwards or redirects — Cassandra (cluster state spread by gossip), Redis Cluster (MOVED and ASK redirects)
Routing tier — A partition-aware router sits in front of the nodes — MongoDB mongos with config servers
Partition-aware client — The client keeps the map and connects directly — Kafka clients fetch metadata from brokers

The map itself must be agreed on, usually by a consensus service. Older Kafka versions stored it in ZooKeeper; Kafka 4.0 removed ZooKeeper mode, so Kafka now runs only in KRaft mode, where a Raft-based controller quorum inside Kafka holds the metadata.

What you will be able to do

Explain why the key-to-partition rule must stay fixed when machines change.
Compare fixed, dynamic and per-node partitioning and name where each is used.
Do the arithmetic for adding a node to a fixed-partition cluster.
Walk through moving a partition with no downtime.
Explain the risks of automatic rebalancing and how systems route requests after a move.

Key concepts

Rebalancing: Moving partitions between machines so data and load are even again, while reads and writes continue.
Fixed partition count: Many more partitions than machines, created once. Rebalancing moves whole partitions; no key changes partition.
Dynamic partitioning: Partitions split when they grow past a size limit and can merge when they shrink, so the count follows the data.
Pre-splitting: Creating a new table with several partitions from chosen split points, so early writes do not all hit one machine.
Partitions proportional to nodes: Each machine owns a fixed number of partitions (for example tokens on a ring), so the count grows with the cluster.
Copy, then switch: Stream the partition to the new owner while the old one serves, switch ownership in one metadata step, delete the old copy last.
Request routing: How a request reaches the node that owns its key after partitions move: forwarding nodes, a routing tier, or a partition-aware client.
Hash slot: One of Redis Cluster’s 16,384 fixed partitions. A key’s slot is CRC16 of the key modulo 16,384, and slots move between nodes.

When to use it

Explaining how a sharded database grows from 10 to 11 machines without downtime
Choosing a partition count, or deciding to pre-split a new table
Discussing why automatic rebalancing can turn a slow node into an outage
Describing how clients find the right node after partitions move

Interview questions

What happens to reads and writes while a partition is being moved?
You have 1,000 fixed partitions on 10 nodes and add one node. What moves?
Fixed or dynamic partitioning: how do you choose?
Should rebalancing be automatic?