Database Sharding

Database Sharding

Sharding (horizontal partitioning) splits a large dataset across multiple databases (shards), each holding a subset of the data. It's the solution when a single database can no longer handle the data volume or write throughput.

When to Shard

• Single database can't fit all data in RAM → cache ineffective
• Write throughput exceeds one server's capacity
• You've already tried vertical scaling, read replicas, and query optimization

Sharding Strategies

Hash-Based Sharding

shard = hash(userId) % numShards

userId=1001 → hash=2341 → shard 1
userId=1002 → hash=4892 → shard 2
userId=1003 → hash=1234 → shard 0

✅ Even distribution, no hot spots ❌ Range queries span all shards; hard to add shards (resharding needed)

Range-Based Sharding

userId 0-999999     → Shard A
userId 1000000-1999999 → Shard B
userId 2000000+     → Shard C

✅ Range queries stay within one shard ❌ Uneven distribution (new users all go to last shard → hot spot)

Directory-Based Sharding

Lookup service: userId → shardId

userId=1001 → Shard 3  ← looked up in a directory/mapping table

✅ Flexible: move data between shards without rehashing ❌ Lookup service is a bottleneck and single point of failure

Consistent Hashing (best for dynamic shards)

Places both servers and keys on a circular hash ring. Each key is served by the nearest server clockwise. Adding/removing servers only redistributes keys belonging to that server's range — not all keys.

     0°  (Server A)
    /
  270° (Server D) ---- 90° (Server B)
    \        
    180° (Server C)

Key hash at 45° → served by Server B (next clockwise)

Hot Spot Problem

A shard that receives disproportionate traffic (e.g., a celebrity user's data on Shard 2 gets 10M reads/sec).

Solutions:

• Add a random suffix to the shard key: celeb_userId_[random 0-9] → distributes across 10 keys
• Store hot data in a dedicated shard or cache layer
• Use CDN for public content

Cross-Shard Queries

Sharding makes JOINs and aggregations across shards very expensive:

-- This query needs all shards:
SELECT COUNT(*) FROM users WHERE country = 'US'; -- must scan all shards

-- Solutions:
-- 1. Scatter-gather: query all shards in parallel, aggregate results
-- 2. Denormalize: store country count in a dedicated analytics store
-- 3. Avoid cross-shard: design queries to target a single shard

Re-Sharding

Adding new shards requires moving data — very expensive. Consistent hashing minimizes data movement:

• Hash sharding: move ~n/(n+1) of all data
• Consistent hashing: move only 1/(n+1) of all data

Interview Tips

1. Always mention consistent hashing as the preferred sharding approach — it minimizes resharding cost.
2. Explain the hot spot problem and how to mitigate it — this shows deep understanding.
3. In practice, many teams avoid custom sharding by using Vitess (MySQL), Citus (PostgreSQL), or native sharding in MongoDB/Cassandra/DynamoDB.