Database Sharding and Consistent Hashing Explained

Replicas help reads, but eventually writes or total data outgrow one server. Sharding splits data across several databases, so that each holds only a part.

Users A-H --> Shard 1
Users I-P --> Shard 2
Users Q-Z --> Shard 3

Sharding is powerful, but costly, so try a bigger server, indexes, caching and read replicas first.

Shard key#

The shard key decides where each row lives, and it is the most important choice.

A good key has many values, spreads load evenly, and matches your main queries.

Hashing spreads data evenly:

import hashlib
from collections import Counter


def shard_for(key, shards):
    h = int(hashlib.md5(key.encode()).hexdigest(), 16)
    return h % shards


counts = Counter(shard_for(f"user{i}", 4) for i in range(100_000))
for shard in sorted(counts):
    print(f"Shard {shard}: {counts[shard]:,} users")

Shard 0: 24,884 users
Shard 1: 24,932 users
Shard 2: 25,150 users
Shard 3: 25,034 users

The problems sharding brings#

• Joins across shards are slow or impossible, so keep related data together, or denormalise.
• Transactions across shards are hard.
• Hot shards: one famous user can overload a shard, known as the celebrity problem.
• Unique IDs: auto-increment does not work across shards, so use something like a Snowflake ID or UUID.
• Operations: backups and schema changes must happen on every shard.

The rebalancing problem#

With hash % N, adding one server moves nearly all the keys:

keys = [f"user{i}" for i in range(100_000)]
moved = sum(shard_for(k, 4) != shard_for(k, 5) for k in keys)
print(f"Going from 4 to 5 shards moves {moved / len(keys):.0%} of keys")

Going from 4 to 5 shards moves 80% of keys

For a cache, that means a sudden flood of misses. For a database, it means copying most of your data.

Consistent hashing#

Consistent hashing puts servers and keys on a ring. A key belongs to the next server clockwise, so when a server is added, only the keys in its section move.

           server A
          /        \
    key 1            key 2 --> goes to server B
         \          /
          server B

To even out the load, each server appears at many points on the ring, called virtual nodes:

import bisect


def position(text):
    return int(hashlib.md5(text.encode()).hexdigest(), 16)


class Ring:
    def __init__(self, servers, vnodes=200):
        self.points = sorted((position(f"{s}#{i}"), s) for s in servers for i in range(vnodes))
        self.keys = [p for p, _ in self.points]

    def lookup(self, key):
        i = bisect.bisect(self.keys, position(key)) % len(self.points)
        return self.points[i][1]


before = Ring(["s1", "s2", "s3", "s4"])
after = Ring(["s1", "s2", "s3", "s4", "s5"])

moved = sum(before.lookup(k) != after.lookup(k) for k in keys)
print(f"Adding one server moves {moved / len(keys):.0%} of keys")

load = Counter(before.lookup(k) for k in keys)
print({s: f"{n / len(keys):.0%}" for s, n in sorted(load.items())})

Adding one server moves 17% of keys
{'s1': '26%', 's2': '26%', 's3': '25%', 's4': '24%'}

Only about a fifth of keys moved, rather than four-fifths, and the load stays fairly even. Cassandra, DynamoDB-style systems and many distributed caches use this idea.

Virtual nodes matter#

for v in (1, 10, 200):
    ring = Ring(["s1", "s2", "s3", "s4"], vnodes=v)
    load = Counter(ring.lookup(k) for k in keys[:20_000])
    print(f"{v:>3} vnodes: busiest server has {max(load.values()) / 20_000:.0%} of keys")

  1 vnodes: busiest server has 30% of keys
 10 vnodes: busiest server has 37% of keys
200 vnodes: busiest server has 26% of keys

With four servers, a perfect share is 25%. A few points on the ring give an uneven, unpredictable split, and many points bring it close to even.

Ready-made options#

You rarely need to build this. Citus (for PostgreSQL) and Vitess (for MySQL) add sharding, and databases such as CockroachDB, Spanner, Cassandra and DynamoDB do it for you.

Common mistakes#

Practice#

import math

usable = 2 * (1 - 0.5)
print(math.ceil(12 / usable))

12

Key takeaway#

Next: Message Queues and Async Work.