Common Problems Associated with Data Partitioning

Every hard problem with partitioning descends from one design decision: the function that maps a key to a partition. That mapping simultaneously fixes how evenly load spreads and how much data must move when the topology changes — so a key that looks fine on day one can produce a hotspot, an expensive reshard, and a scatter-gather query all at once. The seven classic drawbacks below are not independent gripes; they are what that single mapping costs you, and most have a concrete mechanism that tames them.

Worked example: the skew, in numbers

Take a 10-million-row customer database sharded by country into 4 regional shards. If evenly loaded, each shard holds 2.5M rows. But real user bases are lopsided:

S0 carries 2.4× its fair share of both storage and query traffic while S3 sits nearly idle. You cannot scale out of this by adding shards — country has fixed cardinality, so the US rows will not split. The mechanism that fixes it is to stop partitioning on a meaningful attribute and instead route on hash(user_id), whose output is uniform. With 4 shards that yields ~2.50M ± a few thousand rows each; the natural US skew disappears because a hash destroys the correlation between the key and its business meaning.

Worked example: why the resharding scheme decides your downtime

Now you must add a 5th shard to relieve load. The cost of that migration is entirely determined by the mapping function. Trace both, over the same 10M rows.

Naive: shard = hash(user_id) mod N

1. With N = 4, a row hashing to value 7 lands on shard 7 mod 4 = 3.
2. Bump to N = 5: that same row now maps to 7 mod 5 = 2 — it must physically move.
3. A row stays put only when v mod 4 == v mod 5. Over any 20 consecutive values that holds for exactly 4 of them (v = 0,1,2,3). So only 20% stay; ~8M of the 10M rows relocate, and they scatter across every shard at once.

Consistent hashing

1. Keys and the 4 shards are hashed onto one ring; each key belongs to the next shard clockwise.
2. Inserting shard E drops a new point on the ring. E claims exactly the arc between it and its predecessor — about 1/5 of the keyspace.
3. Only the ~2M rows (20%) in that one arc move, and they move onto E alone. The other 8M never change owner.

Same 10M rows, same +1 shard: naive hashing reshuffles 8M keys, consistent hashing touches 2M and localizes them. That 4× difference is the gap between a brief background copy and a multi-hour, cluster-wide migration.

Pitfalls

• Hashing spreads keys, not per-key load. Consistent hashing balances 10M distinct users evenly, but a single viral user_id (a celebrity, a bot account) still resolves to exactly one node. The fix is not more shards — it is salting: split the hot key into user_id#0 … user_id#9 so its traffic fans across ten partitions.
• Monotonic keys defeat range partitioning. Partitioning by an auto-increment id or timestamp sends every new write to the newest partition — the whole cluster idles while one shard is on fire. Prefix the key with a hash bucket, or use hash partitioning for write-heavy tables.
• The noisy-neighbor tenant. Sharding by tenant_id feels clean until one enterprise customer is 90% of the volume; that tenant now owns an entire shard's capacity. Large tenants often need dedicated shards (directory-based pinning), not the shared hash pool.
• Scatter-gather tail latency. A query on a non-partition column (e.g. "find users by email" when sharded by user_id) must hit all N shards; p99 latency becomes the slowest of N responses, which grows with N. Note what does and does not fix this: a local (per-shard) index on email only cheapens each shard's own lookup — all N requests still go out. Removing the fan-out requires a global term-partitioned index or an app-maintained lookup table (email → user_id), which buys the single-shard read by accepting an async, possibly-stale index write.
• Resharding without consistent hashing. Teams that ship mod N discover at scale that adding a node means moving ~80% of data, so they never add nodes — the cluster ossifies. Choose the rebalancing-friendly scheme before you have production data.
• Silent backup inconsistency. Per-shard backups taken at different instants can't be restored into a globally consistent snapshot; cross-shard writes land in one backup and not another. You need coordinated snapshots or logical timestamps.

When to use which scheme — and when not to

These problems are really a choice between three partitioning strategies. Deciding well means matching the scheme to your dominant access pattern and your rebalancing needs.

• Hash / consistent hashing. Signals: point lookups by key dominate, writes are uniform, and cluster membership will change over time. Gain: even distribution and cheap, localized rebalancing (~K/N moved). Cost: you lose efficient range scans (adjacent keys land on different shards), and you need a rebalancing coordinator plus virtual nodes to keep variance low.
• Range partitioning. Signals: time-series or ordered data where queries are ranges ("events in March", "prices $10–$20"). Gain: a range scan touches one or few contiguous shards. Cost versus hashing: monotonic inserts create write hotspots, and skewed ranges need manual split/merge.
• Directory / lookup-based. Signals: you need explicit control — pin a huge tenant to its own shard, or migrate arbitrarily. Gain: maximum flexibility; move any key anywhere. Cost versus hashing: the directory is an extra hop on every request and a single point of failure you must replicate and cache.

Choose consistent hashing when key-value point access dominates and you will add/remove nodes; prefer range partitioning when range and ordered scans are the workload; prefer a directory when a few keys are wildly disproportionate and you need to place them by hand. And before any of them: if a single well-indexed node can still serve your load, do not shard at all — every problem on this page is the price of a distributed key space you did not yet need to pay.

Takeaways

• Every partitioning problem — skew, migration cost, scatter-gather — traces to one thing: the key-to-partition mapping. Pick it deliberately.
• Skew is fixed by destroying correlation: hash the key and add virtual nodes so distribution no longer tracks business meaning.
• Rebalancing cost is a scheme choice: mod N moves ~80% of keys on a reshard, consistent hashing moves ~K/N (~20%) and localizes it.
• Hashing balances keys, not per-key load — a single hot key still needs salting or a dedicated shard.

Re-authored and deepened for this guide. Sources: Martin Kleppmann, Designing Data-Intensive Applications, ch. 6 (Partitioning) — skew, hot spots, rebalancing strategies, and secondary-index approaches; Karger et al., "Consistent Hashing and Random Trees" (STOC 1997); DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007) — virtual nodes and ring rebalancing; and Grokking the System Design Interview (Design Gurus) for the original problem taxonomy. Worked numbers computed for this page.