Sharding Deep Dive for System Design Interviews
Sharding Deep Dive for System Design Interviews
Sharding is one of the most important concepts in system design interviews. When your interviewer asks "How do you handle billions of rows?" or "What happens when data exceeds a single server's capacity?", sharding is the answer.
Yet many candidates struggle with the details: How do you choose a shard key? What happens when you need to add more shards? How do you handle queries that span multiple shards? These are the questions that separate strong candidates from average ones.
This article provides a deep understanding of sharding for system design interviews. We will explore why sharding is necessary, different sharding strategies, consistent hashing, shard key selection, rebalancing, cross-shard operations, and how major databases implement sharding.
Here is what we will cover:
- Why Sharding Matters
- Horizontal vs Vertical Partitioning
- Sharding Strategies
- Consistent Hashing
- Choosing a Shard Key
- Rebalancing and Resharding
- Cross-Shard Operations
- Sharding Patterns and Architectures
- Sharding in Practice
- Common Interview Questions
If you're enjoying this newsletter and want to get even more value, consider becoming a [paid subscriber](https://blog.algomaster.io/subscribe).
As a paid subscriber, you'll unlock all premium articles and gain full access to all [premium courses](https://algomaster.io/newsletter/paid/resources) on [algomaster.io](https://algomaster.io).
1. Why Sharding Matters
Before diving into implementation details, let us understand why sharding is fundamental to scaling databases.
1.1 The Single Server Limit
Every server has limits: CPU, memory, disk space, and I/O bandwidth. When your data grows beyond these limits, you have two options.
1.2 Vertical Scaling vs Horizontal Scaling
Vertical scaling hits a ceiling. The most powerful server money can buy still has limits. Horizontal scaling through sharding is the path to virtually unlimited capacity.
1.3 What Is Sharding?
Sharding is horizontal partitioning of data across multiple database instances. Each shard holds a subset of the total data.
1.4 Benefits of Sharding
1.5 Costs of Sharding
Sharding is not free. It adds significant complexity. Only shard when you must.
Interview insight: "We shard when a single database cannot handle the load, typically when data exceeds a few hundred gigabytes or query throughput exceeds tens of thousands per second. Before sharding, we exhaust other options: read replicas, caching, query optimization, and vertical scaling."
2. Horizontal vs Vertical Partitioning
Understanding the difference between horizontal and vertical partitioning is essential.
2.1 Vertical Partitioning
Split tables by columns. Different columns go to different databases.
Use cases:
- Separate frequently accessed columns from rarely accessed ones
- Isolate large blob columns (avatar images)
- Different access patterns for different column groups
2.2 Horizontal Partitioning (Sharding)
Split tables by rows. Different rows go to different databases.
Use cases:
- Data too large for single server
- Query throughput exceeds single server capacity
- Geographic data distribution
2.3 Comparison
3. Sharding Strategies
How do you decide which shard holds which data? There are several strategies.
3.1 Range-Based Sharding
Assign ranges of the shard key to each shard.
How it works:
Advantages:
Disadvantages:
3.2 Hash-Based Sharding
Apply a hash function to the shard key and use modulo to determine shard.
How it works:
Advantages:
Disadvantages:
3.3 Directory-Based Sharding
Maintain a lookup service that maps keys to shards.
How it works:
Advantages:
Disadvantages:
3.4 Geographic Sharding
Shard based on geographic location.
Use cases:
- Data residency requirements (GDPR)
- Low latency for regional users
- Regulatory compliance
3.5 Strategy Comparison
Interview tip: "For our user table with random access patterns, we use hash-based sharding on user_id for even distribution. For our time-series data with range queries, we use range-based sharding on timestamp. The choice depends on query patterns."
4. Consistent Hashing
Consistent hashing solves the resharding problem of simple hash-based sharding.
4.1 The Problem with Simple Hash Sharding
Impact: Adding one shard moves ~80% of keys. This is unacceptable at scale.
4.2 How Consistent Hashing Works
Imagine a ring from 0 to 2^32-1. Both keys and shards are placed on this ring using hash functions.
Rules:
- Hash each shard to a position on the ring
- Hash each key to a position on the ring
- A key belongs to the first shard clockwise from its position
4.3 Adding a Shard
When adding a shard, only keys between the new shard and its predecessor move.
Result: Only ~1/N of keys move (where N is the number of shards).
4.4 Virtual Nodes
Problem: With few shards, distribution may be uneven.
Solution: Each physical shard has multiple virtual nodes on the ring.
Benefits of virtual nodes:
4.5 Implementation
4.6 Consistent Hashing in Practice
Interview insight: "We use consistent hashing with 256 virtual nodes per shard. When adding a new shard, we only move about 1/N of the data. The virtual nodes ensure even distribution even with heterogeneous hardware, we just assign more vnodes to more powerful servers."
5. Choosing a Shard Key
The shard key is the most critical decision in sharding. A bad choice leads to hotspots, inefficient queries, and painful migrations.
5.1 Shard Key Requirements
5.2 Common Shard Key Choices
User ID as shard key:
Tenant ID for multi-tenant SaaS:
Problem: Large tenants cause hotspots.
Solution: Compound shard key: tenant_id + user_id
Time-based sharding:
Good for: Time-series data, logs, events Problem: Latest shard is always hot
5.3 Compound Shard Keys
Combine multiple fields for better distribution and query routing.
5.4 Shard Key Anti-Patterns
5.5 Decision Framework
Interview tip: "For our e-commerce orders table, we shard by customer_id because 90% of queries are customer-specific (order history, cart). For cross-customer queries like analytics, we use a separate read-optimized replica with different sharding or no sharding at all."
6. Rebalancing and Resharding
As data grows, you need to add shards. This is one of the hardest operational challenges.
6.1 When to Rebalance
Triggers:
6.2 Rebalancing Strategies
Strategy 1: Fixed Number of Shards (Pre-splitting)
Create more shards than needed initially.
Pros: Simple, no data splitting Cons: Must guess correctly upfront, fixed maximum capacity
Strategy 2: Dynamic Splitting
Split shards when they get too large.
Pros: Automatic, adapts to growth Cons: Complex, splits cause temporary slowdown
Strategy 3: Dynamic Merging
Merge small shards to reduce overhead.
6.3 Online Resharding Process
Moving data without downtime is complex.
Phases:
6.4 Minimizing Resharding
Design to minimize resharding frequency:
Interview insight: "We use consistent hashing with 256 virtual nodes per physical shard. When adding a new shard, we use a background migration process that copies data in batches during off-peak hours. During migration, we dual-write to both old and new locations, then atomically switch the routing once migration is complete."
7. Cross-Shard Operations
Some operations inherently span multiple shards. These are challenging.
7.1 Cross-Shard Queries
Example: Find all orders over $1000
Performance implications:
7.2 Cross-Shard JOINs
The most expensive cross-shard operation.
Strategies for cross-shard JOINs:
7.3 Distributed Transactions
Transactions spanning multiple shards require coordination.
Two-Phase Commit (2PC):
Problems with 2PC:
- Blocking: Shards hold locks during entire protocol
- Coordinator failure: Participants stuck waiting
- Performance: Two round trips
7.4 Saga Pattern
For long-running transactions, use compensating transactions instead of distributed locks.
Each step has a compensating action:
7.5 Global Secondary Indexes
Maintain indexes that span all shards for cross-shard queries.
Trade-offs:
Interview tip: "We avoid cross-shard transactions by co-locating related data. Orders and order_items are sharded by customer_id, so a complete order transaction stays within one shard. For truly cross-shard operations like transferring money between users, we use the saga pattern with compensating transactions."
8. Sharding Patterns and Architectures
Different architectural patterns for implementing sharding.
8.1 Application-Level Sharding
Application code decides which shard to query.
Pros: Full control, no middleware Cons: Logic in every application, harder to change
8.2 Proxy-Based Sharding
A proxy layer handles routing transparently.
Popular proxies:
Pros: Transparent to application, centralized logic Cons: Extra hop, potential bottleneck
8.3 Native Database Sharding
Database handles sharding internally.
Databases with native sharding:
Pros: Integrated, automatic rebalancing Cons: Vendor lock-in, less control
8.4 Hybrid Approaches
Combine multiple patterns.
9. Sharding in Practice
How major databases implement sharding.
9.1 MongoDB Sharding
Components:
Shard key selection:
9.2 Cassandra Partitioning
Partition key:
Virtual nodes (vnodes):
9.3 Vitess (MySQL Sharding)
VSchema (sharding configuration):
9.4 CockroachDB Automatic Sharding
Automatic features:
9.5 Comparison
10. Common Interview Questions
10.1 Design Questions
Q: How would you shard a social media posts database?
Q: Design sharding for a multi-tenant SaaS application.
10.2 Troubleshooting Questions
Q: One shard is significantly hotter than others. How do you debug and fix?
Q: How do you handle a cross-shard transaction failure?
10.3 Quick Reference
Summary
Sharding is essential for scaling beyond the limits of a single database server. Here are the key takeaways:
- Shard only when necessary. Sharding adds significant complexity. Exhaust other options first: read replicas, caching, query optimization, vertical scaling.
- Choose the right strategy. Range sharding for range queries, hash sharding for even distribution, consistent hashing to minimize resharding pain. The choice depends on your access patterns.
- The shard key is critical. High cardinality, even distribution, aligned with queries, immutable. A bad shard key means hotspots and expensive cross-shard queries.
- Consistent hashing minimizes data movement. When adding or removing shards, only 1/N of data moves instead of most of it. Use virtual nodes for better distribution.
- Plan for cross-shard operations. They are expensive but sometimes unavoidable. Co-locate related data, use global secondary indexes, consider sagas for transactions.
- Rebalancing is inevitable. Design for it from the start. Pre-split shards, use consistent hashing, have migration tooling ready.
- Different databases, different models. MongoDB, Cassandra, Vitess, and CockroachDB all handle sharding differently. Know the trade-offs of your chosen database.
- Co-locate related data. The best cross-shard query is one that never happens. Design your shard key to keep related data together.
- Monitor shard health. Track size, query load, and latency per shard. Hotspots should trigger alerts, not outages.
- Consider managed solutions. Native sharding databases like CockroachDB, TiDB, or cloud offerings like Aurora reduce operational burden.
When discussing sharding in interviews, be specific about your choices. Do not just say "we shard the data." Explain the shard key, the sharding strategy, how you handle cross-shard queries, what happens when you need to add shards, and how you monitor shard health. This depth demonstrates genuine understanding of distributed database design.
Thank you for reading!
If you found it valuable, hit a like and consider subscribing for more such content every week.
If you have any questions or suggestions, leave a comment.
This post is public so feel free to share it.
P.S. If you're enjoying this newsletter and want to get even more value, consider becoming a [paid subscriber](https://blog.algomaster.io/subscribe).
As a paid subscriber, you'll unlock all premium articles and gain full access to all [premium courses](https://algomaster.io/newsletter/paid/resources) on [algomaster.io](https://algomaster.io).
There are [group discounts](https://blog.algomaster.io/subscribe?group=true), [gift options](https://blog.algomaster.io/subscribe?gift=true), and [referral bonuses](https://blog.algomaster.io/leaderboard) available.
Checkout my [Youtube channel](https://www.youtube.com/@ashishps_1/videos) for more in-depth content.
Follow me on [LinkedIn](https://www.linkedin.com/in/ashishps1/) and [X](https://twitter.com/ashishps_1) to stay updated.
Checkout my [GitHub repositories](https://github.com/ashishps1) for free interview preparation resources.
I hope you have a lovely day!
See you soon,
Ashish
References
- Designing Data-Intensive Applications - Martin Kleppmann's definitive guide to partitioning and distributed systems
- Dynamo: Amazon's Highly Available Key-value Store - The paper that popularized consistent hashing
- Vitess Documentation - MySQL horizontal scaling architecture
- MongoDB Sharding Documentation - Official MongoDB sharding guide
- Cassandra Architecture - Cassandra partitioning and replication
- CockroachDB Architecture - Automatic sharding with distributed SQL