Live rebalancing and replica moves

This design note records proposed work. Only the returning replica case is implemented, for restarted queue followers. The rest is proposed. Current placement is described in clustering, recovery in failover and recovery, and cooperative owner handoff in recovery continuation.

For the lost-follower case, a first step that keeps the queue serving by suspending the lost copy is in follower loss without fencing.

Goals

Use new or idle nodes without stopping the queues that move onto them.
Move a follower copy without a recovery fence. The queue keeps serving while the new copy catches up.
Never drop a copy that might be needed to preserve a confirmed message.
Reuse the same mechanism for returning replicas, replication factor increases, replacing a lost follower and drain.
Pace moves so rebalancing never competes with recovery or saturates disks.

Queues come first. Streams need their own seal and selection path before any of this applies to them.

Current foundation and gaps

| Piece | State | | --- | --- | | Learner admission | A follower absent from the accepted history catches up from a checkpoint and the log tail, then is admitted without changing owner, epoch or write requirement | | Restarted followers | A restarted queue follower is suspended and rejoins through learner admission without a fence, keeping its eligible-set slot. At most W - 1 rejoin at once. See restarted queue followers | | History binding | The accepted history names the exact process and storage instance of each replica, and marks a restarted follower suspended until it is re-admitted | | Reseed | Revokes and re-admits one replica inside the same history | | Recovery candidate handoff | Swaps the recovery driver within a fixed proposed set | | Drain | Moves a node’s partitions away, but through a full crash-style recovery | | Load signals | Publish and delivery rates ride heartbeat labels, owned counts are known |

Gaps:

Any follower placement change on an activated queue creates a pending recovery, which closes serving until seal, inspection and install finish. Only a follower restart on an unchanged placement avoids the fence.
The write requirement is computed from the full assignment. Adding a copy to followers raises it for majority policies while the new copy cannot report confirm progress yet.
There is no safe replica removal and no rebalancer policy.

Learners and the confirm contract

An assignment gains a separate learners list next to followers. Learners replicate from the owner but never count toward confirms and never change the write requirement W.

During a move the write requirement comes from the configured replication factor, not from the number of copies currently assigned. A queue configured for three copies with a majority policy needs two acknowledged copies whether it currently has three or four.

The owner counts confirm progress only from the followers named in the committed assignment it is serving under. Changing who counts is always a guarded coordination write.

Moving a follower: two steps

Moving the follower copy of one partition from node R to node T.

The story below walks through one move with C as R and D as T. Position 500 stands for boundary B. Choose Recovery cancels the move for the abort path and Planned owner handoff for the owner move described further down. Like the rest of this note, the story is proposed and not implemented.

INSIDE FIBRIL / LIVE REBALANCINGProposed · not implemented

A new broker joins. A copy moves without a fence.

Proposed design, not implemented. One queue partition, replication factor 3 with a majority policy, so W = 2 counted copies including the owner. Position 500 stands for the switch boundary. Load bars and step lengths are illustrative.

Follow the story

Read the story, step by step

Move a follower to D · Proposed

01 / A new broker joins empty
D registers with the cluster and holds no partitions. The load score adds up owned and followed partitions, retained history, traffic and transfers in progress. A, B and C sit above the cluster mean. D sits far below it.
02 / Add D as a learner
One guarded coordination write adds D to the learners list. It needs no pending recovery, a matching assignment and room in the sync budget. W stays 2 because it comes from the configured replication factor, not from the number of assigned copies. The queue keeps serving.
03 / D catches up in the background
D copies a checkpoint if the owner has truncated, then follows the log tail. The sync budget caps transfers per node and per cluster, and recovery always comes first. Publishes keep confirming from A plus B or C. D's progress is not confirm evidence.
04 / D is admitted to the history
D has caught up. The existing admission path adds D's process and storage instance to the accepted history. Owner, epoch and W do not change, and D still does not count. The eligible set grows to four, so a recovery would need more seals. That is the safe direction.
05 / Swap who counts
One guarded write moves D into the followers and marks C as leaving. From here A counts confirms only from A, B and D. A records the switch boundary, its confirmed tail at that moment, here position 500. Everything below 500 was confirmed on 2 copies of the old set, at most one of them on C. C keeps replicating and stays eligible.
06 / Removal waits for D to cover 500
D is durable only up to 470. A message below 500 might be confirmed only on A and C. Remove C before D holds it, lose A, and that message is gone. C stays assigned and eligible until D is durable at or beyond 500.
07 / D covers the boundary
D reports durable progress at 500 or beyond. Every message confirmed before the swap now sits on at least 2 copies without C: one surviving old copy plus D. Every later message was counted only from A, B and D.
08 / Remove C, keep its data for a while
One guarded write removes C from the assignment and the eligible set. It needs no pending recovery and no other admission or removal in flight. C stops following but keeps its retained copy for a grace period, so an abandoned move, a recovery that starts right after, or a later move back can still use it.
09 / Repeat until the load evens out
The planner repeats follower moves under the sync budget, then hands off some owners. A move must improve the spread by a margin. Cooldowns stop a node that just received partitions from being drained again. The cluster settles near the mean.

Recovery cancels the move · Proposed

01 / A new broker joins empty
D registers with the cluster and holds no partitions. The load score adds up owned and followed partitions, retained history, traffic and transfers in progress. A, B and C sit above the cluster mean. D sits far below it.
02 / Add D as a learner
One guarded coordination write adds D to the learners list. It needs no pending recovery, a matching assignment and room in the sync budget. W stays 2 because it comes from the configured replication factor, not from the number of assigned copies. The queue keeps serving.
03 / D catches up in the background
D copies a checkpoint if the owner has truncated, then follows the log tail. The sync budget caps transfers per node and per cluster, and recovery always comes first. Publishes keep confirming from A plus B or C. D's progress is not confirm evidence.
04 / A fails while D is still a learner
A stops responding before D is admitted. The controller opens a pending recovery for this partition. A pending recovery cancels any move in progress and pauses rebalancing.
05 / The move is cancelled
D is dropped from the learners here. It could also stay a learner. Either way it never counted toward a confirm, so the confirm contract never changed. No copy is removed. The queue is fenced, as in any failover, until recovery activates a replacement.
06 / Recovery uses the eligible set
B and C seal their history and provide evidence. D was never admitted, so it is not in the eligible set and recovery does not wait for it. Installation, quorum receipts, consensus activation and local admission still have to succeed before B serves.
07 / B activates at epoch 9
Consensus commits the replacement and B serves under epoch 9. Clients refresh topology and reattach. Rebalancing stayed paused the whole time the recovery was pending.
08 / The move retries after activation
With no recovery pending, the planner adds D as a learner again under epoch 9 and runs the same steps. The same mechanism can also replace the copy lost with A. Which copy leaves is chosen again from fresh load scores.

Planned owner handoff · Proposed

01 / The owner carries the most load
After the follower move, A still owns the partition and serves its traffic. D is an admitted, caught-up follower. Owners move only by a planned handoff to a replica like that.
02 / Wait for a quiet point and close admission
At a quiet point A stops accepting state-changing work for this partition. New publishes wait. W, the counted copies and the eligible set stay the same.
03 / Drain and report a final boundary
A drains work already in flight and reports its final boundary. B and D report that they are durable at it. A failure before the next write cancels the handoff and A reopens admission.
04 / Commit D as owner at epoch 9
One guarded write commits D as owner at epoch 9 with a continuation certificate. The final boundary is known and every counted copy holds it, so D activates without seal or inspection. A failure after this write falls back to ordinary recovery.
05 / Clients follow the new owner
D opens admission and serves. Clients refresh topology and reattach to D. A stays on as a follower, so the replica count and W never changed. The owner work now sits on D.

Step 0: add T as a learner

One guarded write adds T to learners.

Preconditions: no pending recovery for the partition, the assignment and activation match the committed ones, T has a registered process, and the sync budget allows another transfer to T.

T catches up with the existing learner worker, from a checkpoint if the owner has truncated, then from the log tail. The queue keeps serving. When T has caught up, the existing admission path adds T’s storage instance to the accepted history. The eligible set grows, so recovery needs more seals, which is the safe direction.

Step 1: swap who counts

One guarded write moves T from learners to followers and marks R as leaving. From this write on, the owner counts confirms from the new set only, which includes T and excludes R. R keeps replicating, keeps its data and stays in the eligible recovery set.

The owner records boundary B, its confirmed tail at the moment it switches to the new set. Everything below B was confirmed under the old set, so it is on W copies of the old set. At most one of those copies is R.

Preconditions: T admitted and caught up close to the tail, no pending recovery.

Step 2: remove R

Once T reports durable progress at or beyond B, one guarded write removes R from the assignment and the eligible set.

