CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 5 of 8 · 3 min read

Partitioning by hash of the key

Scattering keys evenly with a hash function, and what is lost.

Think of dealing playing cards to players. Each card goes to a player chosen by a fair shuffle. Each player gets about the same number of cards. But if you want all hearts in order, you must ask every player.

Hash partitioning

In hash partitioning, a hash function turns each key into a number. Each partition gets a range of hash values, and a key goes to the partition whose range holds its hash.

Example: a hash gives a number from 0 to 99. Partition 1 takes 0 to 24, partition 2 takes 25 to 49, partition 3 takes 50 to 74, partition 4 takes 75 to 99. The key "user:812" hashes to 63, so it goes to partition 3.

The book explains: a good hash function takes skewed data and makes it uniform. Even when input strings are very similar, their hashes spread evenly over the range. The function does not need to be cryptographically strong. Cassandra and MongoDB use MD5, and Voldemort uses the Fowler-Noll-Vo function. The book warns that the hash function built into some programming languages may give different values for the same key in different processes, so it can be unsuitable.

A worked example with a simple stand-in (made up): hash = the sum of the character codes mod 100. This is only to show the idea. Keys "user1", "user2" and "user3" differ by one character, so their sums differ by 1: they land in neighbouring slots. A real hash function would scatter them far apart, which is why real functions are used.

The ranges of hash values can be evenly spaced or chosen pseudo-randomly. The book mentions that the second is sometimes called consistent hashing, and cautions that the term is confusing: it has nothing to do with replica consistency or ACID consistency. It says this approach does not work very well for databases, so it is rarely used in practice, and suggests the term hash partitioning. Module 6 returns to consistent hashing as used in caches and similar systems.

Strength: keys spread fairly among partitions, so the risk of skew from the key pattern is small.

Weakness: the order of keys is lost. Keys that were next to each other are now scattered over all partitions. In MongoDB with hash-based sharding, any range query goes to all partitions. Riak, Couchbase and Voldemort do not support range queries on the primary key.

A compromise: compound key. Cassandra lets a table have a compound primary key of several columns. Only the first part is hashed to find the partition. The other columns serve as a combined sorted index within the partition. A query cannot search a range on the first column, but if it fixes the first column, it can scan a range on the others efficiently. The book's example is a social site with a key of (user_id, update_timestamp). All of one user's updates live on one partition, sorted by time. Different users may be on different partitions.

A worked example. A table of posts has the key (user_id, timestamp). To fetch user 812's posts from last week: hash 812, go to that partition, scan a range of timestamps. One partition is touched. To fetch the latest posts of all users: every partition must be asked.

Key range Hash
Spread of load Depends on key pattern Even
Range query on the key One or a few partitions All partitions
Hot spot risk from sequential keys High Low
Used by Bigtable, HBase Cassandra, MongoDB (hash mode), Riak

Check yourself:

  • Why does hashing a key lose range scans?
  • What does the compound key (user_id, timestamp) allow that a pure hash of the whole key does not?