System Design · Module 7 · Lesson 2 of 4 · 45 min
Sharding Strategies and Choosing a Partition Key
Choose range hash or directory placement from access patterns and explain what happens to queries using another key.
01 The idea
The problem this lesson solves
Replication makes more copies of data; sharding divides data into separately owned subsets. The difficult choice is not the number of shards but the key that determines ownership. A key that makes redirects cheap can make owner listings expensive. This lesson follows those access patterns and shows the consequences for hot spots, joins, constraints and transactions.
Use the API, database, capacity and cache concepts from earlier modules. These lessons add distributed ownership and failure trade-offs.
02 Worked example
Route by code, then ask for an owner listing
03 The method
Understand the mechanism
Find the limit that partitioning is meant to relieve
One database can reach a storage, write-throughput, maintenance or serving limit. Before sharding, investigate query plans, unnecessary indexes, archival policy and whether read replicas or caching address the actual bottleneck. Sharding adds distributed routing and operational complexity.
If every full replica applies all writes, adding replicas does not divide that write stream. Sharding can divide work when independent operations naturally belong to different ownership units. A single hot row or key may remain a bottleneck even after most other data is distributed.
Define the partitioned entity and its access patterns. For short links, redirects locate by code, while management listings locate by owner. Both need to be supported, but one simple partition key may not make both single-shard operations.
The decision should identify the relieved resource and the new costs. “We shard for scale” is incomplete without saying which operations become local and which become distributed.
Compare range, hash and directory placement
Range placement assigns contiguous key intervals to owners. It can preserve useful locality for range scans, but uneven ranges or monotonically increasing keys can concentrate new work on one owner.
Hash placement applies a stable hash and assigns the result to a partition. It can spread suitably distributed keys while losing original-key range locality. Good hash distribution does not guarantee balanced traffic when one key is much more popular than others.
Directory placement uses metadata that maps a logical unit, such as a tenant or partition id, to an owner. It can support explicit movement and heterogeneous placement, but the directory must be available, versioned and kept consistent with routing behavior.
These strategies can be combined. A system may hash into many stable logical partitions, then use a directory to map those partitions to physical servers. The logical partition is the unit of movement; the physical machine is a replaceable host for several units.
Choose locality from the dominant access pattern
If code determines ownership, a redirect can route to one shard and perform one mapping lookup. This fits a read-heavy short-link workload. An owner’s links may be spread across many shards, so the owner listing needs another plan.
If owner_id determines ownership, listings and owner-local updates can be efficient. But a public request containing only code must discover the owner or use a directory/secondary lookup. Encoding routing information in an identifier can help some designs but creates format, migration and exposure considerations.
For a multi-tenant product, tenant_id may provide useful locality for joins and transactions. A very large tenant can then dominate one partition. High cardinality alone does not guarantee balanced workload.
Write the trade-off in terms of actual requests. “Redirect is single-shard; owner listing uses a maintained projection” is reviewable. “Hashing makes everything fast” hides the second access path.
Design cross-shard reads explicitly
Scatter-gather sends a query to several shards and combines the results. It can be appropriate for controlled administrative or analytical work, but the query waits on required responses and consumes work on every contacted shard.
For top-k over independently owned rows with a common total order, each shard’s local top-k can be merged to find the global top-k. This reasoning does not automatically apply to aggregates whose contributions to one group are split across shards. A globally popular group can be absent from each shard’s local top-k.
Fan-out increases exposure to slow components. In a toy model where each of eight shards independently has a 1% chance of exceeding a threshold, the probability at least one is slow is 1−0.99^8 ≈ 7.7%. Independence is an assumption, and correlated incidents can be worse.
Alternatives include a secondary index, materialized projection or offline export. Those create maintenance, lag and repair obligations. The design must say how the secondary path changes after a creation, deletion or ownership move.
Understand the new boundary for constraints and transactions
A unique constraint enforced on each shard does not automatically provide global uniqueness. If two different shards can accept the same external code, local constraints allow a global collision. Route a uniqueness decision to one authority, partition the namespace, or use another explicit allocation protocol.
Joins are cheap to reason about when related rows are colocated and become more expensive when data must move between owners. Colocation keys should follow frequent relationships, but they can also concentrate large customers or groups.
A transaction updating two shards needs a distributed coordination or workflow strategy. Two-phase commit coordinates a common decision but introduces participant and coordinator failure handling and can hold resources while outcomes are resolved. A saga-style workflow uses local commits and compensating actions, which are not equivalent to instantaneous rollback.
Choose the required business semantics before the protocol. Moving money or exclusive inventory across owners cannot be reduced to “send two writes and retry.” Some designs avoid the distributed transaction by changing ownership or introducing a single authority for that operation.
Handle skew and movement as continuing operations
Track per-partition bytes, read/write rate, latency and maintenance load. Equal partition counts per server may still be unbalanced if some partitions are larger or hotter. A placement controller needs evidence about the constrained resource.
Moving a partition while writes continue requires copying data, capturing concurrent changes, verifying catch-up and changing authority in a controlled way. Old clients may still route to the previous owner, so forwarding, rejection or version-aware retry behavior must be defined.
Hot read keys can sometimes be served from more copies under a freshness contract. Hot write keys may require aggregation, partitioned operations or a different data model. Splitting one logical entity into salted keys creates a corresponding combine/read problem.
Sharding is therefore an operating model as well as a schema choice. The initial partition function is only the beginning; growth, skew, failures and resharding must preserve the same user-visible invariants.
Guided tutorial
Compare two candidate keys
For each of redirect-by-code, list-by-owner and update-by-owner, mark whether code sharding or owner sharding gives a direct local route. Identify the missing lookup or secondary index for each candidate. Choose based on the stated hot path rather than making both look free.
Test a global uniqueness claim
Let shard A and shard B each enforce UNIQUE(code). Attempt code a7 on both. Explain why both local inserts can succeed if routing permits it, then assign one authoritative allocation/routing rule that prevents the global collision.
Work a fan-out query
Give three shards disjoint link rows with scores. Take each local top two and merge them to find the global top two under one total order. Then change the task to aggregate counts for owners whose contributions span shards and explain why local top-two groups may be insufficient.
Plan one partition move
Name old owner, new owner, change-capture mechanism, catch-up condition, routing version and cutover rule. Place a delayed client on the old route after cutover and specify whether it is forwarded or rejected with a refresh instruction.
Access-path checklist
redirect: code → partition owner → mapping lookup
owner listing: owner_id → secondary index / projection / scatter
range placement: preserves selected ordering, may skew
hash placement: spreads suitable keys, loses range locality
directory placement: explicit logical owner metadataCheck your result
A redirect reaches one code owner. Your owner-listing design explicitly names a secondary index, projection or fan-out, plus how it recovers from updates and failures.
Count moved keys and fan-out tail risk
Modulo placement and independent shard slowness are two separate toy models. They make their assumptions visible instead of promising a universal movement or latency percentage.
keys = list(range(12))
moved = [key for key in keys if key % 3 != key % 4]
print("moved_keys:", moved)
print(f"moved_fraction={len(moved)/len(keys):.0%}")
print(f"at_least_one_slow_of_8={1-0.99**8:.1%}")
Expected output
moved_keys: [3, 4, 5, 6, 7, 8, 9, 10, 11]
moved_fraction=75%
at_least_one_slow_of_8=7.7%The moved set is exact for these twelve integers. The fan-out probability assumes independent 1% slow events; shared dependencies can make real failures correlated.
04 Cheat sheet
Review the decisions
Use this table to explain the mechanism and its limit without memorizing a product name.
| Choice or concept | Remember | Check |
|---|---|---|
| Range shards | Range locality | Hot newest range or uneven tenant sizes |
| Hash shards | Distributed key ownership | Scatter for range or alternate-key queries |
| Secondary index | Supports another query key | Maintenance and consistency work |
| Cross-shard transaction | Coordinates multi-owner state | Higher complexity and failure surface |
05 Where & why
Check the primary references
Use official references for protocol and implementation details. The questions here are teaching prompts.
06 Interview questions
Explain the reasoning out loud
Answer before opening the explanation. The questions progress from vocabulary to decisions and failure behavior.
What does Shard mean?
What does Shard key mean?
What does Scatter-gather mean?
Does adding read replicas distribute writes?
Why can timestamp sharding hotspot?
What does sharding by owner improve?
Why needs a secondary owner index a consistency policy?
When should you avoid sharding?
07 Practice problems
Practice a new case
Solve the new cases before revealing hints. Complete worked solutions follow the set.
Copies and partitions
EasyShow the hint
Choose locality
EasyShow the hint
Choose a shard key
MediumShow the hint
Merge top results
MediumShow the hint
Partial fan-out
MediumShow the hint
Two-query defense
HardShow the hint
Worked solutions
1. Copies and partitions
There are 4 logical partitions and 12 shard copies. Physical machines depend on how copies are placed.
2. Choose locality
conversation_id is a candidate, with separate analysis for very large conversations and alternate access patterns.
3. Choose a shard key
account_id co-locates an account's history and avoids scattering each lookup. A very large or busy account can become a hotspot; plan a split or special handling if measurements require it. Timestamp partitioning helps retention but can concentrate new writes and scatter account history.
4. Merge top results
The top scores are 99,95,90. Fetching each shard's local top 3 is sufficient for the global top 3 under the same total order; define id ordering for ties and a snapshot or consistency policy for changing data.
5. Partial fan-out
The contract must report partial results or fail/retry under a bounded policy. Silent omission can misrepresent a complete global view.
6. Two-query defense
A code-keyed primary can make redirects local while an owner projection supports listings. Define when that projection updates, how it catches up and what a delayed update means to the owner. Alternatively justify another key and its redirect lookup route.