Cache-aside and the stale fill race

Updating the database and then deleting its cache entry does not prevent every stale cache value. A reader may have already fetched the old value and still be waiting to put it into the cache. If that late fill arrives after the delete, it recreates the value that the writer intended to remove.

This lesson is for application engineers who know what a cache hit and miss mean and can follow five ordered events. You do not need a database server to reproduce the bug: a deterministic Python model lets us inspect every ordering in a small case. We will separate the stale-fill problem from failed invalidations, source replication lag and concurrent work sharing. Those issues need their own contracts.

A delete cannot remove a future fill

A cache-aside reader asks the cache first. On a miss, it loads the value from the authoritative source and may store the result for later readers. A writer changes the authoritative source and then invalidates the cached copy. The cache is an optional copy; losing an entry is allowed, while treating it as the authoritative record would change the design.

This read and write pattern appears in section 2 and Figure 1 of Nishtala and colleagues’ Scaling Memcache at Facebook, published at NSDI 2013. The paper describes deleting cached data after the database update. Its later lease discussion addresses stale sets caused by reordered cache updates. The following example is a small reconstruction of that class of problem, not a reproduction of the paper’s production measurements.

Use value 0 for the old version and value 1 for the new version. Begin with source 0 and an empty cache. The reader observes a miss, then reads source 0. The writer commits source 1 and deletes the cache entry. Finally, the reader stores its previously read 0. Both participants obey their own event order, yet the final source and cache disagree.

Event	Source	Cache
Reader misses	0	absent
Reader reads source	0	absent
Writer commits	1	absent
Writer invalidates	1	absent
Reader fills	1	0

The delete did execute, and it ran after the commit. There is no lost network message in this example. At the moment of deletion there was simply nothing to remove. A subsequent reader can hit the stale entry without visiting the source.

View full-size image ↗

An empty cache at invalidation time does not imply that no older result is still on its way back.

Give pending fills a generation

Attach a generation number to the key’s cache state. On a miss, the reader remembers the current generation as its ticket. Invalidation removes the cached value and advances the generation in one atomic cache operation. A fill compares its ticket with the current generation and installs the value only if they match, again as one atomic operation.

In our race, the reader holds ticket 0. Invalidation advances the key to generation 1. The late fill’s ticket no longer matches, so the cache rejects it and remains empty. A new reader can acquire ticket 1 and fetch the new source value. The number says which invalidation boundary the request preceded; it is not the database value and does not encode a timestamp.

Section 3.2.1 of the Memcache paper describes a related mechanism: a key-bound lease token accompanies a cache miss and is checked when the client sets the value. A delete can invalidate that token. Our model uses an increasing integer to expose the revocation rule. It does not implement the paper’s token issuance throttling, deployment architecture or complete lease protocol.

View full-size image ↗

The important boundary is the cache’s atomic decision. A client-side comparison made earlier is not an authorization to write later.

Run the race with and without that guard

The model below has one key, one reader and one writer. Each named event is indivisible. Source reads return the most recently committed value at that event. The writer’s commit and invalidation are separate events, so the model does not assume a transaction spanning the database and cache.

The schedule is a finite iterable containing the five named strings exactly once, preserving each participant’s order. The function records the source, cached value and generation after every event. None means absent; 0 is a real cached value. The guard is a Boolean policy, not a cache library option.

def run(schedule, *, guarded):
    actions = tuple(schedule)
    required = {'miss', 'read', 'fill', 'commit', 'invalidate'}
    if (len(actions) != 5 or set(actions) != required
            or type(guarded) is not bool):
        raise ValueError('use each event once and a Boolean policy')
    pos = {event: i for i, event in enumerate(actions)}
    if not (pos['miss'] < pos['read'] < pos['fill']
            and pos['commit'] < pos['invalidate']):
        raise ValueError('preserve each participant\'s event order')

    source, cached, generation = 0, None, 0
    ticket = snapshot = None
    accepted = False
    history = []
    for event in actions:
        if event == 'miss':
            assert cached is None
            ticket = generation
        elif event == 'read':
            snapshot = source
        elif event == 'commit':
            source = 1
        elif event == 'invalidate':
            cached = None
            generation += 1
        else:  # fill: comparison and installation are one atomic event
            accepted = not guarded or ticket == generation
            if accepted:
                cached = snapshot
        history.append((event, source, cached, generation))
    return source, cached, accepted, tuple(history)


race = ('miss', 'read', 'commit', 'invalidate', 'fill')
assert run(race, guarded=False)[:3] == (1, 0, True)
assert run(race, guarded=True)[:3] == (1, None, False)
print('unconditional:', run(race, guarded=False)[:3])
print('generation guard:', run(race, guarded=True)[:3])

The unguarded result ends with source 1 and cached 0. The guarded result ends with source 1 and an absent entry, and reports that the fill was rejected. Both outcomes are computed from the same events. No sleeps, thread scheduler behavior or assumed request durations determine the result.

