System Design: Sharding and Partitioning

Choosing a shard key

The shard key is the field whose value decides placement. It is the most important decision in a sharded design, and it is hard to change later because changing it means moving all the data. A good shard key has these properties:

• High cardinality: many distinct values. Sharding by country gives you perhaps 200 values, so at most about 200 shards, and wildly uneven ones.
• Even distribution of data and traffic: no value should hold a large fraction of either.
• Matches the access pattern: the queries you run most should name the shard key, so they hit one shard.
• Stable: the value should not change for a row, or you must move the row between shards.

For a multi-tenant project-tracking SaaS (tenants own projects, projects own tickets), consider the options for the tickets table:

A common answer is tenant_id: nearly every query is "things belonging to this tenant", so one shard answers it. To fetch a ticket by ID alone, embed the tenant or shard number in the ID, or keep a small lookup table. The real point: you pick the shard key for your most important queries, and everything else becomes more expensive.

Hotspots

Even a good key can concentrate load. A huge tenant generates far more traffic than ordinary ones, so its shard becomes hot. Defences include:

• Cache the hot items so reads rarely reach the shard.
• Split the hot key across sub-keys, for example appending a small random number (0 to 9) to a counter's key and summing on read.
• Give heavy tenants their own shard, easy with directory sharding.
• Replicate hot data more widely so reads spread.

Why hash mod N hurts, and consistent hashing

Suppose we use shard = hash(key) mod 4 and add a fifth shard, so the formula becomes mod 5. A key stays put only if its hash gives the same answer mod 4 and mod 5, which for uniformly spread hashes holds for about one key in five. Roughly 80% of all keys move, causing heavy network traffic and degraded performance exactly when you added capacity because the system was strained.

Consistent hashing fixes this. Picture a circle (a ring) of hash values. Each node is placed at a point on the ring, and each key is hashed to a point on the same ring. A key belongs to the first node you meet walking clockwise from the key's position.

When you add a node, it takes over only the keys in the arc just before it, from its neighbour. When you remove a node, only that node's keys move to its neighbour. On average, about 1 in N+1 of the keys move when you add the (N+1)th node, instead of nearly all of them.

Virtual nodes

With only a few nodes, random positions on the ring produce uneven arcs, so one node may own much more than the others. And when a node dies, its whole load falls on one neighbour. The fix is virtual nodes (vnodes): each physical machine is placed on the ring many times, say 100 or 200 points each. Arcs average out, so load balances better. When a node leaves, its many small arcs scatter across many neighbours, spreading the extra work. When a node joins, it takes a little from many others. You can also give a larger machine more vnodes than a smaller one.

Consistent hashing appears in distributed caches, Dynamo-style stores such as Cassandra, and many load-balancing setups. A related and common alternative is fixed partitions: create many more logical partitions than nodes, for example 1,024, assign hash ranges to partitions once, and then move whole partitions between nodes when the cluster changes. The key-to-partition mapping never changes; only the partition-to-node map does. This is simpler to operate and is used by several databases.

Resharding is painful

Whichever method you choose, growth means resharding: moving data to new shards while the system stays online. The hard parts are copying live data while it is being written, switching routing atomically so requests do not go to the wrong shard (or both), keeping the system fast while the copy eats disk and network, and rolling back if the new layout misbehaves.

A typical safe pattern: create the new shard, copy a snapshot, stream changes made since, verify the copies match, flip routing for that key range, and delete the old data after a safety period. Plan for it from the start with many small logical partitions and a routing layer you control, and rehearse on non-critical data.

Cross-shard queries and transactions

Once data is split, anything that needs data from several shards gets harder.

Queries that name the shard key go to one shard and stay fast. Queries that do not must be sent to every shard and the results merged, a pattern called scatter-gather. It works, but the slowest shard decides the latency, and every shard does work for every query. At 100 shards, one query becomes 100 sub-queries.

Joins across shards are expensive and often avoided. Options are to store related data together (same shard key for parent and child rows), to denormalise (duplicate data so a query does not need a join), or to join in the application.

Global secondary indexes (for example, look up a user by email when sharded by tenant_id) face a choice. A local index on each shard means a lookup must ask all shards. A global index is itself sharded by the indexed value, so lookups are fast, but each write updates two places, possibly on different nodes.

Transactions that span shards cannot rely on one machine's locking. They need two-phase commit, which is slow and can block if the coordinator fails, or a saga with compensating actions (Advanced: Distributed Transactions). The best approach is to design the shard key so the operations needing atomicity fall inside one shard: if all of a tenant's data shares a shard, "create ticket and update the project's counters" is a local transaction.

Unique IDs and constraints such as "email must be unique" need care because each shard cannot see the others. Use IDs that include the shard or a time-based component, and enforce global uniqueness through a dedicated lookup keyed by the unique value.

Sharding in the architecture

Many teams put a router or proxy in front of the databases so application code does not need to know the topology, and some databases shard natively and expose one logical table. Either way the trade-offs are the same, and understanding them tells you what the product can and cannot do for you.

In practice: three huge tenants and a hot shard

The situation

A project-tracking SaaS serves about 4,000 business tenants with 12 engineers. Tickets live in PostgreSQL, sharded by tenant_id into 16 logical partitions spread over 4 clusters (each a primary plus a replica), with a small directory table mapping partitions to clusters (and able to hold per-tenant overrides). Traffic is dominated by a few giants: assume three tenants produce 55% of write volume, and two of them landed on cluster 3.

