Resharding and Moving Data Online

Scenario

Example company: a messaging app sharded by conversation_id % 8 across 8 databases. Growth means going to 12 databases. The plan: change the modulus to 12 during a maintenance window.

What you see in production

A dry run shows that changing % 8 to % 12 would move about two thirds of all rows — many terabytes — and every cache keyed by shard would go cold. A maintenance window of that size isn't acceptable.

The naive code

def shard_for(conversation_id):
    return conversation_id % NUM_SHARDS      # NUM_SHARDS: 8 → 12 remaps most keys

Reproduce it

Compare how many keys move when going from 8 to 12 shards with plain modulo hashing vs a consistent-hash ring with virtual nodes:

import bisect, hashlib

def h(s): return int(hashlib.md5(s.encode()).hexdigest()[:8], 16)   # stable, well-spread hash
keys = [f"conv-{i}" for i in range(20_000)]

moved_mod = sum(1 for k in keys if h(k) % 8 != h(k) % 12)
print(f"modulo 8 -> 12: {moved_mod / len(keys):.0%} of keys move")

def ring(nodes, vnodes=200):
    points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
    return [p for p, _ in points], [n for _, n in points]

def owner(r, key):
    points, names = r
    i = bisect.bisect(points, h(key)) % len(points)
    return names[i]

r8 = ring([f"db{i}" for i in range(8)])
r12 = ring([f"db{i}" for i in range(12)])
moved_ring = sum(1 for k in keys if owner(r8, k) != owner(r12, k))
print(f"consistent hashing 8 -> 12: {moved_ring / len(keys):.0%} of keys move (ideal: {4 / 12:.0%})")

modulo 8 -> 12: 66% of keys move
consistent hashing 8 -> 12: 35% of keys move (ideal: 33%)

Root cause

With key % N, changing N changes the result for most keys. Resharding then means moving most of the data at once. Consistent hashing (or a fixed number of logical shards) only moves the data that must move to the new servers.

The fix

1. Map keys to a fixed, large number of logical shards (or a hash ring with virtual nodes) and map logical shards to physical databases. Adding a database moves whole logical shards.
2. Move each logical shard online with the recipe used by Notion and Stripe's online migrations:
   1. Double-write new changes to old and new locations (or replicate via CDC/logical replication).
   2. Backfill existing rows in batches.
   3. Verify — compare counts/checksums, shadow-read and diff.
   4. Switch reads, then writes, per logical shard; keep the old copy until you're confident.

LOGICAL = 1024
routing = {ls: "db0" for ls in range(LOGICAL)}           # stored in a config service / DB, cached

def db_for(conversation_id: int) -> str:
    return routing[zlib.crc32(str(conversation_id).encode()) % LOGICAL]

# move logical shard 37 to db9: double-write → backfill → verify → flip routing[37] = "db9"

-- on the source: publish the tables (or use a per-shard schema)
CREATE PUBLICATION move_ls37 FOR TABLE ls37.messages, ls37.conversations;
-- on the target: initial copy + streaming changes
CREATE SUBSCRIPTION move_ls37 CONNECTION 'host=db0 dbname=app' PUBLICATION move_ls37;
-- when lag is ~0: block writes briefly for ls37, flip routing, drop the subscription

Notion's migration followed double-write, backfill, verification and switch-over, using an audit log to replay writes reliably (Notion engineering); Stripe describes the same dual-write, read-switch, write-switch phases for moving data between tables online (Stripe engineering).

Trade-offs

• Consistent hashing needs virtual nodes to balance well; a routing table is simpler to reason about and lets you move hot shards deliberately.
• Double-writing from the application can diverge on partial failures — prefer an audit log/outbox or database-level replication as the source of truth for the copy.
• The cut-over needs a brief write pause (or a fencing mechanism) per logical shard; keep each unit small.

Detect it in production

• Move progress per logical shard: rows copied, replication lag, verification diffs.
• Per-shard error rates during cut-over; ability to flip routing back instantly.

Key points

• key % N moves most data when N changes; use logical shards or consistent hashing.
• Move data with double-write (or replication) → backfill → verify → switch, one small unit at a time.
• Keep a fast rollback: the old copy stays until verified.