Using Memcached Consistent Hashing to Avoid Cache Stampede When Scaling

The Scaling Problem: Cache Stampede and Mass Invalidations

When a Memcached cluster grows or shrinks, a naïve modulo‑based key distribution (key % N) forces almost every key to be remapped to a different node. The sudden shift floods the backend with misses, creating a cache stampede that can overwhelm databases and increase latency.

Thesis: Client‑Side Consistent Hashing Limits Key Movement

Memcached itself is a shared‑nothing store; the hashing logic lives in the client. By using a consistent hashing algorithm (commonly Ketama) with virtual nodes, only a fraction of keys—roughly 1/N—need to move when the node count changes, dramatically reducing the miss surge.

How Consistent Hashing Works in Practice

• Keys and physical nodes are placed on a logical hash ring (continuum) using a 64‑bit hash function.
• Each physical node is represented by multiple virtual nodes (vnodes) spread evenly around the ring.
• To locate a key, the client hashes the key, walks clockwise until it finds the first vnode, then maps to the owning physical node.
• Adding or removing a node only affects the keys that fall between the old and new positions of its vnodes.

Worked Example: Enabling Ketama Consistent Hashing in a Popular Client

The following snippet shows how to configure the spymemcached Java client (version 2.12+) to use Ketama consistent hashing with 160 virtual nodes per physical node.

// Build the client list
List<InetSocketAddress> addresses = Arrays.asList(
    new InetSocketAddress("cache1.example.com", 11211),
    new InetSocketAddress("cache2.example.com", 11212),
    new InetSocketAddress("cache3.example.com", 11213)
);

// Create the connection factory with Ketama
ConnectionFactoryBuilder cfBuilder = new ConnectionFactoryBuilder()
    .setProtocol(ConnectionFactoryBuilder.Protocol.BINARY)
    .setLocatorType(ConnectionFactoryBuilder.LocatorType.KETAMA)
    .setNumAddrPerConnection(1)
    .setFailureMode(true) // optional: redistribute on failure
    .setHashAlg(ConnectionFactoryBuilder.HashAlg.NATIVE_HASH); // uses MurmurHash

ConnectionFactory cf = cfBuilder.build();

// Instantiate the client
MemcachedClient client = new MemcachedClient(cf, addresses);

// Example operation
client.set("user:12345", 3600, "serialized-data");
String value = (String) client.get("user:12345");
client.shutdown();

Key points:

• setLocatorType(LocatorType.KETAMA) tells the library to use the Ketama consistent hashing algorithm.
• The default number of virtual nodes is 160 per physical node, which can be tuned via setNumCopies(int) if the client exposes it.
• After changing the node list (adding or removing an address), only the keys that hash to the segment between the old and new vnode positions are remapped.

Verifying the Effect

You can observe the limited key movement without relying on speculative output:

1. Record the distribution of keys across nodes before a topology change using the client’s stats command (e.g., stats items or a custom key‑to‑node map).
2. Add a new Memcached node to the client’s address list and restart the client (or use a dynamic reconfiguration API if available).
3. After the change, repeat the stats collection and compare the proportion of keys that reported a different node than before. With Ketama and 160 vnodes, you should see roughly 1 / (old node count + new node count) of keys moved, not near 100 %.
4. Monitor backend request rates during the reconfiguration; a well‑behaved consistent‑hash setup will show only a modest spike, not the orders‑of‑magnitude surge seen with modulo hashing.

Trade‑offs and Limitations

• Consistent hashing does not protect against a thundering herd on a single hot key; if that key is heavily accessed, all clients will still hit the same node and any miss will cause a burst.
• Improper vnode count can create hot spots: too few vnodes leads to uneven load, especially when nodes have different capacities.
• Not all Memcached clients implement Ketama; you must verify that the library you choose explicitly supports consistent hashing (look for “Ketama”, “consistent”, or “CRC32‑based ring” in the documentation).
• The algorithm adds a small CPU overhead for hashing and vnode lookup, but this is negligible compared to network latency in most deployments.

Actionable Checklist

1. Confirm your Memcached client offers a Ketama or equivalent consistent hashing locator.
2. Configure the client with a reasonable vnode count (start with the library default, adjust after load testing).
3. Deploy the client configuration across all application instances.
4. Perform a controlled scaling test: add a node, watch key migration via stats, and verify that miss rates stay within expected bounds.
5. Monitor hot‑key metrics separately; consider using a secondary cache layer or request coalescing if a single key drives excessive traffic.

By relying on client‑side consistent hashing, you gain a predictable, low‑overhead way to scale Memcached clusters without triggering the cache‑miss storms that can destabilize your backend services.