Scaling Memcached with Consistent Hashing: Why It Matters

Why the Classic Modulo Approach Breaks

When you start with a small Memcached cluster, the simplest distribution strategy is to map a key to a server with key % N, where N is the number of nodes. Adding or removing a node forces N to change, which in turn rewrites almost all key-to-node mappings. The result is a sudden drop in cache hit rates and a spike in database traffic—a classic cache stampede.

Consistent Hashing 101

Consistent hashing solves this by placing both servers and keys on a logical 360° ring. Each key is assigned to the first server encountered when moving clockwise from the key’s hash value. Because only the portion of the ring that the new or removed node covers changes, the rest of the keys stay on the same servers.

Key Steps

• Hash the key to a 32‑bit integer.
• Hash each server address to a point on the ring.
• Find the next server clockwise from the key’s hash.
• Route the request to that server.

Virtual Nodes: Balancing the Load

Physical servers often differ in capacity. To avoid a single server becoming a hot spot, virtual nodes (replicas) are used. Each physical server is represented by multiple points on the ring, usually by hashing server:replicaIndex. The more replicas a server has, the larger its share of the key space.

Concrete Example: Adding a Fourth Node

Assume a 3‑node cluster: 10.0.0.1:11211, 10.0.0.2:11211, 10.0.0.3:11211. Each server has 100 virtual nodes. The ring is built and cached by the client library.

# Pseudo‑code for building the ring
servers = ["10.0.0.1:11211", "10.0.0.2:11211", "10.0.0.3:11211"]
replicas = 100
ring = {}
for srv in servers:
    for i in range(replicas):
        key = hash(f"{srv}:{i}") % 2**32
        ring[key] = srv
# Sort keys for efficient lookup
sorted_keys = sorted(ring.keys())

When a new node 10.0.0.4:11211 joins, we only add its 100 virtual nodes to the ring. Keys that previously mapped to the 4th node’s segment now move to it. Roughly 1/4 of the key space shifts; the other 3/4 remain on their original servers. In contrast, with modulo hashing, the entire key set would remap, causing a near‑complete cache miss.

Trade‑Offs and Risks

• Client Complexity: The client must maintain the ring and perform lookups. Libraries like libmemcached provide this, but many simple clients rely on the server to handle distribution.
• Configuration Sensitivity: Too few virtual nodes can create hot spots; too many increase memory usage in the client.
• Hot Spot Mitigation: Monitor cache_hits and cache_misses via stats commands to detect uneven load.

Practical Checklist

1. Choose a client library that supports consistent hashing (e.g., libmemcached, spymemcached).
2. Configure the number of virtual nodes per physical server (common values: 50–200).
3. When scaling, add the new server’s virtual nodes to the ring and let the client redistribute keys.
4. Verify hit ratio stability: echo stats | nc 10.0.0.1 11211 before and after scaling.
5. Watch for hot spot warnings; adjust replica count if one server consistently receives >20% of traffic.

Bottom Line

Consistent hashing with virtual nodes is a proven strategy to keep Memcached clusters stable during scaling. It avoids large cache churn, preserves hit rates, and gives you fine‑grained control over load distribution. The cost is a slightly more involved client setup, but most production‑grade libraries handle it for you. Start by enabling consistent hashing in your client, tune the replica count, and monitor the hit/miss ratios as you grow your cluster.