Pattern card: sharding

The full lesson, with a worked example of growing from 4 shards to 8: Sharding and consistent hashing.

What it is

Sharding splits one dataset across several independent databases. Each piece is a shard: a complete database, usually with its own replicas, holding part of the rows.

• What it fixes: writes and total size. Four shards at about 10,000 writes a second each give about 40,000.
• What replicas can't fix: every replica applies every write, so ten replicas give ten times the reads and zero extra writes.
• The shard key: a field on every row (usually user, customer or order ID) that decides which shard holds it.
• The router: turns a key into a shard and sends the query only there. It can be a library in the app, a proxy, or a small lookup service.
• The price: queries, joins, transactions and uniqueness rules that cross shards get hard.

When to use it

Use it when:

• Writes outgrow one primary, even after tuning. Example: a 5 crore user app peaking at about 40,000 writes a second against a database comfortable at about 10,000.
• Size hurts operations: about 400 KB per user × 5 crore users = about 20 TB. It fits on one machine, but backups and restores take most of a day and index rebuilds crawl.
• Data naturally belongs to an owner: a user, a company, an order. Most queries touch one owner.

Don't use it yet when:

• One database can still cope. Try, in order: indexes, a cache, read replicas, a bigger machine, archiving old data.
• Reads are the problem. That's replicas and caching.
• Most queries span everyone: leaderboards, analytics, global search. Those belong in a separate store built for them.

Sharding early slows every feature. Instead, design IDs and tables so that everything belongs to an owner; then sharding later is possible.

How it works

1. Pick the key. Write down the five most frequent queries and count how many shards each touches under each candidate key. A good key:

