Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 37 ยท Consistency and Failure

Consistency Models and CAS

Understand eventual consistency in a cache, how gets/cas gives optimistic locking with a version token, and how leases and versioned keys prevent lost updates.

"Is the cache consistent?" is a poorly formed question. Consistent with what, and when? A cache gives you eventual consistency at best: if writes stop, the cache eventually agrees with the database, either because items expire or because they were deleted. In between, readers may see old data. What you can control is how long the gap is and whether two writers can corrupt each other's work.

This lesson names the consistency levels you can realistically get with Memcached and then focuses on the one atomic tool Memcached gives you for concurrent updates: CAS (check and set). The server is simulated in Python, with a model of gets and cas that follows the real command semantics.

Consistency models in plain words

  • Eventual consistency: every copy converges if you wait long enough. This is what cache-aside with TTLs provides.
  • Read-your-writes: after you change something, you see the change. A cache can fake this by deleting the key during the write and by reading the database for the writer's next request (or sending a short "just wrote" cookie to bypass the cache).
  • Monotonic reads: you never see data go backwards in time. With several cache servers or replicas, two reads can hit different copies and show newer then older data. Avoiding it means sticking a user to one replica or versioning values.
  • Strong consistency: every read sees the latest write. A cache in front of a database cannot guarantee this without giving up most of its speed, so keep strongly consistent data (balances, stock at checkout) out of the cache or read it from the database with a lock.

The lost update problem

Memcached offers incr and decr for counters, but for arbitrary values the pattern "read, change, write" is not atomic. Two clients can both read version 1, add their changes, and write; the second overwrites the first.

Python Two writers lose an update

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.

CAS: optimistic locking

Memcached attaches a CAS unique number to every stored item, and the number changes whenever the item changes. The workflow:

  1. gets key returns the value and its CAS token.
  2. You change the value locally.
  3. cas key token new_value stores the new value only if the token still matches. If someone else changed the item in between, the server answers EXISTS and nothing is stored.
  4. On EXISTS you reread and retry.

This is optimistic concurrency control: assume no conflict, detect it cheaply, and retry on conflict.

Python Fixing the lost update with gets/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 first attempt fails with EXISTS because the token went stale, the retry rereads the cart that already contains "cheese" and succeeds. Nothing is lost. Keep a retry limit, and add a tiny random back-off for heavily contended keys; if a key gets conflicts constantly, it probably should not be a single shared value at all (split it, or use atomic incr).

Not every client exposes gets/cas, and some proxies do not forward them. Check your client library's documentation. Also, a CAS token is per server and per item version; it tells you nothing across servers or after an eviction (an evicted key answers NOT_FOUND).

Leases: stopping stale fills

Race 1 in Stale Data and Race Conditions happened because a slow reader stored data after a delete. A lease closes that gap. Facebook's design describes it like this: on a miss the server hands the client a lease token; the client may only set using that token, and a delete from a writer invalidates all outstanding tokens for the key. Plain Memcached does not have leases built in, but you can approximate them with versioned keys or add-based tokens.

Versioned keys

Include a version number in the key, stored under a small separate key:

Python
version = cache.get("ver:product:42") or 1
key = f"product:42:v{version}"

To invalidate, increment the version (incr, atomic). Old keys become unreachable and simply age out. A slow reader that fills product:42:v1 after the bump writes into a key nobody reads anymore. This also invalidates a whole family (all keys with that prefix) with one operation, which is handy for lists and search results whose members you cannot enumerate.

The cost: two reads per fetch (version, then data), unless you cache the version for a second in the app.

Choosing the right tool

Need Tool
Counters incr / decr (atomic on the server)
Concurrent edits to one value gets / cas with retries
Slow readers must not overwrite newer data leases or versioned keys
Invalidate many keys at once version in the key
Strict correctness read from the source of truth

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a cache in front of a database typically provide?

    The cache and database can disagree for a while; TTLs and deletes bound how long.
  2. 2. What does the server answer to cas if the item changed since you called gets?

    EXISTS means the CAS token no longer matches, so nothing was stored and you should reread and retry.
  3. 3. Which problem does CAS solve?

    The write succeeds only if nobody changed the item since your read.
  4. 4. How does a versioned key invalidate many cached entries at once?

    The old keys age out by TTL or eviction, and one atomic incr does the invalidation.

Summary

  • A cache gives eventual consistency; keep strongly consistent data out of it.
  • Read-modify-write on a shared value loses updates unless you guard it.
  • gets returns a CAS token and cas stores only if the token is unchanged; retry on EXISTS.
  • Leases, or versioned keys, stop slow readers from storing stale data after an invalidation.
  • Use incr/decr for counters and versions for bulk invalidation.

Next: Hit Ratio and Metrics