Sharding

When one database grows too big — or too busy — for a single machine, you shard it: split the data into pieces, each shard living on its own server holding a subset of the records. The whole game is deciding *which record lives on which shard* via a partition key (say, user ID), in a way that spreads load evenly and doesn't force a massive reshuffle every time you add a server.

Three ways to place records

1. 1Hash sharding — shard = hash(key) % N. Spreads records evenly and avoids hotspots, but range queries ("all users A–C") must hit every shard, and changing N remaps almost everything.
2. 2Range sharding — assign contiguous key ranges to shards (users A–H → shard 1, I–P → shard 2...). Range scans stay on one shard, but uneven key distribution creates hot shards.
3. 3Directory sharding — a lookup table maps each key (or key range) to its shard. Maximum flexibility — you can move any key anywhere — at the cost of a directory that itself must be fast and highly available.

The resharding problem

The naive scheme hash(key) % N has a fatal flaw: change N (add or remove a server) and nearly every key's % N result changes, so almost the whole dataset must move at once — an outage-grade migration. This is the pain that consistent hashing exists to solve.

Consistent hashing

Consistent hashing places both servers and records on a ring (positions 0 to the max hash value, wrapping around). A record belongs to the next server clockwise from its hash position. Add a server and it drops onto one spot on the ring, taking over only the arc between it and the previous server — about 1/n of the keys move, all from a single neighbour, instead of nearly all of them.

hash ring (add S4 between S1 and S2):

   before:            after:
      S1                  S1
    /    \              /    \
  S3      S2   ==>    S3      S4  <- new
    \    /              \    /  \
      -                   -     S2

only keys in the arc [S1 -> S4] move to S4.
S2, S3 and everyone else keep their keys.