• spreads data and traffic evenly (not country, not sign-up date);
• keeps data read together in one place (a user's profile, posts and settings);
• never changes for a row (not city: people move);
• serves the main questions. Sharding rides by rider ID makes "my rides" one shard, and "this driver's rides" every shard.

2. Map the key to a shard (see Variants). Most systems hash the key into a fixed number of slots, say 1,024, and keep a small slot map saying which shard owns each slot.

3. Route every query. Single-key queries go to one shard. Anything else is scatter-gather: ask all shards, merge, and wait for the slowest one.

4. Add secondary lookups. To find a user by phone or email, keep a lookup table from phone to user ID, itself sharded by phone. A login becomes two single-shard reads instead of asking every shard.

5. Make each shard reliable. Each shard is a small cluster: a primary, replicas in other zones and automatic failover. A dead shard without that takes out about 1 in N users.

6. Grow by moving slots, not rehashing. Copy, catch up, briefly pause one slot, flip the map, retry stale routers:

1. 1

   Old shardNew shard

   Bulk copy slot 384 in the background

2. 2

   Old shardNew shard

   Stream changes until about 1 s behind

3. 3

   RouterOld shard

   Pause writes for slot 384 (about 0.25 s)

4. 4

   Old shardNew shard

   Last few changes

5. 5

   RouterNew shard

   Map v18: slot 384 lives here

A router with an old map gets a "wrong shard, map is now version 18" reply, reloads the map and retries. The hash of each key never changes, only the slot map.

Variants

• Range. How: key ranges per shard (A to H, I to P). Good for: range scans such as "names starting with K" or time windows (a range query). Cost: uneven ranges (far more names start with S or A than Q), and time-based keys send all new writes to one shard.
• Hash mod N. How: run the key through a hash function, take the remainder by N shards. Good for: even spread with no lookup. Cost: changing N moves almost everything (4 to 5 shards moves about 80% of keys); range questions hit every shard.
• Consistent hashing. How: shards and keys are hashed onto a ring; each key belongs to the next shard clockwise. Good for: growth, since a new shard takes only its slice of the ring. Cost: uneven gaps unless you add virtual nodes (about 100 points per shard), plus ring bookkeeping.
• Fixed slots. How: hash into, say, 1,024 slots that never change; a slot map assigns slots to shards. Good for: moving one slot at a time, versioned maps, simple operations. Cost: the map must be fast, cached and versioned; slot count caps how finely you can split.
• Directory (lookup table). How: a table says which shard each tenant or user lives on. Good for: moving one noisy customer to its own shard by changing one row. Cost: an extra lookup on every query; the directory must be cached and never lost.
• Two-level key. How: shard by tenant, then split a giant tenant again by a second key such as store or employee ID. Good for: business apps where one customer (say 2 lakh staff) dwarfs the usual 50. Cost: that tenant's queries become scatter-gather across its sub-shards.

Numbers to know

• One well-tuned primary: about 10,000 writes a second, as a working figure.
• Shard count = peak writes ÷ safe writes per shard, plus room for about a year of growth. 40,000 ÷ 10,000 = 4; size 20 TB ÷ 4 = 5 TB each.
• Hash mod N growth: going from 4 to 5 shards keeps only about 1 key in 5 in place. With 1 crore users, about 80 lakh move.
• Consistent hashing growth: adding a fifth shard moves about 1 in 5 keys, about 20 lakh, all to the new shard. In general about 1/(N+1).
• Fixed slots: 1,024 slots on 4 shards is 256 each; doubling to 8 means each old shard hands 128 slots to one new shard.
• Users per slot: 4 crore users ÷ 1,024 slots = about 40,000, so a slot flip only touches that small group.
• Copy time: 1.5 TB at about 100 MB a second = about 15,000 seconds, a little over 4 hours. Run it overnight.
• Flip pause: about a quarter of a second per slot.
• Start early: at 6% user growth a month, a shard at 70% reaches 85% in about four months. Moving data takes weeks.
• Scatter-gather cost: a query that asks every shard does N times the work; with 64 shards, one login by phone would fire 64 queries.
• Hot counter: split into about 20 sub-counters across shards and sum on read; counts lag a few seconds.

Pitfalls

• Sharding too early. A 2 lakh user app spends every feature fighting cross-shard reports and routing bugs. Fix: scale one database first.
• A key that clusters. City, country or date sends most traffic to a few shards. Fix: a stable owner ID; keep a separate copy or index for city views.
• A key that changes. A customer who moves cities ends up split across shards. Fix: keys that never change for a row.
• Hard-coded "ID mod 4". Growth means moving 80% of data in one go, and every service that copied the rule must change the same day. Fix: slots or a ring, with one shared map.
• Hot keys. A film star's post lands every like on one shard. Fix: cache hot reads, split hot counters, move huge accounts to their own shard via a directory.
• Per-shard auto-increment IDs. Four different "order 1,045". Fix: globally unique IDs, time-ordered with a machine number, or with the slot embedded so the ID alone routes the row.
• Cross-shard money moves. Debit on shard 1 succeeds, credit on shard 4 fails. Fix: a ledger entry with a transfer ID, idempotent steps, a compensating action on failure, and nightly reconciliation. Avoid two-phase commit on the hot path.
• Global uniqueness. "No two users share a username" needs its own lookup table sharded by username.
• Partial outages. One shard down means "works for my brother, not for me". Fix: replicas and failover per shard, and screens that degrade instead of crashing.
• Stale routers after a move. Fix: versioned maps and "wrong shard" redirects.

In an interview

Shard because the numbers demand it, not by reflex, and name what it costs.

• The trigger: writes a second and total size against what one machine handles, after replicas and caching.
• The key: chosen from the main queries; explain why it spreads evenly and keeps related data together.
• The mapping: hash into fixed slots or a consistent hash ring with virtual nodes; how you'd add shards.
• What gets hard: cross-shard queries, joins, transactions, uniqueness, and how you'd handle each.
• Reliability: replicas and failover per shard; hot-key handling.

Follow-ups and short answers:

• "How do you find a user by email if you shard by user ID?" A separate email-to-user-ID table, sharded by email. Two single-shard reads instead of asking every shard.
• "What happens when you add a shard?" With slots or a ring, only a small share of keys move: bulk copy, stream changes, pause and flip each slot, and let stale routers retry after a "wrong shard" reply.
• "One celebrity's shard is overloaded. What now?" Cache their hot reads, split hot counters into sub-counters, and move that account to its own shard via a directory.
• "How do you run a query across all shards, like top posts today?" Scatter-gather for rare queries; for frequent ones, feed a separate precomputed store through change data capture.
• "Sharding or read replicas?" Replicas for read-heavy load; sharding when writes or size outgrow one primary. Each shard usually has replicas too. See Pattern card: caching for taking reads off first.