How do you add more shards to a running system without a long outage?
Avoid plain modulo hashing, which moves most keys when the shard count changes. Use consistent hashing or many small virtual shards mapped to servers, then move a few of them in the background while dual-checking routing.
Explain it simply
With key % N routing, going from 4 to 5 shards changes the destination of about 80% of keys, so almost all data must move. That is why naive modulo is a trap.
Better approaches:
- Consistent hashing: adding a node takes over a slice from its neighbours; only about 1/N of keys move.
- Many logical shards: create, say, 1,024 logical shards from day one and map them to a few physical servers in a lookup table. Adding a server means moving some logical shards, not rehashing keys.
Migration steps for a logical shard:
- Copy data to the new server in the background.
- Stream ongoing changes so the copy catches up.
- Briefly pause writes to that shard, finish the sync.
- Update the routing table to the new location.
- Remove the old copy after verification.
Throttle the copy to protect production traffic, and keep routing metadata highly available.
Example
Going from 4 to 5 servers with 1,024 logical shards.
Before: 256 logical shards per server
After : about 205 per server
Moved : 4 x (256 - 205) = 204 logical shards (about 20% of data)
Keys never change logical shard, only the lookup table changesWhat to say in the interview
"Naive modulo remaps most keys, so I use consistent hashing or many logical shards with a routing table. I migrate shard by shard: bulk copy, catch up on changes, short write pause, flip the routing, verify, delete. That keeps the outage to seconds, not hours."