Database Sharding

When One Database Isn't Enough

When your database exceeds the capacity of a single server (as shown by measured storage, throughput, or latency constraints), you have two choices:

1. Vertical Scaling: Buy a bigger machine (more RAM, CPU). Simple but hits a hardware ceiling.
2. Horizontal Scaling (Sharding): Split data across smaller machines. More aggregate capacity, with coordination and shared-resource limits.

What is Sharding?

Sharding is horizontal partitioning for databases. You split a large table (e.g., Users with 100 million rows) into smaller chunks called Shards. Each shard lives on a separate database server and holds a subset of the data.

• Shard 1: Users ID 0-10,000,000
• Shard 2: Users ID 10,000,001-20,000,000
• Shard 3: Users ID 20,000,001-30,000,000

Each shard is a fully functional database with its own indexes, query engine, and storage.

Sharding Strategies

1. Key-Based (Hash) Sharding

Formula: ShardID = hash(UserID) % NumShards.

• Pros: Even distribution of data. A good hash balances keys but cannot prevent a single extremely popular key from becoming hot.
• Cons: Adding servers requires re-sharding (moving data). Consistent Hashing reduces expected movement but does not remove migration and cutover work.

import hashlib

def get_shard(user_id: int, num_shards: int) -> int:
    """Determine which shard a user belongs to."""
    key = str(user_id).encode()
    hash_value = int(hashlib.sha256(key).hexdigest(), 16)
    return hash_value % num_shards

# User 12345 -> Shard 2 (out of 4 shards)
print(f"Shard: {get_shard(12345, 4)}")

2. Range-Based Sharding

Formula: if ID < 10,000,000 -> Shard 1. if ID < 20,000,000 -> Shard 2.

• Pros: Excellent for range queries (SELECT * WHERE ID BETWEEN 100 AND 200 hits only one shard).
• Cons: Hotspots. If you shard by creation_date, all new users go to the latest shard, causing it to become a bottleneck while older shards sit idle.

3. Directory-Based Sharding

A lookup table (service) tells you where data is.

• UserID 123 -> Shard A
• UserID 999 -> Shard B
• Pros: Extremely flexible. Can move individual users between shards for rebalancing.
• Cons: The lookup table becomes a Single Point of Failure (SPOF) and a performance bottleneck. Must be cached and replicated.

4. Geo-Based Sharding

Data is partitioned by geographic region.

• US users -> us-east-1 shard
• EU users -> eu-west-1 shard
• Pros: Low latency for users (data is close to them). Can support a chosen locality policy; legal compliance depends on more than region placement.
• Cons: Uneven distribution if one region has more users. Cross-region queries are expensive.

Challenges of Sharding

1. Cross-Shard Joins

You can't easily join tables across different servers. If User #123 is on Shard A and their Orders are on Shard B, a JOIN users, orders query can't run locally.

Solutions:

• Denormalization: Duplicate data so each shard has everything it needs. Store a copy of user info alongside each order.
• Application-level joins: Fetch User from Shard A, then fetch Orders from Shard B, then merge in application code.
• Shared dimension tables: Keep small, frequently-joined tables (countries, categories) replicated on every shard.

2. Distributed Transactions (ACID)

Committing a transaction across Shard A and Shard B is hard. Two-Phase Commit (2PC) is slow and reduces availability.

Solutions:

• Avoid cross-shard transactions: Design your data model so that related data co-locates on the same shard. For example, store a User and all their Orders on the same shard by sharding on user_id.
• Saga Pattern: Replace a distributed transaction with a sequence of local transactions, each with a compensating action for rollback.
• Use a distributed database: CockroachDB and Google Spanner support distributed ACID transactions natively.

3. Unique IDs

Auto-increment IDs don't work across multiple servers — two shards could both assign ID 1001.

Solutions:

• Snowflake IDs: Timestamp + MachineID + SequenceNumber produces globally unique, sortable IDs.
• UUID v4: Random 128-bit IDs. No coordination needed, but not sortable.
• Custom ID ranges: Shard 1 uses IDs starting at 1,000,000, Shard 2 at 2,000,000.
• See Unique ID Generation for deep dive.

4. Rebalancing

When one shard grows disproportionately (hotspot) or you need to add capacity, you must move data between shards.

Approaches:

• Pre-split: Create more shards than servers initially. Assign multiple shards per server. To scale, move entire shards to new servers without splitting.
• Consistent Hashing: Minimizes data movement when adding/removing nodes.
• Online resharding: Tools such as Vitess copy and replicate data before a controlled routing cutover. This is different from schema migration and still requires validation and a recovery plan.

Real-World Examples

Instagram

Instagram's published historical design describes PostgreSQL logical shards and IDs containing a shard component. Treat that engineering account as a dated design example, not a current inventory of every Instagram datastore.

Vitess (YouTube)

Vitess is an open-source sharding middleware built by YouTube. It sits between your application and MySQL, transparently routing queries to the correct shard. It handles shard splitting, schema migrations, and query routing.

CockroachDB

CockroachDB automatically shards data across nodes using range-based partitioning. It handles shard splitting, rebalancing, and distributed transactions transparently — no manual sharding logic needed.

Interview Tips 💡

1. Delay sharding: "I'd start with read replicas and caching before sharding. Sharding is a last resort due to its operational complexity."
2. Choose the right shard key: "The shard key should have high cardinality, even distribution, and align with query patterns. Sharding by user_id is common because most queries are user-scoped."
3. Address joins proactively: "I'd co-locate related data on the same shard. For cross-shard queries, I'd use denormalization or materialized views."
4. Mention re-sharding: "I'd start with more logical shards than physical servers, so scaling means moving shards — not splitting them."

Comparison Summary

Related Concepts

• Consistent Hashing — Minimizes data movement when adding nodes
• CAP Theorem — Trade-offs introduced by distributing data
• Database Indexing — Indexes within each shard
• Database Replication — Each shard should be replicated for durability
• Unique ID Generation — Generating unique IDs across shards

Sources and a design check

Vitess resharding describes the migration workflow. The CockroachDB replication architecture describes replicated ranges. Test your shard key against the largest tenant and most frequent query: equal row counts do not imply balanced request cost.