Database Sharding

What is database sharding?

Sharding (horizontal partitioning) splits a large dataset across multiple independent database instances called shards. Each shard holds a subset of the data and can be queried independently. Together, all shards cover the full dataset.

Sharding is typically the last resort for database scaling - attempt read replicas, caching, and vertical scaling first.

Sharding Strategies

Range-Based Sharding

Partition by value ranges: user IDs 1-1,000,000 on shard 1, 1,000,001-2,000,000 on shard 2, etc.

• ✅ Simple; supports efficient range queries within a shard
• ❌ Hot shards: if most active users have recent IDs, one shard handles all the load
• ❌ Manual rebalancing when a range fills up

Hash-Based Sharding

shard_id = hash(partition_key) % num_shards

• ✅ Even distribution across shards (no hot spots for uniform data)
• ✅ No lookup table needed
• ❌ Range queries require scatter-gather (query all shards, merge results)
• ❌ Resharding requires moving data - % 4 and % 5 produce entirely different assignments

Directory-Based Sharding

A lookup service maps partition keys to shard IDs: user_id -> shard_3.

• ✅ Most flexible; easy to rebalance by updating the directory
• ✅ Can move specific keys to different shards on demand
• ❌ Lookup service becomes a bottleneck and single point of failure
• ❌ Extra network hop for every query

Choosing a Partition Key

The partition key determines how data is distributed. A bad key causes:

• Hot shards: One shard handles disproportionate traffic (e.g., sharding by country when 60% of users are American)
• Hotspot keys: Celebrity users, viral posts - a single key overwhelms one shard

Good keys have high cardinality and uniform access patterns: user_id, order_id.

Challenges

Cross-Shard Queries

A JOIN across shards requires querying multiple databases and merging in application code. This is expensive and complex. Design your data model to avoid cross-shard queries on hot paths.

Distributed Transactions

A transaction spanning two shards requires distributed coordination (2PC or Saga pattern). Most sharded systems avoid cross-shard transactions by design.

Resharding

Adding new shards requires migrating data. With hash-based sharding, this touches all existing data. Solutions:

• Consistent hashing: Minimises remapping when nodes are added
• Double-write: Write to old and new shard simultaneously during migration
• Online migration: Migrate in background, switch over when complete

Hotspot Mitigation

For viral/celebrity keys: add a random suffix to the partition key (user_id + random(0,10)), fan out writes to 10 sub-keys, fan in reads by querying all 10 and aggregating.

When to Shard

Shard when:

• A single database can't handle write throughput even after vertical scaling
• Dataset is too large for a single node (multi-TB+)
• Read replicas solve reads but not writes

Interview Angle

Mention sharding only after exhausting simpler options. Then be specific: choose a partition key, justify it, and explain how you handle the two hardest problems - cross-shard queries and resharding.