Partitioning & Sharding

Replication copies your whole dataset onto many machines. That solves availability and read scale, but it does nothing for two problems: a dataset bigger than one machine’s disk, and a write volume bigger than one machine’s CPU. For those you need partitioning (also called sharding): cut the dataset into pieces and put each piece on a different node.

What does partitioning buy us, and what does it cost? It buys near-unlimited horizontal scale — double the nodes, roughly double the capacity. It costs you the simplicity of a single machine: now you must decide which node holds each record, queries that span partitions get harder, and one unlucky partition can become a bottleneck that all your horizontal scale can’t fix.

Replication and partitioning are combined, not alternatives: each partition is itself replicated for survival.

   one big table        →   split into shards   →   each shard replicated
   ┌───────────────┐        ┌────┐ ┌────┐ ┌────┐    ┌────┐+copies  ...
   │  users 1..9M  │   →    │1-3M│ │3-6M│ │6-9M│ →  │1-3M│
   └───────────────┘        └────┘ └────┘ └────┘    └────┘
        (one node)            (three nodes)         (survives node loss)

The shard key: the most important decision

Every partitioned system hangs on one choice: the shard key (partition key) — the column whose value decides which node a record lives on. A good shard key spreads both data and traffic evenly, and matches your most common access pattern so reads usually hit a single shard. A bad shard key creates lopsided nodes and cross-shard queries that touch everything. There are two main ways to map a key to a partition.

Range partitioning

Assign contiguous ranges of the key to each partition: users A–F here, G–M there, N–Z over there; or timestamps Jan–Mar, Apr–Jun, and so on.

   key = last_name
   ┌──────────┐ ┌──────────┐ ┌──────────┐
   │  A – F   │ │  G – M   │ │  N – Z   │
   └──────────┘ └──────────┘ └──────────┘

• Buys: efficient range scans. “All orders from last week” reads one or two adjacent partitions, because related keys sit together. Keys stay sorted within a partition.
• Costs: hotspots. If you range-partition by timestamp, today’s partition takes every new write while the rest sit idle — a moving hot node. Sequential keys (auto-increment IDs) have the same disease: all new data piles onto the last partition.

Hash partitioning

