The magic of consistent hashing is that adding or removing a cache server only forces a tiny fraction of keys to be remapped, drastically reducing cache misses when your cluster scales.
Let’s see it in action. Imagine we have three Memcached servers: mc1:11211, mc2:11211, and mc3:11211. A client application needs to store a key, say user:12345. Without consistent hashing, a simple modulo operation on the hash of the key might map it to server 1.
# Using Python's hashlib for demonstration
import hashlib
def simple_hash(key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
servers = ["mc1:11211", "mc2:11211", "mc3:11211"]
num_servers = len(servers)
key = "user:12345"
server_index = simple_hash(key) % num_servers
print(f"Key '{key}' maps to server: {servers[server_index]}")
If we add mc4:11211, num_servers becomes 4. Now, simple_hash(key) % 4 will likely result in a different server index, causing a cache miss for user:12345 even though the data was already in the cache on mc1. This is the problem we’re solving.
Consistent hashing, however, maps both servers and keys onto a conceptual ring. Each server is assigned multiple "virtual nodes" (or "replicas") on this ring. When a key needs to be stored, its hash determines its position on the ring. The client then walks clockwise around the ring until it finds the first server (or its virtual node). This server is responsible for that key.
Consider this ketama configuration (a popular consistent hashing library for Memcached):
# ketama.conf
mclient_host 192.168.1.101 11211 1
mclient_host 192.168.1.102 11211 1
mclient_host 192.168.1.103 11211 1
Here, mclient_host <ip> <port> <weight> defines a server. The 1 is the weight, meaning each server has equal importance. A more robust configuration would use many virtual nodes per server:
# ketama.conf with virtual nodes
mclient_host 192.168.1.101 11211 100
mclient_host 192.168.1.102 11211 100
mclient_host 192.168.1.103 11211 100
The 100 here is not the number of virtual nodes directly, but a weight. Libraries like ketama use this weight to determine how many points on the hash ring each physical server "owns." A higher weight means more virtual nodes, and thus a larger portion of the hash space assigned to that server. When a server is added or removed, only the keys that fall into the range now owned by the new server, or that were owned by the removed server, need to be remapped. The vast majority of keys remain unaffected because their hash points to a server that hasn’t changed its position relative to them on the ring.
The core idea is that the hash of the key determines its position, and the hash of the server (or its virtual nodes) determines its position. When you add 192.168.1.104, it gets placed on the ring. Only the keys whose hash falls between the hash of 192.168.1.103 and the hash of 192.168.1.104 (walking clockwise) will now be served by 192.168.1.104. The keys that were previously mapped to 192.168.1.101 or 192.168.1.102 will likely continue to point to them.
The key to understanding how this minimizes cache misses is to visualize the hash ring. Imagine it as a circle from 0 to 2^32 - 1. Each server (or its virtual nodes) gets a random spot on this circle. A key also gets a spot. The server responsible for the key is the next server encountered when moving clockwise from the key’s position. When you add a new server, it inserts itself into the circle. It only "steals" keys from the server immediately clockwise to it. Conversely, when you remove a server, the server that was previously clockwise to the removed server now becomes responsible for the keys that the removed server held. The number of keys affected is proportional to the "distance" between the servers on the ring, which is generally small due to the random distribution of virtual nodes.
The number of virtual nodes per server is crucial. A common recommendation is 100-200 virtual nodes per physical server. This ensures a more even distribution of keys across the servers, making the load balancing more effective and further reducing the impact of adding or removing a node. If you have too few virtual nodes, the distribution can be uneven, leading to "hot spots" where one server gets disproportionately more keys.
You’re probably wondering about the weight parameter. It’s a multiplier for the number of virtual nodes. If server A has weight 100 and server B has weight 200, server B effectively gets twice as many virtual nodes and will own roughly twice as much of the hash ring, thus handling twice as many keys. This is how you can provision servers with different capacities.
If your client library doesn’t support consistent hashing (like a naive memcached client using mod_hash), you’ll see dramatically increased cache miss rates during cluster resizing events, potentially causing application slowdowns or even outages as your backend database gets hammered.
The next problem you’ll likely encounter is managing the lifecycle of these consistent hash ring configurations, especially in dynamic environments where servers are added and removed automatically.