Art of Codeartofcode
Lesson 6 of 15

15. Sharding

1
The picture to keep in your head
2
15.1 Why shard at all?
3
15.2 How do you choose the shard key?
4
15.3 What are the ways to map keys to shards?
5
15.4 What is a hot shard?
6
15.5 How do you add shards without moving everything?
7
15.6 What happens to queries and joins that cross shards?
8
15.7 How do you keep IDs and unique rules across shards?
9
15.8 How do sharding and replication work together?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
15. Sharding

15.5 How do you add shards without moving everything?

3 min read+10 XP

At the exam centre: Mid-year, a new hall opens. If seats were assigned by "roll number mod 4" and you change it to "mod 5", almost every student changes hall. Chaos. If instead the centre had split students into 1,024 small groups from day one and assigns groups to halls, opening a hall means moving a few whole groups.

In the system: Resharding (rebalancing) means changing how data is spread, usually to add capacity. The trap is plain hash(key) mod N: changing N moves most keys. In the chapter's code, going from 4 to 5 servers moves 80% of keys.

mod N moves 80% of keys; 1,024 logical shards move 20%, as 204 whole buckets.

Figure: with logical shards, keys never re-hash; whole buckets move to the new server.

Better approaches:

  1. Logical shards (fixed buckets): hash keys into a large, fixed number of logical shards (say 1,024), and map logical shards to physical servers. Adding a server moves some whole logical shards to it; keys never change bucket. In the chapter's code: 204 of 1,024 buckets move, about 20% of keys, the minimum possible. Instagram described a similar design: thousands of logical shards mapped onto far fewer database servers.
  2. Hash slots or consistent hashing: the same idea, with a slot range (Redis Cluster's 16,384 slots) or a hash ring (Chapter 28).
  3. Splitting ranges: range-sharded systems split a busy range into two and move one half.

Moving data safely, step by step:

  1. Copy the bucket to the new server (a snapshot plus the changes since).
  2. Catch up: keep applying new writes until the copy is current.
  3. Switch the routing map, briefly pausing writes to that bucket if needed.
  4. Verify, then delete the old copy.

Tools like Vitess (for MySQL) and Citus (for PostgreSQL) automate much of this.

Memory code: "Cut the data into many small groups on day one; later, move groups, not students."