Hash Partitioning and the Range Query It Destroys

A partitioned store answers one question before it can answer any other: given a key, which node holds it. The answer is a function, and the shape of that function decides which operations the store can perform cheaply for the rest of its life. The simplest such function is a hash reduced modulo the number of partitions. It costs a few nanoseconds, needs no metadata beyond a single integer, and permanently removes the ability to read a contiguous key range in one place.

The placement function and what it actually guarantees

A hash partitioner computes a digest of the key and reduces it into the partition space:

import hashlib

def partition_of(key: bytes, n: int) -> int:
    h = hashlib.blake2b(key, digest_size=8).digest()
    return int.from_bytes(h, 'little') % n

Three properties follow directly from the definition. The mapping is deterministic, so any node can compute the owner of any key without consulting a directory. The mapping is stateless, so a routing tier holds one integer rather than a table of ranges. And the mapping is key-uniform: over a large set of distinct keys, the counts per partition concentrate around the mean.

That last property is the whole selling point, and it is also where most reasoning about hash partitioning goes wrong. Uniformity is a statement about keys, not about requests. The hash spreads the key space evenly. It has no opinion about which keys are popular, and it cannot split a single key across two machines. A design that assumes uniform load because the partition function is uniform has confused the two distributions.

The digest width sets a hard ceiling on usable partition counts. A 32-bit hash supports at most 2^32 distinct buckets, and the birthday effect makes collisions between distinct keys likely well before that: with a 32-bit digest any given pair collides with probability 2^-32, about 2.3×10^-10, and across a set of n keys the expected number of colliding pairs is roughly n²/2^33, which is about 116 for n = 10^6. A collision does not corrupt data, since the store compares full keys inside a partition, but it does mean the nominal uniformity degrades. Sixty-four-bit digests push the practical collision count to negligible levels for any realistic key population.

Modulo reduction has its own subtlety. If the digest is a weak function, such as the identity on sequential integers, % n preserves the structure of the input: with n = 10, keys ending in 0 all land in partition 0, and the load is exactly as skewed as the access pattern. Even a good hash can concentrate when n shares a factor with a pattern in the digest. Choosing a prime modulus removes that class of artefact, and it is why hash tables traditionally size themselves to primes; the same reasoning applies to partition counts, though large-scale stores usually accept power-of-two counts and rely on a strong digest instead.

What a range query becomes

Adjacency is what a hash destroys. Two keys that sort next to each other have digests that are uncorrelated, so they land in unrelated partitions with probability (n−1)/n. Every operation defined on key order therefore degenerates into an operation on all partitions at once.

A query for records between two timestamps must be issued to every partition, because the partition that holds the low end has no relationship to the one holding the high end. Each partition returns its fragment, and a coordinator merges them. The costs multiply rather than add:

• Round trips: n parallel requests instead of one, each carrying its own network latency.
• Merge work: the coordinator sorts or merges n result streams, so the result buffer is n times larger than the answer for any prefix-limited query.
• Latency: the query completes when the slowest partition responds, not the average one. The arithmetic of that effect is severe enough to deserve its own treatment, and it is covered in Scatter-Gather Fan-Out and Tail Latency Multiplication.
• Local scan cost: without a per-partition index, each partition reads its entire local key space to find the few matching rows, so total bytes read scales with the whole data set rather than the answer size.

An ORDER BY ... LIMIT k is worse than a scan in one respect. The coordinator cannot ask each partition for k rows and stop, because the global top k may be concentrated in one partition; it must ask every partition for its local top k, then merge and truncate. That is n·k rows materialized to return k. The mitigation is to push a tighter bound down, using the current k-th best value as a filter for later requests, which reduces intermediate volume but not the fan-out.

Point lookups are unaffected. A read by primary key is one hash computation and one request, which is exactly the case hash partitioning was designed for. Stores that choose hashing are making an explicit bet that their workload is dominated by key lookups, and that scans either do not exist or are served by some other structure.

The resize bill

The cost of changing the modulus is the property that made consistent hashing necessary. Suppose the cluster grows from n to n+1 partitions. A key with digest h keeps its placement only if h % n == h % (n+1). Because n and n+1 are coprime, that condition holds for exactly 1 in n+1 residues, so the fraction of keys that must move is n/(n+1).

def fraction_moved(n: int) -> float:
    # keys stay only when h % n == h % (n + 1)
    return n / (n + 1)

print(fraction_moved(4))    # 0.8
print(fraction_moved(9))    # 0.9
print(fraction_moved(99))   # 0.99

Going from nine partitions to ten relocates ninety per cent of the data. Going from ninety-nine to a hundred relocates ninety-nine per cent. The fraction does not shrink as the cluster grows; it converges to one. This is not an implementation defect that a better hash would fix. It is a property of the reduction: the partition index of a key depends on every bit of the modulus, so any change to the modulus re-rolls the assignment for almost every key.

The practical consequence is that modulo hashing over a fixed partition count is only workable when the count is fixed for the lifetime of the data set, or when the store can afford a full rewrite. Systems that expect to grow use a fixed number of logical partitions, often a few hundred or a few thousand, mapped onto a smaller number of physical nodes. Growth then moves whole logical partitions between machines, which is a bounded data movement problem rather than a rehash of everything. The ring-based scheme in Consistent Hashing Rings and Virtual Node Counts is the other standard answer, and it changes the moved fraction from n/(n+1) to roughly 1/(n+1).

Where the uniformity argument fails

Three failure modes recur, and each has a different remedy.

The first is a single hot key. If one key receives a large share of all requests, that key lives on exactly one partition, and no amount of hashing changes that. The partition’s capacity bounds the key’s throughput. Remedies are replication of that key, application-level caching, or splitting the key into sub-keys with a counter suffix, which turns one logical write into several physical ones. The last option appears again in Why Append-Only Keys Concentrate Load on One Shard, where the same mechanism is used against a different cause of skew.

The second is statistical variance in the partition function itself. With k keys and n partitions, the per-partition count is a binomial with mean k/n and standard deviation sqrt(k/n). For a million keys over a hundred partitions the mean is ten thousand and the standard deviation is about a hundred, so a one per cent spread. For a thousand keys over a hundred partitions the mean is ten and the standard deviation is about three, which is a thirty per cent spread: small data sets do not average out, and a freshly created cluster with few keys can look badly balanced purely by chance. The largest of n such bins exceeds the mean by roughly sqrt(2 ln n) standard deviations, so the worst partition is a predictable multiple of the average rather than an unbounded outlier.

The third is range-shaped access to a hash-partitioned key space. A query pattern that reads a narrow key range, such as the last hour of events, touches every partition but finds data in only a few. The work is proportional to n while the useful output is proportional to the range width, and the ratio worsens as the cluster grows.

The choice, stated as an axis

The decision between hash and range partitioning is not a matter of taste; it is a choice of which operation to make cheap. Hashing makes key lookup O(1) with no metadata and keeps load even across nodes, at the price of turning every ordered operation into a fan-out and making resize cost proportional to the whole data set. Range partitioning inverts every one of those properties: it preserves order and locality, requires a boundary table that must be kept consistent, and concentrates writes whenever keys arrive in ascending order.

A store can hold both, and many do: a hash of the key chooses the partition, and a sorted structure inside the partition serves ordered reads within that partition. That hybrid serves range queries only when the range is narrow enough to fall inside one partition’s local ordering, which is useful for secondary attributes but not for the primary key range. The genuine alternatives at the partition level are the ones described in Range Partition Boundaries and the Split Key Contract, where order is preserved and the cost moves into metadata maintenance.

None of this makes hash partitioning wrong. It makes it a specific trade with a specific bill, and the bill comes due at resize time and at every scan.