Database Sharding Explained: Strategies, Shard Keys & Resharding

Sharding is the point in a system's life where "just add a bigger database" stops working. It is also one of the most misunderstood topics in system design interviews: candidates say "we will shard the database" as a magic phrase, without saying by what key, what happens to queries that do not include that key, or how they will add shards later. This guide covers all of that with concrete examples.

What Database Sharding Is (vs Partitioning and Replication)

Three terms get mixed up, so let us separate them:

• Replication copies the same data to multiple servers. Read replicas spread read load and provide failover, but every write still goes to one primary, and every replica stores the full dataset.
• Partitioning splits a table into pieces. Vertical partitioning splits columns (move the big profile_json column to another table). Horizontal partitioning splits rows (orders from 2025 in one partition, 2026 in another). Postgres declarative partitioning does this within one server.
• Sharding is horizontal partitioning across servers. Each shard is an independent database (usually with its own replicas) holding a disjoint subset of rows.

Real systems combine all three: shard for write and storage scale, replicate each shard for availability and read scale, and partition within a shard by time for easy archival.

Do You Actually Need to Shard? Exhaust These First

Sharding has permanent costs in complexity, so the right first answer in both production and interviews is "not yet, unless the numbers say so". Before sharding, teams typically go through:

1. Query and index tuning. Many "the database can't keep up" problems are missing indexes or N+1 queries. See database indexing explained.
2. Caching. A Redis cache in front of hot reads can cut database load dramatically.
3. Read replicas. Route reads that tolerate slight staleness to replicas.
4. Vertical scaling. Cloud instances with dozens to hundreds of vCPUs and hundreds of GB to multiple TB of RAM exist. Expensive, but cheaper than an engineering team's year.
5. Archiving and partitioning. Move cold data (orders older than 2 years) out of the hot table.
6. Functional split. Move different domains (payments, catalogue, notifications) to separate databases. This is often the first "sharding" a company does, and it comes naturally with microservices.

You shard when, after those steps, one of these remains true: write throughput exceeds what one primary can sustain, the dataset no longer fits comfortably on one machine's storage (or makes backups, restores and schema changes take too long), or the blast radius of one database failure is unacceptable.

Back-of-envelope: when does a ride-hailing trips table need sharding?

Assume 20 million trips per day, each generating a trip row (1 KB) plus ~50 location/status updates stored as 200-byte rows. (Numbers are illustrative; see back-of-the-envelope estimation for the method.)

• Writes: 20M × 51 ≈ 1 billion rows/day ≈ 11,800 writes/sec average; peak maybe 3x ≈ 35,000/sec.
• Storage: 20M × 1 KB + 1B × 200 B ≈ 220 GB/day ≈ 80 TB/year before indexes and replication.

Tens of thousands of sustained writes per second, and tens of terabytes per year, is past the comfortable range of a single relational primary. That justifies sharding (or a distributed database built for it). By contrast, a SaaS app with 50,000 customers and 200 writes/sec does not need to shard. Saying this out loud in an interview is a strong signal.

Sharding Strategies: Range vs Hash vs Directory (and Geo)

1. Range-based sharding

Each shard owns a contiguous key range: users A–F on shard 0, G–M on shard 1, and so on, or order IDs 0–10M, 10M–20M. The router keeps a small table of range boundaries.

• Pros: range scans (WHERE created_at BETWEEN ..., "all users starting with S") hit one or a few shards. Splitting a big range into two is natural. HBase, Bigtable, and CockroachDB/TiDB (which split ranges automatically) work this way.
• Cons: uneven distribution and write hotspots. If the key is a timestamp or auto-increment ID, every new row goes to the last range. One shard does all the writes while the others sit idle.

2. Hash-based sharding

Compute hash(key) and map it to a shard. The naive version is hash(key) % N.

• Pros: even spread of data and load, no sequential-key hotspots, the router needs no lookup table.
• Cons: range queries on the key become scatter-gather across all shards. And with % N, changing N remaps almost every key: going from 4 to 5 shards moves about 80% of the data.

The fix for the second problem is either consistent hashing (keys and nodes on a hash ring; adding a node moves only ~1/N of keys, with virtual nodes to smooth the distribution, as in Cassandra and DynamoDB) or, more commonly in SQL sharding, a fixed large number of logical shards:

LOGICAL_SHARDS = 1024                       # fixed forever
logical = murmur3(user_id) % LOGICAL_SHARDS # stable for life of the key
physical = shard_map[logical]               # 1024 entries -> e.g. 8 DB clusters

