Database Sharding

Why This Comes Up in Every Design Interview

When you say "I'll use PostgreSQL" in an interview, the natural follow-up is: "What happens at 100M users? 1B rows? 50K writes/sec?" The answer is sharding. Interviewers specifically test:

• Can you identify WHEN to shard (not too early, not too late)
• Can you choose a shard key that avoids hotspots
• Do you understand the problems sharding creates (joins, transactions, resharding)
• Can you reason about alternatives before jumping to sharding

The Scaling Staircase — Shard LAST, Not First

Interview gold: "I'd exhaust vertical scaling, read replicas, and caching before sharding. Sharding adds enormous complexity — cross-shard queries, distributed transactions, resharding operations. But when a single machine can't handle the write throughput or data volume, it's the only option."

Back-of-Envelope: When to Shard

PostgreSQL practical limits on a single instance (~$20K/month machine):

Example calculation: Social media platform, 500M users, 5 posts/user/day:

Choosing a Shard Key (The Most Critical Decision)

The shard key determines everything: query routing, data distribution, hotspot risk. Once chosen, it's extremely expensive to change.

Properties of a good shard key:

How to evaluate a shard key — the scatter/gather test:

• "What % of my queries can be answered by a single shard?"
• Target: >95% single-shard queries
• If most queries need ALL shards (scatter-gather), your key is wrong

Sharding Strategies Compared

Hash-Based Sharding

shard = hash(user_id) % num_shards

When: Even distribution is priority, access is by primary key.

Range-Based Sharding

Shard 1: user_id 1 - 1M
Shard 2: user_id 1M - 2M
...

When: Data is naturally ordered and range queries are important (time-series, analytics).

Directory-Based Sharding

When: Need flexibility, or combining strategies (move hot users to dedicated shards).

Compound Shard Keys (DynamoDB Pattern)

Problem: You need both even distribution AND range queries within an entity.

Solution: Compound key = Partition Key (hash distribution) + Sort Key (range within partition)

Why this works: All data for one entity (user, order, conversation) lives on the same shard. Range queries work within-shard. No scatter-gather needed.

The Hard Problems Sharding Creates

1. Cross-Shard Queries (Scatter-Gather)

Problem: "Show all orders over $100 across all users"

• Must query EVERY shard, merge results
• Latency = slowest shard
• Can't use DB-level sorting/pagination across shards

Mitigations:

• Denormalize: duplicate data to enable single-shard queries
• Secondary index service: Elasticsearch indexes all data for complex queries
• Materialized views: Pre-compute aggregates

2. Cross-Shard Transactions

Problem: Transfer money from user on Shard 1 to user on Shard 3

• No single DB transaction spans shards
• Need distributed transaction (2PC) or eventual consistency

Mitigations:

3. Resharding (Adding Shards)

Problem: Started with 10 shards, now need 20. With hash % N, ALL keys remap.

Solutions:

4. Unique Constraints Across Shards

Problem: "Email must be unique globally" but data is on different shards.

Solutions:

• Global unique index (separate service/table)
• Shard by the unique field (email)
• UUIDs instead of sequences (guaranteed unique without coordination)
• Snowflake IDs (Twitter): timestamp + machine_id + sequence = unique + sortable

5. JOINs Across Shards

Problem: SELECT * FROM orders JOIN users ON... when orders and users on different shards.

Solutions:

• Denormalize: Store user_name in orders table (duplicate data)
• Application-level join: Fetch from both shards, join in code
• Co-locate: Shard orders by user_id too (same shard)
• Separate analytics DB: ETL into data warehouse for complex queries

Real-World Sharding Examples

Logical vs Physical Shards (Pinterest/Uber Pattern)

The trick: Don't map keys directly to physical machines. Add an indirection layer.

Step 1: key → logical_shard_id (hash % 8192)
Step 2: logical_shard_id → physical_machine (lookup table)

Why:

• Start with 8192 logical shards on 4 physical machines (2048 logical per physical)
• Need more capacity? Move 1024 logical shards to a new machine
• No key remapping, no data copying logic change
• Just update the mapping table

Pinterest's approach: Started with 8192 logical shards. Currently mapped to ~150 physical database instances. Never needed to rehash.

Interview Framework

When the interviewer asks about scaling your database:

Step 1 — Delay sharding: "First I'd add read replicas for read-heavy queries and a cache layer. This gets us to [X] scale without sharding complexity."

Step 2 — When to shard: "Once we exceed [single-machine write capacity / storage], I'd introduce sharding. For this system, that's around [Y] users / [Z] writes/sec."

Step 3 — Shard key choice: "I'd shard by [user_id/merchant_id/entity_id] because [95%+ of queries are per-entity, it's immutable, high cardinality, evenly distributed]."

Step 4 — Strategy: "I'd use [hash-based with consistent hashing / logical shards mapped to physical] so resharding doesn't require data rehashing."

Step 5 — Address hard problems: "For cross-shard queries, I'd [denormalize / use Elasticsearch]. For distributed transactions, I'd use the [saga pattern / co-locate]. For unique constraints, [global index / UUID]."

Quick Recall