Sharding & partitioning

An online store keeps every order in one database. It has 4 TB of orders and grows by a terabyte a year. At the holiday peak it must take 30,000 new orders a second, and load tests show the server tops out around 10,000. Something has to give.

Try the cheap fixes first, because each one keeps the database simple:

None of these raises the write limit. For that the data itself has to be split, so that different servers own different rows. Partitioning means splitting a dataset into pieces. Sharding is partitioning by rows across separate servers: each shard has the same tables but its own subset of the rows, and each shard is a complete database of its own.

With four shards, each takes a quarter of the peak: 30,000 ÷ 4 = 7,500 writes a second, below the 10,000 one server can handle. Each shard is still replicated, so losing a server affects one shard until a replica takes over, never the whole store:

Sharding is one of three ways to split data, and the other two are simpler, so check them first:

• Vertical partitioning splits a table's columns: the order's large, rarely read gift message moves to its own table.
• Functional partitioning gives each feature its own database: orders, the product catalog and reviews no longer share a server.
• Horizontal partitioning, or sharding, splits the rows. It is the only one that keeps scaling, and the only one that changes how every query works.

The names vary by product. MongoDB and Elasticsearch say shard; DynamoDB and Kafka say partition; HBase says region. The idea is the same. One more word: databases can also partition a table inside one server, which helps manage big tables but adds no capacity.

Every row needs a rule that says which shard owns it. The column the rule uses is the shard key (or partition key). A query that names the shard key goes to one shard. A query that doesn't has to ask all of them. So the right key depends on the questions you ask most.

The store asks three questions: show a customer's orders (on every visit to the account page, by far the most common), open order 7731 (from an email link), and what sold today (once a night, for a report). Here is how three candidate keys fare:

The last row needs one trick. Open order 7731 names only the order, so the router can't tell which shard to ask. Fix it by building the customer's shard into the order ID itself (for example c51-7731), or by keeping a small lookup table from order ID to customer. The nightly report reads every shard either way; it runs once a night, so that is fine.

A good shard key has five properties:

• Many distinct values. Shard by country and you can never have more shards than countries; shard by continent and a cluster has at most seven useful shards.
• Evenly used values. If most rows share a few values, those shards carry most of the load (Hot partitions & skew covers the famous customer or celebrity).
• Not always increasing. Timestamps and auto-increment IDs send every insert to the shard holding the newest values.
• Never changes. A row whose key changes has to move to another shard.
• In your main queries. So most requests touch exactly one shard.

Take the time to choose. Changing the shard key later means moving every row to a new layout while the system is live, which is one of the riskiest jobs in data engineering.

Once you have the key, you need the rule that turns a key value into a shard. There are three common rules, plus one for geography:

Real systems often combine two. A compound key has a partition part and a sort part. Hash the customer ID to pick the shard, then keep that customer's orders sorted by date inside it. My orders, newest first becomes one shard and one sorted read. Cassandra's partition and clustering keys, and DynamoDB's partition and sort keys, work exactly like this.

Lookup tables become more flexible with virtual shards: the key maps to one of many small logical shards, say 1,024, and a small table maps those onto the physical servers. The application only ever sees the logical shard, so moving one to a new server is a change to the small table, not to the code.

Something has to know which shard owns what. Three places are common:

• A routing tier, such as MongoDB's mongos: applications talk only to it, and it holds a cached copy of the shard map.
• The client library, which keeps the map itself and connects straight to the right shard.
• Any node, as in Cassandra: the client asks any server, which forwards the request to the owner.

Whichever you pick, the map itself lives somewhere highly available, and every router caches it.

A query with the shard key is targeted: one shard answers. A query without it is a scatter-gather query. The router sends it to every shard, waits for all of them, and merges the results:

Scatter-gather costs more than its share of work. Every shard spends effort on every such query, so adding shards doesn't add capacity for it. And the answer waits for the slowest shard. If each of 16 shards is slow 1% of the time, a query that asks all of them is slow 1 − 0.99¹⁶ ≈ 15% of the time.

Sorting and limits are merged at the router. For the 10 newest pending refunds, each shard returns its own 10 newest, and the router merges 40 rows and keeps 10. Paging deep into such results gets expensive, because to skip 1,000 rows the router has to fetch 1,010 from every shard.

Secondary indexes face the same choice. An index on status can live with the rows or be split by the indexed value:

Inside one database, a join or a transaction across tables is routine. Across shards, each becomes a distributed problem. Sharding works when you design the data so they are rare:

Operations multiply too. Every schema change runs on every shard. Backups are per shard, and restoring one shard to last Tuesday leaves it out of step with the others. Monitoring needs a view across all of them. None of it is impossible, and all of it is permanent: sharding is a decision you live with for the life of the system.

That is why it comes last. If the data and the writes fit on one well-sized server for the next few years, with replicas for reads and a cache in front, that is the better design. Shard when the write rate or the data size says you must, or when the law says some data must live in one country.

The store grows, and four shards become five. How much data has to move? It depends on the rule, and the obvious rule is the worst one.

The obvious rule is hash mod N: shard = hash(key) mod 4. Change N to 5 and a key stays put only if its hash gives the same remainder for 4 and for 5, which is true for just 1 key in 5. So 80% of all orders move, at the busiest time, just to add 20% more capacity. Consistent hashing shows the problem in full.

Many fixed partitions is a common answer. Create far more partitions than servers on day one, 1,024 for 4 servers, 256 each, and never change that number. The key-to-partition rule stays fixed forever; growing only moves whole partitions. The fifth server takes about 51 from each of the others. The catch is that the number can't easily change later: Elasticsearch, for example, sets an index's number of primary shards when the index is created.

Splitting ranges is the other answer, used by range-sharded systems like MongoDB and HBase. A range that grows too big splits in two, and a balancer moves halves to emptier servers. It adapts to the data, but it can't help when every new write targets the same end of the range.

Moving a partition safely follows the same steps whatever the rule: