Hash Partitioning and the Modulo Trap

A hash turns any key — a UUID, an email, a tenant name — into a value that is uniformly distributed even when the input is not. That is genuinely valuable: user ids that arrive in blocks, emails clustered by domain, and sequential order numbers all flatten out. Take the hash modulo N and you have a partition number, computed locally, in nanoseconds, with no lookup and no state.

Two properties that matter and are easy to take for granted. The hash must be deterministic across processes and versions — Java’s String.hashCode() is stable, Python’s hash() of a string is randomised per process by default, and using the wrong one gives every process a different partition map. And it must be cheap and well-distributed but need not be cryptographic: MurmurHash3, xxHash and CRC32 are the usual choices; SHA-256 works and is a hundred times slower for no benefit here.

The mapping is also *stateless*, which is its real charm — there is no directory to replicate, no map to keep consistent, nothing to go stale. Everything a router needs is the function and N.

Here is the concrete fact, and it is worth internalising as a number rather than a vibe. A key stays put when h % 4 === h % 5, which happens only when h mod 20 < 4 — that is, for 20% of hash values. Adding one node to a four-node cluster relocates 80% of the data.

The general result: moving from N to N′ leaves roughly 1 / lcm-worth of keys in place, which for the common case of N′ = N + 1 works out to about 1 / N′ staying and 1 − 1/N′ moving. Going from 10 nodes to 11 moves 91% of the keys. Going from 100 to 101 moves 99%. The scheme gets worse as the cluster gets bigger, which is the opposite of what you want from a scaling technique.

And this is not merely a large data transfer. During the reshuffle, every cache in the system is invalidated at once, every node is simultaneously a source and a destination, the network is saturated by the move rather than by traffic, and any client still holding the old N is routing to nodes that no longer own the keys. A capacity expansion becomes an outage.

Before reaching for consistent hashing, know the simpler fix that many production systems actually use: decouple the number of partitions from the number of nodes. Hash into a large, fixed number of logical partitions — 1024, or 4096 — and then keep a separate, small map from partition to node.

Now hash(key) % 1024 never changes, because 1024 never changes. Adding a node means reassigning some *partitions* to it — moving whole partitions, not rehashing keys. The move is discrete, plannable, resumable, and involves exactly the data you intended to move: with 1024 partitions over 10 nodes, adding an eleventh moves about 1/11 of the data, in units of ~93 partitions.

This is what Kafka does with topic partitions, what Elasticsearch does with primary shards, and what Riak does with vnodes. The cost is that you must choose the partition count up front and it is painful to raise later (changing it *does* rehash), and that you now maintain a map — a small piece of distributed state that must be agreed on and distributed. That is a much better problem to have than an 80% reshuffle.

Consistent hashing (The Ring: Keeping the Mapping Stable When Membership Changes) solves the same problem without a stored map, at the cost of worse balance and a more subtle failure mode. Both are legitimate; the fixed-partition scheme is easier to reason about and easier to operate, and is underrated for it.

Two limitations are structural, and neither is repaired by a better hash function.

Ordering is destroyed. SELECT * WHERE created_at BETWEEN x AND y used a single index scan before; now the rows for that range are uniformly scattered, and the only way to answer is to ask every partition and merge — see Cross-Partition Operations: Paying for What the Split Took Away and Fan Out to 100 and the Component’s Tail Becomes the System’s Median. If ordered scans are a core access pattern, you want Range Partitioning: Scans You Keep, Hotspots You Inherit and its hotspot problems instead.

Traffic skew survives hashing. A hash spreads *keys* evenly. It says nothing about how many requests each key receives. One celebrity account is one key, and one key lands on exactly one partition no matter how good the hash is. Hot Partitions: The Skew Hashing Cannot Fix is a whole lesson because this is the case people expect hashing to solve and it structurally cannot.

A third, softer one: hashing over a key with low cardinality is a trap. hash(country) % 64 gives you at most ~200 distinct destinations and a very lumpy distribution; the number of distinct key values must be *much* larger than the partition count, ideally by two orders of magnitude.