Rebalancing Partitions

Why this matters: partitioning is a decision you make once; rebalancing is something you live with forever. Choosing the wrong scheme means every capacity change is a migration project.

Key takeaway

Rebalancing is necessary when query load becomes uneven, data distribution is skewed, or nodes are added or removed. The goal is to move as little data as possible while restoring balance.

The trap: avoid hash mod n

Using hash mod n is problematic because changing n changes the partition index for almost every key, forcing massive data migration.

Key 1235, with 5 nodes:   1235 mod 5 = 0   -> node 0
Add one node (n = 6):     1235 mod 6 = 5   -> node 5

The key must move. And so must nearly every other key.

This is the same failure the Load Balancers chapter described for stateless routing, and it is why consistent hashing exists. Adding one machine should move roughly 1/n of the data — not all of it.

Three strategies avoid the trap.

1. Fixed number of partitions

Create a large, fixed number of partitions — say 1,000 — at the start, and assign multiple partitions to each node. When a new node joins, it takes entire partitions from existing nodes.

Start:  1,000 partitions across 4 nodes   -> 250 partitions each
Add a node:  1,000 partitions across 5 nodes -> 200 partitions each
             (each existing node hands over 50 whole partitions)

Data moves in chunks rather than individual keys, and the partition count never changes — only their assignment to nodes.

Trade-off: choosing the right number of partitions is critical. Too small and overhead increases; too large and rebalancing becomes expensive. Used in Elasticsearch and Riak.

2. Dynamic partitioning

Partitions are split when they exceed a size threshold and merged when they shrink. The number of partitions adapts automatically to total data volume.

Trade-off: rebalancing while serving active reads and writes is complex — moving data can cause latency and consistency issues. Used in HBase and MongoDB.

The appeal is that it needs no upfront guess: a small database has few partitions and a large one has many, automatically.

3. Partition proportionally to nodes

The number of partitions scales with the number of nodes. Each node manages a fixed number of partitions; when a new node joins, it splits existing partitions to take its share. Used by Cassandra and Ketama.

Each node owns a fixed number of partitions (say 256).
4 nodes -> 1,024 partitions
5 nodes -> 1,280 partitions   (the new node splits existing ones)

Rebalancing here is typically performed automatically: the system calculates partition distribution from current node capacities and moves data when nodes are added or removed. Manual rebalancing, where an administrator redistributes partitions, is uncommon in this context though it may appear in specialized setups.

Comparing the three

Strategy	Partition count	Data moves in	Upfront decision	Used by
Fixed number	Constant, chosen upfront	Whole partitions	Critical and permanent	Elasticsearch, Riak
Dynamic	Adapts to data volume	Splits and merges	None needed	HBase, MongoDB
Proportional to nodes	Scales with node count	Splits on node join	Partitions per node	Cassandra, Ketama

Key takeaway

Never let the partition-to-node mapping depend on n directly. Keep partitions as a stable intermediate layer — fixed, dynamic, or proportional — and rebalance by reassigning partitions rather than recomputing keys.

Interview signal by level

Level	What a strong answer sounds like
L4	"When we add a node we redistribute the data."
L5	Avoids the trap: "not hash mod n — adding a node would remap almost every key. Consistent hashing or a fixed partition count instead."
Staff+	Picks a scheme and throttles it: "fixed partition count as a stable indirection layer, sized for the largest cluster we'd plausibly reach. And I'd throttle rebalancing bandwidth with a human gate on large moves — automatic rebalancing under load can cascade into an outage."

Next: querying by something other than the partition key.