Sharding, replication and consistent hashing
We'll cover the following
| Sharding | Replication | |
|---|---|---|
| What | Split different data across machines | Same data on several machines |
| Scales | Storage and writes | Reads, and survives failures |
| In practice | Real systems do both: each shard has a primary plus replicas |
Shards are sized by data volume and load (say 500 GB to 1 TB each), not by record count. 1B small records might need only a handful. How you shard depends on access patterns; watch for hot spots such as the celebrity problem.
Why plain hash % N is bad
The server is computed from N, so changing N changes almost every answer. Going from 4 to 5 servers, only ~20% of keys stay put and ~80% move. Caches go cold and the DB is flooded.
Consistent hashing
- Picture a ring of hash values.
- Place each server at a point on the ring (hash its name).
- Place each key on the ring. It belongs to the next server clockwise.
- Add a server: it takes only the slice between itself and the previous server. ~80% of keys stay, ~20% move (the mirror image of hash % N).
- A server dies: only its keys move to the next server.
- Virtual nodes: each physical server gets many points (100+) so one server does not own a huge slice by bad luck.
- Replicas: each key lives on its owner and the next 2 nodes clockwise (replication factor 3), so a dead node loses no data.
- Applies to nodes that own data or cache (DB shards, Redis/memcached nodes, sticky routing), not stateless API servers.
- With a cache, a dead node only costs some entries, which refill from the DB: ~1/N affected instead of everything.
- Used by DynamoDB, Cassandra, memcached clients, CDNs.
Summary: say it in the interview
- "Consistent hashing, so adding or removing a node only moves about 1/N of the keys."