The Stale-Set Race

Scenario

Example app: the same store, now invalidating correctly after commit. Prices change often during a sale, and the product page receives thousands of reads per second.

What you see in production

A handful of products show the old price for the full TTL even though the update committed and the cache delete ran. It happens only under heavy read traffic, and the cache never "corrects itself" before the TTL.

The naive code

The textbook cache-aside read path:

def get_price(pid):
    cached = r.get(f"price:{pid}")
    if cached is not None:
        return int(cached)
    price = db.fetch_price(pid)          # (1) read the OLD value from the database…
    r.set(f"price:{pid}", price, ex=600) # (4) …and write it after the invalidation already happened
    return price

def set_price(pid, price):
    db.update_price(pid, price)          # (2) commit the new value
    r.delete(f"price:{pid}")             # (3) invalidate

Integer cached = cache.get(key);
if (cached == null) {
    Integer price = repo.price(id);      // old value
    cache.put(key, price);               // lands after the writer's evict
}

Reproduce it

The interleaving that leaves a stale value in the cache:

db, cache = {"price": 100}, {}

def reader():
    value = db["price"]                       # 1. cache miss → SELECT (sees 100)
    yield "reader: miss, read 100 from the database"
    cache["price"] = value                    # 4. SET price 100  (stale!)
    yield f"reader: SET cache = {value}"

def writer():
    db["price"] = 80                          # 2. UPDATE … COMMIT
    yield "writer: committed price 80"
    cache.pop("price", None)                  # 3. DEL price
    yield "writer: DEL cache"

r, w = reader(), writer()
for step in (r, w, w, r):
    print(next(step))
print(f"database = {db['price']}, cache = {cache['price']}  <- stale until the TTL expires")

reader: miss, read 100 from the database
writer: committed price 80
writer: DEL cache
reader: SET cache = 100
database = 80, cache = 100  <- stale until the TTL expires

Root cause

A reader's database read and its cache write are two separate steps. If a writer commits and deletes in between, the reader then puts its older value back. Facebook's memcache paper calls this a stale set: "a web server sets a value in memcache that does not reflect the latest value that should be cached", which happens "when concurrent updates to memcache get reordered" (Scaling Memcache at Facebook).

The fix

Make the reader's SET conditional on nothing having changed since it read:

1. Leases (memcache): a miss returns a lease token; a delete invalidates outstanding tokens; a SET with an invalid token is rejected. The paper introduces leases for exactly this problem.
2. Versioned values: store a version (e.g. updated_at or a row version) with the value and only overwrite with a newer version — atomically, with a Lua script or a Redis Function.
3. Short TTLs for volatile data, so any stale set heals quickly.
4. Delayed second delete (delete again a few hundred ms after the write) — a cheap mitigation, not a guarantee.

-- KEYS[1] = cache key, ARGV[1] = version, ARGV[2] = value, ARGV[3] = ttl seconds
local current = redis.call('HGET', KEYS[1], 'v')
if current and tonumber(current) >= tonumber(ARGV[1]) then
  return 0                                   -- cache already has this or a newer version
end
redis.call('HSET', KEYS[1], 'v', ARGV[1], 'data', ARGV[2])
redis.call('EXPIRE', KEYS[1], ARGV[3])
return 1

def get_price(pid):
    key, lease = f"price:{pid}", f"lease:price:{pid}"
    cached = r.get(key)
    if cached is not None:
        return int(cached)
    token = uuid.uuid4().hex
    r.set(lease, token, nx=True, px=5000)          # one lease per key
    price = db.fetch_price(pid)
    # set only if our lease is still valid (the writer deletes the lease on update)
    set_if_lease.eval(keys=[key, lease], args=[token, price, 600])
    return price

def set_price(pid, price):
    db.update_price(pid, price)
    r.delete(f"price:{pid}", f"lease:price:{pid}")  # invalidates value AND outstanding lease

// Product rows carry a version column; the cache keeps {version, payload}
redis.execute(SET_IF_NEWER_SCRIPT, List.of("product:" + id),
              String.valueOf(row.getVersion()), toJson(row), "600");

The same simulation with a versioned, conditional set:

db = {"price": 100, "version": 1}
cache = {}

def set_if_newer(value, version):
    if cache and cache["version"] >= version:
        return False
    cache.update(price=value, version=version)
    return True

read = (db["price"], db["version"])            # reader: miss, reads v1 = 100
db.update(price=80, version=2)                 # writer: commit v2 = 80
cache.clear()                                  # writer: DEL
set_if_newer(80, 2)                            # another reader fills v2 right after
accepted = set_if_newer(*read)                 # the slow reader finally tries to set v1
print("stale set accepted?", accepted, "| cache:", cache)

stale set accepted? False | cache: {'price': 80, 'version': 2}

Trade-offs

• Leases and versioned sets need atomic server-side logic (Lua/Functions) — more moving parts than a plain SET.
• Versions require a monotonic version per row (a version column or updated_at with enough precision).
• Short TTLs are the simplest mitigation and often good enough for non-critical data.
• None of this makes a cache strongly consistent; it narrows the window. Critical decisions (checkout) still read the database.

Detect it in production

• Staleness probes comparing cached values and versions with the database; alert on entries older than the latest version for more than N seconds.
• Count rejected conditional sets — a steady rate shows the race is real and being prevented.

Key points

• Cache-aside has a stale-set race: a slow reader can re-cache an old value after a delete.
• Prevent it with leases or version-checked sets; bound it with short TTLs.
• Keep critical reads on the database.