Sharding and consistent hashing

Replication copies the same data to several machines. It helps reads and survival, but every machine still holds everything. Two limits remain: the data may be too big for one machine, and the write rate may be too high for one machine to keep up. The remedy is sharding, also called horizontal partitioning: split the data into pieces, called shards, and put each on a different machine, so each holds only part.

For our link shortener, 30 billion links is about 15 TB. If one machine comfortably holds about 1 TB, we need roughly 15 shards. The 20,000 reads per second also spread out, about 1,300 per shard, which any machine handles easily.

Vertical partitioning splits by feature or by column: users on one database, links on another. It is easy and needs no routing logic, but one feature can still outgrow its machine, and joins across the split are lost. Horizontal partitioning, true sharding, splits the rows of one table across machines. It scales almost without limit, which is why it is the main tool at large scale.

You need a rule that maps a row to a shard. Three common ones:

• Range based: shard 1 holds keys A to F, shard 2 holds G to M, and so on. Range queries are cheap because neighbors live together. The danger is a hot spot: if keys are timestamps or sequential ids, all new writes land on the last shard.
• Hash based: apply a hash function to the key and use the result to choose a shard. Hashing spreads keys evenly and avoids hot ranges, but range queries now touch every shard.
• Directory based: a lookup table records which shard holds which key. It is the most flexible, since you can move data freely, but the directory is an extra hop and a potential single point of failure that must itself be replicated and cached.

The shard key is the field the rule uses, and it is the most consequential choice in the design. A good key has three properties.

• High cardinality: many distinct values, so data can be split finely.
• Even distribution: no value is far more common than the rest.
• Matches the access pattern: the most common queries name the key, so each goes to one shard.

For links, the short key itself is ideal: each lookup names it, and a good hash spreads it evenly. Sharding by user id would put a prolific user's links on one machine, and a viral link would create a hot key no matter how you split. Hot keys are usually handled by caching that key, or by copying it to several shards.

The simplest hash scheme is shard = hash(key) mod N. It works until N changes. Suppose we grow from 4 shards to 5. A key keeps its shard only if hash mod 4 equals hash mod 5. Looking at a repeating cycle of 20 values, that holds for just 4 of them, so about 80 percent of all keys move. Moving 80 percent of 15 TB is a massive transfer, and during it the caches go cold and the database is slammed.

Consistent hashing solves this. Imagine the hash space as a circle, a ring, from 0 up to a large number, then wrapping around. Hash each server to a point on the ring. To find the owner of a key, hash the key to a point and walk clockwise to the first server you meet.

When a server is added, it takes a point on the ring and takes over only the keys between its predecessor and itself. Every other key stays where it was. With N servers, adding one moves only about 1 in N keys on average. Going from 4 to 5 moves about 20 percent, not 80. Removing a server hands its keys to the next server clockwise, and nobody else is touched.

Plain consistent hashing has a flaw: with few servers, points land unevenly, so one server may own a huge arc and another a sliver. It also treats a strong machine and a weak one alike. The fix is virtual nodes: each physical server is hashed to many points, say 100 to 200, scattered around the ring. The load evens out by the law of large numbers, a bigger machine can be given more points, and when a server fails its load spreads across all the others instead of dumping on one neighbor.

The same ring gives replication cheaply: store each key on the owner and on the next distinct servers clockwise, for example three in total. Skip virtual nodes that belong to a server already chosen, so replicas live on different machines. Systems such as Dynamo and Cassandra are built on exactly this idea.

Sharding is powerful and expensive in complexity.

• Joins and transactions across shards are hard or slow. Design so most operations touch one shard.
• Resharding (adding or removing shards) needs careful data movement while serving traffic.
• Hot shards appear if the key or the data is skewed, even with a good hash.
• Referential integrity across shards is no longer enforced by the database.
• Operations multiply: backups, schema changes and monitoring per shard.

Delay it. First try a bigger machine, read replicas and a cache, because each is simpler. Shard when the data or the write rate truly exceeds one machine, and then choose the shard key as carefully as you would choose a database.