Sharding

Sometimes the data or the writes outgrow one machine.

Why shard

Sharding splits the rows of a database across several machines. Each machine, called a shard, holds only a part of the data and takes only the writes for that part. If a shard dies, its part is gone until it comes back, so each shard usually has its own replicas.

The shard key

The shard key is the column that decides which shard a row lives on, like user_id. A query that names the key goes to one shard. A query without it must ask every shard and merge the answers, which is slow. Joins across shards are hard too. So pick a key that most queries use.

Range or hash

Range partitioning gives each shard a span of keys, like names A to H and I to P. Ranges are easy to read, but some spans get far more rows. Hash partitioning turns the key into a number that looks random, called a hash. The shard is the hash mod (the remainder after dividing by) the number of shards. A hash of 27 with 4 shards goes to shard 3. Keys spread evenly, but a range is scattered over every shard.

Hot spots

A hot spot is one shard with far more load than the rest. A celebrity user can make one key very busy. A time-ordered key split by range sends every new write to the newest shard. Hashing fixes the second case, but not the first: one hot key still lives on one shard.

Adding shards

With hash mod N, going from 4 to 5 shards moves about 80% of the keys. Consistent hashing puts shards and keys on a ring. Each key belongs to the next shard clockwise, so a new shard only takes keys from one neighbor. If the shards are spread evenly, adding a fifth shard moves only about a fifth of the keys.

Remember

• Sharding splits data; replication copies it.
• Queries should include the shard key.
• Range is good for ranges; hash spreads evenly.
• Consistent hashing moves few keys when shards change.