Lesson 6 of 15 Data and Storage

Sharding and Consistent Hashing

Split data across machines with range, hash and directory sharding, pick a shard key, avoid hot spots, and rebalance cheaply with consistent hashing.

40-50 min intermediate 0/15 lessons done
Course contents Lesson 6 of 15 · 0 done
On this page (10 sections)
  1. What you will learn
  2. When one database isn’t enough
  3. Three ways to shard
  4. Choosing a shard key
  5. The problem with hash % N
  6. Consistent hashing
  7. Rebalancing in practice
  8. Key takeaways
  9. Exercises
  10. Quiz

What you will learn

  • When you need sharding and what it costs.
  • Range, hash and directory-based sharding.
  • How to choose a shard key and avoid hot spots.
  • Consistent hashing with virtual nodes, with a runnable demo.

When one database isn’t enough

Replication (lesson 5) copies all data to every node, so it scales reads but not data size or write throughput. When the data no longer fits on one machine, or one leader can’t absorb the writes, you shard (partition): each node holds a subset of the data.

Sharding costs: queries that span shards (joins, global sorting, aggregates) become expensive; transactions across shards need extra machinery; and rebalancing data while live is hard. Exhaust simpler options first: a bigger machine, read replicas, caching, archiving old data.

Three ways to shard

Range sharding. Keys a–f on shard 1, g–m on shard 2, and so on (or by date ranges). Range queries are efficient. Risk: hot spots when traffic concentrates in one range (all of today’s writes hitting the “today” shard).

Hash sharding. shard = hash(key) % N. Spreads keys evenly. Range queries need to ask every shard. And the % N part has a nasty problem, shown below.

Directory sharding. A lookup service maps each key (or key range) to a shard. Maximum flexibility (move any tenant anywhere), at the cost of an extra lookup and a critical service to keep available.

Choosing a shard key

The shard key decides everything. Good keys:

  • have high cardinality (many distinct values),
  • spread traffic, not just data, evenly,
  • keep data that’s queried together on the same shard.

For a chat app, sharding messages by conversation_id keeps each conversation’s history on one shard, so “load the last 50 messages” hits one machine. Sharding by message_id would spread a conversation everywhere.

A celebrity key (one user with 100M followers) can still overload one shard. Split it further: append a suffix (user123#0..9) to spread its rows across shards and merge on read.

The problem with hash % N

Add one server and almost every key’s hash % N changes, so almost all data must move. Consistent hashing fixes this.

Consistent hashing

Imagine the hash space as a ring. Each server is placed at points on the ring (by hashing its name); each key goes to the first server clockwise from the key’s hash. Adding a server only takes over keys between it and its predecessor; removing one only hands its keys to its successor. On average just 1/N of keys move.

With one point per server the arcs are uneven, so each server gets many virtual nodes (here 100 points), which evens out the load and lets bigger machines take more points.

"""Consistent hashing ring with virtual nodes."""
import bisect
import hashlib


def h(key: str) -> int:
    return int.from_bytes(hashlib.md5(key.encode()).digest()[:8], "big")


class HashRing:
    def __init__(self, nodes=(), vnodes=100):
        self.vnodes = vnodes
        self.ring = []  # sorted list of (hash, node)
        for node in nodes:
            self.add(node)

    def add(self, node: str):
        for i in range(self.vnodes):
            bisect.insort(self.ring, (h(f"{node}#{i}"), node))

    def remove(self, node: str):
        self.ring = [(hv, n) for hv, n in self.ring if n != node]

    def node_for(self, key: str) -> str:
        hv = h(key)
        i = bisect.bisect(self.ring, (hv, chr(0x10FFFF)))  # first point clockwise
        return self.ring[i % len(self.ring)][1]


def modulo_node(key: str, nodes):
    return nodes[h(key) % len(nodes)]


if __name__ == "__main__":
    keys = [f"user:{i}" for i in range(10_000)]

    before = {k: modulo_node(k, ["A", "B", "C"]) for k in keys}
    after = {k: modulo_node(k, ["A", "B", "C", "D"]) for k in keys}
    moved = sum(before[k] != after[k] for k in keys)
    print(f"hash % N: adding a 4th server moves {moved / len(keys):.0%} of keys")

    ring = HashRing(["A", "B", "C"])
    before = {k: ring.node_for(k) for k in keys}
    ring.add("D")
    after = {k: ring.node_for(k) for k in keys}
    moved = sum(before[k] != after[k] for k in keys)
    print(f"consistent hashing: adding a 4th server moves {moved / len(keys):.0%} of keys")
    load = {n: sum(1 for k in keys if after[k] == n) for n in "ABCD"}
    print("keys per server:", load)
hash % N: adding a 4th server moves 75% of keys
consistent hashing: adding a 4th server moves 24% of keys
keys per server: {'A': 2577, 'B': 2466, 'C': 2509, 'D': 2448}

Exactly the theory: moving from 3 to 4 servers with modulo hashing moves about 3/4 of keys; with consistent hashing it moves about 1/4 (the new server’s fair share), and the load stays balanced.

Consistent hashing is used in DynamoDB-style stores and Cassandra, in distributed caches (client-side sharding across Memcached nodes), and in load balancers that want cache locality.

Rebalancing in practice

Many databases avoid moving individual keys by creating many more partitions than nodes (say 1,024 partitions on 8 nodes) and moving whole partitions when nodes join. Others split a partition when it grows too big. Either way, move data in the background, throttle it, and keep serving traffic.

Key takeaways

  • Shard when data size or write throughput outgrows one leader; replication alone won’t help.
  • Range sharding suits range queries but risks hot spots; hash sharding spreads load; directories add flexibility.
  • Choose a high-cardinality shard key that keeps related data together and spreads traffic.
  • Consistent hashing with virtual nodes moves only ~1/N of keys when servers change.

Exercises

  1. Change vnodes to 1, 10 and 500 and record how even the per-server load is.
  2. Pick shard keys for: an e-commerce orders table, a multi-tenant SaaS app, and a metrics time-series store. Justify each.
  3. Extend HashRing so a node can have a weight (a server twice as big gets twice the virtual nodes).

Quiz

  1. Why doesn’t replication solve “the data is too big for one machine”?
  2. Roughly what fraction of keys move when you add a 5th server with consistent hashing?
  3. What are virtual nodes for?
Show answers
  1. Every replica stores a full copy, so each still needs to hold all the data.
  2. About 1/5, the new server’s share.
  3. They spread each server across many points on the ring so load is even, and allow weighting servers by capacity.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).