Database Sharding & Partitioning

Why Sharding Exists

A single database node has hard limits: CPU, RAM, disk I/O, and network throughput. Vertical scaling (bigger machine) eventually hits diminishing returns and cost ceilings. Sharding — also called horizontal partitioning — distributes data across multiple nodes (shards), each owning a subset of the dataset. The total capacity grows linearly with the number of shards.

Vertical vs Horizontal Partitioning

Sharding Strategies

Range-Based Sharding

Rows are assigned to shards based on a contiguous range of the shard key. Example: shard 1 holds `user_id` 1–1,000,000, shard 2 holds 1,000,001–2,000,000, and so on. Range queries are efficient because they only touch one or a few consecutive shards.

Hash-Based Sharding

Apply a hash function to the shard key and assign `hash(key) % num_shards` to determine the target shard. This distributes data uniformly regardless of key distribution, eliminating hot spots from sequential keys. The downside: range queries require scatter-gather across all shards because adjacent keys hash to different shards.

def get_shard(user_id: int, num_shards: int) -> int:
    return hash(user_id) % num_shards

# user_id=1   → shard 1
# user_id=2   → shard 3
# user_id=3   → shard 0
# Keys are scattered — no hot spots, but no range locality

Directory-Based Sharding

A lookup service (the shard directory) maintains a mapping from key to shard. This provides maximum flexibility — you can move individual keys between shards without rehashing. The cost is an extra network hop and a single point of failure if the directory is unavailable.

Choosing a Shard Key

The shard key is the most consequential architectural decision when sharding. A bad shard key causes hot spots, expensive cross-shard queries, or both. A good shard key has three properties:

1. High cardinality: Many distinct values so data distributes across shards evenly (not `country_code` with only 200 values).
2. Low correlation with write patterns: Avoid monotonically increasing keys (auto-increment IDs) for hash sharding, as they create temporal hot spots for range sharding.
3. Query alignment: The shard key should match your most frequent access pattern. If 90% of queries filter by `tenant_id`, shard by `tenant_id`.

Rebalancing Shards

When you add shards, existing data must be redistributed — a process called rebalancing. Naive hash sharding (`hash % n`) is catastrophic to rebalance: changing `n` from 4 to 5 remaps ~80% of all keys, requiring a massive data migration.

Consistent hashing solves this. Keys and nodes are mapped onto a ring. When a node is added, only the keys between the new node and its predecessor move — typically `1/n` of the total data. This is how DynamoDB, Cassandra, and Riak handle rebalancing.

Cross-Shard Queries and Joins

The biggest operational pain with sharding is cross-shard queries. A query like `SELECT * FROM orders WHERE status = 'pending'` must be broadcast to all shards (scatter), results collected (gather), and merged. This is slow, expensive, and complex. Design your schema to avoid cross-shard queries on hot paths by keeping related data on the same shard.