Database sharding simulator

The table is a generated orders table: 20,000 orders over 30 days, from 2,000 users who belong to 40 companies. Company sizes follow a skewed distribution, so the biggest company has 28% of all orders, and some users order far more than others, as in real data.

Pick a shard key and a placement method. The bars show how many rows each shard holds and how many of the last day’s orders it received. Choose a query to see which shards the router has to ask, and press Add a shard to see how many rows have to move. Things to try:

• Key ranges on Created at: perfectly balanced storage, and every new write on one shard.
• Tenant ID with any method: the biggest company cannot be split, and adding shards does not help it.
• Hash modulo N, then hash slots, each followed by Add a shard: compare how many rows move.

Sharding is splitting the rows of a database table across several servers, each of which holds part of the data and handles the reads and writes for it. Each part is a shard. It is also called horizontal partitioning, in contrast to vertical partitioning, which splits a table’s columns or moves whole tables to different servers.

The point is to go beyond what one machine can do. Read replicas can spread reads, but every write still goes to one primary, and the whole data set must fit on it. With sharding, writes and storage are divided too. The cost is that the database no longer sees all the data in one place: a query, a join or a transaction that touches rows on different shards becomes a distributed operation.

Every sharded system has the same parts: a shard key, the column whose value decides where a row goes; a placement rule that maps key values to shards; and a router that sends each query to the right shards, either as a library in the application, a proxy in between, or the database itself.

The shard key is the decision that is hardest to change later, because changing it means moving almost every row. A good key has three properties:

• The most common queries filter on it, so they can go to one shard instead of all of them.
• It has many distinct values, so the data can be divided finely. A key with a few values, such as a country, can never be spread over more shards than it has values.
• Its values are used evenly, and do not all arrive at the same end of the range. A key that grows over time, such as a timestamp or an auto-increment ID, sends every new row to the same place under range placement.

No key is good for every query. In the simulator, sharding by user sends “one user’s orders” to one shard but has to ask every shard for a company’s orders; sharding by company does the reverse. Here is every combination on the simulator’s data with 4 shards, computed by the model:

Hash modulo N computes a hash of the key and takes the remainder after dividing by the number of shards. It spreads keys evenly and needs no metadata, but neighbouring keys end up on unrelated shards, so range queries must ask every shard, and changing N moves most of the data.

Hash slots hash the key into a fixed number of slots, far more than there are servers, and keep a small table of which server owns each slot. The simulator uses 64 slots; Redis Cluster uses 16,384 and computes a key’s slot as CRC16 of the key modulo 16,384. Adding a server means reassigning some slots to it and moving only the keys in those slots. Virtual nodes in Cassandra and the logical shards of systems such as Citus apply the same idea, and consistent hashing achieves it without a slot table.

Key ranges give each shard a contiguous range of key values. Range queries on the key touch only the shards whose ranges overlap, and ranges can be split when they grow. The router needs a table of range boundaries, and a key that grows over time sends every insert to the last range. Google’s Bigtable and Spanner, HBase and CockroachDB split data into ranges and split them automatically as they grow; MongoDB supports both ranged and hashed shard keys.

A lookup table (also called directory-based sharding) stores the shard of every key, or of every tenant, explicitly. It is the most flexible, since any key can be moved on its own, at the cost of a lookup on every request and a table that must be kept consistent and available.

Sooner or later a sharded database needs more shards, and the placement method decides how much data has to move. Sharding by user ID, going from 4 to 5 shards on the simulator’s data:

A hot shard gets far more data or traffic than the others, and since every shard is a separate server, the busiest one sets the limit for the whole system. The simulator shows the two usual causes.

Skewed keys. When the key is the company, the biggest company’s 28% of the orders all sit on one shard, whatever the placement method. Hashing spreads keys evenly, not load: it cannot divide one key. The same happens with a celebrity account or a best-selling product. The fixes are to give very large keys their own shards, to add a second component to the key (company plus user, for instance) so a big key is spread over several shards, or to cache the hottest reads.

Keys that grow over time. With key ranges on the creation time, storage is perfectly balanced, yet 100% of the last day’s writes land on one shard, because every new order has the latest timestamp. Auto-increment IDs behave the same way. Either hash such keys, or prefix them with something that spreads writes, and accept that time-range queries then have to ask several shards.

A query that filters on the shard key goes to one shard. Any other query is sent to every shard and the results are merged, which is called scatter-gather. It works, but every shard does work for every such query, and the query is as slow as the slowest shard, so it gets worse as shards are added. Sorting, limits and aggregates have to be finished by the router after it collects the partial results. Joins between tables only stay local if both tables are sharded by the same key, which is why multi-tenant systems shard every table by tenant.

Transactions that change rows on more than one shard need a distributed protocol such as two-phase commit, which adds round trips and blocks if the coordinator fails at the wrong moment. Many sharded systems avoid it: they keep each transaction within one shard by design, or use sagas, a series of local transactions with compensating steps. Databases built for it, such as Google Spanner and CockroachDB, run distributed transactions natively, paying for them in latency. Secondary indexes have the same problem: a global index on another column is itself sharded differently from the table and must be kept in sync, while a local index on each shard is easy to maintain but needs scatter-gather to use.

Sharding is hard to undo, so the usual advice is to exhaust the simpler options first:

• A bigger server. Single machines with hundreds of cores and terabytes of memory are available, and moving to one is a much smaller change than sharding.
• Read replicas for read-heavy work, and caching for repeated reads.
• Archiving or partitioning old data, so the working set stays small.
• Splitting by function: moving whole tables or services to their own databases, which is often an easier first step than splitting a table.

Shard when writes or data size truly outgrow one primary, or when customers need to be isolated from each other, and choose the shard key with the most frequent queries in mind.

• Vitess shards MySQL. Rows are mapped to a keyspace ID, usually by hashing a column, and each shard owns a range of keyspace IDs, so shards can be split by range.
• Citus shards PostgreSQL by hashing a distribution column into a fixed number of shards per table, 32 by default (citus.shard_count), which are then placed on worker nodes.
• MongoDB supports ranged and hashed shard keys and moves ranges of data between shards in the background with its balancer.
• Apache Cassandra hashes the partition key onto a token ring (Murmur3 by default), and each node owns several token ranges through virtual nodes.
• Amazon DynamoDB hashes the partition key to choose a partition and splits partitions as they grow.
• Redis Cluster maps each key to one of 16,384 hash slots; a hash tag in braces, as in {user1000}.following, makes related keys share a slot.
• Google Spanner and CockroachDB divide tables into key ranges that are split and moved automatically, and support transactions across them.

System design interviews raise sharding whenever the data or write rate is too large for one database: a URL shortener, a messaging service, a social feed, a multi-tenant SaaS product. Interviewers listen for three things: a justified shard key (what queries need, and what would make it hot), a placement method and how you would add capacity (hash slots or consistent hashing rather than modulo N), and what you give up (cross-shard queries, joins and transactions, and how you would handle the few that are needed).

Good follow-up answers mention hot keys and how to split them, monotonically increasing keys, and generating IDs without a central counter, for instance by embedding the shard number in the ID.