Why this is safe: every message confirmed before the swap was on W copies of the old set. Without R that leaves at least W - 1 old copies, and T holds everything below B, so W copies remain in the new set. Every message confirmed after the swap was counted only from the new set. Recovery seals at least E - W + 1 replicas of the new eligible set, which intersects every confirm set.

Preconditions: T durable at or beyond B, no pending recovery, no other admission or removal in flight for the partition.

After removal

R stops following but keeps its retained data for a grace period, the same way destroyed partitions go to trash/. A move that is abandoned, or a recovery that starts right after, can still use that copy. A later move back to R can start from it.

Aborts

A pending recovery for the partition cancels any move in progress. Learners are dropped or stay learners, they never count. A move retries after the recovery activates.
If T fails before step 1, drop the learner. Nothing about the confirm contract changed.
If T fails between steps 1 and 2, R is still in the eligible set and still holds its data. The partition behaves like any queue with a failed follower, and recovery can use R.

A joint confirm (a quorum in both the old and the new set during the swap, as in Raft joint consensus) would do the swap in one step. It needs more code in the confirm path, so it is left for later.

Moving an owner

Owners move only by a planned handoff to an already admitted, caught-up replica, at a quiet point, as described in recovery continuation. The old owner closes admission for state-changing work, drains in-flight work and reports a final boundary. One guarded write commits the new owner at epoch + 1 with a continuation certificate, so the new owner activates without seal or inspection. Failure before the commit cancels the handoff. Failure after it falls back to ordinary recovery.

Follower moves come first in any plan because they are cheap and never interrupt serving. An owner move onto a node that is not yet a follower is a follower move followed by a handoff.

Load score

Placement and rebalancing need a per-node score.

Each node gets a small vector:

| Dimension | Meaning | | --- | --- | | Owned partitions | Each costs serving and confirm work | | Followed partitions | Each costs replication and disk | | History weight | Sum over partitions of a saturating function of retained history, for example h / (h + k), so a large history weighs more than a small one but one huge partition cannot dominate | | Traffic | Publish and delivery rates from heartbeat labels | | Sync load | Expected remaining bytes of transfers in progress to or from the node |

Each dimension is divided by the node’s capacity and combined with weights. The sync term is transient. It stops the planner from piling work onto a node that is still catching up.

Move cost is kept separate from load. Copying a partition costs roughly linear in its history, so a target that already holds a retained copy of the partition is much cheaper and wins ties.

Policy:

A node sheds load only when its score is above the cluster mean by a threshold, and only toward nodes below the mean by a threshold.
A move must improve the spread by a minimum margin.
Hard limits on concurrent transfers per node and per cluster, separate from the score. Recovery always takes priority over rebalancing.
Cooldowns per node and per partition, so a node that just received partitions is not judged overloaded and drained again.
Rebalancing pauses while any recovery is pending.

Uses of the same mechanism

| Situation | Steps | | --- | --- | | New empty node joins | Repeated follower moves under the sync budget, then owner handoffs | | Returning replica | Implemented for restarted queue followers on an unchanged placement: the follower is suspended, rejoins as a learner and becomes a follower again without a fence. A replica returning to a changed placement would use step 0 only | | Replication factor increase | Step 0 then promotion to follower, no removal | | Lost follower replaced | Step 0 on the replacement, then remove the lost copy once the threshold allows | | Drain | Planned owner handoff to an admitted follower, then follower moves off the node |

Operator surface

Pause and resume rebalancing cluster-wide.
Show moves in progress with phase, bytes remaining and blocking reason.
Request or cancel a specific move.
Report the score vector per node in the admin dashboard.

Implementation order

learners list and W from the configured replication factor. Adding a follower becomes step 0 instead of a recovery.
Swap and removal writes with the boundary check, plus fault tests at every write boundary.
Transfer budget and move status in admin.
Score, thresholds and the rebalancer loop.
Planned owner handoff.
Stream equivalents after stream recovery exists.

Precedents

Kafka partition reassignment adds new replicas, waits for them to join the in-sync set, then removes old ones, with a replication throttle.
CockroachDB adds a non-voting learner, sends a snapshot, promotes it and then removes the old voter. Its allocator rebalances against the mean with thresholds.
TiKV PD scores stores by region size and free space and limits snapshot traffic per store separately from the score.
Elasticsearch weighs shard counts and disk use and throttles concurrent recoveries per node.
Kafka Cruise Control ranks hard and soft goals and searches for moves that improve soft goals without breaking hard ones.