Art of Codeartofcode
Lesson 4 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.3 What are the ways to map keys to shards?

3 min read+10 XP

At the exam centre: Three kinds of notice board: ranges ("rolls 1 to 2,500: Hall 1"), a formula ("roll number mod 4 + 1"), or a printed list with each student's hall.

In the system:

range, hash and directory sharding compared.

Figure: three ways to decide which shard a key belongs to.

15.3.1 Range sharding

At the exam centre: Consecutive roll numbers sit together: Hall 1 has rolls 1 to 2,500.

In the system: Each shard owns a contiguous range of key values. Range queries ("user IDs 1,000 to 2,000", "orders in March") stay on one or a few shards, and a busy range can be split into two. The danger is keys that grow over time, like timestamps or auto-increment IDs: every new row lands in the last range, so one shard takes all new writes (15.4). Used by HBase and Bigtable, and common in hand-built SQL sharding.

15.3.2 Hash sharding

At the exam centre: A formula scatters students so neighbouring roll numbers end up in different halls.

In the system: Compute hash(key) and use it to pick the shard. Neighbouring keys land in different places, so load spreads evenly and there's no "latest" shard. The cost: range queries hit every shard, because the hash scatters ranges. And the naive formula hash(key) mod N reshuffles almost everything when N changes (15.5); real systems use hash slots, logical shards or consistent hashing (Chapter 28) instead. Used by Cassandra, DynamoDB and Redis Cluster.

15.3.3 Directory sharding

At the exam centre: A printed list says exactly where each student sits. The exam centre can put the big coaching institute's 800 students in their own hall.

In the system: A lookup table maps each key (or tenant, or range) to a shard. Fully flexible: move one big customer to its own shard, rebalance one tenant at a time. The cost: the directory is on the path of every request, so it must be fast, cached and highly available, and kept consistent while things move. Common in multi-tenant software (one shard per large customer, many small customers per shared shard).

StrategyGreat atWatch out for
RangeRange queries, splitting busy rangesEver-growing keys → one hot shard
HashEven loadRange queries everywhere; plain mod N reshuffles
DirectoryTotal flexibility, moving tenantsThe directory itself must be fast and always up

Memory code: "Ranges keep neighbours together, hashes scatter them, a list puts anyone anywhere."