Sharding

Hash, range and consistent hashing: balance, hotspots and resharding cost.

On the roadmap:Intermediate · step 3: Sharding

Intermediateabout 10 to 15 min6 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

How a key picks its shard

Shards4

What the keys look like

Change the number of shards

Total data2.0 TB

Busiest shard vs. even share

1.01x

Keys that move (4 to 5)

80%

Data to move

1.6 TB

Hot shard

none

Hashing spreads keys evenly, but changing the shard count remaps about 80% of them: moving 1.6 TB of 2.0 TB. Consistent hashing fixes this.

Where 20,000 keys land (Hash (key mod N))

4,992

4,937

5,069

5,002

An even share would be 5,000 keys per shard. A red bar holds more than one and a half times that.

Where does one key live?

Keyis on shard 4 now, and stays put after the change.

In plain words

Sharding splits one big table across several machines, each holding a slice. A rule decides which machine owns each key: hash it, give each machine a range of keys, or place the machines on a ring.

Why it matters

One machine cannot hold or serve everything forever. Splitting the data lets you add machines, but the rule you choose decides two things that hurt in practice: whether some machines get far more traffic than others (a hotspot), and how much data has to move when you add or remove a machine.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

Cassandra and other Dynamo-style stores place keys on a ring of tokens, so adding a node moves only a slice of the data.
Range sharding keeps neighbouring keys together, which makes range scans cheap, but time-ordered keys all land on the newest range.
A single very popular key cannot be split by a hashing rule. Common fixes are to split the key into several by adding a suffix, to give it a shard of its own, or to cache it in the application.
Google's consistent hashing with bounded loads caps how far above average a server can go. Vimeo used it in HAProxy and reported a large drop in cache bandwidth.