hard Rebalancing Strategies (Beyond Consistent Hashing)

Mechanism: partitions must move when the node count changes — the only real question is HOW

Every partitioned datastore eventually adds or removes a node, and when it does, some fraction of the data has to relocate so load stays roughly even on the new set of machines. What separates a good rebalancing strategy from a bad one is not whether data moves, but how MUCH moves and how CLEANLY — does the whole cluster reshuffle, or does only the minimum necessary slice change hands? Three real strategies answer this differently, plus one anti-pattern that should never ship in an elastic system:

• Hash mod N — don't. shard = hash(key) % N bakes the node count into the placement formula, so changing N remaps almost every key at once. Traced in full in Data Sharding Techniques — the short version: adding one node to four moves roughly 80% of all rows.
• Fixed number of partitions. Create far more partitions than nodes up front — say 1000 partitions for 10 nodes, 100 each — and never change that count again. Adding a node just reassigns whole partitions to it; nothing inside a partition is ever re-hashed (Elasticsearch, Riak, Couchbase).
• Dynamic partitioning. Let a partition split when it outgrows a size threshold and merge when it shrinks — the partition count itself adapts to data volume, the way a B-tree grows and shrinks its own nodes (HBase, MongoDB).
• Consistent hashing with virtual nodes. Hash both keys and nodes onto a ring so adding or removing a node only touches its own arc — roughly K/N keys move, not whole partitions. Already covered in full, with the ring trace, in Data Sharding Techniques; this page is about the two strategies that page didn't cover.

Traced: 1000 fixed partitions, 4 nodes → 5 nodes

Start with 4 nodes and 1000 partitions split evenly: 250 partitions per node. A 5th node joins.

1. Compute the new even split. 1000 partitions ÷ 5 nodes = 200 partitions per node.
2. Each existing node donates the surplus. N1–N4 each currently hold 250; the new fair share is 200, so each donates its surplus of 50 (250 − 200 = 50) to N5.
3. N5 fills up from four donors. 4 × 50 = 200 — exactly N5's fair share. No node did any hashing; whole partitions were physically handed over as units.
4. Result. Total partition count is still 1000, fixed since creation. Roughly 1/5 of all keys moved — the same fraction as the new node's share of the cluster — but every key that moved did so as part of an already-existing, self-contained partition. No key inside a partition that stayed put was ever touched.

Compare this to hash mod N on the same cluster growth: mod-N would recompute hash(key) % 5 for every one of the (say) hundreds of millions of keys behind those 1000 partitions and copy roughly 80% of them individually. Fixed partitioning turns that into a bulk transfer of 200 pre-existing, self-contained partitions — a segment/file copy the storage layer can do in one shot, not a row-by-row rewrite.

Dynamic partitioning: split when large, merge when small

Fixed partitioning has one weakness: the count is chosen once, at creation, and never changes. If the dataset grows 100× past what that count was sized for, every partition individually becomes huge and hot, and there is no lever left to pull except "re-partition everything" — a migration project, not a routine operation. Dynamic partitioning solves this the way a B-tree solves the same problem for its own pages: each partition monitors its own size, and when it crosses a threshold, it splits into two roughly-equal halves that keep serving traffic without any global recomputation. Symmetrically, when neighbouring partitions shrink — old data was deleted, or a range simply never grew — they can be merged back into one. HBase (region splits) and MongoDB (chunk splitting) both work this way: the partition count is a function of live data volume, not a number fixed on day one.

Judgment: fixed count vs. dynamic vs. consistent-hash vnodes — how a senior engineer decides

The real axis all three sit on is: how much are you willing to decide up front, versus let the system decide at runtime? Fixed partitioning asks you to guess final scale once, correctly, and rewards that guess with the simplest possible logic — no splitting code to write or debug, no split-storm failure mode. Dynamic partitioning removes the guess entirely at the price of runtime complexity: you are now shipping and operating a splitter, and it can misfire under a sudden burst. Consistent hashing sits at a different granularity altogether — it doesn't reshuffle whole partitions, it reshuffles individual keys along a ring, which is the right tool when your unit of data is a single key-value pair rather than a coarse range, and cluster membership itself is expected to churn often rather than grow in occasional, planned steps.

Pitfalls

• Too few fixed partitions caps future scaling. Provision 10 partitions for 10 nodes and you can never usefully add an 11th — there's nothing left to steal. Size the partition count for the cluster's eventual scale, not its starting size (a common rule of thumb: 10–100× the number of nodes you expect to ever run).
• Too many fixed partitions adds real overhead. Every partition carries fixed costs — metadata, open file handles, compaction bookkeeping, replication streams. Thousands of tiny partitions per node means thousands of small, inefficient operations instead of a few large, efficient ones.
• Auto-rebalancing + failure detection interacting badly — a "rebalance storm." If a node is merely slow (a GC pause, a network blip) rather than dead, an over-eager failure detector can declare it gone, trigger a rebalance that copies its partitions elsewhere, then see it come back — now the cluster rebalances AGAIN to undo the first move, right as it may also be serving the load spike that caused the slowness in the first place. Production systems make rebalancing a deliberate, rate-limited operation, not a reflex to every transient health blip.
• Dynamic partitioning's split storm. A sudden write burst can push many partitions over threshold simultaneously, triggering many concurrent splits — each one consuming I/O and briefly reducing availability of the range it covers — at exactly the moment the cluster can least afford it.

Takeaways

• Rebalancing is unavoidable once node count changes; the strategy determines how much moves and how cleanly — hash mod N is the anti-pattern that moves almost everything.
• Fixed number of partitions (Elasticsearch, Riak, Couchbase) moves whole partitions only and is simple, but the count is welded in at creation time.
• Dynamic partitioning (HBase, MongoDB) adapts the partition count to data volume like a B-tree, at the cost of split/merge operational complexity.
• Consistent hashing with vnodes operates at key granularity (~K/N keys move), not partition granularity — a different, complementary answer for elastic key-value workloads (see Data Sharding Techniques).

Synthesized from Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Ch. 6, "Partitioning and Rebalancing" — covering fixed number of partitions, dynamic partitioning, and partitioning proportional to nodes — plus Elasticsearch, Riak, Couchbase, HBase, and MongoDB documentation on their respective rebalancing mechanics. Re-authored/Deepened for this guide.