System Design Data
Database Sharding
Imagine Instagram's user table no longer fits on one primary database. Storage is nearly full, write QPS (queries per second) keeps climbing, and lock contention (transactions waiting on each other for the same rows) stretches every request. Replicas helped reads. Caching helped hot profiles. The write wall remains.
is the answer to that wall: split the dataset so each database node owns one slice and takes only that slice's writes. The price is routing every request to the right node, joins that now cross machines, when you outgrow the layout, and when one slice gets far more traffic than the others. The decides most of that price, so most of this page is about choosing it well.
Request routing journey
App request
The app asks for user 42's profile and posts in one request.
The value that picks the owning database, usually user_id or tenant_id.
Shard router
A hash, range, or directory lookup turns that key into one node.
Local work
Keep the common path on one shard; fan out to many only rarely.
What actually happens
Before every read or write, a router asks one question: which physical database owns this key? The is the column the router uses to answer it. A good key makes the answer cheap and keeps the whole request on one node. A bad key sends most new writes to a single while the other nodes sit idle, and you have paid for sharding without getting its benefit.
There are three common ways to turn a key into a node. runs the key through a hash function so rows land pseudo-randomly and load spreads evenly. keeps neighbouring keys together, which makes scans over a range cheap. A map is an explicit table from key to shard, so you can move a large tenant by editing one row. Many teams also place many onto fewer physical nodes, so a rebalance moves a mapping rather than rewriting the keys the application uses.
Two costs follow you around after the split. Queries that need data from several shards use (ask every shard, merge the answers), denormalization (copy data so the query stays local), or a separately maintained read model. And when growth forces a topology change, doing safely matters more than the first hash function you picked. The rest of the page takes these one at a time: how to choose the key, the three strategies, sizing, hotspots, resharding, cross-shard queries, and multi-tenant layouts.
How to choose a shard key
The router question above only has a cheap answer if the was chosen well, and the choice is hard to undo once data has landed. Five questions decide it.
1. What limit are you hitting? Storage, write QPS (queries per second), working set (the data that must stay in memory to serve requests quickly), or noisy tenants: name it before splitting, because each limit points to a different key and shard count.
2. Which entity appears in almost every query? Shard by that entity (user, tenant, channel, region, account) so common joins and filters stay on one shard.
3. Which operations must stay transactional across rows? Those rows need to share a shard, because a transaction that spans two databases is much harder to keep correct.
4. How often do you need global queries? If reports that touch every user are frequent, plan an analytics or read model for them instead of asking the sharded database.
5. How will you move data later? Prefer or (both explained under Logical, virtual, physical below) so growth does not require rewriting every key.
What makes a shard key good
A good key balances both ownership and access. Hashing user_id may spread users evenly, but a single very active user can still dominate one shard. Sharding orders by customer keeps customer history local, while querying every seller’s recent orders may now require another projection. Write down the most frequent queries and largest tenants before choosing a key; the key determines which operations remain local and which become distributed.
The questions above boil down to four properties. Score any candidate key against them.
Candidate keys compared
Here is how common candidates score on those properties. The column is the one that surprises people.
| Shard Key | Distribution | Locality | Hotspot Risk |
|---|---|---|---|
| user_id | Excellent | All user data on same shard | Low (unless celebrity user) |
| timestamp | Terrible | Recent data on one shard | Extreme (all writes to latest shard) |
| channel_id | Good | Messages in channel together | Medium (popular channels) |
| geo_region | Moderate | Region data together | Medium (US shard > Iceland shard) |
| compound key | Excellent | Customizable trade-off | Low |
Shard by the entity your queries filter on most; the four properties above explain why each row scores as it does.
Simple rule of thumb
Exhaust replicas, caching, and schema tuning before . When you do shard, treat the key as a long-lived API: high cardinality, even traffic, query locality. In simple terms: split only when one machine is truly full, and pick a key you can live with for years.
How to say it in an interview: "I'll shard by tenant or user for locality, use virtual shards for movement, keep global reporting out of the OLTP path (the live transactional database), and monitor skew continuously."
Routing mental model
With a key chosen, here is the path every request takes. The router sits between the application and the databases, and the hashed decides which physical node the request lands on.
Application request
Shard router or lookup table
user_id hash 0-31
Shard A
Read replica
user_id hash 32-63
Shard B
Read replica
user_id hash 64-95
Shard C
user_id hash 96-127
Shard D
Scatter-gather only for rare global queries
Logical, virtual, physical
A logical partition is a unit of ownership; a physical node hosts many such units. Keeping more logical partitions than machines lets the system move a subset of data when adding capacity. The routing map connects the two. Clients and routers need a way to notice a stale map and retry safely against the current owner, otherwise a migration can leave some writes going to a retired location.
The diagram above maps a hash straight to a physical node, which is simple until you need to add a node. Adding one indirection fixes that: the hash picks a , and a small mapping says which physical node currently holds it.
user_id hash
Virtual shard 042
Physical database node
Replicas
Replica 1
Replica 2
Rebalance
Rebalance event
Virtual shard 042
Different database node
Keep many virtual shards mapped onto fewer physical database nodes. Rebalancing then moves one virtual shard's mapping and its data instead of changing every application key. reaches a similar result without a mapping table, by arranging nodes on a ring so a new node takes over only a fraction of the keys.
Sharding strategies
The router in the diagrams above needs a rule for turning a key into a node. There are three, and each trades distribution against flexibility in a different way.
Hash-Based
shard = hash(user_id) % Ngives even distribution and simple routing. The catch is that changing N moves about (N-1)/N of the data, because almost every key lands in a new bucket. fixes this by moving only about K/N keys when a node is added.
Common in managed key-value tables, wide-column rings, and in-memory cache clusters.
Range-Based
shard_1:
user_id_range: "1 … 1M"
shard_2:
user_id_range: "1M … 2M"
shard_3:
user_id_range: "2M … 3M"keep range queries inside one shard. The catch is that whichever range is active becomes a . The fix is dynamic range splitting: divide the hot range and move half elsewhere.
Common in range-partitioned storage and distributed SQL systems.
Directory / Lookup-Based
mapping_table:
user_123: shard_7
user_456: shard_3A gives flexible placement and easy migration, since moving a tenant is a row update. The catch is that the lookup table is a SPOF (single point of failure) on every request, so it must be cached and replicated.
Common when tenant movement and explicit placement matter.
Shard sizing for a million users
Strategy decides where a row goes; sizing decides how many places there are. The count comes from whichever resource runs out first, then gets headroom and a movement plan added on top.
Rows, bytes, QPS, tenants
Storage per shard
Write QPS per shard
Read QPS per shard
Hot-key skew
From size and QPS
Initial shard count
Use virtual shards for movement
Rebalance before saturation
From hot-key skew
Split, salt, or isolate hot tenants
Each input in the flow becomes one sizing question. Work the four rows below for your own numbers; the right-hand column is the shape of a good answer, not a single value. Hot-key skew (a few keys taking far more than their share) gets its own section next.
| Sizing question | Example | Answer shape |
|---|---|---|
| Storage per shard | 1 TB logical data x 3 replicas / 250 GB target ≈ 12 physical copies, or 4 logical shards with RF=3 | Leave 30-50% headroom for compaction, backfills, and growth. |
| Write QPS (Queries Per Second) | 20K write QPS / 2K safe writes per shard = 10 write shards | Use the lower of engine limit and p99 latency target. |
| Read QPS (Queries Per Second) | 100K read QPS with 80% cache hit = 20K DB read QPS; divide across shards and replicas | Cache hit rate and replica safety change shard pressure. |
| Skew | Top 1% tenants produce 50% traffic | Dedicated shards or salted hot entities beat average-only sizing. |
Numbers to know
The table gives the questions; these are the reference figures the rest of the page points back to. RF is replication factor, the number of physical copies of each shard, and p99 is the latency of the slowest 1% of requests.
logical_shards = ceil(total_bytes / target_shard_bytes); qps_per_shard = total_qps / active_shards; apply skew_multiplier for top tenant.
- Shard count from storage: 20 TB logical data x 3 replicas / 500 GB target per physical copy = 120 physical shard copies, which with RF 3 means about 40 logical shards, before headroom for growth, reindexing, and backfills.
- Resharding time: moving 2 TB at an effective 100 MB/s takes about 5.6 hours before validation and catch-up, and live writes must keep flowing to both layouts throughout.
- Resharding duration by approach: manual takes weeks, automated hours, a managed range split minutes; all should be zero downtime.
- Health targets: keep shard sizes within 20% of the average, and cross-shard queries under 5% of all queries.
Hotspots
Adding shards does not split an indivisible hot key. If one tenant exceeds a shard’s write capacity, options include isolating it, partitioning its data by an additional key, or changing an operation to use multiple independent counters or buckets. Each option affects query locality and consistency. Measure the busiest partition and tenant, not only the average utilization across all shards.
Sizing by averages hides the most common sharding failure: one key, tenant, or range takes far more than its share and one node melts while the rest idle. That is a , and there are a few standard shapes of it.
The same ideas as a taxonomy, one row per kind of hotspot. A monotonic key is one that always increases, like an auto-increment id or a timestamp, so every new write lands on the newest page or range.
| Hotspot type | Symptom | Mitigation |
|---|---|---|
| Hot row | One inventory, like counter, or quota row gets all writes | Split counters, reservation ledger, append events plus async aggregation |
| Hot partition | One shard key range receives too many requests | Salt keys, split ranges, improve shard key cardinality |
| Hot tenant | One customer dominates a shared shard | Move tenant to dedicated shard or tenant-specific routing |
| Hot index | Monotonic key writes target the latest index pages | Hash prefix, bucket by time plus id, or use append-friendly storage |
| Hot global query | Scatter-gather overloads every shard | Derived read model, analytics path, or precomputed aggregate |
Resharding
A safe move copies a partition while recording changes that arrive during the copy, catches the destination up, and transfers ownership at a controlled boundary. Reads may temporarily consult both places, but writes need one authoritative owner or a migration protocol that prevents divergence. Verify row counts and sampled checksums, monitor replication lag, and retain a rollback path until the new location has served correctly. Data movement consumes capacity the live workload also needs.
Hot shards, growth, or cost pressure eventually change the shard count, and that means moving data while the system keeps serving traffic. This is , and it is where most sharding projects get hurt.
Whether you need more shards (growth) or fewer (cost), you must redistribute data without downtime. Four approaches cover almost every real migration; the first three differ mainly in who does the copying.
How long a move takes, and how manual, automated, and managed approaches compare, is in Numbers to know above. During that window you also need mismatch alerts and a rollback route, because parity failures are normal and must be visible.
Cross-shard queries
For a global top-20 list, asking each shard for its local top 20 and merging the results can work when all shards use the same ordering. Its work still grows with shard count, and its latency waits for slow shards unless partial results are acceptable. Cross-shard transactions are harder because several owners must agree on one outcome. A separately maintained global read model can simplify frequent global reads while keeping transactional ownership local.
Even a perfect key leaves some queries that need several shards, and once data is split those become the biggest day-to-day operational pain. There are five standard ways to handle them.
Multi-tenant layouts
Sharding by tenant is so common in SaaS that it has its own vocabulary for how strongly each customer is isolated. The three models below trade cost against isolation; the two patterns after them are how tenant routing usually looks in practice.
Pool model
All tenants share the same tables, with a tenant_id column in every table. Cheapest but noisiest; row-level security (the database filters rows by tenant) provides isolation.
Schema-per-tenant
Same server, a separate schema per tenant. Moderate isolation, and thousands of tenants per server when metadata and migrations are managed well.
Database-per-tenant
Full isolation, typical for enterprise customers. Expensive but operationally simplest: each tenant can be backed up, restored, and scaled independently.
Workspace locality
All data for a team or workspace lives on the same shard, and cross-tenant queries are rare enough to handle separately.
Tenant routing
The largest tenants get dedicated shards and the smallest share shards. A cached tenant routing table gives O(1) (constant-time) shard lookup.
Try it: pick a shard key and watch hotspots
Choose how rows partition and how traffic arrives. The bars show write share per shard after a burst. Good keys preserve locality without concentrating every update on one physical shard.
- Skew ratio (max / min)
- 1.2
- Hottest shard
- #3
- Even split would be
- ~100 each
Loads spread across 4 shards with skew ratio 1.2. This key choice survives uniform traffic; re-check when one tenant dominates.
Monotonic keys heat the trailing shard. Created-at or auto-increment ids concentrate recent writes even when reads are range-friendly.
Tenant isolation beats naive hashing when one customer dominates. Route large tenants to dedicated shards or virtual shards before resharding the whole cluster.
Choosing and explaining what to ask before sharding
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
I will not shard just because user count is large; I will identify the resource limit and the access pattern.
The shard key should preserve query locality, distribute writes, and remain stable for years.
I will use virtual shards or a routing table so movement is possible without rewriting application code.
When it belongs
A single primary is near storage, write QPS, lock, or working-set limits.
A few tenants or entities dominate traffic and need isolation.
Global queries can move to derived read models instead of OLTP scatter-gather.
How it fails
Timestamp or low-cardinality keys put all new writes on one shard.
Cross-shard joins move latency to the slowest shard and make transactions harder.
Resharding without dual-write, backfill, and validation causes missing or duplicated rows.
Trade-offs to weigh
Hash keys spread load but hurt ranges; range keys support scans but can hotspot.
Directory routing enables tenant moves but adds a critical lookup path.
More shards add capacity but increase operational work, fan-out risk, and rebalance frequency.
Common misunderstandings
Do not average QPS without checking hot tenants and hot rows.
Do not shard before using indexes, read replicas, caching, archiving, and query tuning.
Do not pick a shard key that your top reads cannot provide.
Wrap-up
You have seen the key, the strategies, the sizing math, and the three things that go wrong afterwards. What keeps a sharded system healthy from here is watching the right per-shard signals.
What to watch
- Per-shard size and QPS against the median, not cluster totals, so one hot shard shows early.
- Replication lag (how far each replica trails its primary), tracked per shard and per replica.
- Cross-shard query percentage and the p99 latency contributed by the slowest shard.
- Hot-key rate, celebrity tenants, queue depth, and lock waits, each broken down per shard.
- Rebalancing time, backfill lag, and dual-write mismatch count during any resharding window.
Targets for size balance and cross-shard share are in Numbers to know above.
What to remember
Shard last (the rule of thumb above says when). When you do, treat the as a long-lived API: it drives locality, hotspots, and migration cost for years. Prefer platforms that automate splits and routing if your team cannot own every edge case.
Primary sources
- Instagram Engineering: Sharding & IDs: the practical shard allocation scheme behind the hero example above.
- Vitess Docs: Sharding: how range and hash sharding are configured for MySQL in production.
- AWS: DynamoDB Partition Key Design: hot partitions and key design, the managed-service view of the Hotspots section.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Partition data with balanced keys, versioned routing, tenant movement, global-index strategy, and a recoverable online resharding state machine.
Explain the decision
What makes a good shard key?
Read the reasoning
High cardinality, even load and growth, query locality, stable ownership, and compatibility with tenant movement and isolation requirements.
Apply it to a production scenario
One tenant creates 35% of writes on a hash-sharded cluster. What options exist?
Read one approach
Isolate or sub-shard that tenant, split hot entities, apply tenant quotas, and version routing changes with a verified migration protocol.
Work through the numbers
A 12 TB dataset with 30% headroom is spread over shards capped at 1 TB usable. How many shards?
Read the worked calculation
ceil(12 × 1.3 / 1) = 16 shards, then add failure and rebalance headroom if replicas share limits.
Reason through a failure
What must a shard move guarantee?
Read the recovery reasoning
Each key has a known source of truth; dual reads/writes are idempotent, routing versions are monotonic, and cutover is reversible until validation passes.