Sharding
Master data partitioning strategies — horizontal vs vertical partitioning, range-based, hash-based, and directory-based sharding. Learn how to distribute data and traffic across machines.
Table of Contents
The Big Picture — Why Sharding?
A single database has limits — CPU, memory, disk I/O, and connection count. When your data grows to billions of rows and your traffic hits tens of thousands of queries per second, no single machine can keep up. Sharding splits your data across multiple machines so each one handles a fraction of the total load.
The Library Analogy
Imagine a city with one library. It has every book, but there's one entrance, one librarian, and one catalog. As the city grows, the line stretches around the block. Solution: split into branch libraries. Branch A has books A-H, Branch B has I-P, Branch C has Q-Z. Each branch handles a third of the traffic. Need a book starting with 'M'? Go to Branch B. That's sharding — splitting data across multiple stores, each responsible for a subset. The 'shard key' is the rule that determines which branch holds which books (in this case, the first letter).
🔥 Key Insight
Sharding is not about making one machine faster — it's about distributing the problem across many machines. Each shard is a fully functional database that handles a subset of the data. Together, they handle the full dataset at a scale no single machine could.
Vertical vs Horizontal Scaling
⬆️ Vertical Scaling (Scale Up)
- Bigger machine: more CPU, RAM, faster SSD
- Simple — no code changes, no data distribution
- Hard limit: the biggest machine money can buy
- Single point of failure
- Expensive at the top end (diminishing returns)
➡️ Horizontal Scaling (Scale Out)
- More machines: split data across N nodes
- Complex — need sharding logic, routing, rebalancing
- No hard limit: add more machines as needed
- Fault tolerant: one node down ≠ total failure
- Cost-effective: commodity hardware, linear scaling
Vertical scaling: Start: 1 server, 16 GB RAM, 4 cores → handles 5K QPS Scale: 1 server, 256 GB RAM, 64 cores → handles 50K QPS Scale: 1 server, 1 TB RAM, 128 cores → handles 100K QPS Scale: ??? → no bigger machine exists. Dead end. Horizontal scaling (sharding): Start: 1 server → handles 5K QPS Scale: 4 shards → handles 20K QPS Scale: 20 shards → handles 100K QPS Scale: 100 shards → handles 500K QPS Scale: 1000 shards → handles 5M QPS → No ceiling. Add more machines. The trade-off: horizontal scaling requires sharding logic, cross-shard queries are expensive, and rebalancing is complex. But it's the only path to truly massive scale.
💡 The Practical Rule
Start with vertical scaling (it's simpler). When you hit the ceiling of the biggest machine you can afford, or when you need fault tolerance across machines, switch to horizontal scaling. Most systems don't need sharding until they have hundreds of millions of rows or tens of thousands of QPS.
Horizontal vs Vertical Partitioning
Vertical Partitioning — Split by Columns
Vertical partitioning splits a table by columns. Frequently accessed columns go to one store, rarely accessed or large columns go to another. It's not true sharding — it's more like decomposing a table.
Original table: users id | name | email | bio (10KB) | avatar_url | preferences (JSON) Split into: users_core: id | name | email | avatar_url users_profile: id | bio | preferences Why? → users_core is read on every page load (small, fast) → users_profile is read only on the profile page (large, rare) → Separating them means the hot path reads less data per query → The 10KB bio column doesn't slow down the login query
Horizontal Partitioning (Sharding) — Split by Rows
Horizontal partitioning splits a table by rows. Each shard holds a subset of rows. This is what people mean when they say "sharding" — distributing data across multiple database instances.
Original: users table (100M rows, 1 database) Sharded into 4 databases: Shard 0: users where user_id % 4 = 0 (25M rows) Shard 1: users where user_id % 4 = 1 (25M rows) Shard 2: users where user_id % 4 = 2 (25M rows) Shard 3: users where user_id % 4 = 3 (25M rows) Each shard: → Has the same schema (all columns) → Holds a different subset of rows → Runs on a separate machine → Handles ~25% of the total traffic
| Dimension | Vertical Partitioning | Horizontal Partitioning (Sharding) |
|---|---|---|
| Splits by | Columns | Rows |
| Each partition has | Different columns, same rows | Same columns, different rows |
| Scales | Limited (still one machine per partition) | Unlimited (add more shards) |
| Use case | Separate hot/cold columns, microservice decomposition | Scale beyond single machine capacity |
| Complexity | Low (just split tables) | High (routing, rebalancing, cross-shard queries) |
| Example | users_core vs users_profile | users on Shard 0, 1, 2, 3 |
🎯 Interview Insight
When an interviewer says "sharding," they mean horizontal partitioning. Vertical partitioning is a useful optimization but doesn't solve the fundamental scaling problem. Know both, but focus your answer on horizontal partitioning.
Range-Based Sharding
Range-based sharding assigns data to shards based on value ranges of the shard key. It's the most intuitive approach — like splitting a phone directory alphabetically.
The Phone Directory
A phone directory split into 3 volumes: A-H, I-P, Q-Z. Looking for 'Smith'? Go to volume 3. Looking for 'Garcia'? Volume 1. The range determines which volume to check. Simple, intuitive, and range queries are efficient — 'all names starting with S' only needs volume 3. But there's a problem: if 40% of names start with S-Z and only 20% start with A-H, volume 3 is overloaded while volume 1 is underused. That's the hotspot problem.
Shard key: user_id (auto-incrementing integer) Shard A: user_id 1 – 1,000,000 Shard B: user_id 1,000,001 – 2,000,000 Shard C: user_id 2,000,001 – 3,000,000 Query: SELECT * FROM users WHERE user_id = 1,500,042 → Route to Shard B (1M–2M range) Range query: SELECT * FROM users WHERE user_id BETWEEN 500,000 AND 600,000 → Route to Shard A only (entire range is on one shard) → Efficient! No need to query all shards.
Strengths
- ✅Simple to understand and implement
- ✅Range queries are efficient (scan one shard, not all)
- ✅Easy to add new shards (extend the range)
- ✅Good for time-series data (shard by date range)
- ✅Sorted data stays together on the same shard
Weaknesses
- ❌Hotspot problem: uneven data distribution across ranges
- ❌New users all go to the latest shard (write hotspot)
- ❌Requires manual range planning and monitoring
- ❌Rebalancing means moving data between shards
- ❌Some shards may be nearly empty while others overflow
Shard key: created_at (timestamp) Shard A: Jan 2023 – Jun 2023 (old data, rarely accessed) Shard B: Jul 2023 – Dec 2023 (old data, rarely accessed) Shard C: Jan 2024 – Jun 2024 (recent data, heavily accessed) Shard D: Jul 2024 – now (ALL new writes go here!) Problem: Shard D handles 90% of writes (all new data) Shard A handles 2% of reads (old data nobody looks at) → Shard D is a hotspot, others are idle → This defeats the purpose of sharding
🎯 Interview Insight
Range-based sharding works well when the shard key has uniform distribution (e.g., hash of user ID mapped to ranges) or when range queries are critical (time-series data, alphabetical lookups). Avoid it when the key is monotonically increasing (auto-increment IDs, timestamps) — all writes go to one shard.
Hash-Based Sharding
Hash-based sharding uses a hash function to determine which shard holds a given key. The hash distributes data evenly across shards regardless of the key's value — solving the hotspot problem that plagues range-based sharding.
The Random Room Assignment
Imagine 1,000 students arriving at a conference. Instead of assigning rooms alphabetically (A-H → Room 1), you give each student a random room number based on their student ID: room = hash(student_id) % 4. The distribution is nearly perfect — each room gets ~250 students regardless of their names. But if a student asks 'which room are all the S-names in?' — you can't answer without checking every room. That's the trade-off: even distribution, but no locality for range queries.
Shard key: user_id Number of shards: 4 Hash function: MD5 or MurmurHash shard_number = hash(user_id) % 4 Examples: hash("user_42") % 4 = 2 → Shard 2 hash("user_43") % 4 = 0 → Shard 0 hash("user_44") % 4 = 3 → Shard 3 hash("user_45") % 4 = 1 → Shard 1 Result: users are distributed evenly across all 4 shards. No hotspot — even if user IDs are sequential. Query: SELECT * FROM users WHERE user_id = 'user_42' → hash("user_42") % 4 = 2 → route to Shard 2 ✅ Range query: SELECT * FROM users WHERE user_id BETWEEN 40 AND 50 → Must query ALL 4 shards (data is scattered) ❌
Strengths
- ✅Even data distribution (no hotspots)
- ✅Works with any key type (strings, integers, UUIDs)
- ✅Simple to compute: hash(key) % N
- ✅Most common approach in distributed systems
- ✅Predictable load balancing across shards
Weaknesses
- ❌Range queries are expensive (must query all shards)
- ❌Re-sharding is painful: changing N reshuffles most keys
- ❌Adding a shard means hash(key) % 5 ≠ hash(key) % 4
- ❌~80% of data moves when going from 4 to 5 shards
- ❌Consistent hashing solves the re-sharding problem
Current: 4 shards, hash(key) % 4 key "alice" → hash % 4 = 2 → Shard 2 key "bob" → hash % 4 = 0 → Shard 0 key "carol" → hash % 4 = 1 → Shard 1 Add a 5th shard: hash(key) % 5 key "alice" → hash % 5 = 3 → Shard 3 (MOVED from Shard 2!) key "bob" → hash % 5 = 0 → Shard 0 (stayed) key "carol" → hash % 5 = 4 → Shard 4 (MOVED from Shard 1!) ~80% of keys move to different shards. During migration: massive data transfer, potential downtime. Fix: use consistent hashing (only ~1/N keys move when adding a shard).
🎯 Interview Insight
Hash-based sharding is the most common approach. When asked "how would you shard this?" — default to hash-based. Mention the re-sharding problem and say you'd use consistent hashing to minimize data movement. This shows you understand both the approach and its limitation.
Directory-Based Sharding
Directory-based sharding uses a lookup service (directory) that maps each key to its shard. Instead of computing the shard from the key, you ask the directory: "Where does this key live?"
The Reception Desk
A large office building has departments on different floors. Instead of a formula to figure out which floor, there's a reception desk. You walk in and say 'I need the Finance team.' The receptionist checks a directory and says 'Floor 7.' If Finance moves to Floor 3 next week, only the directory is updated — visitors still ask the same question and get the right answer. That's directory-based sharding: a central lookup that decouples the key from the physical location.
Lookup table (stored in a fast store like Redis or Zookeeper): user_42 → Shard A user_43 → Shard B user_44 → Shard A user_45 → Shard C Query: SELECT * FROM users WHERE user_id = 'user_42' 1. Ask directory: "Where is user_42?" → Shard A 2. Route query to Shard A 3. Return result Re-sharding: Move user_42 from Shard A to Shard D Update directory: user_42 → Shard D Done. No hash function change. No mass data migration.
Strengths
- ✅Maximum flexibility — any key can be on any shard
- ✅Easy rebalancing — just update the directory entry
- ✅No re-sharding problem (no hash function to change)
- ✅Can handle uneven data sizes (move hot keys to less loaded shards)
- ✅Supports complex routing logic (geo-based, tenant-based)
Weaknesses
- ❌Extra lookup on every request (directory query overhead)
- ❌Directory is a single point of failure (must be replicated)
- ❌Directory must be fast (Redis, Zookeeper) — can't be a slow DB
- ❌Directory size grows with number of keys
- ❌More complex to operate than hash-based
🎯 Interview Insight
Directory-based sharding is used when flexibility matters more than simplicity — multi-tenant SaaS (route each tenant to their shard), geo-based routing (route users to the nearest region), or when you need fine-grained control over data placement. Mention it as an alternative when hash-based sharding's rigidity is a problem.
End-to-End Scenario
Let's design the sharding strategy for a social media platform with 500M users and 50,000 write QPS.
📱 Social Media — 500M Users
Tables: users (500M rows), posts (10B rows), follows (50B rows).
Single PostgreSQL max: ~5,000 write QPS. We need 50,000.
Single machine storage: ~2 TB. We have ~20 TB of data.
Choose the shard key: user_id
Most queries are user-centric: 'get user profile', 'get user's posts', 'get user's feed'. Sharding by user_id keeps all of a user's data on the same shard — no cross-shard queries for the most common operations. Posts and follows tables are also sharded by user_id (the author's ID).
Choose the strategy: hash-based with consistent hashing
Hash-based ensures even distribution across shards. Consistent hashing minimizes data movement when adding shards. shard = consistent_hash(user_id). Start with 16 shards — each handles ~31M users and ~3,000 write QPS (well within a single PostgreSQL's capacity).
Handle uneven load: monitor and rebalance
Some users are power users (celebrities with millions of followers). Their shards get more traffic. Monitor QPS per shard. If a shard is hot, split it into two using consistent hashing (only ~6% of data moves). For extreme cases (a single celebrity causing hotspot), use a secondary cache layer.
Handle cross-shard queries
'Get all followers of user X' — if followers are sharded by follower_id, this requires querying all shards. Solution: denormalize. Store a 'following' list on the user's shard (who I follow) AND a 'followers' list (who follows me). Reads are fast (single shard). Writes are slightly more complex (update two shards on follow/unfollow).
Plan for growth: 16 → 32 → 64 shards
With consistent hashing, going from 16 to 32 shards moves only ~50% of data (each shard splits in half). Schedule migrations during low-traffic hours. Use read replicas during migration to serve reads while data moves. Target: each shard stays under 70% capacity to absorb traffic spikes.
Shard key: user_id (hash-based, consistent hashing) Shards: 16 PostgreSQL instances (expandable to 64+) Routing: App → Consistent Hash Ring → Shard N shard = hash(user_id) → ring position → nearest shard Data layout per shard: users: rows where consistent_hash(user_id) → this shard posts: rows where consistent_hash(author_id) → this shard follows: rows where consistent_hash(user_id) → this shard Cross-shard queries: "Global trending posts" → fan-out to all shards, merge results "User's own feed" → single shard (all data co-located) Growth plan: 16 shards → 500M users, 50K QPS 32 shards → 1B users, 100K QPS 64 shards → 2B users, 200K QPS
Trade-offs & Decision Making
| Strategy | Distribution | Range Queries | Re-sharding | Complexity | Best For |
|---|---|---|---|---|---|
| Range-based | Uneven (hotspots) | Efficient (single shard) | Move data between ranges | Low | Time-series, alphabetical data |
| Hash-based | Even | Expensive (all shards) | Painful (most keys move) | Low | General purpose, most systems |
| Hash + consistent | Even | Expensive (all shards) | Minimal (~1/N keys move) | Medium | Systems that grow frequently |
| Directory-based | Configurable | Depends on mapping | Easy (update directory) | High | Multi-tenant, geo-routing |
Choosing the Shard Key
| Shard Key | Pros | Cons | Good For |
|---|---|---|---|
| user_id | User data co-located, most queries are per-user | Celebrity users create hotspots | Social media, user-centric apps |
| order_id | Even distribution (random IDs) | User's orders spread across shards | E-commerce (if queries are per-order) |
| timestamp | Time-range queries efficient | All writes go to latest shard (hotspot) | Time-series, logs (with care) |
| geo_region | Data locality for regional users | Uneven if regions differ in size | Geo-distributed systems |
| tenant_id | Tenant isolation, easy per-tenant scaling | Large tenants create hotspots | Multi-tenant SaaS |
🎯 The Golden Rule of Shard Keys
Choose a shard key that: (1) distributes data evenly, (2) co-locates data that's queried together, and (3) avoids hotspots. The most common queries should hit a single shard. Cross-shard queries should be rare. If you can't find a key that satisfies all three, prioritize even distribution and denormalize to avoid cross-shard reads.
Interview Questions
Q:How do you shard a database?
A: Pick a shard key (the column that determines which shard holds each row). Apply a sharding strategy: hash-based (hash(key) % N) for even distribution, range-based for efficient range queries, or directory-based for maximum flexibility. Use consistent hashing to minimize data movement when adding shards. Co-locate related data on the same shard to avoid cross-shard queries. Plan for rebalancing from day one.
Q:Range vs hash sharding — when to use each?
A: Range-based when you need efficient range queries and the key has uniform distribution — time-series data (shard by month), alphabetical lookups, sequential scans. Hash-based when you need even distribution and your queries are point lookups (get by ID) — user data, order data, most CRUD applications. Hash-based is the default choice; range-based is the exception for specific query patterns.
Q:How do you handle re-sharding?
A: With simple hash (key % N), changing N reshuffles ~80% of keys — painful. Use consistent hashing: keys are mapped to a ring, and adding a shard only moves ~1/N of keys. During migration: (1) set up the new shard, (2) start copying affected keys, (3) dual-write to old and new shard during transition, (4) switch reads to new shard, (5) remove old copies. Use read replicas to serve traffic during migration. Schedule during low-traffic windows.
Your e-commerce database has 1B orders and queries are slow
How would you shard the orders table?
Answer: Shard key depends on query patterns. If most queries are 'get orders for user X' → shard by user_id (co-locates a user's orders). If most queries are 'get order by order_id' → shard by order_id (even distribution). If both → shard by user_id and create a secondary index/lookup for order_id → shard mapping. Use hash-based with consistent hashing. Start with 8 shards (~125M orders each). Each shard handles ~12% of traffic.
After sharding by user_id, one shard has 10x more traffic than others
What's happening and how do you fix it?
Answer: A celebrity or power user on that shard generates disproportionate traffic (millions of followers reading their posts). Fixes: (1) Split the hot shard into two using consistent hashing. (2) Add a cache layer in front of the hot shard (cache the celebrity's data in Redis). (3) For extreme cases, use a dedicated shard for the celebrity's read-heavy data. (4) Long-term: consider a secondary sharding dimension (shard posts by post_id for reads, keep user_id sharding for writes).
Common Mistakes
Choosing the wrong shard key
Sharding by timestamp for a social media app. All new posts go to the latest shard (write hotspot). Or sharding by country for a global app where 60% of users are in one country. The shard key must distribute data AND traffic evenly.
✅Analyze your query patterns first. The shard key should be the column in your most common WHERE clause. For user-centric apps: user_id. For order-centric apps: order_id. Test the distribution before deploying — simulate with production data.
Ignoring hotspots
Assuming hash-based sharding eliminates all hotspots. It distributes data evenly, but not traffic. A celebrity with 100M followers generates 1000x more read traffic than an average user — their shard becomes a hotspot even with perfect data distribution.
✅Monitor QPS per shard, not just data size. Use caching for hot keys. For extreme hotspots, consider dedicated shards or fan-out reads across replicas. The shard key distributes data; caching and replicas distribute traffic.
Not planning for re-sharding
Using hash(key) % N with a fixed N. When you need to add shards, 80% of data must move. Teams discover this during a crisis when the current shards are at capacity and there's no time for a careful migration.
✅Use consistent hashing from day one. It costs nothing extra and makes adding shards trivial (~1/N data moves). Also: start with more shards than you need (16 instead of 4) — it's easier to merge underused shards than to split overloaded ones.
Hardcoding shard logic in application code
Scattering shard routing logic across 50 microservices. When you need to change the sharding strategy, you must update and deploy all 50 services simultaneously. One missed service routes to the wrong shard.
✅Centralize shard routing in a library or a routing service. All applications use the same routing logic. When the strategy changes, update one place. Even better: use a proxy layer (like Vitess for MySQL or Citus for PostgreSQL) that handles sharding transparently.