Consistent hashing

A site's pages are cached on four servers. Which server is responsible for a page? The first thing that comes to mind is to take the hash of the address modulo four. That works while there are four servers. Add a fifth: the remainder modulo five is different for almost all addresses, and four fifths of the cache become useless instantly. All requests at once bypass the cache and go to the database, and the database goes down. Below are the real 8966 pages of legost.in. Add a server in both modes and compare.

With hash mod N 80.8 % of the pages changed server. On the ring, about twenty percent, the share the fifth server should take. And only its keys move, not one extra: the new server starts with an empty cache, everything it gets has to be handed over by the other servers, and the remaining keys are not touched.

The idea

Put both servers and keys on one ring, by their hashes. Each key belongs to the first server clockwise. A new server takes some point on the ring and picks up only the keys on the arc before it; all other keys stay where they were.

The ring is simply the numbers from 0 to 2⁶⁴ − 1, closed into a loop: after the largest comes zero again. The servers' hashes are kept in a sorted array, and finding the server for a key is a binary search for the first point greater than the key's hash. If there is none, take the very first one: the circle has closed.

Virtual nodes

Set one virtual node in the scene. The servers land at random points of the ring, and the arcs between them come out very different: one server holds twenty-five times as many pages as another. That is not bad luck but the nature of a random partition: a few random points on a circle almost never divide it evenly.

The solution is to put each server on the ring many times, at the points of the hashes of the names “cache-1#0”, “cache-1#1”, … These are virtual nodes. Each server collects many small arcs, and their sum is much closer to the average. With a hundred nodes the load on our pages ranges from 1682 to 1848 against a fair share of 1793. A handy lever comes along too: a server twice as powerful can be given twice as many virtual nodes.

There is a second benefit. When a server is switched off, with one node all its keys would go to a single neighbour on the ring, while with a hundred nodes they spread over all servers a little at a time.

Code

The ring is a sorted list of pairs “hash, server”, and the search is bisect in Python and sort.Search in Go. The hash is the first eight bytes of MD5: cryptographic strength is not needed here, what is needed is that the hash is the same on all machines and in all languages. Python's built-in hash() will not do for this: it changes from run to run.

Note the second line: with one virtual node only 8 % moved, less than the “due” 20 %. That is no gain: the fifth server simply landed on a short arc and got few keys, while the busiest server holds 3519 pages instead of 1793.

What it costs

Finding a server is a binary search over N·v points: O(log(N·v)). For ten servers of a hundred nodes that is ten comparisons. Adding or removing a server means re-sorting, O(N·v log(N·v)), but that is a rare event. Memory is the same N·v points.

The main bound here is not about time but about moves: adding a server to N existing ones moves about 1/(N + 1) of the keys, against N/(N + 1) for the remainder modulo N. For four servers that is 20 % against 80 %, for a hundred 1 % against 99 %.

What else there is

• Rendezvous hashing (highest random weight): for each key compute the hash of the pair “key, server” for all servers and take the server with the largest. No ring and no virtual nodes, an even load, but a lookup costs O(N).
• Jump consistent hash (Lamping and Veach, Google, 2014): a few lines of arithmetic, no memory, a perfectly even load, but servers are numbered consecutively, and a server cannot be removed from the middle.
• Bounded load: if a server is overloaded, the key goes to the next one on the ring. This is how “hot” keys, which alone can overload a server, are fought.

History

Consistent hashing was invented in 1997 by David Karger, Tom Leighton, Daniel Lewin and their co-authors, for distributed web caches that would take the load off popular sites at peak hours. A year later Leighton and Lewin founded Akamai on this idea, one of the first content delivery networks. Later the ring with virtual nodes became the basis of the Amazon Dynamo store (a 2007 paper) and of the databases that grew out of it, such as Cassandra.

Problems

Implement the ring yourself and count how many keys move when a new server is added to the cluster. The main trap is the keys that “step over” zero.