Notes
The limit
Here's the wall. Two terabytes of data and fifty thousand writes a second. Adding followers doesn't help: every follower still stores two terabytes and applies every write. The leader is the bottleneck, and the leader is one machine. The only way out is to split the data so each machine holds and serves a part.
- data: 2 TB and growing;
- one disk, one RAM, one CPU
- writes: every replica takes
- every write; followers only
- help with reads
- answer: split the data
Vertical vs horizontal
Two ways to split. Vertical partitioning puts different tables on different servers: users here, orders there. Easy, and often the first move. But each table still lives on one machine, so it has a ceiling. Horizontal partitioning, sharding, splits the rows of one table across machines. Users A to H here, I to P there. Now every table can grow without limit.
- vertical: by table or column
- users on one server,
- orders on another
- simple, but each table still
- has a ceiling
- horizontal (sharding): by row
- users A–H here, I–P there
- every table can grow forever
Shard key
The whole design rests on one decision: the shard key. One column decides where a row lives. For a social app, user id. For a SaaS, tenant id. A router looks at the key in each request and sends it to the right shard. The rule: pick a key that is in almost every query, because a query without the key has to ask every shard.
How do you map keys to shards? Option one: by range. Shard one holds ids one to a million, shard two the next million. Range queries, like all orders from March, stay on one shard, and a full shard is easy to split. The catch: with increasing ids or dates, every new row lands on the last shard. One machine does all the writes. A hot spot.
- one column decides where
- a row lives: the shard key
- user_id for a social app
- tenant_id for a SaaS
- order_id for orders
- rule: the key should appear
- in almost every query
shard 1: user_id 1 – 1,000,000 shard 2: user_id 1,000,001 – 2,000,000 shard 3: user_id 2,000,001 – … + range queries stay on one shard + easy to split a full range - new users all land on the last shard: a hot spot
Hash sharding
Option two: hash the key. Shard equals hash of user id modulo the number of shards. Rows spread evenly and new ids go everywhere, so no hot spot. The costs: a range query now hits every shard, and if you change the number of shards, the modulo changes and almost every row moves. That second problem is what consistent hashing fixes, next episode.
shard = hash(user_id) % N + rows spread evenly + no hot spot from new ids - a range query hits every shard - changing N moves almost every row (next episode)
Routing
Where does the routing live? Three options. The application computes the shard itself, cheap but every client needs the logic. A routing tier in front of the shards, which is what Vitess, Citus and MongoDB's mongos do. Or a lookup table, key range to shard, in a small config store, which makes moving ranges around easy.
- 1. app computes it
- (hash in the client library)
- 2. a routing tier
- (Vitess, Citus, MongoDB mongos)
- 3. a lookup table
- key range → shard, in a small
- config store (ZooKeeper, etcd)
What breaks
Now the three things that break. One: reads that don't have the shard key. Find the user by email, when the key is user id. The router has to ask every shard and merge. Joins across shards don't exist at all. The usual fix is a small lookup table, email to user id, sharded by email, so it's two targeted queries instead of a scatter.
Two: transactions. A transfer between two users on two shards is two separate databases, and episode eighteen's begin and commit don't span them. You either accept two-phase commit, which is slow and fragile, use sagas, or, best of all, choose a shard key that keeps rows that change together on the same shard. That's why SaaS products shard by tenant.
Three: resharding. A shard fills up, or one celebrity makes it hot, and rows have to move while the system keeps serving. The trick that makes it bearable: start with many logical shards, say a thousand and twenty four, spread over a few machines. Then growing means moving whole logical shards to new machines, never re-splitting rows.
- WHERE email = … has no user_id
- → scatter to every shard, gather
- JOIN users ⋈ orders across shards
- → no joins; denormalise or
- do it in the app
- fix: secondary index table
- (email → user_id) on its own key
- a transfer between two users
- on two shards is two databases
- no single BEGIN … COMMIT
- options: two-phase commit (slow),
- sagas (episode 33), or choose a
- key that keeps related rows
- together (tenant_id)
- a shard fills up or runs hot
- → split it, or add shards
- moving rows while serving traffic:
- copy, then dual-write, then cut over
- plan for it on day one:
- start with many logical shards
- (e.g. 1024) on few machines
In practice
In practice you rarely write the routing yourself. Vitess shards MySQL, Citus shards Postgres, and MongoDB, Cassandra and DynamoDB are sharded by design. But every one of them makes you choose the key, and gets the same three problems. And the rule interviewers like to hear: don't shard until you must. Replication, caching and a bigger box come first.
managed sharding: Vitess (MySQL, YouTube), Citus (PG), MongoDB, Cassandra, DynamoDB, CockroachDB, Spanner you still choose the shard key rule: do not shard until you must; replication + caching first
In the interview
Say it like this. Shard by user id with hashing, so writes spread evenly. All of a user's data sits on one shard, so their reads and transactions stay local. Lookup by email goes through a small index table. I'd start with a thousand and twenty four logical shards so we can rebalance without resharding. Four sentences, and you've covered the key, the distribution, locality and growth.
- “Shard by user_id with hashing,
- so writes spread evenly. All of a
- user’s data sits on one shard, so
- their reads and transactions stay
- local. Email lookup goes through
- a small index table. I’d start with
- 1024 logical shards so we can
- rebalance without resharding.”