Cruxly › System design › Foundations of Data Systems

Partitioning and Sharding

the shard key is the design

When one machine cannot hold the data or absorb the writes, you split it. The split is the hard part: choose the key badly and you get hot partitions, cross-shard queries and a migration you cannot perform online.

Establish that you need it

Sharding costs complexity, so earn it with a number. One well-provisioned OLTP primary handles roughly 10-20k small durable writes/s (more with careful batching), and modern hardware holds tens of terabytes.

Reason	Shard?
Write throughput exceeds what one primary can absorb	Yes
Data volume exceeds one node's storage	Yes
Blast radius: one failure should take out 1/N of users, not all	Yes
Read throughput	No. Replicas are simpler

If none applies, say so: "3,000 writes/s is one Postgres primary with room to spare. I'll keep it simple and revisit at 10x." Candidates lose points for unjustified complexity far more often than for insufficient scale.

Choosing the key

You need all three properties.

Property	Passes	Fails	Why it fails
High cardinality	`user_id` — millions of values	`country` — about 200	Not enough distinct values to spread across partitions after 10× growth
Even distribution	`user_id`	`conversation_id`	Fine until one conversation has 50,000 members
Query alignment	`conversation_id` for a chat read	`message_id`	Perfect spread, but every conversation read becomes a scatter-gather

:::key Shard by whatever appears in the WHERE clause of your hottest read Cardinality and distribution are the easy two. Query alignment is where answers fall apart: a key can be statistically perfect and still force every common read to fan out to every shard. Even spread is worthless if nothing can be answered from one partition. :::

Hash, range, and directory

Strategy	How	Good at	Costs
Hash	`partition = hash(key) % N`	Even distribution	Range queries become scatter-gather
Range	Contiguous key ranges per partition	Efficient range queries	Sequential keys create a hot partition
Directory	Explicit lookup table from key to partition	Total flexibility: move one noisy tenant to its own shard. Right for multi-tenant systems with wildly uneven tenants	A lookup on every operation, and a service that must not go down

:::warn The % N trap Changing N remaps nearly every key, so adding one node effectively invalidates the whole placement. Consistent hashing fixes it: adding a node moves only 1/N of keys. :::

Walk the ring. "Consistent hashing" recited without the walk sounds memorized.

The hash space is a circle, say [0, 256), wrapping from 255 back to 0. Servers A, B, C hash to points on it.
A key hashes to its own point and walks clockwise to the first server, its owner: key-1 → A, key-2 → B.
Add D just behind B. D only takes the keys in its own arc: key-2 → D. key-1 never crosses D's arc and stays on A.
Remove A instead: its keys walk on clockwise to the next server, so key-1 → B. Keys that weren't on A don't move.

Adding or removing one server only perturbs the keys in that server's arc, never the rest of the ring. That's why it costs 1/N instead of "nearly everything."

Virtual nodes. With one point per server, arc sizes are luck of the hash: A gets a huge arc, C a sliver everyone piles onto. Give each physical server many points scattered around the ring. Its total coverage is the sum of many small arcs, which averages out close to 1/N. Without them the distribution comes out lumpy.

Range keys need a high-cardinality prefix:

shard by timestamp  →  every write today lands on today's partition

shard by (user_id, timestamp)  →  user_id spreads writes,
                                  timestamp still orders within a user

Hot partitions

Even a good key produces outliers: the celebrity account, the enormous group chat, the tenant a hundred times bigger than everyone else.

:::key Lead with detection, because it's what gets pushed on "I'd see one partition's p99 write latency and CPU climbing while the others stay flat, so I need per-partition metrics. An average across shards hides exactly this: the healthy shards dilute the one that's dying." :::

Then the fixes, in the order you'd reach for them:

Fix	How	Cost
Sub-partition the hot key	`conv_id:bucket`, bucket a small random number	Reads must query all k buckets and merge — apply only to keys you've identified as hot
Dedicated capacity	Move the outlier to its own partition	Requires a directory scheme
Cache in front	Absorb the reads	Does nothing for a write hotspot
Change the approach entirely	Fan out writes for normal users; skip fan-out for celebrities and merge at read time	Two code paths, chosen by a threshold — usually the best answer when available

What sharding costs you

Say these unprompted. This is the part that shows you've lived with a sharded system.

What you lose	The workaround	What the workaround costs
Cross-shard transactions	A saga: steps plus compensating actions	No atomicity; you hand-roll rollback
Cross-shard joins, global indexes	A separate index table sharded by that column	It's now eventually consistent with the primary data
Cheap aggregates	Running counters	`COUNT(*)` was a scatter-gather; now it's bookkeeping you maintain
Easy uniqueness	A separate authority, or IDs unique by construction	Timestamp + node + counter — which at least sorts roughly by time

:::key The real fix for cross-shard transactions Choose a key so that things that must be transactional share a shard. A saga is the answer when you're stuck. A key that keeps the invariant inside one partition is the answer while you're still designing. :::

Rebalancing is an operational project, not a config change. Going from 8 shards to 16 means moving data while serving traffic: dual-write → backfill → verify → cut over reads → stop the old write. Knowing that order is a strong signal on its own.

The pre-emptive trick: create many more logical partitions than physical nodes up front, say 1,024 logical on 8 physical. Growth becomes reassigning logical partitions to new hardware, a cheap metadata change, instead of a re-hash that moves nearly every key.

How to say it in the interview

"At 50k writes per second a single primary is an order of magnitude over, so this has to partition. The key decision is the shard key — I'll pick one, then immediately check it for hot partitions and for queries it makes expensive."

Checklist

Justified sharding with a throughput or volume number
Chose a key with high cardinality, even spread, and query alignment
Named the strategy: hash (consistent, with virtual nodes), range, or directory
Avoided modulo-N hashing, or said why remapping is acceptable
Could walk the ring mechanically — hash a key, walk clockwise, land on a server
Said how you would detect a hot partition
Gave a hot-key mitigation matched to read vs write hotness
Named what breaks: cross-shard transactions, joins, aggregates, uniqueness
Had a story for rebalancing without downtime

Practice this interactively