Sharding Strategies

How do you decide which shard holds which data? That's where sharding strategies come in. The strategy you choose affects query performance, data distribution, and operational complexity.

There are three main approaches:

Hash-Based Sharding

The most common approach. Apply a hash function to the shard key, then use modulo to determine the shard.

def get_shard(user_id, num_shards):
    # Hash the key for even distribution
    hash_value = hash(user_id)
    return hash_value % num_shards

# Examples with 4 shards
get_shard(12345, 4)  # hash(12345) % 4 = ?
get_shard(67890, 4)  # hash(67890) % 4 = ?

How It Works

User ID: 12345
         │
         ▼
   hash(12345) = 8234567891
         │
         ▼
   8234567891 % 4 = 3
         │
         ▼
      Shard 3

The Resharding Problem

What happens when you add a 5th shard to a 4-shard cluster?

# Before: 4 shards
user_12345: hash % 4 = 3 → Shard 3

# After: 5 shards
user_12345: hash % 5 = 1 → Shard 1  # MOVED!

Range-Based Sharding

Assign data to shards based on value ranges. Common for time-series data or alphabetical ordering.

def get_shard_by_range(created_date):
    if created_date < "2023-01-01":
        return "shard_2022"
    elif created_date < "2024-01-01":
        return "shard_2023"
    else:
        return "shard_2024"

# Or by user ID ranges
def get_shard_by_id_range(user_id):
    if user_id < 1_000_000:
        return "shard_1"
    elif user_id < 2_000_000:
        return "shard_2"
    else:
        return "shard_3"

How It Works

┌─────────────────────────────────────────────────────┐
│                     User IDs                        │
├───────────────┬───────────────┬───────────────┬─────┤
│    0 - 1M     │   1M - 2M     │   2M - 3M     │ ... │
│   Shard 1     │   Shard 2     │   Shard 3     │     │
└───────────────┴───────────────┴───────────────┴─────┘

User 500,000  → Shard 1
User 1,500,000 → Shard 2
User 2,500,000 → Shard 3

The Hotspot Problem

Range-based sharding can create hotspots when access patterns aren't uniform:

Directory-Based Sharding

Use a separate lookup service to track which shard holds each key (or key range).

# Lookup table (could be in Redis, DB, etc.)
shard_directory = {
    "user_1": "shard_A",
    "user_2": "shard_B",
    "user_3": "shard_A",
    # ... millions of entries
}

def get_shard(user_id):
    return shard_directory.get(user_id)

How It Works

┌─────────────┐     ┌──────────────────┐
│   Client    │────▶│  Lookup Service  │
└─────────────┘     │  (Directory)     │
                    │                  │
                    │  user_1 → shard_A│
                    │  user_2 → shard_B│
                    │  user_3 → shard_A│
                    └────────┬─────────┘
                             │
         ┌───────────────────┼───────────────────┐
         ▼                   ▼                   ▼
    ┌─────────┐         ┌─────────┐         ┌─────────┐
    │ Shard A │         │ Shard B │         │ Shard C │
    └─────────┘         └─────────┘         └─────────┘

Strategy Comparison

*Consistent hashing solves the rehashing problem (covered in lesson 4)

Real-World Examples

MongoDB: Hash + Range

MongoDB supports both strategies and lets you choose based on your use case:

// Hash-based sharding (even distribution)
sh.shardCollection("mydb.users", { user_id: "hashed" })

// Range-based sharding (range queries)
sh.shardCollection("mydb.logs", { timestamp: 1 })

Vitess (YouTube's MySQL Sharding)

YouTube uses Vitess for sharding MySQL. It combines approaches:

Cassandra: Consistent Hashing

Apache Cassandra uses a token ring with consistent hashing:

-- Cassandra partition key (shard key)
CREATE TABLE users (
    user_id UUID PRIMARY KEY,
    name TEXT,
    email TEXT
);
-- user_id is hashed to determine which node stores the data

Choosing a Strategy

Key Takeaways

Next up: Shard Key Selection - The most critical decision in your sharding design.