Meta’s Secret to Near‑Zero Cache Inconsistency

Why Cache Consistency Matters

Caching reduces latency, improves read‑heavy workload scalability, and cuts costs, but inconsistent caches can cause data loss‑like failures from a user perspective. The article explains that cache invalidation errors are a core source of such inconsistencies.

Defining Cache Invalidation and Consistency

Cache invalidation is the process of actively expiring stale entries when the underlying data source changes. It requires an external program (client or subsystem) to notify the cache; simple TTL‑based expiration is out of scope.

An example shows a race where a write to the database (x=43) arrives before the cache fills x=42, leading to a stale cache entry.

Challenges of Maintaining Consistency

Beyond protocol complexity, monitoring consistency and diagnosing the root cause of inconsistency are difficult. Designing a consistent cache differs from designing a protocol like Paxos; the former must handle real‑world operational constraints.

Cache Invalidation Model

Static caches have a simple model: data never changes after being written, and there is no active invalidation. Dynamic caches such as TAO and Memcache experience reads (fills) and writes (invalidations) on the same path, creating many race conditions.

Meta’s TAO processes billions of queries daily; even with a 99% hit rate, it performs over 10 trillion fills per day, making exhaustive logging impractical.

Observability with Polaris

To measure consistency, Meta built Polaris , a service that observes cache behavior without assuming knowledge of internal implementations. Polaris watches for violations of the invariant “cache should eventually match the database.” When an invalidation event arrives, Polaris queries all cache replicas; any replica returning a stale value is flagged as inconsistent.

Polaris reports inconsistencies on multiple time scales (e.g., 1 min, 5 min, 10 min) and delays expensive database checks until an inconsistency persists across a time window, reducing load on the primary store.

Polaris also tags queries with a flag indicating whether the target cache has already processed the invalidation, allowing it to distinguish transient replication lag from permanent inconsistency.

Consistency Tracking

Meta introduced a lightweight “consistency tracking” library that records cache mutations only during windows where inconsistencies are likely. The library buffers recent modifications, supports code‑path tracing, and integrates with the invalidation pipeline.

Using this library, engineers can answer three key questions for any cache server:

Did it receive an invalidation?

Did it process the invalidation correctly?

Did the cache become inconsistent afterward?

Real‑World Bug Example

A production bug involved a versioned key where the cache stored metadata=0 @version4 while the database held metadata=1 @version4. The bug arose from a rare transient error during invalidation, followed by error‑handling code that incorrectly dropped the entry, leaving stale metadata indefinitely.

The sequence of events captured by consistency tracking:

Cache attempted to add version and metadata.

Old metadata was filled first.

A transaction atomically updated both metadata and version tables.

Cache filled the new version data, interleaving with the transaction.

A subsequent invalidation failed to propagate.

The cache’s error handler deleted the entry without re‑validating.

Polaris detected the anomaly quickly, enabling engineers to locate and fix the bug in under 30 minutes.

Future Work

Meta aims to push cache consistency toward 100 % physical consistency, improve read‑time consistency metrics, and develop high‑level consistency APIs (e.g., C++ std::memory_order) for distributed systems.

Key Takeaways

The article provides a systematic, scalable approach to improving cache consistency: precise invalidation semantics, observability via Polaris, selective mutation tracking, and concrete metrics that can be applied to any large‑scale cache system.