Choosing a Sharding Strategy for Memcached Clusters

The Scaling Problem: Cache Stampedes

Memcached lacks built‑in clustering; the client decides which server stores a key. Adding or removing a node changes the mapping. With simple modulo (hash(key) % N) almost every key remaps, causing a cache stampede.

Sharding Options Comparison

Aspect	Modulo	Ketama	HRW (Rendezvous)
Redistribution on add/rm	~100% of keys move	~K/N keys move (K = virtual nodes)	~1/N keys move
Distribution uniformity	Poor unless N is power of 2	Good (via virtual nodes)	Excellent
Implementation effort	Trivial	Medium (ring + binary search)	Low (max hash per node)
Common client support	Most basic clients	libmemcached, spymemcached, java‑client, php‑memcached	gomemcache, rust‑memcache, python‑memcached (hrw)

Trade‑offs

Modulo is simplest but yields near‑total key movement during scaling, flooding the backend with requests.

Ketama places physical and virtual nodes on a hash ring; only keys assigned to the moved node’s virtual nodes are remapped. Uniformity improves with many virtual nodes (typically 160 per host). The ring must be rebuilt when the node list changes, requiring O(log V) lookup per key.

HRW (Rendezvous) computes hash(key, node) for each node and picks the maximum. No virtual‑node ring is needed, giving O(N) lookup per key but excellent uniformity and natural weighting.

Implementation and Validation

All clients must use identical algorithm, node list, and ordering to avoid split‑brain misses.

Java (spymemcached) – Ketama

// Build the client once at startup
List<InetSocketAddress> servers = Arrays.asList(
    new InetSocketAddress("memcache-01.internal", 11211),
    new InetSocketAddress("memcache-02.internal", 11211),
    new InetSocketAddress("memcache-03.internal", 11211)
);
// Sort lexicographically to guarantee identical ordering across clients
Collections.sort(servers, Comparator.comparing(Object::toString));

KetamaConnectionFactoryBuilder factory = new KetamaConnectionFactoryBuilder();
MemcachedClient client = new MemcachedClient(factory.build(), servers);

To validate, run a local 3‑node cluster (Docker) and map 100 000 keys. Record the node for each key. Add a fourth node to the sorted list and remap the same keys. With Ketama you should see roughly 1/4 of keys change node; with modulo you will see >90% change.

Go (gomemcache) – HRW (default)

import "github.com/bradfitz/gomemcache/memcache"

func newClient(addrs []string) *memcache.Group {
    // gomemcache uses rendezvous hashing internally
    return &memcache.Group{Addrs: addrs}
}
// Example usage:
// client := newClient([]string{"memcache-01:11211","memcache-02:11211","memcache-03:11211"})

Add or remove an address from the slice and repeat the key‑mapping test; only keys that mapped to the removed node should miss.

Weighted Nodes

If hosts differ in RAM, assign a weight proportional to memory. In Ketama increase the virtual‑node count for the heavier host; in HRW multiply the hash score by the weight. Most modern clients (libmemcached ≥ 1.0, gomemcache, python‑memcached) expose a weight parameter.

Operational Tips

• Store the sorted server list in a service‑discovery system (Consul, etcd, DNS SRV) and reload clients on change without restart.
• When using DNS, sort the returned IPs lexicographically before building the ring to guarantee identical ordering.
• Memcached ≥ 1.6 removed UDP; use TCP for all production traffic.
• Consistent hashing does not alleviate hot keys; pair with a local L2 cache (Caffeine, Guava) for frequently accessed items.

Limitations

• All clients must agree on hashing algorithm, virtual‑node count (Ketama), and node ordering; mismatched clients cause silent cache splits.
• Ketama ring construction is not thread‑safe in some older libraries (e.g., spymemcached < 2.12); build the ring once at startup.
• HRW incurs O(N) lookup per key; with very large clusters (> 100 nodes) consider Ketama or a hybrid approach.