The pain, illustrative: cluster 3 runs at 95% CPU and 80% storage while the other three sit near 25%. Ticket API p95 is about 1.8 seconds for the roughly 1,000 ordinary tenants sharing cluster 3, against about 150 ms elsewhere. One of those two giants also has a contract requiring its data to stay in an EU region, and the budget allows at most two more clusters this year.

Starting architecture

Hashing spread the tenant count evenly, but not the load, because the load per tenant varies by orders of magnitude.

Options considered

The decision

Rollout and verification

Migrate one tenant at a time, smallest first as a rehearsal:

The order matters: the tenant is fenced (its writes rejected, other tenants on the old cluster unaffected) before the final catch-up and verification, because checksums only match once writes have stopped. The tenant's writes pause for the seconds or minutes this takes. Fencing before the flip also means a router with a stale mapping fails loudly instead of writing to the wrong place. Dashboards that prove it worked: per-cluster CPU, write rate and storage; ticket API p95 per cluster and for the top ten tenants; migration lag in rows; checksum mismatches (target zero); and directory version per API pod.

The 2 a.m. failure

After cutover of tenant 17, the page reads "Write errors for tenant 17 on 2 of 6 pods". Those pods still cache the old directory entry and send writes to the old cluster, where tenant 17 is fenced.

First three checks: compare the directory version gauge across pods; SELECT tenant_id, cluster_id, version FROM tenant_directory WHERE tenant_id = 17;; and the count of tickets for tenant 17 created in the last 15 minutes on both clusters, to confirm nothing landed on the old one. Mitigation: trigger a directory refresh on the lagging pods (or, if there is no refresh hook, delete just those two pods so they reload the mapping), and keep tenant 17 fenced on the old cluster. Follow-up: stamp every directory entry with a version and send it with each query so a shard can reject a mismatch, shorten the directory cache TTL (a few seconds) with push invalidation, and put "fence before flip" in the migration runbook.

Architect's notes

• Measure skew, not just totals. Rank tenants by write volume, storage and p99 query cost; a long tail plus a few giants needs a different plan from uniform growth.
• Ask in the review: "What is the largest tenant we expect in two years, and does it fit one shard?" If not, plan the within-tenant split now.
• The cost is the special cases. Dedicated clusters are cheap to create and expensive to remember. Record every override in the directory with an owner.
• Treat the directory as tier-0. It needs replication, caching with versioning, and a tested recovery path.
• Pick who is paged. Tenant moves are a platform team operation with a runbook, not an ad hoc script someone runs at night.
• Defer full resharding until one tenant outgrows a cluster; it is the biggest change you can make and the hardest to reverse.

Common mistakes

• Sharding too early. The operational cost is high and permanent. First try indexes, caching, replicas, a larger machine and archiving.
• Choosing a low-cardinality or skewed key. Sharding by country or status gives few, uneven shards. Pick a key with many values and an even load.
• Using a monotonically increasing key with range sharding. All new writes hit the last shard. Hash the key, or add a prefix that spreads writes.
• Using plain hash mod N and planning to add nodes later. Most keys move when N changes. Use consistent hashing or many fixed partitions.
• Ignoring cross-shard needs. Reports, joins, uniqueness and transactions become hard. List them before choosing the key and keep them within a shard where possible.
• Forgetting that shards need replication. Each shard is a single point of failure without replicas. Replicate every shard and spread replicas across zones.
• Having no resharding plan. Moving data live is the hardest operation. Design small logical partitions and rehearse moves early.

Key takeaways

• Sharding splits data, replication copies it. Use sharding for storage and write scale, replication for availability and read scale; real systems use both.
• Exhaust cheaper options first. Indexes, caching, replicas, scaling up and archiving often postpone sharding for years.
• The shard key is the key decision. It should have high cardinality, spread load evenly and match the most important queries.
• Range favours scans, hash favours balance, directory favours control. Each has a matching weakness: hotspots, scattered scans, and a critical lookup service.
• Hotspots need explicit handling. Cache, split hot keys, isolate heavy tenants or replicate hot data.
• Consistent hashing limits movement. Adding a node moves roughly 1 in N+1 keys, and virtual nodes smooth the balance.
• Cross-shard operations are the real cost. Scatter-gather queries, joins, secondary indexes and transactions all get harder.
• Plan resharding from day one. Use many logical partitions and a routing layer you control.

Practice exercises

Exercise 1 — Starter (30 min): A database is sharded with hash(key) mod 4. Take 20 keys with made-up hash values from 0 to 99, assign each to a shard, then recompute with mod 5. Count how many keys change shards and compare with the "about 80%" estimate.

Exercise 2 — Intermediate (2 hours): For a chat app with tables for users, conversations and messages, evaluate three shard keys (user_id, conversation_id, message_timestamp). For each, write the three most common queries and say whether they hit one shard or all. Pick a key, justify it, and name the one query that becomes expensive because of your choice and how you would mitigate it.

Exercise 3 — Advanced (half day): Implement a small consistent-hashing ring in any language with virtual nodes. Place 3 physical nodes with 100 vnodes each, hash 100,000 sample keys, and report the key counts per node. Then add a fourth node and measure the fraction of keys that moved, and repeat with 1 vnode per node. Write a short comparison of balance and movement between the two settings.

Related reading

• System Design: Replication — every shard still needs replicas; the previous lesson covers how they work.
• System Design: CAP and Consistency — the consistency trade-offs that sharded and replicated stores force on you.
• System Design: Advanced Caching — distributed caches use consistent hashing and face the same hot-key problems.
• System Design: Distributed Transactions — what to do when one operation must change data on several shards.
• System Design: Databases Basics — indexes, transactions and the single-node foundations that sharding builds on.