Catalog My learning Blog
Scalability Patterns: Load Balancing, Caching, Sharding · Phase 3 · Lesson 14 · 11 min read

Resharding and Rebalancing Without Downtime

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Splitting One Overloaded Shard Into Two
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Describe the phases of an online shard migration, from dual-write through backfill, verification, cutover, and cleanup, explain why a fixed logical shard count makes rebalancing a routing change rather than a data reshuffle, and identify the failure modes that make a rollback plan mandatory rather than optional.

Concept Explanation

Every sharded system eventually needs to move data. Shards grow unevenly, a tenant outgrows its shard, hardware is replaced, or the fleet simply needs more capacity. How painful this is was largely determined at design time. If keys were hashed directly to physical machines, then changing the machine count changes the mapping for a large fraction of keys and rebalancing is a global data reshuffle that must effectively complete atomically. If there is a fixed, generous number of logical shards mapped to physical machines through a directory, then rebalancing means copying some logical shards to a new machine and updating a small map, one shard at a time, each step independently verifiable and reversible. This is the single strongest argument for the indirection layer, and the difference between a routine capacity addition and a quarter-long project.

The general online migration sequence has five phases and is worth knowing precisely, because it applies equally to moving a shard, changing a shard key, and migrating between database engines. Phase one is dual-write: the application begins writing every affected change to both the old and the new location, while continuing to read only from the old. The new location is now receiving all new data but is missing history. Phase two is backfill: historical rows are copied in batches, sized and rate-limited so the copy does not saturate the source, with each batch handling the case where the dual-write has already written a newer version of a row, normally by not overwriting anything newer than the batch snapshot. Phase three is verification: read from both, compare, and measure the divergence rate, ideally by shadow-reading a sample of live production traffic so the comparison reflects real access patterns rather than a synthetic scan. Phase four is cutover: shift reads to the new location progressively, by percentage or by shard, watching error rates and latency, with the ability to shift back instantly because writes are still going to both. Phase five is cleanup: stop dual-writing, remove the old data, and delete the migration code, which matters because half-removed migration scaffolding is a common source of later incidents.

The properties that make this work are worth stating explicitly. Writes must be idempotent, because the backfill and the dual-write will overlap and the same row will be written more than once. Every write needs a version or timestamp so that an older backfill value never overwrites a newer live one, which is the single most common source of silent corruption in migrations. The migration must be resumable, since a backfill over a large table will be interrupted, so progress needs to be checkpointed rather than restarted. And the cutover must be a configuration change, not a deployment, because a deployment takes minutes to roll and cannot be reversed in seconds, whereas a flag flip can.

There are two approaches to the physical move itself. Copy-based migration reads from the source and writes to the destination through the application or a migration tool, which is portable and allows transformation but is slow and generates write load. Replication-based migration sets up the destination as a replica of the source, lets it catch up using the database native replication, and then promotes it and drops the ranges it should not own, which is dramatically faster because it uses the engine own optimized path. A common hybrid is to clone a shard to a new machine via replication, point half the logical shards at the clone, and then delete the non-owned half from each side, which turns a data move into a filtered delete.

Rollback deserves its own attention because migrations fail in ways that are not obvious for hours. The property that makes rollback possible is that the old location remains fully current throughout, which is why dual-write continues through cutover rather than stopping at it. If dual-write is stopped when reads shift, the old copy immediately begins to diverge and rollback becomes impossible within minutes, so a problem discovered later has no remedy except rolling forward through an incident. The cost of continuing dual-write is a period of doubled write load and doubled storage, and that cost is the price of an exit. It is also worth noting that the most common cause of a failed shard migration is not the data movement at all: it is that some part of the system, a batch job, an analytics pipeline, an admin tool, a second service, was writing to the old location through a path nobody enumerated, so the new location silently missed those writes.

PhaseReadsWritesRollback CostWhat Can Go Wrong
1. Dual-writeOld onlyOld and newTrivial; stop writing newAn unenumerated writer bypasses the dual-write path
2. BackfillOld onlyOld and newTrivialA batch overwrites a newer live value without a version guard
3. VerifyOld, with shadow reads of newOld and newTrivialComparing a synthetic scan instead of real traffic patterns
4. CutoverShifting to new, by percentageOld and newSeconds, via a config flagCutover implemented as a deploy, so reversal takes minutes
5. CleanupNew onlyNew onlyImpossible; the old copy is now staleCleaning up before confidence is earned

Worked Example: Splitting One Overloaded Shard Into Two

The scenario is the most common rebalancing operation there is: one physical machine holds 1024 logical shards and has run out of headroom. The sequence below moves half of them with no downtime and a working rollback at every step.

SQL
# Starting state: db-03 owns logical shards 2048-3071 and is at 88% disk
# and 74% sustained CPU. Goal: move 2560-3071 to a new machine db-09.

# --- Phase 0: clone via native replication (fast path) ---
#   db-09 <- streaming replica of db-03
#   Wait until replication lag < 1s. No application involvement at all.

# --- Phase 1: dual-write the moving range ---
#   Router config: for logical shards 2560-3071,
#       write -> [db-03, db-09]        read -> db-03
#   db-09 is already consistent from replication, so this is belt and
#   braces, but it is what makes the later cutover reversible.

# --- Phase 2: promote and verify, do NOT delete anything yet ---
#   Promote db-09 out of replication. It now holds 2048-3071 (a superset).
#   Shadow-read 1% of live production reads for 2560-3071 against BOTH
#   and compare:
#       mismatches per million reads, by table
#       any mismatch is investigated, never explained away

