Sharding / Partitioning
Split a big database into smaller pieces (shards) and place them on different servers.
13.1 Why is it used?
- One server has limits on disk, RAM and CPU; billions of rows do not fit on one machine.
- Read replicas scale only reads; sharding is needed to scale writes.
- Each shard is small, so queries, indexes and backups are fast.
- If one shard goes down only some users are affected, not the whole site.
13.2 How it works
- Shard key: the column that decides which shard a row goes to (user_id, order_id, tenant_id).
- Range sharding: by key range: user_id 1-1M on shard A, 1M-2M on shard B. Range queries are easy, but there is a hotspot risk.
- Hash sharding: hash(key) % N or consistent hashing; data is spread evenly, range queries are hard.
- Geo / directory sharding: by region or a lookup table: India users on the Mumbai shard, US users on the Virginia shard.
- Vertical partitioning: put tables or columns in separate DBs (users DB, orders DB); this is different from horizontal sharding.
- Resharding: moving data when a shard fills up; easier with consistent hashing or virtual shards.
- Cross-shard query/join: fetching data from several shards is slow and complex; so choose the shard key carefully.
- Hotspot: too much traffic on one shard (a celebrity user); use a salt/random suffix in the key or special handling.
- 1.New message: chat_id = 8841
- 2.Shard router (Vitess / app): hash(8841) % 256 = vshard 137
- 3.Mapping table: vshard 128-143 -> server S9
- 4.16 physical DB servers (S1..S16), 16 vshards on each server
- 5.Read "last 50 messages of chat 8841": the query goes only to S9, the other 15 servers do not even know
The shard key keeps all messages of a chat on one shard, so there is no cross-shard JOIN
- 1.Range: Shard A user_id 1-1M, Shard B 1M-2M; range queries are easy (BETWEEN), but all new users land on Shard B -> hotspot risk
- 2.Hash: hash(key) % N, S1..S4 get 25% each; data is even, but range queries go to all shards
- 3.Geo / directory: Mumbai shard for India users, Virginia shard for US users; lower latency + data stays within local laws
- 4.Resharding 16 -> 32 servers is easy with virtual shards: of S9's vshards 128-143, vshards 136-143 move to the new S25; only half the vshards move, not all the data
- 5.Mistake: shard key = timestamp -> all of today's writes go to S1 (hotspot) while the other shards stay empty
13.3 Tools
| Tool | Type | How it is used |
|---|---|---|
| Vitess | MySQL sharding layer | Sharding, routing and resharding on top of MySQL. Built at YouTube; Slack and GitHub also use it. |
| Citus | PostgreSQL extension | Makes PostgreSQL distributed: tables are split into shards and queries run in parallel. Available in Azure Cosmos DB for PostgreSQL. |
| MongoDB sharding | Built-in sharding | A mongos router + config servers; hashed or ranged shard key. |
| Amazon DynamoDB | Managed auto-partitioning | Data goes into partitions by the hash of the partition key and splits automatically. |
| Apache Cassandra | Built-in partitioning | The Murmur3 hash of the partition key is placed on the token ring. |
| Google Spanner / CockroachDB / YugabyteDB | Distributed SQL | SQL and ACID transactions with automatic range sharding. |
13.4 Comparison: Vitess vs Citus vs MongoDB Sharding vs DynamoDB
| Point | Vitess (MySQL) | Citus (PostgreSQL) | MongoDB Sharding | DynamoDB |
|---|---|---|---|---|
| Base | MySQL | PostgreSQL | MongoDB | AWS managed NoSQL |
| Sharding type | Hash/range via VSchema vindex | Hash distribution column | Hashed or ranged shard key | Hash of the partition key, automatic |
| Resharding | Online resharding tools | Shard rebalancer | The balancer moves chunks | Fully automatic |
| Cross-shard queries | Supported, but costly | Parallel distributed queries, good | Scatter-gather via mongos | No, only key-based / scan |
| Ops effort | High | Medium | Medium | Very low (serverless) |
| Best for | Scaling large MySQL apps | Multi-tenant SaaS, analytics | Flexible documents at scale | Key-value at any scale on AWS |
13.5 When to choose which
- First try vertical scaling, read replicas and caching: sharding is the last option because it adds complexity.
- Vitess: when you already have MySQL and want to shard without rewriting the app.
- Citus: when you have PostgreSQL and need multi-tenant (tenant_id) or real-time analytics.
- MongoDB/DynamoDB/Cassandra: when you want horizontal scale from the start and the access pattern is key-based.
- Shard key: it should have high cardinality, even distribution and be present in most queries.
13.6 Real-world example
Messages of a WhatsApp-like chat app (an illustrative scenario)
- Billions of messages arrive every day: keeping them in one DB is impossible.
- Chose shard key = chat_id so that all messages of a chat are on one shard.
- hash(chat_id) creates 256 virtual shards, mapped onto 16 physical servers.
- The query "open chat, show last 50 messages" goes to only one shard: fast.
- When traffic grew, servers went from 16 to 32; only some virtual shards moved, not all the data.
- If the shard key were a timestamp, all of today's writes would go to one shard: a hotspot. So do not make time the key.
13.7 Interview tips
- A wrong shard key (like created_at or country) is a mistake: hotspots and uneven data.
- Using hash % N is a mistake: the moment N changes almost all data has to move; use consistent hashing.
- Not planning for cross-shard joins and transactions is a mistake.
- Interview tip: replication = copies (availability/reads), sharding = pieces (writes/storage); explain the difference between the two.