Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 37 ยท Memcached Basics

CAS and Concurrent Updates

Prevent lost updates in Memcached with gets and cas: how the CAS token works, what EXISTS means, how to write a retry loop, and where CAS cannot help.

Two web workers read the same cached value, each modifies it, and each writes it back. The second write silently erases the first. This is the lost update problem, and it happens whenever you use a read-modify-write cycle on shared data without protection.

Memcached solves it with CAS, short for check and set (or compare-and-swap). You read a value together with a version token, and you write it back only if the token has not changed. If somebody else got there first, the write is refused and you try again with the fresh value. This lesson shows the commands, a retry loop, and the limits of the technique.

The idea

Every item in Memcached has a 64-bit CAS unique number. It changes every time the item is modified (by set, append, incr and the other commands that change the data). The commands:

TEXT
gets <key>                         -> VALUE <key> <flags> <bytes> <cas>
cas <key> <flags> <exptime> <bytes> <cas>

cas stores the data only if the item's current CAS number equals the one you supply. Answers:

Reply Meaning
STORED Nobody changed it; your write succeeded
EXISTS Someone else modified it since your gets; nothing was written
NOT_FOUND The item vanished (deleted, expired or evicted)

The lost update, reproduced

First watch the problem happen without CAS. Two "workers" each add a tag to a shared list stored as text.

Python Lost update without CAS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fix: gets and cas

With CAS the second writer is told it lost, and can try again on top of the first writer's result.

Python Detect the conflict with cas

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second cas answers EXISTS, so nothing is overwritten. After a re-read, B's retry succeeds and both tags survive.

A reusable retry loop

In real code you wrap the pattern in a helper that takes a function describing how to change the value. Always bound the number of retries, because under heavy contention a loop that never gives up can spin forever.

Python update() with bounded retries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The helper needed three attempts because two other writers got in first, and the final value contains their changes as well as ours.

What CAS does and does not protect

CAS protects one key on one server against concurrent modification of that key. It does not give you:

  • Transactions across keys. You cannot atomically update two keys. If your invariant spans several items, restructure the data or keep it in the database.
  • Protection against eviction. If the item disappears, cas returns NOT_FOUND and you must decide what to do.
  • Fairness. Under heavy contention some writers retry many times. For a hot counter, use incr, which never conflicts, instead of CAS.
  • Correctness for the real data. The cache is not the system of record; CAS only keeps the cached copy consistent with itself. The database still needs its own concurrency control.

Prefer the simpler tool when it exists:

Need Best tool
Count something incr / decr
Add text to a value append / prepend
Change a structured value (JSON) based on its old contents gets + cas loop
Make sure only one writer creates it add

Detail: the token is opaque

Treat the CAS number as an opaque token. Do not compare tokens with < or assume that a larger token means "newer" across restarts or servers. Only "same" or "different" is meaningful. Also, in a multi-server pool the token is only valid on the server that issued it, so clients always route gets and cas for the same key to the same server, which consistent hashing guarantees in the normal case.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the server reply to cas when the token is out of date?

    EXISTS means the item was modified since you read it, so the write was refused.
  2. 2. Which command returns the CAS token along with the value?

    gets is get plus the CAS unique number.
  3. 3. For a hot page-view counter, what should you use instead of a CAS loop?

    incr is applied inside the server in one step, so no retry is needed.
  4. 4. What is a good practice for a CAS retry loop?

    Under contention an unbounded loop can spin. A bounded loop lets you fall back, for example by deleting the key.

Summary

  • Read-modify-write on cached data loses updates when workers interleave.
  • gets returns a CAS token; cas writes only if the token is unchanged, answering STORED, EXISTS or NOT_FOUND.
  • On EXISTS, re-read and try again with a bounded retry loop.
  • CAS covers one key on one server; it is not a transaction and it does not replace the database's own concurrency control.
  • Use incr, append or add when they fit; they need no retries.

Next: Keys, Values, Flags and Serialization