Cache Invalidation at Meta’s Scale
Caches are foundational to reducing latency, scaling read-heavy workloads, and cutting costs. They exist in browsers, phones, CDNs, and DNS — essentially any system where data is replicated geographically or temporarily. The longstanding challenge, as Phil Karlton famously put it, is that cache invalidation is one of the two hard problems in computer science. When a cache is updated incorrectly, it can lead to inconsistencies that persist indefinitely, often surfacing as subtle and costly bugs.
Meta operates some of the world’s largest cache fleets, including TAO and Memcache. Over time, the company has improved TAO’s cache consistency from 99.9999% (six nines) to 99.99999999% (ten nines) for one key metric. The principles here are applicable broadly, whether you’re caching Postgres data in Redis or maintaining disaggregated materializations.
The Problem with Simple Invalidations
Cache invalidation requires an external actor — a client or a pub/sub system — to notify the cache of mutations in the source of truth. A cache that relies solely on TTLs to maintain freshness isn’t performing true invalidations and falls outside this discussion. For caches that do handle invalidations, the core challenge is ensuring that stale data from read paths never overwrites fresher data from write paths.
Consider a simple race: a cache fills x from the database with the value x=42. Before that reply is processed, a mutation sets x=43. The invalidation event for x=43 arrives first, but then the delayed x=42 response overwrites it in the cache. The cache now permanently disagrees with the database. Solutions can introduce version fields to enable conflict resolution, but those may be lost if the cache entry gets evicted before the older reply arrives.
This problem is compounded by the sheer volume of operation. A cache is usually introduced to scale reads, so most state changes happen on the fill path. TAO, for example, serves over a quadrillion queries daily. Even a 99% hit rate translates to more than 10 trillion cache fills a day. Logging every state change would turn a read-optimized service into a write-heavy logging burden. This makes debugging caches fundamentally different from debugging databases, which have transaction logs for every mutation.
A Mental Model for the Stateful Cache
To understand invalidation issues, treat a cache as a stateful service where data can be mutated on both the read (fill) and write (invalidation) paths. This dual mutation source is what enables a host of race conditions:
- Static caches — e.g., simplified CDNs — store immutable data. No invalidations are needed.
- Databases — mutate only on writes/replications, and they keep logs for nearly every state change. You can always audit and recover from anomalies.
- Dynamic caches — like TAO and Memcache — mutate on both reads and writes. Combined with non-durable storage that can evict important version metadata, this makes them vulnerable to race conditions far beyond what you see in databases.
An Observable Invariant as the Solution
The first step in solving cache invalidation is reliable measurement. Metrics must have zero false positives — any noise causes operators to tune out the alert. The measurement also has to be precise enough to distinguish improvements measured to a scale of ten nines or better.
Meta built a service called Polaris to address this. Polaris’s guiding principle is that an anomaly exists only if a client can observe it. Consequently, it tracks client-observable invariants, not internal implementation details. The most common invariant it verifies is: “Cache should eventually be consistent with the database.”
Polaris operates as an external client — it simulates a cache server to receive invalidation events. For each event, e.g., “x=4 @version 4,” Polaris queries all cache replicas to see if any still hold stale data. If one replies with “x=3 @version 3,” Polaris flags it, then requeues the sample for a later check. It reports inconsistencies according to configurable timescales (e.g., one minute, five minutes, ten minutes).
This multi-timescale approach isn’t only for internal backoff efficiency; it’s also essential for preventing false positives. Suppose Polaris receives an invalidation for “x=4 @version 4” but queries a replica that reports x as missing. It’s not immediately clear if:
- The database write at version 4 is the latest and the cache is lagging, or
- There is a subsequent version 5 that deletes
x, making the cache’s empty state correct.
Disambiguating requires a cache-bypass query to the database — expensive and risky, since the whole point of a cache is to shield the database from excessive load. Polaris delays those heavy queries until an inconsistency crosses a reporting timescale. Real inconsistencies and racing writes on the same key are rare, so most consistency checks get resolved with simple retries before requiring a cache-bypass.
Polaris also adds a special flag to its queries so the reply indicates whether the target cache server has processed the invalidation event. This allows Polaris to distinguish transient inconsistencies (caused by replication or invalidation lag) from permanent ones, where a stale value remains in the cache indefinitely after the latest invalidation has been handled.
[BLOCK_1]
Quantifying Consistency Gains
Polaris reports metrics formatted as “N nines of cache writes are consistent in M minutes.” The TAO improvement to 99.99999999% refers to consistency over a five-minute timescale — meaning fewer than one in ten billion writes in TAO remain inconsistent after five minutes. Polaris runs as a separate, independently scalable service; measuring to even higher nines is a matter of increasing Polaris throughput or aggregating over a longer window.
These practices offer a path from theoretical models to practical, reliable cache consistency at any scale.
Watching the Window
Cache diagrams usually show a single box, but production reality is far messier: caches fill from multiple upstreams at different times, and promotions, shard moves, failure recoveries, and network partitions can all introduce subtle bugs.
Logging and tracing every cache mutation is impractical. But what if we only traced the mutations where inconsistencies actually get introduced? The key insight is to ask where most inconsistencies originate. The answer comes from looking at the problem from a single cache server's perspective:
- Did it receive the invalidate?
- Did it process the invalidate correctly?
- Did the item become inconsistent afterwards?
After a client write, there's a window where invalidation and cache fill race to update the cache. Once that settles, the cache reaches a quiescent state. Cache fills can still happen at high volume, but with no writes in flight, the cache is effectively static and consistency issues are unlikely to arise.
This insight drove a stateful tracing library that logs cache mutations only inside that small race window — where all the interesting and complicated interactions happen. It covers cache evictions, and the absence of a log entry can itself reveal that an invalidate event never arrived. The library is embedded in major cache services and throughout the invalidation pipeline, maintains an index of recently modified data to decide whether subsequent changes should be logged, and supports code tracing so every logged query has an exact code path.
This approach — consistency tracing — has been highly effective at finding and fixing flaws that are systemic and hard to diagnose at scale.
Case Study: A Rare Indefinite Inconsistency
In one system, data is versioned for ordering and conflict resolution. Engineers observed "metadata=0 @version 4" in cache while the database held "metadata=1 @version 4", and the cache stayed inconsistent indefinitely. That state should have been impossible.
Consistency tracing delivered the complete timeline of events leading to the bad state.
The system transactionally updates two database tables — a metadata table and a version table — via a rare operation. The trace revealed this sequence:
- The cache attempted to fill the metadata along with its version.
- In the first round, the cache filled the old metadata.
- A write transaction then atomically updated both the metadata and version tables.
- In the second round, the cache filled the new version data, interleaving with the database transaction. This is rare because the racing window is tiny — but so far everything worked as expected.
- Cache invalidation later tried to update the entry to both new metadata and new version. This almost always works, but this time it failed.
- The invalidation hit a rare transient error on the cache host, triggering error handling code.
- The error handler dropped the cache item based on version comparison:
drop_cache(key, version);The handler drops the item only if its version is less than specified. But the inconsistent item already carried the latest version, so the drop did nothing — leaving stale metadata in cache indefinitely.
The real bug was more intricate, involving database replication and cross-region communication, and only manifests when all these steps occur in exactly the right order. It hides in error handling code behind interleaved operations and transient failures. Years ago, finding the root cause would have taken weeks from an engineer deeply familiar with the code — if they found it at all. With consistency tracing, Polaris flagged the anomaly immediately, and on-call engineers located the bug in under 30 minutes.
What's Next
Consistency tracing gives a generic, systemic, and scalable approach to cache coherence. The roadmap ahead includes pushing consistency for disaggregated secondary indices, measuring and improving consistency at read time, and building a high-level consistency API for distributed systems — analogous to C++'s std::memory_order, but for distributed architectures.
