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.
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