← DDIA

Chapter 06 · Partitioning

Partitioning

One customer is 30% of your traffic. One shard is on fire. Now what?

Split the data across N nodes. Every scheme trades one pain for another.

Three acts: 1. fire 2. schemes 3. pick

The fire

Even by design. Skewed by workload.

C clients P0 node-A P1 node-A P2 node-B P3 node-B P4 node-C P5 node-C req/s celebrity key · 1 partition · fan-out amplification

The fix waits three slides down. Hash first, then salting.

Distributing the load

Same board, four moves. Every scheme is a trade.

sorted keys, grouped by range. Range scans are one seek.

A-D E-H I-L M-P Q-T U-Z P0 A-D P1 E-H P2 I-L P3 M-P P4 Q-T P5 U-Z WHERE key BETWEEN "M" AND "P" one partition touched · fast scan

hash the key, mod N. Load spreads. Scans die.

hash(key) mod 6 — P0 bucket 0 P1 bucket 1 P2 bucket 2 P3 bucket 3 P4 bucket 4 P5 bucket 5 WHERE key = "alice" range scan · all 6 partitions touched

celebrity key floods one partition. Append a random suffix to spread the writes.

hash(key + suffix) mod 6 celeb P0 bucket 0 P1 bucket 1 P2 bucket 2 P3 bucket 3 P4 bucket 4 P5 bucket 5 write "celeb" writes spread · reads must fan-out + merge

fixed-N partitions. Add a node, hand it a few whole partitions. No re-hash.

node-A node-B node-C node-D P00 P01 P02 P03 P04 P05 P06 P07 P08 P09 P10 P11 partitions moved: 0 / 12 fixed count · reassign, don't rehash

Takeaway

Hash spreads load. Range keeps scans cheap. Salting patches hot keys. Every scheme is a trade.

Pick your partitioning scheme.

01

Range

sorted keys, scan-friendly.

PICK WHEN range queries dominate · time-series with rolling windows.
STRUGGLES AT sequential keys (timestamps) → all writes on one partition.
EXAMPLES HBase, BigTable.
02

Hash

even load, no scans.

PICK WHEN point lookups dominate · load must spread evenly.
STRUGGLES AT range queries → scatter/gather across every partition.
EXAMPLES Cassandra hash, DynamoDB.
03

Fixed-N partitions

even load · cheap rebalancing.

PICK WHEN nodes come and go · you want to add capacity without downtime.
STRUGGLES AT range queries (same as hash) · one hot key still needs salting.
EXAMPLES Riak, Elasticsearch, Couchbase.

Rebalancing is orthogonal: fixed-N is the default sane choice; dynamic (HBase, Mongo) splits as data grows; proportional-to-nodes (Cassandra) scales bins with the cluster.