Dynamic Rebalancing

Rebalancing adjusts the distribution of existing data and service responsibilities from the current state to a target state. Triggers include scaling out, scaling in, hotspots, and failure recovery. It involves three core questions: what to move, when the target service can be activated, and how to recover upon failure.

The statement "consistent hashing only changes a small number of assignments" answers only part of the first question. Migration is not simply copying files after updating the routing table; during replication, business data continues to change, and old clients may continue to request the original location.

Migration Granularity: Fixed Partitions, Dynamic Splitting, and Token Ranges

For example, if 1000 equal-sized partitions were originally evenly distributed across 10 machines, adding one machine could involve each original node moving out 9 partitions. The result would be 91 partitions per original node and 90 for the new node, totaling 1000. There is no need to re-number all partitions consecutively; only the ownership of the migrated partitions needs to be updated.

This is an equal-sized pedagogical example. In practice, scheduling must also consider byte volume, read/write rates, disk space, and failure domains, rather than simply averaging by partition count. To eliminate hotspots, more migration may be required than pure capacity balancing would suggest.

Splitting and migration are different: splitting changes logical boundaries, while migration changes placement location. A partition can be split into two and still remain on the original machine; one of them can be moved away only after the boundary stabilizes. Metadata can be managed by a replicated control plane, which does not imply reliance on a single non-fault-tolerant central machine.

Why "Replicate First, Then Change Routing" Is Still Insufficient

Assume x=1 at the start of replication, and the user changes x to 2 during the process. If the target only has the snapshot value of 1, switching the route will result in reading the stale value. If writes occur simultaneously to both old and new nodes, and the old node succeeds while the new node times out, inconsistency between the two locations may still occur.

A correct protocol must answer: which log entry records this update? From where does the target catch up? Does timeout retry cause duplicate effects? Could an older record in the snapshot overwrite a newer value that arrived first? How are deletions synchronized? These issues cannot be dismissed with a single statement like "dual-write ensures no data loss."

A Deductible Single-Writer Migration Protocol

The following describes a general design using source S, target T, and versioned routing, assuming the system can persistently record migration state and constrain write permissions. This is not a fixed implementation adopted by all databases.

Snapshots Must Correspond to a Log Boundary

Take a consistent snapshot and determine the log position L0. The snapshot covers the state up to that boundary, while incremental changes cover subsequent modifications. The target loads the snapshot first and then replays increments, or merges them via reliable versioning rules to prevent older snapshots from overwriting newer updates. Log retention periods must be long enough; otherwise, if the required increments are reclaimed before the target catches up, a new snapshot must be established.

Replay requires recoverable positions and idempotent semantics. Writing the same version repeatedly should be identifiable; deletions must propagate as log events or tombstones, and cannot be assumed synchronized just because the target hasn't seen the record.

How a Target Replica Rejects Gaps and Late Snapshots

Assume the snapshot corresponds to position 10, with state {x:1,y:9}; subsequent log entry 11 changes x to 2, and 12 deletes y. Below assumes this is a dedicated, position-continuous partition log, unlike Watch which can skip other key revisions. Each application publishes both data and position; actual storage must maintain this atomic relationship using transactions or recovery protocols.

class Target:
    def __init__(self):
        self.position = None
        self.data = {}

    def install_snapshot(self, position, data):
        if self.position is not None:
            raise ValueError("Snapshot already installed for this task; cannot overwrite post-increment state")
        self.data, self.position = dict(data), position

    def replay(self, position, operation, key, value=None):
        if self.position is None:
            raise ValueError("Install snapshot completely first")
        if position <= self.position:
            return False  # Historical replay under the same task/log identity
        if position != self.position + 1:
            raise ValueError("Log gap detected; cannot skip")
        updated = dict(self.data)
        if operation == "put":
            updated[key] = value
        elif operation == "delete":
            updated.pop(key, None)
        else:
            raise ValueError("Unknown log type")
        self.data, self.position = updated, position
        return True

target = Target()
target.install_snapshot(10, {"x": 1, "y": 9})
assert target.replay(11, "put", "x", 2)
assert not target.replay(11, "put", "x", 2)
try:
    target.replay(13, "put", "z", 3)
except ValueError:
    pass
assert target.position == 11 and "z" not in target.data
assert target.replay(12, "delete", "y")
assert target.data == {"x": 2}
try:
    target.install_snapshot(10, {"x": 1, "y": 9})
except ValueError:
    pass
assert target.data == {"x": 2} and target.position == 12

The model adopts a serial strategy: "replay begins only after snapshot is fully installed." Therefore, the deletion at 12 does not need to retain a tombstone indefinitely to block old snapshots in this task, as the old snapshot installation itself was rejected; if out-of-order blocks and increments are allowed to merge in parallel, finer versioning rules are needed to prevent x from regressing or y from resurrecting.

The same position corresponds to only one immutable log record. Real systems must also validate the migration task ID, source log identity, snapshot checksum, and range; position 11 from another task cannot be treated as processed. The positions in the example are in-memory only and do not simulate process or disk crashes; a persistent implementation must ensure no state like "position reached 12, but delete not yet saved" remains.

After Catching Up Data, Write Permissions Must Be Handed Over

"Zero lag for the target" is merely a snapshot in time. The source may still accept new writes in the next instant, so an explicit cutover barrier Lcut is needed, ensuring old writers can no longer produce unconstrained successful writes.

A simple implementation temporarily blocks new writes for this range during the cutover window, waits for accepted operations to complete, allows the target to apply up to Lcut, and then publishes the new routing version. More complex implementations can reduce downtime via forwarding, log protocols, or replica group reconfiguration, but must still prove that old writes are not missed.

Epochs represent permission generations. When requests carry an old version, the server should reject or forward them according to the protocol; merely updating client caches is insufficient to isolate an old process that still considers itself the master after recovery. Permission checks must be enforced at the resource boundary that actually accepts writes.

"Just Caught Up" vs. "Caught Up After Barrier" Differs by One Write

Assume t1 observes both source and target at 12. At t2, the source accepts log 13. If the controller switches the route at t3 based on the t1 observation, the target will miss the already successful 13. Zero lag is a transient snapshot and cannot serve as a barrier to prevent subsequent writes.

The key to establishing an effective barrier is to first stop the old authorization from accepting new writes and process already accepted in-flight operations, thereby obtaining an Lcut that will not continue to grow. If the last accepted operation was 13, the target must catch up to 13; it cannot be activated early just because it previously caught up to the source's tail at 12. This brief window of rejecting writes is the availability cost paid by this simplified protocol in exchange for clear handover boundaries.

Routing Publication Can Have Atomic Decisions, But Clients Won't Refresh Simultaneously

Metadata can contain a clear ownership switch point, but clients, proxies, and long-lived connections will see the new state at different times. Old entries therefore require transitional behavior and cannot assume global routing consistency instantly. Redirects and forwards must also limit the number of hops to prevent two nodes from pointing to each other in a loop.

Migrating a replica does not mean directly replacing voting members. Replication groups like Raft need their own member change protocols to guarantee quorum safety; migration tools cannot bypass them to unilaterally declare new replicas have full rights.

Just Caught Up Does Not Mean Switching Is Possible Now

Let the target catch up first, then write one entry to the source, to construct a counterexample of "zero lag followed by falling behind again." The freeze button includes stopping acceptance and completing in-flight writes to obtain a fixed Lcut; it is not merely refreshing the client's routing cache. Before publishing the new owner, both old permission isolation and target coverage of the barrier must be satisfied. After switching, the old source cannot be treated as a still-valid write entry.

Failure Recovery: Next Steps Determined by Persistent State

Before cutover, migration can usually be stopped while keeping the source service active; after cutover, the target has accepted new writes, so the old replica cannot simply be re-enabled as a "rollback." New changes on the target must be synchronized, and permissions re-handled.

Capacity and Rate Limiting: Catch-up Must Be Faster Than New Changes

Assume snapshot size D and effective replication bandwidth b. Ignoring compression and other bottlenecks, the full-volume phase requires at least D/b. If there is a backlog B afterward, with an incremental generation rate r and target effective application rate a, in a simplified steady-rate model, catch-up takes approximately B/(a-r), provided a>r. If a≤r, waiting alone will not catch up.

Therefore, rate limiting cannot look only at the network; it must also monitor disk latency, write amplification, CPU, log retention space, target application rate, and frontend request tail latency. Scheduling can limit concurrent migration scope, reserve capacity for failure recovery, and pause when service metrics degrade. Not all scenarios require per-node scaling; concurrency should be determined by resource budgets and protocol limits.

Redis Cluster: Distinguish Temporary Redirects from Ownership Changes

Redis Cluster uses 16384 hash slots, and the mapping between slots and nodes can change. In migration-related client protocols, ASK indicates that the current request needs to be temporarily executed on a specified node, accompanied by ASKING; it does not require directly changing the long-term route for that slot to the new node. MOVED indicates that the understanding of slot ownership should be updated. This illustrates that temporary service locations during migration and stable routing cannot be conflated. Redis Cluster Specification

Use the following pure routing model to distinguish the two types of responses. Slot 8 is initially cached as S; upon receiving ASK, only a one-time retry plan is generated for the target; upon receiving MOVED, the stable slot cache is updated.

routes = {8: "S"}

def redirected(kind, slot, target):
    if kind == "ASK":
        return target, True   # Send ASKING on the target connection, then send this request
    if kind == "MOVED":
        routes[slot] = target
        return target, False
    raise ValueError("Unsupported redirect type")

assert redirected("ASK", 8, "T") == ("T", True)
assert routes[8] == "S"  # Next independent request still tries S first
assert redirected("MOVED", 8, "T") == ("T", False)
assert routes[8] == "T"

ASKING is a one-time permission on a connection; you cannot send ASKING on one connection and then take another connection from the pool to send the original request. Actual clients must ensure these two commands are correctly chained on the same connection and handle redirect counts and total deadlines. This only simulates single-slot cache changes, without implementing connection pooling, command execution, or full slot table refresh; the latter is also a common update method after MOVED. ASK and Client Routing Semantics

This example is for understanding routing handover and does not imply that Redis uses the complete snapshot and log migration process described above.

Continue reading: Consistent Hashing, Sharding Strategies, Failure Detection.

References

• Redis Cluster Specification: Slots, migration, and client redirection.
• Raft Paper: Safety of replication group member changes.

Keywords: rebalancing, resharding, snapshot, log catch-up, fencing, epoch, routing, ASK, MOVED