Cache Revalidation Correctness: Generation Fence, Singleflight, and Stale Write Rejection

Web Tiered Caching Strategy explains how Cache-Control, CDN, and application caches divide the work, and Common Redis Patterns covers mutex reconstruction and stampede. The really tricky race happens after "only one origin fetcher is allowed": rebuilder A reads a stale database snapshot, the invalidation event advances, rebuilder B writes the new value, and A wakes up last and overwrites it with the stale value again. Singleflight only coalesces calls in the same process at the same instant, and a distributed lock expiring does not mean the old owner loses the ability to write.

Cache identity is more than the business key

Publish cache.materialization.v1, separating the logical slot from the immutable value. The slot consists of the tenant/auth scope, enumerable dependency namespace, projection schema, query parameter digest, and policy version; the namespace control record holds a monotonically increasing requiredGeneration, and the slot holds the most recently committed generation/value digest, fresh/stale deadlines, and status. Dynamic collection queries bind to the collection/projection namespace rather than requiring the source transaction to enumerate arbitrary query digests. The value envelope also binds the source snapshot, dependency generation vector, producer version, and creation time.

DependencyNamespace(scope, resourceOrCollection, projection)
  requiredGeneration, authEpoch
CacheSlot(namespace, queryDigest, policy)
  committedGenerationVector, committedDigest

CacheValue(slotDigest, generation, sourceRevision,
           producerRevision, payloadDigest, freshUntil, staleUntil)

Any content-changing update raises the requiredGeneration of the corresponding resource, collection, or projection namespace within the source transaction and writes an outbox; deletes use a higher-generation tombstone. A complex query that cannot declare a finite dependency namespace is not cacheable. A physical DEL key is just a cleanup optimization and cannot bear correctness, because messages can be lost and stale values can come back from replicas. Database CDC can deliver changes, but the consumer must still apply them conditionally by generation.

On read, validate the slot identity and each dependency generation of the value. Authorization transactions must also synchronously raise the authoritative auth epoch; before each return it must be compared with the live epoch—if the auth store is unavailable, fail closed, and the async outbox is only responsible for rebuild and cleanup. Permission revocation, tenant deactivation, and deletion never allow stale; only ordinary public content may, per the versioned policy, return a stale value before staleUntil. RFC 5861 does not decide for the application which fields can be stale.

Singleflight coalesces; the Fence rejects latecomers

In-process, singleflight is first applied by full slot digest to reduce duplicate work on the same instance. Cross-instance rebuilds atomically claim (slot, requiredGeneration) through a control store, obtaining a rebuildAttemptId, an incrementing fence, and a short lease; only one attempt is the leader, while other requests return permitted stale, wait for a bounded time, or take a rate-limited bypass. The lease is used to judge when a takeover can happen; the fence decides who can commit.

The leader reads the dependency generation vector from an explicit snapshot, then publishes the payload conditionally after generation: every namespace generation, the current fence, the projection/policy version, and the auth epoch must all still match what they were at claim time. Write the immutable value first, then CAS the committed pointer; a failed late result can only be discarded. Lease renewal likewise compares the attempt and the fence; the old leader cannot renew after a takeover or delete the new leader's lock. Optimistic vs. Pessimistic Locking provides storage primitives; here the version comparison is extended to the cache publication acceptance point.

If the value was written but the pointer response was lost, the recovery reads the pointer and digest to confirm instead of creating a new generation. If the source read spans multiple tables, it must use the same database snapshot or a versioned projection; "seeing half old, half new when the query starts" is not a qualified value even if the generation is correct. An origin-fetch failure is not cached as a normal empty value; only a schema-distinguished NOT_FOUND can generate a short-lived negative cache, while permission errors, timeouts, and 5xx remain failures.

Limit the stale window and resource amplification

Each slot policy declares maxBuildTime, freshTtl, maxStale, a wait budget, the maximum candidate bytes, and a fallback. A hot miss cannot let unlimited requests block waiting for the leader; once waiters hit the cap, return existing stale or an explicit 503. Rebuild retries, database client retries, and request-layer retries share the same total budget, preventing a single stampede from amplifying into a multi-layer storm. What Chaos Engineering should validate is not just the hit rate, but also source QPS and the stale acceptance boundary.

The fault suite pauses A after reading the stale snapshot, advances the namespace generation, and has B publish, then resumes A; it also covers queries depending on multiple records, out-of-order CDC, an auth transaction already committed but with outbox delay, an unavailable auth store, lease takeover, an old key coming back to life, and ten thousand simultaneous misses. Assert that the committed generation vector never regresses, the count of accepted stale values after permission revocation is 0, a normal generation has only one source query, and all updates with an old fence fail. After lease expiry, computation may briefly overlap; the fence only promises one commit and cannot disguise duplicated computation as eliminated.

The release gate requires stale coverage of 0 in race tests, that a hot 10,000-concurrent miss without takeover faults triggers only 1 source query per slot/generation, that during takeover overlapping computations do not exceed 2 with only 1 commit, that the P99 from invalidation to a readable new generation is under 5 seconds, that out-of-window stale acceptance for ordinary content is 0, that permission-class stale acceptance is 0, and that on rebuild failure the cache layer's memory and wait queues stay within bounds. First compute the generation in shadow mode, then dual-write the envelope without reading it, then enable it for public low-risk slots. On rollback, disable rebuild and bypass to the source or only read verified old-protocol values; raise the global cache epoch so new readers reject the problem generation, and do not re-enable the old fenceless writer.

Further reading

• Web Tiered Caching Strategy
• Common Redis Patterns
• Database CDC
• Chaos Engineering