Sharding

Sharding splits data across multiple databases for horizontal scaling.

Strategy Overview

1. Range-Based Sharding
   Shard 1: Users 1-1000
   Shard 2: Users 1001-2000
   Shard 3: Users 2001-3000

2. Hash-Based Sharding
   shard_id = hash(user_id) % num_shards
   User 1 → hash(1) % 3 = 1 → Shard 1
   User 2 → hash(2) % 3 = 2 → Shard 2

3. Directory-Based Sharding
   Lookup table maps keys to shards
   User 1 → Shard 2
   User 2 → Shard 1

4. Geographic Sharding
   US users → Shard US
   EU users → Shard EU

Strategy Comparison

Strategy	Pros	Cons
Range	Simple, ordered	Hotspots
Hash	Even distribution	Rebalancing hard
Directory	Flexible	Extra lookup
Geographic	Low latency	Uneven data

Hash-Based Sharding

Example: 3 shards

user_id: 1 → hash(1) = 7 → 7 % 3 = 1 → Shard 1
user_id: 2 → hash(2) = 11 → 11 % 3 = 2 → Shard 2
user_id: 3 → hash(3) = 15 → 15 % 3 = 0 → Shard 0
user_id: 4 → hash(4) = 19 → 19 % 3 = 1 → Shard 1

Even distribution across shards

Range-Based Sharding

Example: User ID ranges

Shard 1: user_id 1-1000000
Shard 2: user_id 1000001-2000000
Shard 3: user_id 2000001-3000000

Problem: New users all go to Shard 3 (hotspot)

Directory-Based Sharding

Directory Table:
user_id | shard_id
1       | 2
2       | 1
3       | 3
4       | 2

Lookup: Query directory, then query shard

Pros: Flexible, can move data between shards
Cons: Extra query, directory can be bottleneck

Geographic Sharding

Shard US: US-based users
Shard EU: EU-based users
Shard Asia: Asia-based users

Benefits:
- Low latency (data near users)
- Compliance (data residency)
- Natural partitioning

Challenges:
- Uneven data distribution
- Cross-region queries difficult

Consistent hashing minimizes data movement when adding/removing nodes.

The Problem with Simple Hashing

Simple hashing: shard = hash(key) % N

N=3: user 1 → Shard 1
N=4: user 1 → Shard 3 (moved!)

Adding a shard moves most keys!

Consistent Hashing Solution

Hash Ring:

        0
    ┌───┐
    │   │
┌───┤   ├───┐
│ A │   │ B │
└───┤   ├───┘
    │   │
    └───┘
      33

Nodes placed on ring:
- Node A at position 10
- Node B at position 30

Key K1: hash(K1) = 15 → Node A (next clockwise)
Key K2: hash(K2) = 25 → Node B
Key K3: hash(K3) = 5 → Node A

Virtual Nodes

Physical nodes have multiple positions:

Node A: 10, 50, 90
Node B: 30, 70, 110

Better distribution:
- 6 positions on ring
- More even spread
- Better load balancing

Adding/Removing Nodes

Before: Node A (10), Node B (30)

After adding Node C at 20:
Node A (10), Node C (20), Node B (30)

Only keys between 10-20 move to Node C
Minimal data movement!

Consistent Hashing Implementation

1. Create hash ring
2. Place nodes (with virtual nodes)
3. Place keys on ring
4. Each key → next clockwise node
5. Adding node → only nearby keys move
6. Removing node → keys move to next node

Consistent Hashing Benefits

1. Minimal data movement
   - Adding/removing node moves ~1/N keys
   - vs N/N keys with simple hashing

2. Even distribution
   - Virtual nodes spread load
   - No hotspots

3. Scalability
   - Add nodes incrementally
   - No full rebalancing needed

When to Use Consistent Hashing

Use when:
- Distributed cache (Redis, Memcached)
- Distributed database
- Load balancing
- CDNs

Examples:
- DynamoDB
- Cassandra
- Memcached
- Akamai CDN

Rebalancing distributes data evenly when adding or removing shards.

Why Rebalancing is Needed

Problem: Uneven data distribution

Shard 1: 1M rows (overloaded)
Shard 2: 100K rows (underloaded)
Shard 3: 50K rows (underloaded)

Solution: Rebalance to ~383K rows each

Rebalancing Strategies

1. Full Rehash
   - Redistribute all data
   - Simple but expensive
   - Downtime required

2. Consistent Hashing
   - Minimal data movement
   - No downtime
   - Best for most cases

3. Directory-Based
   - Update lookup table
   - Move data gradually
   - Flexible but complex

4. Range Splitting
   - Split large shards
   - Merge small shards
   - Maintain ordering

Online Rebalancing

1. Start rebalancing
   - New shard added
   - Start moving data

2. Serve during rebalance
   - Both old and new shards serve
   - Reads from old, write to both

3. Complete rebalance
   - All data moved
   - Update routing
   - Remove old shard

Rebalancing Challenges

1. Data Movement
   - Large data volumes
   - Network bandwidth
   - Time-consuming

2. Consistency
   - Data in transit
   - Dual writes during migration
   - Conflict resolution

3. Performance
   - Degraded during rebalance
   - Resource contention
   - Query routing complexity

4. Operational
   - Monitoring required
   - Rollback plan
   - Testing needed

Rebalancing Best Practices

1. Plan ahead
   - Estimate data movement
   - Schedule during low traffic
   - Test in staging

2. Monitor progress
   - Track data movement
   - Monitor performance
   - Alert on issues

3. Gradual approach
   - Move small chunks
   - Verify each step
   - Rollback if needed

4. Automate
   - Use built-in tools
   - Script common operations
   - Document procedures