Sharding

One machine can hold only so much data and take only so many writes. When the data or the write rate passes that limit, the only way forward is to split the data across machines. That split is sharding (also called horizontal partitioning). Each machine, a shard, holds a slice and handles the reads and writes for it.

Crux: shard only when a number forces you to, choose a key that spreads load evenly and matches how you query, and know that every query that crosses shards gets harder.

Partitioning and sharding

The words overlap, so fix them first. Partitioning splits one table inside a database: horizontally (by rows, for example one partition per month) or vertically (by columns, moving a rarely used large column to its own table). It helps maintenance and scans but still lives on one machine. Sharding is horizontal partitioning where each part lives on a different machine with its own CPU, memory, disk and connection limit. Only sharding adds capacity.

When the numbers force it

Try the cheaper options first. They are simpler and you can usually do them in a day.

• A bigger machine. More memory, faster disks. Modern servers hold many terabytes, so a surprising number of systems never need more.
• Read replicas. Copies that serve reads. They fix a read problem but not storage and not writes, because every write still goes to the primary.
• Caching. Takes read load off the database.
• Archiving or time-partitioning. Move old data out of the hot store.

Shard when the data does not fit one node, or the write rate is more than one primary can take. Arithmetic with the click data from the estimation lesson:

Clicks:       ~12.6 TB per year
One node (assume ~2 TB is comfortable):  12.6 ÷ 2 = 6.3  →  7 shards for the first year
Keep 3 years:                            37.8 ÷ 2 = 18.9 →  19 shards

Links, at 240 GB a year, do not need it. Say that: it shows you shard what is big and leave the rest alone.

How it works

Every record has a shard key. A function maps the key to a shard, and a router (a library in the app, a proxy, or the database itself) sends each request there.

This works only if every request carries the shard key. A query that does not has to ask all the shards and merge the answers, which is called a scatter-gather. It is slower, and one slow shard slows the whole query.

Three ways to divide the data

• Range. Each shard owns a continuous range of keys (A to H, I to P). Range scans ("all orders from March") stay on one shard. The risk is a hot spot: with keys that grow over time, all new writes land on the last shard.
• Hash. Run the key through a hash function and use the result to choose a shard. Load spreads evenly, even for sequential keys. The cost is that neighbouring keys are scattered, so a range query touches every shard.
• Directory. A lookup table says which shard holds each key. You can move any key anywhere, one at a time. The cost is that the table is another component that must be fast, available and correct, and that every request pays a lookup (cache it, and then handle stale entries).

Default: hash the key. Use range only when range queries are the main access pattern.

A plain hash(key) mod N has a flaw: when N changes, almost every key moves. The next lesson, on consistent hashing, fixes it.

Choose the shard key

The key is the most important decision in this lesson, and it is hard to change later. A good key has three properties.

• High cardinality. Many distinct values. Sharding on country gives you at most a few hundred shards, and one country is far bigger than the rest.
• Even load. No value takes a big share of the traffic.
• Matches the queries. The most common queries filter on it, so they hit one shard.

Examples, with a feed of messages:

• user_id suits "show this user's data": one shard per request. Good default for user-centred products.
• timestamp is a trap: every write goes to the newest shard.
• country is a trap: uneven and low cardinality.
• For a chat app, conversation_id keeps one conversation on one shard, so "load this conversation" touches only one.

Hot keys

A good key can still have a hot key: one celebrity user, one viral link, one popular product. Hashing cannot split a single key. Fixes, each with a cost:

• Cache the hot key's reads in front of the shard.
• Add a suffix (key#0 to key#9) and spread writes over ten sub-keys. Reads must now ask all ten and combine.
• Give hot keys their own shard, or their own treatment, once you can detect them.
• Use a compound key such as (user_id, day), so one very active user spreads over many shards; the cost is that reading a whole user now touches several.
• Split dynamically. Some systems notice a busy range and split it in two on their own. It works, and it is operational machinery you must trust.

Time-ordered data has the same shape: the newest slice takes all the writes. Prefix the key with something that spreads it (a user or device ID) rather than shard on the clock.

What gets harder

Sharding trades simplicity for capacity. Name these costs, because they are what the interviewer is waiting for.

• Queries that cross shards. A join or aggregate across shards means scatter-gather. Design so the common queries stay on one shard. Duplicate data if you must.
• Transactions across shards. A single database gives you atomic commits. Across shards you need two-phase commit (slow, and blocks if the coordinator fails) or a saga (a chain of local steps with compensating undo steps). Better: choose the key so one transaction stays on one shard.
• Secondary indexes. An index on a non-key field is either local (each shard indexes its own rows, so a lookup asks every shard) or global (one index spread by its own key, so a write updates two places and the index may lag).
• Unique constraints. "Email must be unique" cannot be checked by one shard alone. Shard by the field that must be unique, or keep a separate unique table.
• Rebalancing. Adding a shard means moving data while the system runs. Plan it from the start.
• Operations. More machines to back up, monitor and upgrade. One bad shard is a partial outage.

Plan for growth

A common trick is to create many more logical shards than machines, for example 256 logical shards on 4 machines. Adding a machine then moves whole logical shards (a copy) instead of re-splitting every key. Redis Cluster works this way, with 16,384 hash slots.

Sharding you do not build yourself

Most real systems give you sharding as a feature, and the interview answer is to name which one. Cassandra and DynamoDB spread data by hashing a partition key you choose (consistent hashing in the Dynamo family), so the key design is your job and the movement is theirs. MongoDB shards by a key you pick, ranged or hashed. For relational data, Vitess (MySQL) and Citus (Postgres) add a sharding layer on top, and distributed SQL systems (Spanner, CockroachDB, and cloud options such as Aurora's scale-out modes) hide it at a higher price in write latency. Details differ by version, so check the docs before claiming a specific behaviour.

How to talk about it

• 1. Prove the bottleneck. State the numbers that force sharding (data size, write rate), after the cheaper options.
• 2. Name the shard key and the queries it serves.
• 3. Choose the strategy (usually hash) and say what stays on one shard and what scatters.
• 4. Name the cost: cross-shard queries, transactions, rebalancing.
• 5. Plan growth: logical shards, and how a new node is added.

Common mistakes

• Sharding "for scale" with no numbers.
• A key that only grows (a timestamp or an auto-increment ID) combined with range sharding.
• A key that does not appear in the main queries.
• Forgetting hot keys.
• Promising cross-shard transactions with no plan for them.
• Using hash mod N and no plan for changing N.
• A low-cardinality key (a boolean, a status, a country).
• Reaching for two-phase commit by default instead of choosing a key that keeps a transaction on one shard.
• A directory with no thought for its latency or what happens when it is down.

Check yourself

• What would you try before sharding?
• How many shards does 12.6 TB need if a node comfortably holds 2 TB?
• What is a scatter-gather query, and when does one happen?
• Why is timestamp usually a bad shard key?
• Range versus hash: which one for "all orders from March", and which for even load?
• How do you handle one key that is far hotter than the rest?
• What is the difference between partitioning and sharding?
• Name two properties a shard key should have, and a field that fails them.