Using Memcached CAS to Avoid Race Conditions in Counter Updates

The Problem: Lost Updates When Multiple Clients Increment a Counter

Imagine two web servers both trying to increment a shared counter stored in Memcached. Each server reads the current value, adds one, and writes the result back. If the reads happen almost simultaneously, both servers may base their increment on the same old value, and the final stored number reflects only one increment instead of two. This classic lost‑update problem can corrupt metrics, rate‑limiting counters, or any numeric state that relies on read‑modify‑write.

How CAS Works in Memcached

Memcached’s compare‑and‑swap (CAS) operation adds a 64‑bit token to every stored item. When a client issues gets for a key, the server returns the value together with its current CAS token. The client can then modify the value locally and send a cas command that includes the new value and the token it received. Memcached updates the item only if the token still matches the one stored on the server; otherwise it replies with NOT_FOUND, signalling that another client changed the key in the meantime. The application must retry the gets‑modify‑cas loop until it succeeds or gives up after a configurable number of attempts.

Worked Example: Using telnet to Demonstrate CAS

Start a local Memcached instance on the default port:

memcached -p 11211 -vv

In another terminal, connect with telnet (or netcat) and run the following commands. Replace mykey with any key name you like.

1. Initialize the key with a numeric value:

set mykey 0 0 5
0
STORED

2. Fetch the value and its CAS token:

gets mykey
VALUE mykey 0 5 12345
0
END

The line VALUE mykey 0 5 12345 shows the value (0) and the CAS token (12345). Your token will be different.

3. Increment the value locally (to 1) and attempt a CAS update:

cas mykey 0 0 5 12345
1
STORED

Because no other client changed the key, Memcached replies STORED and the new value is now 1.

4. Simulate a competing client: open a second telnet session, repeat gets mykey (it will return the same token 12345 because the first CAS hasn’t run yet), then in the first session run the CAS command again. The second session’s CAS will succeed first, changing the token. When the first session’s CAS runs, Memcached replies:

cas mykey 0 0 5 12345
1
NOT_FOUND

The NOT_FOUND tells the application that its token is stale; it must retry from gets.

Trade‑offs and Limitations

• Extra round‑trip: Each successful update requires a gets followed by a cas, doubling the latency compared with a plain set under low contention.
• Application‑level retry logic: Developers must implement a loop that handles NOT_FOUND and limits retries to avoid infinite loops.
• Memory fragmentation: While a CAS operation is pending, the old value remains allocated until the new value is stored or the item expires. With large values and high contention, this can lead to temporary fragmentation.
• Protocol support: Both text and binary protocols expose CAS, but the binary protocol encodes the token more efficiently, reducing per‑packet overhead.

When to Use CAS and What to Monitor

Use CAS when the cost of a lost update outweighs the added latency—typical cases include counters, rate limiters, or any shared state where correctness is critical. In deployments, keep an eye on Memcached statistics to verify that CAS is being used and to spot excessive retries:

stats

Look for the fields cmd_get, cmd_cas, get_hits, and cas_badval (if your version exposes it). A rising cmd_cas with a low cas_badval indicates healthy usage; a high cas_badval or many NOT_FOUND responses from clients suggests contention that may warrant sharding the key or using a different synchronization primitive.

Finally, most language‑specific Memcached clients already wrap CAS in a retry‑able helper (e.g., the cas method in libmemcached or the cas operation in Spymemcached). Leveraging those wrappers reduces boilerplate and ensures consistent error handling.