Sharding & Partitioning

7 min read

In a Nutshell

When a single database machine can't hold your data or handle your traffic, you split the data across multiple machines. Partitioning is the general concept of dividing a dataset into smaller pieces. Sharding is horizontal partitioning across separate database instances — each shard holds a subset of the rows and runs on its own server. The shard key determines which shard holds which data. Choose well (high cardinality, even distribution, matches query patterns) and your system scales linearly. Choose poorly (low cardinality, skewed distribution) and you get hot shards, cross-shard queries, and uneven growth. Sharding is the most impactful and most painful scaling decision you'll make.

2D minimalistic diagram showing a single large database on the left, an arrow labeled "shard by user_id", and four smaller database boxes on the right, each labeled with a range of user IDs (1-25M, 25M-50M, etc.), with a router box directing queries to the correct shard

How It Actually Works

Partitioning vs Sharding

Term	What It Means	Example
Vertical Partitioning	Split columns across tables (each table has different columns for the same entity)	Move `user_bio` and `user_avatar` to a `user_profiles` table
Horizontal Partitioning	Split rows across partitions within the same database	PostgreSQL table partitioned by `created_at` month
Sharding	Split rows across separate database instances	Users 1–25M on Shard 1, 25M–50M on Shard 2

Sharding Strategies

Range-Based Sharding

Assign rows to shards based on a range of the shard key.

Shard 1: user_id    1 — 25,000,000
Shard 2: user_id    25,000,001 — 50,000,000
Shard 3: user_id    50,000,001 — 75,000,000
Shard 4: user_id    75,000,001 — 100,000,000

Pros	Cons
Simple to understand and implement	Uneven distribution if ranges are skewed
Range queries on the shard key are efficient	New users always hit the latest shard (hot shard)
Easy to split/merge ranges	Time-based keys create write hotspots

Hash-Based Sharding

Hash the shard key, mod by the number of shards.

shard = hash(user_id) % num_shards

Pros	Cons
Even distribution regardless of key pattern	Range queries require hitting all shards
No hot shard from sequential inserts	Adding/removing shards requires rehashing (mitigated by consistent hashing)
Simple computation

Directory-Based Sharding

A lookup service maintains the mapping from key to shard.

Pros	Cons
Maximum flexibility (any key → any shard)	Lookup service is a single point of failure
Easy to move individual keys between shards	Extra network hop for every query
Can handle uneven data sizes by rebalancing	Directory must be highly available

Consistent Hashing

Standard hash-based sharding breaks when you add or remove shards — every key gets reassigned. Consistent hashing minimizes redistribution: only ~1/n of the keys move when a shard is added or removed.

Hash ring (0 to 2^32):

    Shard A       Shard B       Shard C
      ↓             ↓             ↓
  ────●─────────────●─────────────●────
  0   ^             ^             ^    2^32
      Keys in       Keys in       Keys in
      [A, B)        [B, C)        [C, A)

Adding Shard D between B and C:
  ────●──────●──────●──────●──────────
      A      D      B      C
  Only keys in [B, D) move to D — everything else stays

What Breaks When You Shard

Challenge	Why It's Hard
Cross-shard joins	Joining data across shards requires reading from multiple databases and assembling in application code
Cross-shard transactions	ACID across shards requires distributed transactions (2PC) — slow and complex
Auto-increment IDs	Each shard has its own sequence — IDs collide. Use UUIDs, Snowflake IDs, or a central ID service
Aggregations	`COUNT(*)`, `AVG()`, `ORDER BY` across all data requires scatter-gather from all shards
Schema changes	Every shard needs the migration — coordinate or face inconsistency
Rebalancing	When one shard grows too large, moving data is operationally complex
Operational overhead	N shards = N database instances to monitor, backup, upgrade

2D minimalistic diagram showing a query that requires data from multiple shards: a request enters a router, fans out to three shards with parallel arrows, results merge back at the router, labeled "scatter-gather" with a note about increased latency

Seeing It in Action

Scenario: Sharding a messaging platform (1B users, 50B messages/day)

Shard key: conversation_id (hash-based)

Why conversation_id:
  ✅ All messages in a conversation are on the same shard
     → "get messages for conversation X" is a single-shard query
  ✅ Conversations are roughly equal size → even distribution
  ✅ No cross-shard joins for the primary query pattern

Why NOT user_id:
  ❌ A user participates in many conversations across different shards
     → "get all conversations for user X" requires scatter-gather
  ❌ Celebrity users with millions of messages create hot shards

Architecture:
┌──────────┐
│  Client   │
└─────┬────┘
      │
┌─────▼──────┐     ┌───────────┐
│   Router    │────▶│ Shard Map │ (conversation_id → shard_id)
│ (Shard-Aware)│    │  (Redis)  │
└──┬──┬──┬───┘     └───────────┘
   │  │  │
   │  │  └──▶ Shard 3: conversations C
   │  └─────▶ Shard 2: conversations B
   └────────▶ Shard 1: conversations A

Handling the "user's conversations" query:

Maintain a separate lookup table: user_conversations(user_id, conversation_id, shard_id)
This table can live in a non-sharded database or be sharded by user_id
Trade-off: denormalization (write amplification on conversation creation)

Interview Questions

Q: How do you choose a shard key? What criteria matter? Hint: High cardinality (many distinct values), even distribution (no hot shards), aligns with primary query pattern (queries hit one shard, not scatter-gather). For a messaging app: conversation_id. For an e-commerce app: user_id. For a multi-tenant SaaS: tenant_id. Avoid time-based keys (all writes hit latest shard).
Q: What is consistent hashing, and why is it important for sharding? Hint: Standard modular hashing (hash(key) % N) reassigns nearly all keys when N changes. Consistent hashing places shards on a ring — adding/removing a shard only moves ~1/N of keys. This minimizes data migration when scaling. Used by DynamoDB, Cassandra, and many in-house sharding systems.
Q: How do you handle cross-shard queries in a sharded database? Hint: Scatter-gather: send the query to all shards, merge results in application code. For aggregations (COUNT, SUM), each shard returns its partial result and the coordinator combines them. For ORDER BY ... LIMIT, each shard returns its top-K and the coordinator re-sorts. Cross-shard queries are inherently slower — design the shard key to minimize them.
Q: Your sharded database has one shard that's 3× larger than the others. What do you do? Hint: This is a hot shard / skewed distribution. Options: 1) Split the large shard into two (range split). 2) Reshard with a better key. 3) Use consistent hashing with virtual nodes for more even distribution. 4) For hash-based, check if the hash function is distributing well. Prevention: monitor shard sizes proactively and set alerts.
Q: When should you NOT shard your database? Hint: When a single instance handles the load (vertical scaling, read replicas, and caching haven't been exhausted). Sharding adds enormous complexity — cross-shard joins, distributed transactions, operational overhead. Many applications with millions of users run fine on a single PostgreSQL with read replicas. Only shard when you've genuinely hit the limits of a single instance.

References

Designing Data-Intensive Applications by Martin Kleppmann — Chapter 6: Partitioning
Consistent Hashing — Tom White — clear explanation with implementation
Vitess — YouTube's MySQL sharding layer, now open source

Dive Deeper

Instagram's Sharding Strategy — how Instagram generates IDs and shards PostgreSQL
Stripe's Approach to Online Migration — migrating data between shards without downtime
PlanetScale (Vitess) — managed MySQL with built-in horizontal sharding