Sharding: Splitting Data Across Machines

📘 Chapter 4: Databases & Storage ⏱️ 10 min read 🏗️ Lesson 017

Replication helps with read scalability — but every replica still holds all the data and every write still goes to one leader. When you have more data than fits on one machine, or more writes than one machine can handle, you need to shard: split the data horizontally across multiple databases.

When Replication Isn't Enough

Replication's Limits

  • Write bottleneck — All writes still go to one leader node. You can't scale writes with more replicas.
  • Dataset size — 10TB of data means every replica needs 10TB of storage. Adding replicas doesn't reduce per-node storage.
  • Memory pressure — If your working set exceeds one machine's RAM, you get constant disk I/O regardless of replica count.

What Is Sharding?

Sharding (also called partitioning) splits your table's rows across multiple databases. Each shard holds a subset of the data. Together, all shards hold the complete dataset.

Sharding by user_id % 4 users (all data) user_id=1, Alice user_id=2, Bob user_id=3, Carol user_id=4, Dave user_id=5, Eve user_id=6, Frank user_id=7, Grace user_id=8, Hank user_id=9, Ivy user_id=10, Jack ... → shard key: user_id % 4 Shard 0 (mod=0) 4: Dave 8: Hank 12: ... Shard 1 (mod=1) 1: Alice 5: Eve 9: Ivy Shard 2 (mod=2) 2: Bob 6: Frank 10: Jack Shard 3 (mod=3) 3: Carol 7: Grace 11: ... ✅ Each shard handles ~25% of writes • ✅ Each shard stores ~25% of data ✅ Queries for one user hit only one shard • ✅ Add more shards = more capacity Challenges: ❌ "Find all users named Alice" → must query ALL shards (scatter-gather) ❌ JOINs across shards are impossible or very expensive ❌ Adding a 5th shard means redistributing ~80% of data (resharding)
Hash-based sharding distributes rows evenly but makes cross-shard queries expensive.

Shard Key Selection

The shard key is the most critical decision. It determines which shard a row lives on, and therefore what queries are efficient.

Good Shard Key Properties

  • Even distribution — All shards get roughly equal data and traffic. No hotspots.
  • Matches query patterns — If you always query by user_id, shard by user_id. Queries stay on one shard.
  • High cardinality — Many distinct values (user_id ✅, country ❌ — 200 values isn't enough).
  • Immutable — If the shard key changes, the row must move between shards. Use IDs, not mutable fields.

Sharding Strategies

Strategy How It Works Pros Cons
Hash-based hash(key) % N Even distribution Range queries scatter, resharding is expensive
Range-based A-M on shard 1, N-Z on shard 2 Range queries stay on one shard Hotspots if data isn't uniform (most names start with S)
Directory-based Lookup table maps key → shard Flexible, easy to rebalance Lookup table is a bottleneck/SPOF

Consistent Hashing

A better approach for hash-based sharding: consistent hashing. Instead of hash % N (which breaks when N changes), place both nodes and keys on a ring.

Consistent Hashing Ring N1 Node 1 N2 Node 2 N3 Node 3 key_A → N1 key_B → N2 key_C → N3 key_D → N2 clockwise → Each key goes to the next node clockwise. Adding/removing a node only moves ~1/N of keys.
Consistent hashing: keys walk clockwise to find their node. Adding Node 4 only moves keys between N4's neighbors — not all keys.

The Challenges of Sharding

What Gets Hard

  • Cross-shard queries — "SELECT * FROM users ORDER BY created_at" now requires querying all shards, merging, and sorting results.
  • Resharding — When you need to add shards (growth) or remove them (cost), data must move. This can take hours/days.
  • Hotspots — A celebrity's data shard gets 1000x more traffic than others. Even good hash functions can't prevent temporal hotspots.
  • Referential integrity — Foreign keys can't span shards. Application must enforce data consistency.
  • Transactions — ACID across shards requires distributed transactions (2PC), which are slow and complex.

Instagram: Sharding by User ID

Instagram shards their PostgreSQL databases by user_id. This works brilliantly for individual user feeds (all a user's photos are on one shard). But when they needed to build "Explore" — which queries across all users — they had to:

  • Build a separate aggregation pipeline that reads from all shards
  • Maintain denormalized data in a search index (Elasticsearch)
  • Accept that cross-shard features have higher latency

Lesson: Your shard key optimizes for one access pattern. Every other pattern gets harder.

Discord: Sharding by Guild ID

Discord shards messages by guild_id (server ID). This means:

  • ✅ All messages in a server are on one shard — channel history is fast
  • ✅ Each shard handles a subset of servers — even load distribution
  • ❌ DMs (direct messages) span guilds — they need a separate sharding strategy
  • ❌ Large servers (millions of members) become hot shards — Discord handles this with further sub-sharding

They use Cassandra for messages — which has built-in hash-based partitioning — and ScyllaDB for improved tail latencies.

Interactive: Shard Key Analyzer

Try different shard keys on sample data. See how evenly (or unevenly) data distributes across 4 shards. Watch for hotspots!

Shard key: