Consistent Hashing: Explained

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:

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:

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.

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s