How Memcached Client-Side Sharding Works: Ketama Consistent Hashing in Practice

The problem: scaling Memcached without a central coordinator

Memcached itself has no clustering logic. When you add more servers, it's up to every client to decide which server holds a given key. The de facto standard is Ketama consistent hashing, a client-side algorithm that maps keys onto a hash ring populated with virtual nodes representing each physical server. Because every client runs the same deterministic function, they all agree on key placement without talking to each other.

How the ring works

Each physical server gets multiple virtual nodes (typically 100–200) placed on a 32-bit or 64-bit ring. The hash of a key (usually MD5 for historical compatibility) lands at a point on the ring; the next virtual node clockwise owns that key. When a server joins or leaves, only the keys between its virtual nodes and their successors move — roughly 1/N of all keys for N servers. This is a dramatic improvement over modulo hashing, where adding one server remaps nearly every key.

A concrete worked example

Imagine three servers — A, B, C — each assigned 4 virtual nodes on a 32-bit ring (12 nodes total). The ring positions (hex) might look like:

A-v1: 0x1000   B-v1: 0x3000   C-v1: 0x5000
A-v2: 0x2000   B-v2: 0x4000   C-v2: 0x6000
A-v3: 0x7000   B-v3: 0x9000   C-v3: 0xB000
A-v4: 0x8000   B-v4: 0xA000   C-v4: 0xC000

A key user:123 hashes to 0x7A3F. Binary search finds the next virtual node clockwise: A-v3 at 0x7000. So A stores that key.

Now add server D with its 4 virtual nodes. They insert between existing nodes. Only keys whose hashes fall between a new D node and the node that previously followed it will remap to D. The rest stay put. In a 3-server cluster, adding a fourth moves about 25% of keys — far less than the near-100% churn of modulo hashing.

Tuning virtual nodes: balance vs. overhead

More virtual nodes give better load distribution, especially when servers have different capacities. You can encode weight by giving a beefier server more virtual nodes (e.g., 320 for a 2× machine). The trade-off is client-side memory and lookup time: the ring is a sorted array of size servers × virtual_nodes, and each lookup is a binary search (O(log V)). Most libraries default to 160 virtual nodes per server, which keeps variance under 5% in typical tests.

Virtual nodes per server	Expected key variance	Ring size (10 servers)	Lookup cost
40	~10%	400 entries	~9 steps
160 (default)	<5%	1,600 entries	~11 steps
320	<3%	3,200 entries	~12 steps

Practical engineering decisions

• Hash function: Ketama originally uses MD5. It's cryptographically broken but fine as a deterministic distribution function. Newer clients may offer CRC32 or xxHash for speed; just ensure every client in your fleet uses the same one.
• Configuration versioning: During rolling deployments, clients may update their server list at different times. If the ring changes mid-rollout, you get temporary hot spots. Tag the ring configuration with a version or feature flag and switch all clients atomically.
• Data affinity: Consistent hashing doesn't guarantee related keys land together. If you need user:123:profile and user:123:posts on the same server (for multi-get atomicity), hash a shared prefix like user:123 instead of the full key.
• Small clusters: With fewer than 5 servers, consistent hashing's benefits shrink. A simple modulo with a prime divisor can be simpler and equally effective.

Verification you can run today

1. Check your client library: Look at the source for spymemcached (Java), python-memcached (Python), or gomemcache (Go). Confirm the virtual node count and hash function are configurable and match across all services.
2. Run a distribution test: Generate 100,000 synthetic keys, map them with your configured ring, and plot per-server key counts. Expect <5% variance with 160 virtual nodes.
3. Simulate a failure: Remove one server from the ring and measure the percentage of keys that remap. It should be close to 1/N.
4. Monitor per-server metrics: Watch get/set/hit/miss rates per server. Uneven command rates often reveal virtual node misconfiguration or hash collisions before application symptoms appear.

Closing: make the ring a first-class config artifact

Treat the Ketama ring like any other critical configuration: version it, review it in code review, and automate the distribution test in CI. When you add capacity, you'll know exactly how many keys move and can plan for the brief cache-warm period. And if you ever see a sudden spike in misses on one server, check the ring first — it's usually a client-side mismatch, not a Memcached bug.