Run the key through a hash function and assign by the hash value (often hash(key) mod N, or a slice of the hash range). The hash scatters even sequential keys uniformly.

   partition = hash(key) mod N
   user_42  → hash → 0x9f.. → partition 1
   user_43  → hash → 0x2a.. → partition 0   (neighbors land far apart — that's the point)

• Buys: even distribution. Hashing destroys the ordering that causes hotspots, so writes and data spread uniformly even for sequential or skewed keys.
• Costs: you lose efficient range scans — adjacent keys now live on random partitions, so “all orders last week” must query every partition (a scatter-gather).

The classic compromise

Many systems use a compound key: hash a high-cardinality prefix to spread load, then keep a sorted suffix within each partition for local ranges. Cassandra’s (partition_key, clustering_key) is exactly this — hash(partition_key) scatters across nodes, clustering_key stays sorted inside a node so you still get ranges where they matter.

Rebalancing without a stampede

When you add nodes (or one fills up), data must rebalance to the new layout. The naive hash(key) mod N has a brutal flaw: change N from 4 to 5 and almost every key remaps to a different node — a near-total reshuffle that saturates the network and tanks the cache.

The standard fixes:

• Consistent hashing places nodes and keys on a ring so adding a node moves only the keys in one arc, not everything. Read that page for the full mechanism.
• Fixed partition count — create many more partitions than nodes up front (say 1024 partitions on 4 nodes). Adding a node just reassigns whole partitions, never re-splits keys. This is how Elasticsearch and others keep rebalancing cheap and predictable.

Either way, the goal is the same: move as little data as possible when the cluster changes shape.

Hotspots: when one shard ruins the party

Even with hash partitioning, a single key can be hammered far more than others — a celebrity’s profile, a viral post, a flash-sale product. All requests for that key hit one partition, and no amount of total cluster capacity helps, because a single key can’t be split across nodes by a shard key alone.

   Normal:    requests spread evenly across shards   → all nodes ~equal
   Hot key:   90% of reads hit ONE key on ONE shard  → that node melts, others idle

This is the celebrity problem, and partitioning alone cannot solve it. The escapes — caching the hot key, adding a random suffix to split it, or replicating it specially — are the subject of Hot Partitions & the Celebrity Problem. The lesson here: a perfectly balanced partitioning scheme can still be wrecked by skewed access, and that skew often comes from the real world, not your code.

By the numbers — how much data moves when you add a node

The rebalancing scheme is the difference between a routine capacity bump and a cluster-wide stampede:

   naive  hash(key) mod N,  N: 4 → 5
       a key stays put only if (k mod 4) == (k mod 5) → just 4 of every 20 keys
       ≈ 80% of all keys relocate to a different node   (network + cache meltdown)

   fixed partitions: 256 partitions pre-split across 4 nodes (64 each)
       add a 5th node → move ~256/5 ≈ 51 whole partitions → only ~20% of data moves,
       and not a single key is re-split

Same cluster growth, wildly different blast radius. Pre-splitting into far more partitions than nodes (or consistent hashing) is exactly what keeps “add a node” from saturating the network and cold-starting every cache at once — you move a fair share, not the whole dataset.

The thread

Partitioning is how data systems escape the limits of a single machine, scaling storage and write throughput by spreading records across nodes. The price is a web of new decisions: the shard key governs everything; range partitioning gives you cheap scans but courts hotspots; hash partitioning spreads load but kills ranges; and the cluster must rebalance without melting the network when it grows. Get the shard key right and you scale almost linearly; get it wrong — or get a celebrity key — and one overloaded shard turns all that horizontal capacity into wasted iron.

The architect’s lens

Sharding is a one-way door for your data — interrogate it with the five questions before you walk through:

• Why does it exist? Because replication copies the whole dataset but does nothing for a dataset bigger than one machine’s disk or a write volume bigger than one machine’s CPU. Partitioning cuts the data into pieces and puts each on a different node.
• What problem does it solve? Near-unlimited horizontal scale of storage and write throughput — double the nodes, roughly double the capacity, where a single box has a hard ceiling.
• What are the trade-offs? You surrender single-machine simplicity. The shard key now governs everything; range partitioning gives cheap scans but courts hotspots, hash spreads load but kills range scans, cross-partition queries become scatter-gather, and growing the cluster must move minimal data (consistent hashing or a fixed partition count) or it saturates the network.
• When should I avoid it? Until you actually outgrow one machine — premature sharding buys you the shard-key decision and cross-shard pain for capacity you don’t need. Replication, a bigger box, or a cache often defers it. And it can’t fix a single hot key.
• What breaks if I remove it? You’re capped at one machine’s disk and write CPU. And the failure mode is subtle: a bad shard key — or a celebrity/hot key all requests funnel to — turns all your horizontal capacity into one melting shard while the others sit idle.

Check your understanding

1. Why doesn’t replication solve the problems partitioning solves? How are the two combined?
2. What makes a good shard key? Give one property that matters for data and one for traffic.
3. Contrast range and hash partitioning by what each buys and what each costs.
4. Why is naive hash(key) mod N bad for rebalancing, and what two techniques fix it?
5. Why can’t a shard key alone solve the celebrity/hot-key problem, even with perfect balancing?

Show answers

1. Replication copies the whole dataset onto many machines, which fixes availability and read scale but not a dataset bigger than one machine’s disk or a write volume bigger than one machine’s CPU — partitioning splits the dataset to fix those. The two are combined, not alternatives: each partition is itself replicated for survival.
2. A good shard key spreads both data and traffic evenly, and matches your most common access pattern so reads usually hit a single shard. For data: even distribution so no node holds a lopsided share; for traffic: matching the common access pattern so requests don’t all pile on one shard or force cross-shard queries.
3. Range buys efficient range scans (related keys sit together, so “all orders last week” reads one or two adjacent partitions) but costs hotspots (sequential keys like timestamps pile every new write onto one partition). Hash buys even distribution (hashing destroys the ordering that causes hotspots) but costs efficient range scans (adjacent keys land on random partitions, forcing scatter-gather).
4. Naive hash(key) mod N remaps almost every key when N changes (e.g. 4→5), a near-total reshuffle that saturates the network and tanks the cache. The fixes: consistent hashing (a node moves only the keys in one arc) and a fixed partition count far larger than the node count (adding a node just reassigns whole partitions, never re-splits keys).
5. A single key maps to a single partition, and a single key can’t be split across nodes by a shard key alone — so if 90% of reads hit one hot key, all of them hit one shard, melting that node while others sit idle no matter how perfectly the partitioning is balanced. This is the celebrity problem, caused by skewed access, not skewed partitioning.