Sharding: splitting the data itself

Part of the free System Design course on LogicWiz, in the chapter: Databases at scale. The interactive whiteboard exercises and simulations run in the app.

Week 5, Day 4: One machine, 15 TB, and a festival sale

"We added replicas and the writes were still melting the primary. Kabir said: copies do not share the writing."

From Meera's notebook

Why one machine is not enough

Replicas help reads, but every write still goes to one primary, and every replica stores everything. This lesson is a growth story. SwiftKart today does about 500,000 orders a day and one SQL database copes. Three years on, imagine about 20 million orders a day at roughly 2 KB each: about 40 GB a day, or about 14.6 TB a year. That is more than one server's disks should carry. During a festival sale the primary also takes about 20,000 writes a second. Even a large, well-tuned machine is comfortable at only about 5,000 simple writes.

You cannot make one machine endlessly bigger. At some point you split the data across machines so each holds and serves only a slice. That is sharding (also called partitioning). Meera moves orders to a sharded key-value store, and the price is real: cross-order joins are gone. Each shard comfortable at 5,000 writes a second adds 5,000. So you need at least 4 shards to reach 20,000, and 6 to 8 to leave headroom for the next sale.

Sharding comes down to one decision: for any given order, which shard owns it? The field you use to decide is the shard key.

The shard key: a good one and a bad one

Meera's first idea: shard orders by city. Mumbai orders on shard 1, Delhi on shard 2, Bengaluru on shard 3, the rest on shard 4. It looks tidy, and queries like "all orders in Pune" are easy.

Then the IPL final starts and Mumbai orders spike. Shard 1 gets about 60% of all traffic while the others idle. This is a hotspot: the key spreads data unevenly, so one machine is overloaded while three sit nearly idle. Adding more shards does not help, because Mumbai is still one key.

Better: shard by customer id. Customers are numerous and roughly equal, so load spreads evenly, and "my orders" only ever touches one shard. A good shard key has three traits:

  • High cardinality (many distinct values): millions of customers, not 4 cities.
  • Even load: no single value is dramatically busier than the rest.
  • Matches the common query: the question you ask most should hit one shard.

💡 Tip: Ask "what is the most common query, and what does it filter on?" Usually that field, if it is evenly spread, is your shard key.

Try it yourself below. Shard the same orders by city, then by customer id, then by order date, and change the shard count from 2 to 8. Watch the busiest bar and the skew factor (busiest shard divided by the average): with city, adding shards barely helps.

Range sharding versus hash sharding

Two ways to turn a key into a shard:

  • Range: customer ids 1 to 25 million on shard 1, 25 to 50 million on shard 2, and so on. Range queries ("ids 100 to 200") are cheap. But new customers always get the highest ids, so the last shard takes all new writes. Another hotspot.
  • Hash: compute a hash of the id and take it modulo the shard count. Load is spread evenly because a hash scrambles the order. The price: neighbouring ids land on different shards, so range scans must ask every shard.

The simple hash formula is shard = hash(key) mod N. With N = 4 it works. Now Kabir asks: what happens when you add a fifth shard?

Resharding pain, and consistent hashing

Change N from 4 to 5 and almost every key's answer changes. A key that hashed to 7 was on shard 3 (7 mod 4) and is now on shard 2 (7 mod 5). Roughly 80% of all data must move, while the app is live. That is resharding pain.

Consistent hashing fixes it. Picture a ring of positions from 0 to 99. Place each shard on the ring (one spot each here; real systems use many): A at 10, B at 35, C at 60, D at 85. To find a key's home, hash it to a position and walk clockwise to the first shard. Key at 40 goes to C (at 60). Key at 90 wraps around to A (at 10).

flowchart LR
  A["A at 10"] --> B["B at 35"] --> C["C at 60"] --> D["D at 85"] --> A

Now add shard E at position 72. Only the keys between 60 and 72 used to belong to D; now they belong to E. Everything else stays put. In this ring E takes only the 12 positions between 60 and 72, so about 12% of keys move, not 80%. Removing a node is the mirror image: only its slice moves, to its clockwise neighbour.

One spot per shard makes slices uneven: E got 12% where a fair share is 20%. So real systems give each shard many ring positions, called virtual nodes. With many small slices per shard, each shard's total evens out. A new fifth node takes about 1 in 5 keys, the ideal share. A failed node's load spreads over many neighbours instead of landing on one.

Play with the ring below. Add and remove servers, and compare the share of keys that move against mod-N hashing. Then switch virtual nodes from 1 to 10 to 50 and watch the per-server load bars even out.

Notice what Meera gave up. She can no longer ask the database for orders sorted by time across the whole country in one query. She trades that convenience for the ability to keep growing, and decides where the rare global question gets answered instead, such as a nightly copy for reporting.

Cross-shard queries, and when not to shard

The cost of sharding appears when a question does not include the shard key. "Total orders today across India" must ask every shard and combine the answers. This is called scatter-gather. It is slower, and it is only as reliable as the slowest shard. Joins and transactions across shards are hard, so designers avoid them. Keep an order and its items on the same shard (same customer id), and run analytics on a separate copy. Rider questions, such as "orders for rider 77 today", also lose out. They need a secondary index (a separate lookup from rider id to the shards holding those orders) or a separate copy keyed by rider. Otherwise they scatter-gather too.

In mock interviews, candidates often say "If a database is slow, shard it." Sharding is the last step, not the first. It adds routing, resharding and cross-shard complexity. Try the cheap things first: an index, a cache, read replicas. Shard when data size or write volume truly exceeds one primary, as the numbers above do.

📌 Summary: Shard only when one primary cannot cope. Pick a shard key with many values and even load (customer id, not city). Consistent hashing moves only about 1/N of keys.

What Meera learns next

Even a sharded database is slow if every request reaches it. Next week: caching, keeping the answers you give most often somewhere much faster.

Check your understanding

  1. Orders are sharded by city across 4 shards. During the IPL final the Mumbai shard takes about 60% of all traffic. A teammate proposes going to 8 shards. What happens?
  2. SwiftKart places keys with shard = hash(key) mod 4 and adds a fifth shard, switching to mod 5. Roughly what share of keys must move?
  3. On a consistent-hash ring with one position per shard, a newly added shard took only 12% of the keys, while another shard owns about 35%. What evens this out?
  4. Orders are sharded by customer id. The finance team's "total orders today across India" query is now slow and fails whenever one shard is slow. What should Meera do?