Partitioning by Hash of Key

Key ranges put related keys next to each other, and that adjacency turned out to be both the feature and the fault: cheap range scans on one side, a saturated partition on the other. Because of exactly that risk of skew and hot spots, many distributed datastores take the opposite approach and destroy the adjacency on purpose.

They hash the key.

A Hash Turns Skew Into Uniformity

A good hash function takes skewed input and returns a uniform distribution. Hand it a 32-bit hash function and any string comes back as a seemingly random number between 0 and 2³² − 1. Crucially, very similar inputs get very dissimilar outputs — user:1001 and user:1002 differ by one character and land nowhere near each other.

Hashing the key, then partitioning the hash

Six adjacent user ids are hashed. Showing the first two bytes of each hash, the values land at scattered points across a 16-bit space divided into eight equal partitions, so neighbouring ids end up on unrelated partitions. Partition boundaries are ranges of hashes, not ranges of keys.

That is the entire trick. Whatever clustering your keys had — sequential ids, timestamps, everything sharing a tenant prefix — the hash flattens it. And it flattens it without knowing anything about your data, which is the real appeal: no boundary tuning, no administrator watching for a partition going lopsided, no adjusting as the distribution shifts. The uniformity is a property of the hash function, not of the data.

Which Hash

The hash does not need to be cryptographically strong. Cassandra and MongoDB use MD5; Voldemort uses the Fowler–Noll–Vo function. Nobody is defending against an adversary here, only against clumping, so the bar is “spreads well and runs fast” rather than “resists collision attacks”.

What it does need is to be stable. Many languages ship a built-in hash intended for hash tables, and those are specifically unsuitable:

Java’s Object.hashCode() and Ruby’s Object#hash may return a different value for the same key in a different process. Some implementations seed the hash randomly at startup, precisely to defend hash tables against collision attacks.
The consequence is that two nodes computing the partition for the same key can disagree — so a write goes to one node and the subsequent read looks on another.
Worse, a single node restarting can start computing different partitions than it did an hour ago. The data has not moved; the function that finds it has.

None of this announces itself. There is no error, no crash, no divergence alarm — the records simply stop being where anything thinks they are. Pick a hash with a specified, version-stable output and treat it as part of your storage format, because that is what it is.

Ranges of Hashes, Not Ranges of Keys

Once you have a suitable hash, the mechanism is the same as the previous post’s, one level removed. Each partition owns a continuous range of hashes rather than a range of keys, and a key belongs to whichever partition’s hash range its hash falls into.

Because the hash output is uniform by construction, the boundaries no longer need to adapt to anything. Split the hash space into equal slices and each slice gets roughly the same share of keys, whatever the keys look like. That is the work the key-range scheme had to do by watching the data, done for free.

The boundaries can be evenly spaced, or chosen pseudorandomly.

A Word on “Consistent Hashing”

That pseudorandom variant is often called consistent hashing, and the term causes more confusion than it removes.

As Karger et al. defined it, it is a way of spreading load across an internet-wide system of caches — a CDN — using randomly chosen partition boundaries so that no central control or distributed consensus is needed to agree on them. The consistent in the name has nothing to do with replica consistency, and nothing to do with ACID consistency either. It is a statement about rebalancing behaviour.

It also does not work particularly well for databases, so it is rarely used as defined — while the documentation of several databases claims to use it, often inaccurately. Kleppmann’s advice is worth adopting wholesale: skip the term and say hash partitioning. If someone tells you their database uses consistent hashing, the useful follow-up is what happens when a node is added, not what the term is supposed to mean.

The Bill: Range Queries

Hashing buys the even spread by destroying the sort order, and the sort order was doing real work.

One range query, under key ranges and under hashing

The same query — one user's posts over one month — run against both schemes. Under key-range partitioning it is a single sequential scan inside one partition. Under hash partitioning the rows are scattered, so the same query has to be sent to every partition and the results merged.

Keys that were once adjacent are now scattered across every partition, so a range query no longer maps to one node. Databases handle that differently, and none of them handle it well:

Riak, Couchbase and Voldemort do not support range queries on the primary key at all. The operation is simply absent.
MongoDB, with hashed sharding enabled, accepts the query and broadcasts it to every partition. It works, and it costs you the entire cluster for one read.

The feed store’s central read — one user’s posts over one month — has gone from a sequential scan on one node to a scatter-gather across the cluster. In exchange, no partition is ever hot because of what the keys look like.

Cassandra’s Compromise

Cassandra splits the difference, and the mechanism is worth understanding because it is not a hack.

A table declares a compound primary key of several columns. Only the first column is hashed to determine the partition. The remaining columns are not hashed at all — they become a concatenated index used to sort the data within that partition.

A compound key: hash the first column, sort by the rest

A compound primary key of user id and timestamp. Only the user id is hashed, and that alone picks the partition; the timestamp is a sort key inside it. So writes spread across partitions by user, while one user's posts stay adjacent and in time order, which keeps the range scan cheap.

The consequence is precise: a query cannot range over the first column, because the first column’s ordering is gone. But if it specifies a fixed value for the first column, it can then range efficiently over the others.

Which is exactly the query the feed store cares about. With a primary key of (user_id, timestamp), different users are spread across partitions by the hash, while within each user the posts are stored in timestamp order on a single partition. Even write distribution, and a cheap scan of one user’s timeline.

This is an elegant fit for one-to-many relationships generally — a user and their many posts, an article and its many comments, a device and its many readings. The “one” side picks the partition; the “many” side stays sorted inside it.

Scheme	Write spread	Range scans	Boundary tuning	Used by
Key range	poor if key is sequential	one partition	must follow the data	HBase, Bigtable, RethinkDB
Hash	even, always	every partition	none needed	Riak, Couchbase, Voldemort
Compound key	even by first column	within one partition	none needed	Cassandra

The compound key is not strictly better — it only works when your queries genuinely have a fixed value for the first column. If they do, it dominates. If they do not, you are back to choosing between the first two rows.

Key Takeaways

A good hash makes skewed keys uniform, so hash partitioning removes the hot spots that key ranges create — and it does so without knowing anything about the data.
The hash need not be cryptographic, but it must be stable across processes. Object.hashCode() and Object#hash are not, and the failure is silent.
Partitions own ranges of hashes rather than ranges of keys, so the boundaries never need tuning.
“Consistent hashing” is a CDN technique whose name means neither replica nor ACID consistency, works poorly for databases, and is best called hash partitioning.
Hashing costs you the sort order, and with it efficient range queries on the primary key — either unsupported outright, or broadcast to every partition.
A compound key recovers both: hash the first column for spread, sort by the rest for scans within a fixed value of it.

There is one kind of skew none of this touches. Hash the key all you like — if every request is for the same key, they all still land on the same partition.

References

Martin Kleppmann, Designing Data-Intensive Applications, chapter 6 — the treatment of partitioning this sub-series works through.
David Karger et al., Consistent Hashing and Random Trees — the 1997 paper the term comes from, and the CDN problem it was actually solving.
Giuseppe DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store — hash partitioning applied to a production datastore.
Apache Cassandra — Dynamo-style architecture and CQL data definition — partition keys, clustering columns, and what a compound primary key actually permits.
MongoDB — Hashed Sharding — including the note that range queries under a hashed shard key are broadcast.
Fowler–Noll–Vo hash — the non-cryptographic hash Voldemort uses.