Real-world use

Consistent hashing began with a 1997 paper by Karger and colleagues at MIT on distributing web caches, and that research fed into the content delivery network Akamai. Today it shows up in distributed caches, key-value stores and load balancers. Not every system that "shards" uses it, though, so check what a given system actually does.

Distributed caches

Memcached servers know nothing about each other; the client decides which server holds a key. Ketama, released by last.fm in 2007, gives each server many points on a ring, and libmemcached along with several other clients and proxies such as twemproxy offer ketama-compatible distribution. Adding a cache server leaves most keys where they were, so the hit rate does not collapse.

Redis Cluster does not use a consistent hashing ring. It maps each key to one of 16,384 hash slots with CRC16(key) mod 16384 and assigns slots to nodes explicitly. When a node is added, an operator moves some slots, so the amount of movement is similarly small, but the mechanism is different.

Dynamo-style stores

Amazon's 2007 Dynamo paper combined a consistent hashing ring, virtual nodes and a preference list that replicates each key to the next N nodes clockwise, and it was hugely influential. The paper also reports that splitting the ring into fixed, equal-sized partitions assigned to nodes worked better for balance and operations. Note that the AWS DynamoDB service was inspired by the paper but is a separate system with a different internal design.

• Apache Cassandra: each node holds several tokens on the ring (num_tokens), and the default partitioner uses Murmur3. Replication walks the ring for the next nodes; NetworkTopologyStrategy also takes data centers and racks into account.
• Riak KV: the ring is split into a fixed number of partitions when the cluster is created; each partition is a virtual node (vnode), and physical nodes claim them.
• Chord, a distributed hash table: nodes and keys share one identifier circle, and a key belongs to its successor node, the same rule as consistent hashing.

Load balancers

Sending the same user or URL to the same backend lets caches and sessions be reused. Nginx switches its hash directive to ketama consistent hashing when you add consistent.

upstream cache_backend {
    hash $request_uri consistent;
    server 10.0.0.11:8080;
    server 10.0.0.12:8080;
    server 10.0.0.13:8080;
}

HAProxy does the same with hash-type consistent, and hash-balance-factor turns on consistent hashing with bounded loads, which caps any server at a multiple of the average load. A value of 150 means 1.5 times the average.

backend cache_servers
    balance uri
    hash-type consistent
    hash-balance-factor 150
    server c1 10.0.0.11:8080 check
    server c2 10.0.0.12:8080 check