An absent entry is a successful safety outcome for this property. The next read may cost a source request, but the obsolete fill is not retained for other callers. Rejection does not automatically replace the value already held by the original reader. If that reader is about to return 0 to its caller, the application still needs to decide whether to retry, return an error or permit the older observation.

Check all ten event orders

A reader has three ordered events and a writer has two. Choosing the reader’s three positions among five yields ten possible interleavings. The next block enumerates exactly those orders. Append it after the first block in the same Python file.

def interleave(left, right):
    if not left:
        yield right
    elif not right:
        yield left
    else:
        for tail in interleave(left[1:], right):
            yield (left[0],) + tail
        for tail in interleave(left, right[1:]):
            yield (right[0],) + tail


schedules = list(interleave(('miss', 'read', 'fill'),
                            ('commit', 'invalidate')))
assert len(schedules) == 10
bad = [s for s in schedules if run(s, guarded=False)[1] == 0]
assert bad == [race]
assert all(run(s, guarded=True)[1] in (None, 1) for s in schedules)
fresh_but_rejected = ('miss', 'commit', 'read', 'invalidate', 'fill')
assert run(fresh_but_rejected, guarded=True)[:3] == (1, None, False)
print('stale final entries, unguarded/guarded:', len(bad), 0)

# A previous successful comparison is not permission to write later.
ticket, generation, snapshot = 0, 0, 0
permission = ticket == generation
source, cached = 1, None  # the writer commits and invalidates
# Invalidation also revokes tickets from generation 0.
generation += 1
if permission:
    cached = snapshot
assert (source, cached, generation) == (1, 0, 1)
print('split check/store is unsafe:', cached)

Exactly one of these ten schedules leaves a stale final entry with unconditional fills. All ten guarded schedules end with either no cached entry or value 1. This is an exhaustive statement about the declared five-event model. It is not a ten-percent incident probability: real workloads need not produce these schedules equally often, and many relevant events are absent from the model.

The last assertions deliberately split the generation comparison from installation. The comparison succeeds at generation 0, the writer invalidates, and then the reader uses its old Boolean permission to install 0 anyway. This fails even though the counter advanced correctly. Putting a check in application code followed by an unconditional cache write does not reproduce an atomic conditional fill.

A cache server can supply such an operation as part of its protocol. A local process can protect the comparison and installation with the same synchronization that protects invalidation. Whichever mechanism is used, every participant that changes the relevant state must follow it; a lock in one client process does not coordinate other processes or a remote database automatically.

Prove the narrow property

Consider a reader that observed 0. Its source read occurred before the commit of 1. If its fill runs before invalidation, invalidation subsequently removes the entry. If its fill runs after invalidation, its ticket was acquired even earlier than its source read, so the generation has changed and the fill is rejected. Either way, this reader cannot leave 0 in the cache after all five events finish.

A reader that observed 1 can only install 1 or have its fill rejected. Together, the two cases establish the final-state property for this model. The proof depends on atomic cache operations, a source with the stated read semantics, a successful invalidation and a generation that is not reused while an old ticket remains possible.

That property is weaker than making every read return the latest committed value. There can be a window between commit and invalidation. With a preexisting cached value, a request in that window can still read the old cache entry. A source replica can also return an older snapshot after invalidation unless its read contract rules that out. The model intentionally starts with an empty cache and reads one authoritative source; it does not conceal those differences inside the word “consistent.”

Revocation has storage and availability costs

A generation guard can reject fresh data too. In fresh_but_rejected, the reader gets ticket 0, the writer commits 1, the reader reads 1, and invalidation advances the generation before the fill. The value is current, but the ticket no longer proves permission to install it. Conservatively refusing the fill avoids needing to inspect a source-version relationship that this cache does not understand.

Repeated writes can therefore cause repeated rejected fills. Retrying forever is not a useful completion guarantee. Bound the work and choose an explicit caller policy. Also, this generation rule does not elect one loader: several readers may hold tickets from the same generation and all perform source work. Preventing a burst of duplicate loads is a separate responsibility.

The generation metadata cannot be discarded as casually as the cached payload. Suppose an old ticket 0 is outstanding, invalidation advances the generation to 1, and cleanup resets it to 0 because the entry is absent. That old ticket matches again. Restarting the cache with reused ticket identities can create the same problem. A real design needs a suitable incarnation or non-reuse rule, or a demonstrated boundary after which old tickets cannot return. A fixed-width counter needs an explicit wraparound story; the Python integer model does not wrap.

A repeated invalidation remains conservative: it removes the value and revokes more pending tickets. The paper’s ordinary delete is idempotent with respect to entry absence; incrementing a generation is not identical state after repetition, even though another increment does not revive an old ticket. Delayed retries can thus reduce cache usefulness without creating this particular stale-fill failure.

For an exercise, add a second reader and enumerate its three events alongside the existing five. Keep each reader’s ticket and snapshot separate. Retain schedules in which the named miss events find absent entries, or model hits explicitly instead of treating them as misses. Then add a deliberately reused generation and find the stale fill it allows. The useful result is a concrete ordering that violates a named property, not an assurance that a cache is safe because each individual request looks correct in isolation.