Database Sharding & Partitioning

Consistent hashing, in the previous chapter, is a general technique for dividing keys among machines. Sharding is what you call it when you apply that idea to a database: the data is split into slices, each slice lives on its own independent database instance, and each instance is responsible for only its slice. It is the main way to get past the limit of what one machine can store and write.

A city library has outgrown its building. Rather than build an impossibly large one, it opens several branches, and every book has to live in exactly one of them. The question is the rule for deciding where: by the first letter of the author's name, by a number worked out from the book's ID, or by looking each book up in a master catalog that says which branch holds it. Each rule works, each has awkward cases, and moving books between branches later is expensive.

• -The branches are the shards, each holding its own slice of the books.
• -Sorting by the author's first letter is range-based sharding.
• -A number worked out from the book's ID is hash-based sharding.
• -The master catalog is directory-based sharding.
• -The desk that points a reader to the right branch is the shard router.

Sharding is usually the last resort, not the first move. Try the cheaper fixes first, and shard only when the numbers say a single primary database cannot cope. A rough gut check:

• -Hash-based: shard = `hash(key)` mod number of shards. With four shards and user ids 1001 to 1008 using id mod 4, the ids land on shards 1, 2, 3, 0, 1, 2, 3, 0, an even spread. Its weakness is range queries (neighboring ids are scattered) and changing the number of shards: as the previous chapter showed, going from 3 shards to 4 with a plain modulo moves about three keys in four.
• -Range-based: each shard owns a contiguous range, such as users A to F on shard 1. Range queries are efficient, since neighboring keys sit together. The weakness is hotspots: if the key is a timestamp or an ever-increasing id, all new writes go to the last shard while the rest sit idle.
• -Directory-based: a lookup table records which shard holds each key. It is the most flexible, because you can move any key by editing the table, but the directory is itself a critical component that every request depends on, so it must be fast, replicated and cached.

In practice, systems that need to add shards without moving most of their data combine hashing with the ring technique from the previous chapter, which keeps most keys where they are when a shard is added.

The shard key, the field the placement rule is applied to, is the most important decision, because it is very hard to change later. A good key has many distinct values, spreads load evenly, and matches the way you query. Take an orders table. If you shard by user id, all of one user's orders sit on one shard, so the common query all orders for user 42 touches a single shard. If you shard by order id, the data spreads very evenly, but that same query must ask every shard and merge the answers, which is called scatter-gather and gets slower as shards are added. A celebrity account can still make one shard a hotspot even with a good key, and the usual remedy is to split that one key further.

The diagram shows the shape: a router sits in front, works out which shard owns the key, and sends the request there.

• -Cross-shard queries: a join between data on two shards is no longer a simple database join, and often has to be done in the application.
• -Cross-shard transactions: keeping a change that touches two shards all-or-nothing is much harder than inside one database, as a later module on distributed transactions explains.
• -Resharding: moving data between shards while the system is live is slow and delicate.
• -Operational weight: many databases to back up, monitor, upgrade and keep balanced.

The Wiki card below goes further into partitioning strategies and what to watch out for: