Consistent Hashing: Explained

Update: We no longer use basic ring consistent hashing. We further improved our consistent hashing by implementing Maglev hashing. Read MagLev, our new consistent hashing scheme.

One great MemCachier feature is built-in support for consistent hashing. Consistent hashing ultimately gives you better hit ratios when servers in your cache are either added or removed. In this post we’ll explain consistent hashing and show you why you should care.

Basic Hashing

A basic hashing algorithm involves a hash function and a modulo operation. The modulo operation is necessary because the number of possible cache buckets is finite. With memcache, the modulo is required to choose which server your key should be hashed to. The equation looks like this:

server_with_key = hash(key) % server_list.length

Basic hashing works great when your list of servers never changes. However, when the list of servers is increased or decreased, a large percentage of your keys will be hashed to different servers. This will result in a huge increase in cache misses. An increase in cache misses means your app will need to re-calculate the values for lost keys, usually resulting in slower HTTP response times due to increased server load.

Consistent Hashing: Explained

Consistent hashing is an alternate hashing algorithm that will impact cache miss rates far less when the list of servers changes. Consistent hashing works by defining a ring of servers like this:

Hashing diagram

When a key is hashed, it is placed somewhere on the edge of the circle. If it isn’t hashed directly to a server, the nearest server is chosen:

Hashing diagram

When a server is added to the circle, it will be placed on the edge of the circle. When keys are hashed onto the circle edge, keys closer to the new server will hash to the new server instead of the other servers.

Hashing diagram

When a new machine is added, only a subset of keys will be hashed differently, which reduces the impact on your cache miss rate, resulting in faster HTTP responses and less server load.

Consistent Hashing in MemCachier

All key-based api calls to MemCachier are consistently hashed regardless of the client you’re using. This is one benefit to using MemCachier – other caching alternatives including memcached rely on the client library to implement consistent hashing. With MemCacheir, consistent hashing is built-in and enabled by default.

Dive Deeper into Consistent Hashing

Michael Nielsen has an excellent, detailed explanation of consistent hashing if you’d like to learn more.

Diagram Credit: Michael Nielsen

Get Started with MemCachier

Current we we offer memcache in Heroku and memcache in AppHarbor. More platforms will be coming soon!