Skip to content

PATTERN Cited by 1 source

Nonce-indirection bulk eviction

Problem

An invalidation-based cache indexed by query shape typically evicts exactly one cache entry per invalidation — perfect for "easy" (equality-predicate) query shapes where a row mutation maps to a single affected query. But for range/inequality predicates (created_at > $T, score BETWEEN $a AND $b), one row mutation affects potentially infinitely many cached queries — every query whose bound falls on the wrong side of the change.

Naïve invalidation of all affected parameterizations is infeasible: either (a) the invalidator enumerates every live parameterization (stateful, defeats patterns/stateless-invalidator), or (b) it broadcasts invalidations for an infinite set (absurd).

Figma's solution (LiveGraph 100x)

(Source: sources/2026-04-21-figma-keeping-it-100x-with-real-time-data-at-scale)

Normalize every query to (easy-expr) AND (hard-expr) and cache with two-layer keys tied by a nonce:

  • Top-level key: {easy-expr} → stores a nonce (random UUID).
  • Actual data key: {easy-expr}-{nonce}-{hard-expr} → stores the DB query result.

Cache is sharded by hash(easy-expr), co-locating all hard queries sharing the same easy expression on the same cache instance. Then:

  1. On easy-expression invalidation, the cache deletes the top-level {easy-expr} key — destroys the nonce.
  2. Every hard-query key {easy-expr}-{nonce}-{hard-expr} that embeds the deleted nonce becomes orphaned — next read can't look them up (it would be seeking a stale {easy-expr}-{old-nonce}-* key that won't match a new nonce generation). In one O(1) operation, all hard queries sharing that easy expression are invalidated.
  3. TTL reaps the orphan data keys eventually.
  4. Next read for any hard query: fetches a new nonce (cache miss on the top-level key → write new nonce → fetch DB result under the new composite key).

Upstream propagation: invalidation is forwarded to the edge (via the cache's cuckoo filter); edges only re-query hard queries that are actually in active sessions, so the fan-out is bounded to the active-hard-query count, not the theoretically-infinite universe.

Key properties

  • Over-invalidation is accepted. Every hard query sharing the easy-expr is invalidated, not just ones whose hard-expr mathematically overlapped the mutation. This is fine because (a) invalidations are rare, (b) hard-query counts per easy-expr are small, (c) the alternative is tracking live parameterizations.
  • Invalidator stays stateless. It only emits easy-expression invalidations; hard-expression logic lives entirely in the cache.
  • Indirection cost: hard-query lookups have an extra hop — top- level nonce lookup → data-key lookup. Acceptable overhead.
  • Cache sharding strategy is dictated by this — hash(easy-expr) (not hash(query)) so the nonce co-locates with all dependent queries.

Trade-offs

Axis Direct invalidation Nonce-bulk-eviction
Invalidator state O(active queries) O(1) — none
Invalidation message count O(affected queries) per mutation O(1) per mutation
Over-invalidation None Small (all hard queries w/ same easy-expr)
Lookup latency Direct One extra key lookup
Fit Easy shapes only Easy + hard shapes
Memory cost Cache entries only Cache entries + nonce entries (small)

Generalized shape

This is an instance of a broader nonce-by-reference / generational reference idiom:

To invalidate many related cache entries atomically, version them all under a shared generation counter / nonce; to invalidate them all, increment the counter / rotate the nonce.

Variants in the wild:

  • Memcached "cache tag" / "key-set" invalidation. Store a shared-tag version number; compose the real key with it; incrementing the version invalidates every composed key in one op.
  • Browser HTTP cache busting via ?v=123 query params. The shared build ID acts as the nonce; bumping the build rotates every asset's effective URL.
  • Git tree-hash invalidation of composite build caches (Bazel, BuildKit). The tree hash is the nonce; any subtree change rotates all downstream composite-key hits.
  • JWT key rotation (kid header). The kid acts as the nonce; decommissioning a kid invalidates every token ever signed with it.
  • DB-level epoch-based MVCC. Bumping the epoch invalidates all snapshots taken under the previous epoch.

Pre-conditions

  • Cache keys for the "many related entries" can be composed to include the shared nonce.
  • There's a natural partition ("sharing key") under which entries co-locate (in Figma's case: the easy-expression).
  • Over-invalidation of the sharing group is acceptable — bulk eviction isn't precise.

Anti-patterns

  • Per-affected-query invalidation — works for easy shapes, fails catastrophically for hard shapes (infinite fan-out). The naïve alternative this pattern replaces.
  • Subscription-table walk — stateful, high-coordination cost; defeats the scaling properties of stateless invalidators.
  • Tiny TTL as invalidation proxy — sidesteps the invalidation logic but kills cache effectiveness.

Numbers (from Figma's post)

  • ~11 of ~700 query shapes in LiveGraph's schema are hard. The pattern is needed for the 1.6% minority that couldn't be dropped.
  • No perf numbers disclosed (extra lookup latency, nonce cache size, TTL reaping rate).

When it's a mis-fit

  • Hard queries dominate — over-invalidation is now the common case; cache effectiveness drops.
  • No natural "sharing key" — no way to partition hard queries into small co-located groups; the nonce ends up shared globally, defeating the purpose.
  • Consumers can't tolerate over-invalidation — strict per-query invalidation required (e.g. invalidation is itself expensive in upstream effects).

Seen in

Last updated · 200 distilled / 1,178 read