Database Sharding¶

Prerequisites: Consistent Hashing

Why This Exists¶

A single database server has physical limits: disk I/O bandwidth, CPU for query processing, memory for buffer pool, network bandwidth. When your write throughput exceeds what one node can handle, you need to scale writes horizontally — sharding.

Sharding = splitting data across multiple database instances based on a shard key.

Mental Model¶

Single DB (vertical limit):         Sharded (horizontal):
┌─────────────────┐                 ┌──────┐ ┌──────┐ ┌──────┐
│   All 100M      │                 │ 33M  │ │ 33M  │ │ 34M  │
│   Users         │        →        │Users │ │Users │ │Users │
│   (1 server)    │                 │Shard0│ │Shard1│ │Shard2│
└─────────────────┘                 └──────┘ └──────┘ └──────┘

Abstraction Levels¶

Sharding Strategies¶

1. Range-Based Sharding¶

Shard 0: user_id 1 – 33,333,333
Shard 1: user_id 33,333,334 – 66,666,666
Shard 2: user_id 66,666,667 – 100,000,000

Pros: Range queries efficient, easy to reason about Cons: Uneven load if recent users are more active (new users go to shard 2 only → hot shard)

2. Hash-Based Sharding¶

shard_id = hash(user_id) % num_shards
# user_id=1 → shard 0
# user_id=2 → shard 2
# user_id=3 → shard 1

Pros: Even distribution Cons: Range queries require scatter-gather; resharding expensive (use consistent hashing)

3. Directory-Based Sharding¶

Lookup table: user_id → shard_id stored in a separate service.

Pros: Flexible, can move data between shards without changing shard key logic Cons: Lookup service is a bottleneck and single point of failure

Architecture¶

graph TD
    App[Application] --> SR{Shard Router}
    SR -->|user_id % 3 = 0| S0[(Shard 0)]
    SR -->|user_id % 3 = 1| S1[(Shard 1)]
    SR -->|user_id % 3 = 2| S2[(Shard 2)]
    S0 --> R0[(Replica 0)]
    S1 --> R1[(Replica 1)]
    S2 --> R2[(Replica 2)]

Interactive Simulation¶

Four hash shards. Run write load, then Hot key 70% — consistent hashing cannot save a celebrity user_id. Toggle Traffic: uniform → skewed to see a milder, more realistic customer-distribution imbalance (a Pareto-ish spread across customers, not one celebrity key) — notice it degrades shard balance without ever tripping the single-hot-key alarm. Add a shard to see modular hash remap everything; Reshard simulates the even cutover you wish you had.

Choosing a Shard Key¶

Good shard keys: - High cardinality (many distinct values) - Even distribution (no hot values) - Used in most queries (avoid cross-shard queries) - Stable (doesn't change after record creation)

Poor shard keys: - user_country — uneven distribution (US >> all others) - created_at — range hot shard problem - status — low cardinality (active vs inactive)

Examples: - E-commerce: user_id → all orders for a user on one shard - Multi-tenant SaaS: tenant_id → all data for a tenant on one shard - Time-series: (device_id, timestamp_bucket) → device data co-located

Problems with Sharding¶

Cross-Shard Queries¶

-- This requires querying all shards and merging results:
SELECT * FROM orders WHERE total > 1000 AND created_at > '2024-01-01'
-- Solution: denormalize, use a separate reporting DB (not sharded), or accept scatter-gather

Hot Shard¶

One shard receives disproportionate traffic (e.g., one large tenant, one viral product).

Detection: Per-shard CPU/IOPS metrics diverge significantly Fix: Shard splitting, move hot tenant to dedicated shard, application-level caching

Resharding¶

Adding new shards requires moving data. With consistent hashing, only K/N keys move. With modular hashing, almost everything moves.

Zero-downtime resharding: 1. Dual-write to old and new shard 2. Backfill data to new shard 3. Validate consistency 4. Switch reads to new shard 5. Remove old shard

Distributed Transactions¶

A transaction touching data on multiple shards requires a distributed transaction protocol (2PC) — complex, slow, and failure-prone.

Better solution: Design shard key so related data is co-located (no cross-shard transactions). See Sagas when a business flow must touch two shards anyway.

Production Debugging¶

Symptom: One shard's CPU is 90%, others 20%. p99 only for some users.

1. Per-shard QPS, CPU, IOPS, replication lag
   → if one shard: hot key or bad range. if all: you need more shards or bigger boxes.
2. Top keys / tenants by request rate
   → celebrity user_id, one tenant, one viral SKU
3. Router metrics: scatter-gather fan-out
   → a missing shard key in the WHERE clause
4. After a reshard: dual-write mismatch rate
   → checksum row counts and sampled hashes
5. Cross-shard TX failures / 2PC coordinator logs
   → you accidentally coupled two user_ids in one checkout

Metrics: qps{shard}, cpu{shard}, rows{shard}, scatter_queries, reshard_lag, hot_key_share.

Scaling Limits¶

• Modular hash % N is fine until the first reshard. Plan consistent hashing or a directory before you are on fire.
• A single hot key is a vertical problem; more shards do not help.
• Cross-shard joins at request time will not survive 50 shards. Reporting belongs on a warehouse.
• Practical primary count: dozens is routine; hundreds needs automation for schema, backups, and failover.

Trade-offs¶

Interview Questions¶

Key Takeaways¶