In Database Replication we made many copies of the data so that more machines could serve reads. But every copy still holds all the data and applies every write. What happens when the data is 40 TB, or when writes alone overwhelm one machine? Copies cannot help. We have to split the data so that each machine owns only a part of it.
That splitting is called partitioning, and when the parts live on different servers it is usually called sharding. It is how systems like Instagram, Uber, Discord and every large SaaS product store their data, and it is a favourite system design interview topic because the hard part is not the idea but the choice of shard key.
Sharding (horizontal partitioning across servers) splits one large dataset into smaller, independent pieces called shards, each stored on a different database server, so that storage and write load are spread across many machines.
Partitioning vs Sharding: Terminology
Partitioning is the general idea of dividing a table into parts. It can happen inside one database server (PostgreSQL and MySQL both support declarative table partitioning by range, list or hash) to make queries and maintenance faster.
Sharding means the parts are placed on different servers. Each shard is a full database instance holding a subset of the rows.
Different databases use different names for the same thing: a shard in MongoDB and Elasticsearch, a region in HBase, a tablet in Bigtable, a vnode or token range in Cassandra, a partition in DynamoDB and Kafka.
Vertical vs Horizontal Partitioning
users table: id | name | email | city | bio | profile_photo
Vertical partitioning (split COLUMNS) Horizontal partitioning (split ROWS)
+----------------------+ +-------------+ +------------------------------+
| id | name | email | | | id | bio | | | rows with id 1 – 1,000,000 | shard 0
| city | | photo | +------------------------------+
+----------------------+ +-------------+ | rows with id 1,000,001 – 2M | shard 1
hot, small columns large, rarely +------------------------------+
read columns | ... |
Vertical partitioning moves some columns (often large or rarely used ones) to another table or store. Each piece keeps the primary key.
Horizontal partitioning keeps every column but splits the rows. When spread over servers, this is sharding, and it is the focus of this chapter.
Functional partitioning (a close cousin): put different features in different databases, such as users in one database, payments in another. This often comes naturally with Monolith vs Microservices designs.
Why Shard?
Data too large for one machine's disk, or too large to back up and restore in reasonable time.
Write throughput beyond what one primary can handle.
Smaller indexes per shard fit in memory, so queries get faster.
Fault isolation: if one shard is down, only the users on that shard are affected.
Data locality: keep Indian users' data in an Indian region (useful for latency and for data-residency laws).
But sharding is a one-way door that adds lots of complexity. Exhaust simpler options first: query and index tuning, caching (see Caching), read replicas, a bigger machine, and archiving old data.
Choosing a Sharding Strategy
The shard key (partition key) is the column used to decide which shard a row lives on. Common strategies:
1. Range-Based Sharding
Each shard owns a continuous range of key values.
user_id 1 – 250,000 → Shard 0
user_id 250,001 – 500,000 → Shard 1
user_id 500,001 – 750,000 → Shard 2
user_id 750,001 – 1,000,000 → Shard 3
Pro: range queries are efficient (
WHERE user_id BETWEEN ...or "orders from last week" hits only a few shards).Con: uneven load. If the key increases over time (auto-increment ids, timestamps), all new writes go to the last shard, a hotspot.
2. Hash-Based Sharding
Apply a hash function to the key and use the result to pick a shard, in the simplest form shard = hash(key) mod N.
Pro: spreads keys (and usually load) evenly, even for sequential keys.
Con: range queries must ask every shard, because neighbouring keys are scattered. And with plain
mod N, changing N moves most keys (we will measure this).
3. Directory (Lookup) Based Sharding
A separate lookup service stores a mapping from key (or key group) to shard.
+-----------+-------+
| tenant | shard | App ─► Directory ─► "tenant acme is on shard 7"
+-----------+-------+ │
| acme | 7 | ▼
| globex | 2 | Shard 7
+-----------+-------+
Pro: total flexibility: move a single big customer to its own shard just by updating the directory.
Con: the directory is an extra lookup on every request and a critical component that must be highly available and cached.
4. Geographic Sharding
Shard by region or country (all India data in the Mumbai cluster). Good for latency and data-residency requirements; risky if one region is much bigger than others.
Worked Example: Hash vs Range in Code
The script below creates 100,000 users, places them with hash sharding and range sharding, and measures three things: balance, hotspots and range-query cost. Note that we use MD5 instead of Python's built-in hash(), because hash() for strings is randomised per process: a server restart would send keys to different shards!
import hashlib
from collections import Counter
def h(key: str) -> int:
# stable hash (Python's built-in hash() is randomised per process)
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def hash_shard(key, n):
return h(key) % n
def range_shard(user_id):
# shard 0: 1-250000, shard 1: 250001-500000, ...
return (user_id - 1) // 250_000
users = [f"user:{i}" for i in range(1, 100_001)]
print("--- hash sharding, 4 shards ---")
print(sorted(Counter(hash_shard(u, 4) for u in users).items()))
moved = sum(hash_shard(u, 4) != hash_shard(u, 5) for u in users)
print(f"4 -> 5 shards: {moved} of {len(users)} keys move ({moved/len(users):.1%})")
print("--- range sharding, new sign-ups hit the last shard ---")
new_signups = range(900_001, 1_000_001) # the latest 100,000 users
print(sorted(Counter(range_shard(u) for u in new_signups).items()))
print("--- range query cost ---")
q = range(240_000, 260_001) # user_id BETWEEN 240000 AND 260000
print("range sharding touches shards:", sorted({range_shard(u) for u in q}))
print("hash sharding touches shards:", sorted({hash_shard(f'user:{u}', 4) for u in q}))
Output:
--- hash sharding, 4 shards ---
[(0, 24902), (1, 25161), (2, 24770), (3, 25167)]
4 -> 5 shards: 80087 of 100000 keys move (80.1%)
--- range sharding, new sign-ups hit the last shard ---
[(3, 100000)]
--- range query cost ---
range sharding touches shards: [0, 1]
hash sharding touches shards: [0, 1, 2, 3]
Reading the results:
Hash sharding is balanced: each shard got about 25,000 users.
Range sharding creates a hotspot: all 100,000 newest sign-ups (and their activity) landed on shard 3 while shards 0–2 sat idle.
Range sharding wins for range queries: the
BETWEENquery touched 2 shards instead of all 4.Plain
mod Nis terrible for growth: going from 4 to 5 shards moved 80% of keys. A key stays put only whenh mod 4 = h mod 5, which happens for 4 out of every 20 hash values, so 1 − 4/20 = 80% move, matching the measurement. Moving 80% of a 40 TB database is a huge, risky migration. This exact problem is what Consistent Hashing (next chapter) solves.
Choosing a Good Shard Key
A good shard key has:
High cardinality: many distinct values. Sharding by
countrygives at most ~200 shards and one giant India shard.Even frequency: no single value dominates traffic.
Non-monotonic writes (or hashed): avoid raw timestamps and auto-increment ids as range keys.
Query alignment: the most frequent queries include the shard key, so they go to one shard.
| System | Good shard key | Why |
|---|---|---|
| Chat app messages | conversation_id | "Load this chat's messages" hits one shard; messages stay ordered within it |
| Multi-tenant SaaS | tenant_id | Each customer's queries stay on one shard; easy per-customer isolation |
| E-commerce orders | user_id (hashed) | "My orders" is the hottest query; hashing spreads users evenly |
| IoT sensor readings | (device_id, day) | Spreads devices, and bounds how big one partition grows |
The Celebrity (Hot Key) Problem
Even a perfect hash cannot fix one key that is extremely hot. If a cricket star with hundreds of millions of followers posts, every like and comment for that post hits the shard that owns it.
Techniques:
Key salting / splitting: store the hot key's counter as
post123#0…post123#9on different shards; writes pick a random suffix, and reads sum all ten.Caching hot reads in front of the shard.
Dedicated shards for known heavy tenants (directory-based sharding makes this easy).
What Becomes Hard After Sharding
Cross-Shard Queries
A query without the shard key must be sent to every shard and the results merged (scatter-gather). Its latency is set by the slowest shard, and it puts load on all of them.
"Top 10 products by sales today" (not keyed by shard)
Query router
/ | | \ each shard returns its own top 10
S0 S1 S2 S3
\ | | /
merge 40 rows → final top 10
Joins
Joining tables that live on different shards is expensive. Common fixes: shard related tables by the same key (orders and order_items both by user_id, so they are co-located), replicate small reference tables (countries, categories) to every shard, or denormalise.
Transactions Across Shards
A transaction touching two shards needs a distributed protocol such as two-phase commit (slow and blocking), or an application-level saga (a sequence of local transactions with compensating actions). Good shard key design keeps most transactions on a single shard.
Secondary Indexes
Local index (document-partitioned): each shard indexes only its own rows. Writes are cheap, but a query by the indexed column is scatter-gather.
Global index (term-partitioned): the index itself is sharded by the indexed value. Reads go to one place, but a single write may update index entries on other shards, usually asynchronously. DynamoDB's Global Secondary Indexes work this way and are eventually consistent.
Unique IDs
Auto-increment ids no longer work across shards (two shards would both create id 1001). Use UUIDs (UUIDv7 is time-ordered, which is friendlier to indexes), or a Snowflake-style id that combines a timestamp, machine id and sequence number.
Rebalancing: Adding Shards Later
Data grows, so shards must be added and data moved. Good rebalancing moves as little data as possible and keeps the system online.
| Approach | How it works | Used by |
|---|---|---|
| hash mod N | Change N, recompute everything | Avoid: ~80% moved in our example |
| Fixed number of logical partitions | Create many more partitions than servers up front (e.g. 1,024); a new server takes over whole partitions from others. Key → partition never changes, only partition → server. | Redis Cluster (16,384 hash slots), Elasticsearch (primary shard count chosen when the index is created), Kafka partitions |
| Dynamic splitting | When a range grows too big, split it in two and possibly move half | HBase regions, Bigtable tablets, DynamoDB partitions, CockroachDB and TiDB ranges |
| Consistent hashing | Keys and servers placed on a hash ring; adding a server moves only ~1/N of keys | Cassandra, Amazon Dynamo, Riak (next chapter) |
Fixed logical partitions: 12 partitions, servers 3 → 4
Before: S1: p0 p1 p2 p3 S2: p4 p5 p6 p7 S3: p8 p9 p10 p11
After: S1: p0 p1 p2 S2: p4 p5 p6 S3: p8 p9 p10 S4: p3 p7 p11
Only 3 of 12 partitions (25%) moved, and no key changed partition.
Back-of-the-Envelope: How Many Shards?
An e-commerce platform stores order history: 20 million orders/day, about 1 KB per order including indexes, kept for 5 years, 3 copies of each shard for availability. We want each shard to stay at or under 4 TB.
orders_per_day = 20_000_000
row_bytes = 1_000 # row + indexes, rounded
years = 5
replicas = 3
total = orders_per_day * row_bytes * 365 * years
print(f"raw data: {total/1e12:.1f} TB")
per_shard = 4e12 # keep each shard <= 4 TB
shards = -(-total // per_shard)
print(f"shards needed at 4 TB each: {int(shards)}")
print(f"with {replicas} copies: {int(shards*replicas)} database servers, {total*replicas/1e12:.1f} TB stored")
peak_writes = orders_per_day / 86_400 * 3 # 3x peak factor
print(f"avg writes/s: {orders_per_day/86_400:.0f}, peak: {peak_writes:.0f}, per shard at peak: {peak_writes/shards:.0f}")
Output:
raw data: 36.5 TB
shards needed at 4 TB each: 10
with 3 copies: 30 database servers, 109.5 TB stored
avg writes/s: 231, peak: 694, per shard at peak: 69
Interesting lesson: the write rate (about 700/s at peak) is easily handled by a single good database server. Here we shard because of data size, not write load. Another valid design is to keep recent orders in the main database and move old ones to cheaper archive storage, which might avoid sharding altogether. Saying this in an interview shows good judgement.
Sharding in Real Databases
MongoDB: built-in sharding with ranged, hashed and zone sharding; a
mongosrouter sends queries to the right shard; the shard key can be refined or the collection resharded in recent versions.Cassandra / ScyllaDB: the partition key is hashed (Murmur3 by default in Cassandra) to a token on a ring.
DynamoDB: the partition key is hashed; partitions split automatically as data and traffic grow.
MySQL: sharded with a middleware layer such as Vitess (originally built at YouTube).
PostgreSQL: Citus extension for distributed tables; or application-level sharding.
Distributed SQL (Spanner, CockroachDB, TiDB, YugabyteDB): automatic range splitting with SQL and distributed transactions on top.
In practice, sharding and replication are combined: each shard is itself a small replica set.
Router / query layer
/ | \
Shard 0 Shard 1 Shard 2
[L][R][R] [L][R][R] [L][R][R] L = leader, R = replica
Common Mistakes
Sharding too early. It complicates every query, migration and transaction. Prove you need it with numbers.
Low-cardinality shard keys such as country, status or gender.
Monotonic range keys (timestamps, auto-increment ids) that send all writes to one shard.
Using
hash(key) mod Nand then needing to change N.Using a non-stable hash (like Python's built-in
hash()on strings) to route data.Choosing a shard key that your main queries do not include, turning every request into scatter-gather.
Confusing sharding with replication. Sharding splits data; replication copies it.
Interview Questions
1. What is the difference between partitioning, sharding and replication?
Partitioning divides data into parts (possibly within one server). Sharding is partitioning where the parts live on different servers. Replication keeps copies of the same data on multiple servers. Large systems shard for scale and replicate each shard for availability.
2. Compare range-based and hash-based sharding.
Range sharding keeps nearby keys together, so range queries are cheap, but sequential keys create hotspots. Hash sharding spreads keys evenly, but range queries must hit all shards, and simple hash mod N moves most keys when N changes.
3. How would you shard a chat application's messages table?
By conversation_id (hashed), so that loading a conversation reads one shard, and messages within a conversation are clustered by time. Very large group chats could additionally be split by time bucket, for example (conversation_id, month).
4. What is a hotspot, and how do you handle a celebrity key?
A hotspot is a shard receiving far more traffic than others. For a single hot key, split it into several sub-keys with random suffixes spread over shards (and aggregate on read), cache hot reads, or move it to a dedicated shard.
5. With hash(key) mod N, what fraction of keys move when N goes from 4 to 5?
A key stays only if h mod 4 equals h mod 5, which holds for 4 of every 20 consecutive hash values (h mod 20 in 0–3). So 80% of keys move. Consistent hashing reduces this to about 1/5 = 20%.
6. How do you run a query that does not include the shard key?
Scatter-gather: send it to all shards and merge the results, which is slower and costlier. Alternatives are a global secondary index, a separate copy of the data partitioned by the other key, or a search/analytics system fed by change data capture.
Summary
Sharding splits rows across servers so storage and writes scale beyond one machine; vertical partitioning splits columns.
Strategies: range (good for range queries, risk of hotspots), hash (even spread, poor range queries), directory (flexible, extra lookup) and geographic.
A good shard key has high cardinality, even traffic, non-monotonic values and matches the main queries.
Sharding makes joins, transactions, secondary indexes and unique ids harder.
Plan rebalancing from day one: fixed logical partitions, dynamic splitting or consistent hashing, never plain mod N.
Replication scales reads; sharding scales writes and data size. Real systems shard first by a well-chosen key, then replicate every shard.