Sharding a Database

The ask

One database machine can hold only so much data. It also answers only so many queries.

The table has outgrown one machine. Reads and writes both slow as the table grows.

The ask is a split that keeps one logical table. Callers keep asking for rows by key, unaware of the split.

Growth continues after the split. The split must leave room to split again.

Estimate the scale

The worked table holds 1,000,000,000 rows. One row takes 1 KB.

1,000,000,000 rows x 1 KB = 1 TB of table.

The target size for one shard is 100 GB.

1,000 GB / 100 GB a shard = 10 shards.

The table grows by 10,000,000 rows a day. 10,000,000 rows x 1 KB = 10 GB of growth a day.

100 GB of room / 10 GB a day = one new shard about every 10 days.

Choosing the shard key

A shard key is the value that decides which shard holds a row. The user ID is a common choice for a users table.

A good key spreads rows evenly. Even spread keeps every shard near the target size.

A good key also matches the queries. Most queries name one key, so most queries visit one shard.

A bad key creates a hot shard. One famous account can overload the shard that holds it.

API and data

Callers keep the usual operations. Get, put, and delete each name a row by its key.

A routing layer reads the key and picks the shard. The routing layer is a small service, or a library inside the caller, that knows the split.

Queries without a key are the awkward ones. They must visit every shard and merge the answers.

Counts and sums across the whole table work the same way. Each shard answers for its rows, and the answers combine.

High-level design

Each shard is a full database on its own machine. It holds its rows, its indexes, and its copies.

Copies of each shard live on other machines. A machine failure costs no rows.

The routing layer holds the map of key ranges to shards. The map is small and changes rarely.

Consistent hashing can hold the map instead of ranges. Either way, the map decides placement and must stay accurate.

Deep dive: resharding

Resharding is changing the number of shards and moving rows until each shard sits near the target size again.

Growth forces resharding at the worked pace. A new shard is needed about every 10 days, and waiting longer overloads one shard.

The move copies a range of rows to the new shard. Writes during the move go to both the old home and the new home.

A check compares row counts and checksums on both sides. Only a matching range switches over.

The switch flips the map entry for the range. Callers then reach the new shard, and the old copy is removed.

A failed move is abandoned, not forced. The old shard keeps serving, and the move retries later.

Hot shards and balance

Even splits by count can still run hot. Reads concentrate on famous rows, not on average rows.

A hot shard can split on its own. Its range divides, and half its rows move to a fresh machine.

Very hot single rows need a different answer. Copies for reading can spread that load across machines.

Balance is a moving target. Steady small moves beat rare huge moves.

Evaluation and trade-offs

Sharding buys size and speed together. The table outgrows any one machine without changing its shape for callers.

Cross-shard queries pay the price. Questions that ignore the key visit every shard.

Joins across shards are painful or impossible. Data that must join belongs on the same shard.

Transactions across shards are hard. The design keeps each transaction inside one shard where it can.

Many ordinary databases, split by a well-chosen key, act as one large database. The key choice decides whether the split feels invisible.

The worked table in numbers