Sharding
The conceptWhy no single database could hold all of Instagram
Sharding splits one big dataset into pieces called shards and puts each shard on a different machine, so each machine holds and serves only its slice. A shard key, such as the user ID, decides which shard every row belongs to.
Say an app has 400 million users and one server handles 100 million. With 4 shards chosen by hash(user_id) mod 4, user 1,234 always lands on shard 2, and every read or write for that user goes only there.
This is different from replication: replicas are full copies of the same data, while shards hold different data. Real systems usually do both, so each shard has its own set of replicas.
What it’s forDecides which machine stores a given row, using its shard key.
shard = hash(key) mod N
- key
- the shard key of the row, e.g. a user ID or channel ID
- hash
- a hash function that spreads keys evenly over numbers
- N
- the number of shards, e.g. 4
- mod
- the remainder after dividing by N, giving a shard number from 0 to N−1
What it givesA shard number, so any server can work out where a row lives without asking anyone.
- Take hash(1234) = 1234 and N = 4.
- 1234 = 4 × 308 + 2, so the remainder is 2.
- User 1,234 lives on shard 2.