Theory
Database Sharding
📋 Overview
Sharding is a horizontal scaling strategy that involves partitioning a large database into smaller, more manageable pieces called shards. Each shard is a distinct database that contains a subset of the total data. By distributing the data across multiple machines, sharding allows a system to handle massive datasets and high query volumes that would overwhelm a single server.
🏗️ Core Principles & Characteristics
- Horizontal Partitioning: Data is split by rows rather than columns.
- Shard Key: A specific column (e.g.,
user_id) used to determine which shard a particular row belongs to. - Independence: Each shard operates as its own standalone database instance.
- Distribution Strategies:
- Algorithmic (Hash-based):
shard = hash(key) % N. Ensures even distribution but makes resharding difficult. - Range-based:
shard = f(range). Good for range queries but prone to hotspots (e.g., all new users in one shard). - Directory-based: A lookup table maps keys to shards. Flexible but adds a level of indirection and a potential bottleneck.
- Algorithmic (Hash-based):
⚖️ Trade-offs: Pros & Cons
Pros
- Unlimited Scalability: Add more shards to increase storage and throughput indefinitely.
- Fault Isolation: A failure in one shard doesn't necessarily take down the entire system.
- Geographic Distribution: Place shards closer to users in specific regions to reduce latency.
Cons
- Operational Complexity: Managing multiple database instances is significantly harder (backups, migrations, monitoring).
- No Cross-Shard Joins: Joins across shards are extremely inefficient or unsupported.
- Referential Integrity: Enforcing foreign keys across shards is generally not possible at the database level.
- Resharding: Moving data between shards to rebalance the system is a complex and risky operation.
🌍 Real-World Implementation
- Instagram: Sharded their PostgreSQL database using a custom ID generation scheme to handle billions of photos.
- Vitess: An open-source sharding middleware for MySQL used by YouTube and Slack to manage massive clusters.
- Citus: An extension that transforms PostgreSQL into a distributed database through transparent sharding.
💡 Interview "Gotchas" & Tips
- Consistent Hashing: Always mention consistent hashing when discussing hash-based sharding to show you understand how to minimize data movement during resharding.
- Hotspots: Be prepared to discuss how to handle "celebrity" accounts or popular data that can overwhelm a single shard (e.g., adding a random suffix to the shard key).
- Logical vs. Physical Shards: Distinguish between logical shards (the data partition) and physical shards (the actual server instance).
📐 Suggested Architecture Primitives
- Shard Mapping Service: To route queries to the correct shard.
- Global ID Generator: (e.g., Snowflake) To ensure unique IDs across all shards.
- Aggregation Layer: To merge results from multiple shards for complex queries.
- Gossip Protocol: Used in some distributed systems to manage cluster state and shard health.
Canvas