Skip to content

CONCEPT Cited by 1 source

Read-invalidation rendezvous

Definition

Read-invalidation rendezvous is the concurrency problem of coordinating in-flight reads against in-flight invalidations in an invalidation-based cache so that no invalidation is lost and no reader returns stale data that outlives an invalidation.

The name comes from Figma's LiveGraph 100x post (sources/2026-04-21-figma-keeping-it-100x-with-real-time-data-at-scale): "juggling simultaneous reads and invalidations, or what we like to call the 'read-invalidation rendezvous.'"

The core race

An invalidation-based cache processes two concurrent operation types against the same key:

  • Reads — check cache; on miss, fetch from source and set cache.
  • Invalidations — delete cache entry (and propagate upstream).

When a read and an invalidation overlap on the same key, three question shapes appear:

  1. Read completes, then invalidation arrives — safe; the next read re-fetches.
  2. Invalidation completes, then read starts — safe; the read misses and re-fetches post-invalidation state.
  3. Invalidation arrives mid-read — ambiguous. Did the cache result we're about to set reflect pre-invalidation or post-invalidation state? Can't tell from the cache value; the read was kicked off before the invalidation and might have seen either side.

Case 3 is the rendezvous problem. If handled naïvely (write-through the read result unconditionally), the just-fetched stale value overwrites the correct-after-invalidation state, and the invalidation is effectively skipped upstream — a correctness bug for anyone on the other side of the cache.

Figma LiveGraph's three rules

LiveGraph's cache has a synchronization layer above the in-memory cache enforcing:

  1. Operations of the same type can coalesce.
  2. Two concurrent reads on the same key share one cache read + one DB round-trip.

  3. Two concurrent invalidations dedup to one. This is a capacity-control measure as much as a correctness one — prevents fan-out of duplicate work at hot keys.

  4. During an inflight read, an incoming invalidation marks the read as invalidated. The invalidation waits for the ongoing cache-set to finish. New readers kicked off because of the invalidation must not coalesce onto the invalidated reader — else the invalidation is silently lost upstream (the new readers would return the same stale result the invalidator was trying to remove).

  5. During an inflight invalidation, incoming reads are marked invalidated and must not set the cache. A read that raced to fetch from DB could return stale state and re-stamp the cache on top of the just-cleared entry.

Why the rules are the way they are

Rules 2 and 3 exist because the cache is the only place where an invalidation manifests as a user-visible correctness property — "nothing stale lives past this invalidation." Invalidations upstream (notifying edges, clients, etc.) depend on the cache's guarantee; if the cache silently restamps stale data after the invalidation fired, the upstream chain is broken and the whole invalidation was wasted.

Rule 1 is almost the opposite concern — a capacity / efficiency constraint. Without same-type coalescing, a frequently-updated query could cause the cache to issue many parallel DB fetches from many coincident clients, each of which then triggers the same delete/set cycle. Coalescing makes this a single round-trip.

All three rules together yield eventual consistency (concepts/eventual-consistency) at the cache tier: in the absence of further writes, every subscriber converges on the post-mutation result, and no invalidation is ever logically-overwritten by a racing stale read.

Validation methods (from the post)

Because the rules are "tricky to write code that satisfies," Figma validates at three layers:

  • Chaos test — many threads, small set of keys, maximize concurrency; run reads and invalidations against the same keys in adversarial interleavings. Gives high confidence pre-ship.
  • Online cache verification — in production, randomly sample cache keys and concurrently query the primary DB for the same key. If results differ, log whether an invalidation was observed or silently skipped. Catches skipped-invalidation cases that chaos tests miss.
  • Convergence checker vs the old engine during migration — a side-by-side validation harness confirms the new engine's results match the old one's. Required fine tuning because the old engine was often seconds slower, and convergence comparisons have to account for it.

Axes that make this problem harder / easier

Factor Easier Harder
Hit rate Low (few reads to rendezvous) High (contended hot keys)
Invalidation rate Low (Figma's case) High (many races per second)
Coalescing allowed? Yes (reduces race surface) No (can't dedup work)
Upstream relies on invalidation? No (cache is self-contained) Yes (LiveGraph's case — edges / clients must never miss it)
Consistency model needed Eventual / session Strong / per-key linear

Adjacent problems / precedents

  • Cache stampede avoidance / singleflight — same-type read-coalescing without the invalidation-correctness dimension.
  • MESI cache-coherence race handling — hardware equivalent; the state machine (M / E / S / I) is how CPU caches solve this without per-access handshake cost.
  • Distributed-lock-based invalidation — the heavier alternative, where every read takes a read-lock and invalidations take a write- lock. Correct but slow; rules 1-3 above are the optimistic, lock- avoiding version of the same guarantees.
  • Kafka Streams' interactive-queries + compaction race — same shape: a local store is serving reads while the change stream is applying updates. Kafka Streams solves it with RocksDB snapshots and single-threaded processors rather than multi-threaded rendezvous.
  • Database MVCC snapshot isolation — the DB equivalent. Commit order / visibility order / reader's snapshot time interact with each other; see concepts/visibility-order-vs-commit-order.

Seen in

Last updated · 200 distilled / 1,178 read