You start with 1,024 logical shards on 8 physical clusters (128 each). To scale, move some logical shards to new clusters and update shard_map. No key ever changes its logical shard, so you never rehash. Vitess's keyspace ID ranges, Citus's shard count, and the "many small databases per host" approach used by companies like Pinterest and Notion (as described in their engineering blogs) are variations of this idea.

3. Directory-based (lookup) sharding

A lookup service stores an explicit mapping: tenant_42 → shard 7. The application asks the directory (heavily cached) where a key lives.

• Pros: total flexibility. Move one big tenant to its own shard; place tenants by region for data residency; rebalance key by key.
• Cons: an extra lookup on each request (mitigated by caching), and the directory becomes a critical dependency that must be highly available and consistent.

4. Geo-sharding

Shard by region: Indian users' data in a Mumbai region, EU users in Frankfurt. Driven by latency and data residency rules (for example, RBI's payment data storage directive requires payment system data to be stored in India). Usually combined with hash sharding inside each region.

How to Choose a Shard Key

The shard key decides which queries are cheap (single-shard) and which are expensive (scatter-gather or impossible). Changing it later means rewriting the entire dataset. Evaluate candidates against four criteria:

1. Query alignment. Do the most frequent and latency-sensitive queries include the key? If 90% of queries are "for this user", user_id is a strong candidate.
2. Cardinality. There must be far more distinct values than shards. country (a handful of values, India dominating) or status are terrible. user_id with 100M values is great.
3. Even load. Writes and reads must spread evenly. A monotonic key with range sharding fails this; so does a key where one value is huge (a single enterprise tenant with 40% of the data).
4. Co-location of related data. Rows that are read or updated together (a user's orders, order items, and payments) should share the key, so joins and transactions stay on one shard.

Worked example: a food delivery platform

Tables: users, restaurants, orders, order_items, menu_items. Main queries:

• Customer views their order history (very frequent).
• Restaurant views incoming orders today (frequent, latency-sensitive).
• Order placement writes order + items atomically (critical).
• Ops dashboard: orders by city per hour (analytics).

Candidate keys:

A sensible design: shard orders and order_items by customer_id. For the restaurant-side view, maintain a separate denormalised store (a table sharded by restaurant_id, fed asynchronously via CDC or events) holding only active orders. Analytics goes to a warehouse, never the OLTP shards. This pattern, one write model plus differently-keyed read models, is the same idea behind CQRS (event sourcing and CQRS explained).

Compound keys and IDs that embed the shard

A useful trick: embed the shard into generated IDs. Instagram's widely cited scheme puts a logical shard ID inside the 64-bit ID along with a timestamp and sequence. Then any query by order_id can be routed without a lookup, because the ID itself says where it lives. See unique ID generator design.

| 41 bits: ms since epoch | 13 bits: logical shard | 10 bits: sequence |
order_id -> (order_id >> 10) & 0x1FFF = logical shard -> physical node

Hot Shards: Causes and Fixes

Even with a good key, real traffic is skewed. A hot shard is one that receives far more load than its share, and it bottlenecks the whole system because the hot shard's latency becomes your p99.

Common causes

• Celebrity keys: a viral creator's posts, a cricket star's account during IPL, a flash-sale product.
• Whale tenants: in B2B SaaS, one enterprise customer may be thousands of times bigger than the median.
• Sequential keys with range sharding: all new writes hit the last range.
• Time-based bursts: lunchtime orders, Tatkal booking at 10 AM.

Fixes, from cheapest to most involved

1. Cache hot reads. If the hot traffic is reads of the same rows, a cache absorbs it.
2. Split or move the shard. With logical shards, move the hot logical shard to its own physical node.
3. Isolate whales. Directory sharding lets you put a giant tenant on a dedicated shard (or several, sub-sharded by its own user ID).
4. Key salting for hot write keys. For a counter or a single hot partition key, append a random suffix 0–9 so writes go to 10 sub-keys, and sum on read. DynamoDB's documentation recommends this "write sharding" pattern for hot partition keys.
5. Hash prefix on time keys. Use (hash(device_id) % 16, timestamp) instead of timestamp alone, so writes spread across 16 ranges.

Cross-Shard Queries, Joins, Transactions and Unique Constraints

Everything a single database gave you for free gets harder once data is split. Here is what breaks and the standard answers.

Queries without the shard key

"Find order by order_id" when orders are sharded by customer_id: either embed the shard in the ID (above), keep a global secondary index table (order_id → customer_id, itself sharded by order_id), or scatter-gather to every shard. Scatter-gather is fine for rare admin queries, terrible for user-facing ones: latency equals the slowest shard, and load multiplies by N.

Cross-shard joins

Avoid them in hot paths through co-location (shard related tables by the same key). Small, rarely changing tables (cities, cuisines, currencies) can be replicated to every shard as reference tables, which Citus supports natively. Anything else becomes an application-level join or moves to an analytics system.

Cross-shard transactions

A transfer from user A (shard 2) to user B (shard 5) cannot use a single local transaction. Options are two-phase commit (blocking, coordinator failure issues), a saga with compensating actions, or redesign so the money movement is recorded as events in a ledger. We go deep on this in saga pattern and distributed transactions.

Global uniqueness

"Usernames must be unique" cannot be enforced by a per-shard unique index if users are sharded by user_id. Use a separate uniqueness table sharded by the username itself (insert there first, conditional on not existing), or shard users by username if that is the main lookup.

Aggregations and pagination

"Top 10 restaurants by orders this week" needs per-shard top-K, then a merge. Global ORDER BY ... LIMIT 20 OFFSET 1000 needs each shard to return its top 1,020 rows; deep pagination across shards is expensive, so prefer cursor-based pagination on a sortable key.

Resharding a Live Database Without Downtime

Eventually some shards fill up, and you need to split them or add more. Doing this while serving production traffic is the hardest operational part of sharding. The standard playbook:

1. Provision the targets. Create the new shard clusters with the same schema.
2. Snapshot copy. Copy existing rows for the logical shards being moved. Use a consistent snapshot and record the replication log position (MySQL binlog GTID, Postgres LSN).
3. Catch-up via change data capture. Tail the source's change log from that position and apply changes to the target until lag is near zero. Tools: Vitess VReplication, Debezium, native logical replication.
4. Verify. Compare row counts and checksums per chunk between source and target (Vitess has VDiff for this).
5. Cutover. Briefly stop writes for the moving shards (typically seconds), wait for the last changes to apply, flip the routing map, resume writes on the new location.
6. Keep a reverse path. Replicate from new back to old for a while so you can roll back if something goes wrong.
7. Clean up. Delete moved data from the source after a safety period.

An alternative some teams use is dual writes (write to both old and new during migration). It is simpler to explain but fragile: a crash between the two writes leaves them inconsistent unless you add reconciliation. Log-based copying is preferred because the database's own log is the single source of truth.

Vitess, Citus and Managed Distributed Databases

You rarely need to hand-build sharding today. The main options:

For a choice between relational and document stores in the first place, see SQL vs Postgres vs MySQL vs MongoDB.

Vitess VSchema example

{
  "sharded": true,
  "vindexes": {
    "hash": { "type": "hash" }
  },
  "tables": {
    "orders":      { "column_vindexes": [ { "column": "customer_id", "name": "hash" } ] },
    "order_items": { "column_vindexes": [ { "column": "customer_id", "name": "hash" } ] }
  }
}

Both tables use the same vindex on customer_id, so a customer's orders and items land in the same shard and a join between them stays local.

Citus example

CREATE EXTENSION citus;
SELECT create_distributed_table('orders', 'customer_id');
SELECT create_distributed_table('order_items', 'customer_id',
                                colocate_with => 'orders');
SELECT create_reference_table('cities');

How to Talk About Sharding in a System Design Interview

Interviewers do not want "we will shard it". They want to see the decision process. A strong answer has five parts:

1. Justify with numbers. "At 35K writes/sec peak and 80 TB/year, one primary won't hold, so we shard the trips table."
2. Name the key and why. "Shard by rider_id: trip history and active trip lookup are per rider; high cardinality; even load."
3. Name the strategy. "Hash into 1,024 logical shards mapped to 16 clusters, so we can rebalance by moving logical shards."
4. Handle the non-aligned queries. "Driver-side views come from a separate store keyed by driver_id, fed by CDC. Lookup by trip_id works because the ID embeds the shard."
5. Address hotspots and growth. "Hot keys are unlikely for riders. Resharding is copy + binlog catch-up + cutover per logical shard."

Common follow-up questions

• What happens when one shard goes down? (Each shard has replicas with automatic failover; only users on that shard are affected during failover. This is also where CAP trade-offs come in.)
• How do you run a schema migration across 64 shards? (Tooling applies it to each shard; code must handle both old and new schema during rollout.)
• How do you generate unique IDs across shards?
• How would you find all orders above ₹10,000 placed yesterday? (Not on OLTP shards; warehouse query.)
• Your biggest tenant just signed a contract 50x larger. What changes? (Directory mapping, dedicated shard, sub-sharding.)

Mistakes I see in mock interviews

• Sharding a dataset that fits on one machine with room to spare.
• Choosing hash % N with no plan for changing N.
• Sharding by timestamp with range strategy, creating a single hot shard for all writes.
• Forgetting that secondary-key lookups become scatter-gather.
• Using cross-shard transactions casually on the hot path.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.