# --- Phase 3: cutover reads, one slice at a time, by CONFIG ---
#   t+0h   shards 2560-2600 read -> db-09   (about 4% of the range)
#   t+2h   shards 2560-2800 read -> db-09
#   t+6h   shards 2560-3071 read -> db-09
#   Writes still go to BOTH. Reverting any slice is a one-line config
#   change that takes effect in seconds, because db-03 is still current.

# --- Phase 4: soak, then stop dual-writing ---
#   Hold for at least one full business cycle (a week, including the
#   monthly batch job if there is one). Only then:
#       write -> [db-09]     read -> db-09
#   This is the point of no return. Everything before it was reversible.

# --- Phase 5: reclaim space ---
#   db-03: DELETE FROM ... WHERE logical_shard BETWEEN 2560 AND 3071
#   db-09: DELETE FROM ... WHERE logical_shard BETWEEN 2048 AND 2559
#   Both in rate-limited batches so the deletes do not cause the incident
#   the migration was meant to prevent.

# --- The check that actually prevents failure ---
# Before Phase 1, enumerate EVERY writer to this data, not just the
# main application:
#   [x] api service           -> goes through the router
#   [x] async job workers     -> goes through the router
#   [ ] nightly ETL           -> connects to db-03 DIRECTLY  <-- FOUND IT
#   [ ] admin console         -> uses a hardcoded connection string
#   [ ] on-call runbook       -> tells engineers to psql into the primary
# Every unchecked line is data that silently will not reach db-09.
# This, not the data movement, is what usually breaks a migration.
A five-phase online shard split shown as a timeline, with dual-write beginning before the backfill, reads shifting in percentage slices during cutover while writes continue to both locations, and the rollback window closing only at the moment dual-write stops.
A five-phase online shard split shown as a timeline, with dual-write beginning before the backfill, reads shifting in percentage slices during cutover while writes continue to both locations, and the rollback window closing only at the moment dual-write stops.

Real-World Examples

  • Notion 2021 account of sharding PostgreSQL describes exactly this sequence, including auditing every path that wrote to the database before enabling dual-writes, running a backfill of existing data, verifying with both a full comparison and sampled production reads, and performing the final switch during a short maintenance window with a documented rollback. The team published that the discovery and enumeration of all writers, rather than the data movement, was among the most demanding parts of the project.
  • Stripe published an account of migrating hundreds of millions of objects between database systems using a four-phase pattern that matches this lesson closely: dual-writing to both stores, backfilling existing records, dual-reading with comparison to validate correctness on live traffic, and only then making the new store authoritative and removing the old path. The published emphasis on comparing reads from both systems under real traffic before cutover is the verification phase described here.
Best PracticeKeep dual-writing through the entire cutover and for a full business cycle after it. The moment you stop, the old copy begins to diverge and your rollback disappears, which means any problem discovered later, and migration problems are routinely discovered days later, can only be rolled forward through an incident. The doubled write cost during the soak period is not waste, it is the price of an exit.

Review Questions & Answers

Because the function mapping a key to a logical shard does not take the machine count as an input, so growing or shrinking the fleet cannot change which logical shard a key belongs to. Only the much smaller map from logical shards to physical machines changes. That means a rebalance moves whole logical shards, which are self-contained sets of rows, and each move can be performed independently: copy that shard data, verify it, flip its mapping entry, and move on. Nothing about any key location within the logical partitioning changes, so caches keyed by shard remain valid, denormalized references remain correct, and there is no moment at which the whole fleet must switch together. Hashing directly to machines removes that indirection, so the mapping function output changes for a large fraction of keys the instant the machine count changes, and the migration becomes a single global operation with no safe intermediate state.

The backfill reads a row as it existed at some earlier point, and by the time it writes that row to the destination, the dual-write path may have already delivered a newer version of the same row. Writing unconditionally replaces the new value with the old one, so the destination now holds stale data that will never be corrected, because the backfill has moved on and the dual-write only fires on future changes. It is hard to detect because nothing errors, the row exists and looks plausible, and the corruption affects only rows that happened to be updated during the window in which the backfill was processing their batch, which is a small and essentially random subset. A full comparison run after the backfill completes will find it, which is exactly why the verification phase exists, but a spot check almost certainly will not. The prevention is a conditional write that refuses to overwrite anything with a version or timestamp newer than the backfill snapshot.

Because the value of cutover is the ability to reverse it faster than the problem can cause damage. A configuration flag can be flipped in seconds, applies fleet-wide at once, and requires no build, no artifact, and no rolling restart. A deployment takes minutes at best to roll across a fleet, may require a rollback deployment that takes just as long, and during that window the fleet is running a mixture of two versions with different routing behaviour, which is itself a source of inconsistency. If the cutover reveals a correctness problem, several minutes of continued incorrect reads is the difference between a non-event and a customer-visible incident. Making cutover a flag also lets it be applied progressively, one percentage or one shard slice at a time, which a deployment cannot do at fine granularity.

An unenumerated writer. Some path writes to the old location without going through the routing layer that implements dual-write, so those changes never reach the new location and the new copy is silently incomplete. The usual culprits are batch and ETL jobs with their own connection strings, admin consoles, internal tools, a second service that was given direct database access years ago, and on-call runbooks that instruct engineers to connect directly to the primary. Prevention is an explicit audit before dual-write begins: enumerate every process, job, tool, and human procedure that can write this data, confirm each one routes through the migration-aware path, and where possible enforce it technically by revoking direct write credentials so that an unaudited writer fails loudly rather than succeeding quietly. Verification against live traffic is the backstop that catches what the audit missed, which is why it must run before cutover rather than after.