Partitioning: the four strategies

What do round-robin, random, hash and range partitioning each buy, and how should the key be chosen?

Partitioning means splitting a stream (or a data set) across N destinations. The strategy is fully described by one function:

destination = f(record)

Four choices of f cover almost everything. (Applied to stored data, partitioning is called sharding, and the destination becomes an owner: choosing the shard key, and moving shards between nodes, are coordination's.)

Round-robin

f = counter++ % N

(The symbol % is the modulo operator: the remainder after division. 7 % 3 = 1. So the counter cycles through destinations 0, 1, 2, …, N−1, 0, 1, …)

Perfect balance. Nothing beats it.
Zero locality and zero order. Related records are scattered as widely as possible.
Zero state. There is no key to extract, no lookup, no skew to analyze.

Round-robin is correct when records are truly independent and nothing downstream groups them: log lines going to a search index, independent task units, any work that is per record and stateless.

The mistake is to use it because it balances well, and then find that downstream code needs to group records per entity. Now every consumer must read every partition. You did not avoid the coordination cost. You moved it downstream and made it worse.

Random

f = random()

This is almost the same as round-robin, with one real difference: there is no shared counter, so it needs no state across producers. Round-robin across 50 producer instances needs either 50 independent counters (fine, and what everyone really does) or coordination between them (which nobody does). Random gets the same long-run result with no state at all.

The balance is slightly worse than round-robin, because random placement has the variance of "balls in bins" (throwing M balls at random into N bins). With M records into N partitions, the fullest partition exceeds the mean by roughly √(2 · (M/N) · ln N).

Worked example

Take N = 10 partitions.

M = 1,000,000 records: the mean is 100,000 per partition. The excess is √(2 × 100,000 × ln 10) = √(2 × 100,000 × 2.303) = √460,517 ≈ 680, which is 0.7% above the mean. Negligible.
M = 1,000 records: the mean is 100. The excess is √(2 × 100 × 2.303) = √460.5 ≈ 21, which is 21% above the mean. Visible.

RelationshipBalls in bins: the fullest partition →

2 \cdot (M / N) \cdot ln N

$M$: records placed at random
$N$: partitions (bins)
$M / N$: records per partition on average

N = 10 partitionsN = 100

Data table

How far the fullest partition sits above the mean, by records
Records M	series	Fullest partition above the mean
100	N = 10 partitions	67.9%
119	N = 10 partitions	62.2%
141	N = 10 partitions	57.1%
168	N = 10 partitions	52.4%
200	N = 10 partitions	48%
237	N = 10 partitions	44.1%
282	N = 10 partitions	40.4%
335	N = 10 partitions	37.1%
398	N = 10 partitions	34%
473	N = 10 partitions	31.2%
562	N = 10 partitions	28.6%
668	N = 10 partitions	26.2%
794	N = 10 partitions	24.1%
944	N = 10 partitions	22.1%
1.12K	N = 10 partitions	20.3%
1.33K	N = 10 partitions	18.6%
1.58K	N = 10 partitions	17%
1.88K	N = 10 partitions	15.6%
2.24K	N = 10 partitions	14.3%
2.66K	N = 10 partitions	13.2%
3.16K	N = 10 partitions	12.1%
3.76K	N = 10 partitions	11.1%
4.47K	N = 10 partitions	10.2%
5.31K	N = 10 partitions	9.31%
6.31K	N = 10 partitions	8.54%
7.5K	N = 10 partitions	7.84%
8.91K	N = 10 partitions	7.19%
10.6K	N = 10 partitions	6.59%
12.6K	N = 10 partitions	6.05%
15K	N = 10 partitions	5.55%
17.8K	N = 10 partitions	5.09%
21.1K	N = 10 partitions	4.67%
25.1K	N = 10 partitions	4.28%
29.9K	N = 10 partitions	3.93%
35.5K	N = 10 partitions	3.6%
42.2K	N = 10 partitions	3.3%
50.1K	N = 10 partitions	3.03%
59.6K	N = 10 partitions	2.78%
70.8K	N = 10 partitions	2.55%
84.1K	N = 10 partitions	2.34%
100K	N = 10 partitions	2.15%
119K	N = 10 partitions	1.97%
141K	N = 10 partitions	1.81%
168K	N = 10 partitions	1.66%
200K	N = 10 partitions	1.52%
237K	N = 10 partitions	1.39%
282K	N = 10 partitions	1.28%
335K	N = 10 partitions	1.17%
398K	N = 10 partitions	1.08%
473K	N = 10 partitions	0.987%
562K	N = 10 partitions	0.905%
668K	N = 10 partitions	0.83%
794K	N = 10 partitions	0.761%
944K	N = 10 partitions	0.698%
1.12M	N = 10 partitions	0.641%
1.33M	N = 10 partitions	0.588%
1.58M	N = 10 partitions	0.539%
1.88M	N = 10 partitions	0.494%
2.24M	N = 10 partitions	0.454%
2.66M	N = 10 partitions	0.416%
3.16M	N = 10 partitions	0.382%
3.76M	N = 10 partitions	0.35%
4.47M	N = 10 partitions	0.321%
5.31M	N = 10 partitions	0.295%
6.31M	N = 10 partitions	0.27%
7.5M	N = 10 partitions	0.248%
8.91M	N = 10 partitions	0.227%
10.6M	N = 10 partitions	0.209%
12.6M	N = 10 partitions	0.191%
15M	N = 10 partitions	0.175%
17.8M	N = 10 partitions	0.161%
21.1M	N = 10 partitions	0.148%
25.1M	N = 10 partitions	0.135%
29.9M	N = 10 partitions	0.124%
35.5M	N = 10 partitions	0.114%
42.2M	N = 10 partitions	0.105%
50.1M	N = 10 partitions	0.096%
59.6M	N = 10 partitions	0.088%
70.8M	N = 10 partitions	0.081%
84.1M	N = 10 partitions	0.074%
100M	N = 10 partitions	0.068%
100	N = 100	303%
119	N = 100	278%
141	N = 100	255%
168	N = 100	234%
200	N = 100	215%
237	N = 100	197%
282	N = 100	181%
335	N = 100	166%
398	N = 100	152%
473	N = 100	140%
562	N = 100	128%
668	N = 100	117%
794	N = 100	108%
944	N = 100	98.8%
1.12K	N = 100	90.6%
1.33K	N = 100	83.1%
1.58K	N = 100	76.2%
1.88K	N = 100	69.9%
2.24K	N = 100	64.1%
2.66K	N = 100	58.8%
3.16K	N = 100	54%
3.76K	N = 100	49.5%
4.47K	N = 100	45.4%
5.31K	N = 100	41.7%
6.31K	N = 100	38.2%
7.5K	N = 100	35%
8.91K	N = 100	32.1%
10.6K	N = 100	29.5%
12.6K	N = 100	27%
15K	N = 100	24.8%
17.8K	N = 100	22.8%
21.1K	N = 100	20.9%
25.1K	N = 100	19.1%
29.9K	N = 100	17.6%
35.5K	N = 100	16.1%
42.2K	N = 100	14.8%
50.1K	N = 100	13.6%
59.6K	N = 100	12.4%
70.8K	N = 100	11.4%
84.1K	N = 100	10.5%
100K	N = 100	9.6%
119K	N = 100	8.8%
141K	N = 100	8.07%
168K	N = 100	7.41%
200K	N = 100	6.79%
237K	N = 100	6.23%
282K	N = 100	5.72%
335K	N = 100	5.24%
398K	N = 100	4.81%
473K	N = 100	4.41%
562K	N = 100	4.05%
668K	N = 100	3.71%
794K	N = 100	3.41%
944K	N = 100	3.12%
1.12M	N = 100	2.87%
1.33M	N = 100	2.63%
1.58M	N = 100	2.41%
1.88M	N = 100	2.21%
2.24M	N = 100	2.03%
2.66M	N = 100	1.86%
3.16M	N = 100	1.71%
3.76M	N = 100	1.57%
4.47M	N = 100	1.44%
5.31M	N = 100	1.32%
6.31M	N = 100	1.21%
7.5M	N = 100	1.11%
8.91M	N = 100	1.02%
10.6M	N = 100	0.932%
12.6M	N = 100	0.855%
15M	N = 100	0.785%
17.8M	N = 100	0.72%
21.1M	N = 100	0.66%
25.1M	N = 100	0.606%
29.9M	N = 100	0.555%
35.5M	N = 100	0.509%
42.2M	N = 100	0.467%
50.1M	N = 100	0.429%
59.6M	N = 100	0.393%
70.8M	N = 100	0.361%
84.1M	N = 100	0.331%
100M	N = 100	0.303%

Principle: Variance costs more than volume →

At high volume this variance disappears. At low volume it is visible. Know it, so that you do not spend a week chasing a "skew" that is only chance.

Kafka's sticky partitioner is an interesting refinement. Assignment is still random, but batched: the producer fills one partition's batch, then switches to another. The long-run balance is the same, but batching is much better. The reason: a producer sends records in batches to each partition, and a batch pays a fixed cost per request (this is the batching lesson of Flow control). If you spray single records across N partitions, you get N tiny batches and lose the benefit. This is routing and flow control interacting: the naive routing choice damages batching, and the fix is to make the routing coarser in time.

Key-based (hash)

f = hash(key) % N

A hash function turns any value (a string, a number) into a large, evenly spread number. The same key always gives the same number. Taking it modulo N gives a destination between 0 and N−1. In Python:

import zlib

def partition_for(key: str, n_partitions: int) -> int:
    return zlib.crc32(key.encode()) % n_partitions

partition_for("order-4711", 12)   # always the same partition for this key

This is the default in data engineering, and correctly so, because our records are facts about entities (an order, a seller, a user) and nearly all downstream work is per entity.

What it buys:

All records for one key land on one partition. So per-key order is preserved (see "Message keys and key-based ordering" below).
Stateful processing becomes local. A consumer that keeps per-key state (a running total, a join, a session, a set of already-seen IDs for deduplication) needs no coordination with any other consumer, because no other consumer will ever see that key. This is what makes distributed stream processing tractable at all. It is worth saying plainly: key partitioning converts one distributed state problem into N independent local state problems.
Co-partitioned joins. If two streams are partitioned by the same key with the same N, they can be joined partition by partition, with no shuffle (a shuffle is a network-wide redistribution of records).

What it costs:

Skew, proportional to your data's real distribution. Covered in the next section. It is the dominant operational concern.
N is nearly immovable. hash(key) % N reassigns almost every key when N changes. For a stateful consumer, state must be moved. For a log, the historical order of each key is broken across the boundary. Kafka forbids decreasing the number of partitions for exactly this reason.
Cross-key operations require a shuffle. Anything global (a total distinct count, a top-K across all keys, a join on a different key) needs a repartition: a full network reshuffle of the data.

Choosing the key

Choosing the key is the highest-leverage decision in this article. Here are the criteria, in order of importance:

High cardinality relative to N. Cardinality is the number of distinct key values. If cardinality is lower than N, some partitions are idle forever.
Even distribution in the real data, not in theory. Look at the actual histogram.
Matches the ordering requirement. If order matters per account, the key must be the account.
Matches the dominant downstream access pattern. Partition by what you group by.
Stable over a record's lifetime. If the key value changes (a status, a region), the entity moves to another partition in the middle of its life, and both order and state locality break.

When criteria 3 and 4 disagree, ordering usually wins, because you can repartition for the access pattern downstream, but you cannot recover an order you never had.

Range

f = the range that contains the key

For example, keys A–F go to partition 0, G–M to partition 1, and so on.

It preserves sort order globally. Range scans are efficient: a scan for keys between X and Y touches the minimum number of partitions.
It allows split and merge. A hot range can be split in two, and a cold pair can be merged. You rebalance without reassigning everything. This is why range partitioning is practical for storage systems, where hash partitioning would require a full redistribution.
But sequential keys create a write hotspot. Timestamps, auto-increment IDs and ULIDs (time-ordered unique IDs) all grow over time, so every new write goes to the last range. You have serialized all writes onto one node while N−1 nodes are idle. This is the most common data-modeling failure in HBase, Bigtable, DynamoDB, and Cassandra with a sequential clustering key (the part of the key that orders rows inside a partition).

Standard mitigations, each with a real cost:

Salting. Prefix the key with hash(key) % M. Writes spread across M ranges. The cost: a range scan now needs M sub-scans and a merge. You deliberately traded read simplicity for write distribution.
Reverse or hash the high-order part of the sequential component. This distributes writes and destroys range-scan locality completely.
A composite key with a high-cardinality prefix, such as (tenant_id, timestamp). Writes spread across tenants, while scans inside one tenant stay sequential. This is usually the right answer, because it keeps locality where you need it and takes distribution from a dimension you already have.

Hash versus range in one line: hash gives you balance and destroys ordering; range gives you ordering and hands you the responsibility for balance. Choose by whether your dominant query is a point lookup (hash) or a range scan (range).