{"id":596,"date":"2022-06-08T17:30:16","date_gmt":"2022-06-08T17:30:16","guid":{"rendered":"https:\/\/fde.cat\/index.php\/2022\/06\/08\/cache-made-consistent-metas-cache-invalidation-solution\/"},"modified":"2022-06-08T17:30:16","modified_gmt":"2022-06-08T17:30:16","slug":"cache-made-consistent-metas-cache-invalidation-solution","status":"publish","type":"post","link":"https:\/\/fde.cat\/index.php\/2022\/06\/08\/cache-made-consistent-metas-cache-invalidation-solution\/","title":{"rendered":"Cache made consistent: Meta\u2019s cache invalidation solution"},"content":{"rendered":"

Caches help reduce latency, scale read-heavy workloads, and save cost. They are literally everywhere. Caches run on your phone and in your browser. For example, CDNs and DNS are essentially geo-replicated caches. It\u2019s thanks to many caches working behind the scenes that you can read this blog post right now.<\/span><\/p>\n

Phil Karlton famously said, \u201cThere are only two hard things in computer science: cache invalidation and naming things.\u201d If you have ever worked on a cache that uses invalidations, chances are you have run into the annoying problem of cache inconsistency.<\/span><\/p>\n

At Meta, we operate some of the largest cache deployments in the world, including<\/span> TAO<\/span><\/a> and<\/span> Memcache<\/span><\/a>. Over the years, we\u2019ve improved TAO\u2019s cache consistency by one measure, from 99.9999 percent (six nines) to 99.99999999 percent (10 nines).\u00a0<\/span><\/p>\n

When it comes to cache invalidation, we believe we now have an effective solution to bridge the gap between theory and practice. The principle and methodology in this blog post apply broadly to most, if not all, cache services at any scale. It does so whether you are caching Postgres data in Redis or maintaining a disaggregated materialization.<\/span><\/p>\n

We want to help reduce the number of cache invalidation issues that engineers have to deal with and help make all caches with invalidations more consistent.<\/span><\/p>\n

Defining cache invalidation and cache consistency\u00a0<\/span><\/h2>\n

By definition, a cache doesn\u2019t hold the source of truth of your data (e.g., a database). Cache invalidation describes the process of actively invalidating stale cache entries when data in the source of truth mutates. If a cache invalidation gets mishandled, it can indefinitely leave inconsistent values in the cache that are different from what\u2019s in the source of truth.<\/span><\/p>\n

Cache invalidation involves an action that has to be carried out by something other than the cache itself. Something (e.g., a client or a pub\/sub system) needs to tell the cache that a mutation happened. A cache that solely depends on time to live (TTL) to maintain its freshness contains no cache invalidations and, as such, lies out of scope for this discussion. For the rest of this post, we\u2019ll assume the presence of cache invalidation.<\/span><\/p>\n

Why is this seemingly straightforward process considered such a difficult problem in computer science? Here\u2019s a simple example of how a cache inconsistency could be introduced: <\/span><\/p>\n\n

The cache first tries to fill <\/span>x<\/span> from the database. But before the reply \u201cx=42\u201d reaches the cache host, someone mutates <\/span>x<\/span> to 43. The cache invalidation event for \u201cx=43\u201d arrives at the cache host first, setting <\/span>x<\/span> to 43. Finally, \u201cx=42\u201d in the cache fill reply gets to the cache, setting <\/span>x<\/span> to 42. Now we have \u201cx=43\u201d in the database and \u201cx=42\u201d in the cache indefinitely.\u00a0<\/span><\/p>\n

There are different ways to solve this problem, one of which involves maintaining a version field. This allows us to perform conflict resolution, as older data should never overwrite newer data. But what if the cache entry \u201cx=43 @version=2\u201d gets evicted from cache before \u201cx=42\u201d arrives? In that case, the cache host would lose knowledge of the newer data.<\/span><\/p>\n

The challenge of cache invalidation arises not only from the complexity of invalidation protocols, but also from monitoring cache consistency and determining why these cache inconsistencies occur. Designing a consistent cache is very different from operating a consistent cache \u2014 much like designing<\/span> Paxos<\/span><\/a>, where the protocol is different from building Paxos that actually works in production.<\/span><\/p>\n

Why do we care about cache consistency at all?<\/span><\/h2>\n

Do we have to solve this intricate cache invalidation problem? Yes. In some cases, cache inconsistencies are almost as bad as data loss on a database. From the user\u2019s perspective, it can even be indistinguishable from data loss.<\/span><\/p>\n

Let\u2019s examine another example of how cache inconsistencies can lead to split-brain. A messaging use case at Meta stores its mapping from user to primary storage in<\/span> TAO<\/span><\/a>. It performs shuffling frequently to keep the user\u2019s primary message storage close to where the user accesses Meta. Every time you send a message to someone, behind the scenes, the system queries TAO to find out where to store the message. Many years ago, when TAO was less consistent, some TAO replicas would have inconsistent data after reshuffling, as illustrated in the example below.<\/span><\/p>\n

Imagine that after shuffling Alice\u2019s primary message store from region 2 to region 1, two people, Bob and Mary, both sent messages to Alice. When Bob sent a message to Alice, the system queried the TAO replica in a region close to where Bob lives and sent the message to region 1. When Mary sent a message to Alice, it queried the TAO replica in a region close to where Mary lives, hit the inconsistent TAO replica, and sent the message to region 2. Mary and Bob sent their messages to different regions, and neither region\/store had a complete copy of Alice\u2019s messages. <\/span><\/p>\n\n

A mental model of cache invalidation<\/span><\/h2>\n\n

Understanding the unique challenges of cache invalidation is particularly challenging. Let\u2019s start with a simple mental model. A cache, at its very core, is a stateful service that stores data in an addressable storage medium. Distributed systems are essentially state machines. If every state transition is performed correctly, we will have a distributed system that works as expected. Otherwise, we\u2019ll have a problem. So, the key question is: What\u2019s changing the data for a stateful service?\u00a0<\/span><\/p>\n\n

A static cache has a very simple cache model (e.g., a simplified CDN fits this model). Data is immutable. No cache invalidations. For databases, data gets mutated only on writes (or replications). We often have logs for almost every state change for a database. Whenever an anomaly occurs, the logs can help us understand what happened, narrow down the problem, and identify the issue. Building a fault-tolerant distributed database (which is already difficult) comes with its own set of unique challenges. These are just simplified mental models. We do not intend to minimize anyone\u2019s struggles.\u00a0<\/span><\/p>\n\n

For a dynamic cache, like <\/span>TAO<\/span><\/a> and<\/span> Memcache<\/span><\/a>, data gets mutated on both read (cache fill) and write (cache invalidation) paths. This exact conjunction makes many race conditions possible and cache invalidation a difficult problem. Data in cache is not durable, which means that sometimes version information that is important for conflict resolution can get evicted. In combining all these characteristics, a dynamic cache produces race conditions beyond your wildest imagination.<\/span><\/p>\n

And it\u2019s almost impractical to log and trace every cache state change. A cache often gets introduced to scale a read-heavy workload. It implies that most of the cache state changes transpire from the cache fill path. Take TAO, for example. It serves more than one quadrillion queries a day. Even if the cache hit rate reaches 99 percent, we would be doing more than 10 trillion cache fills a day. Logging and tracing all the cache state changes would turn a read-heavy cache workload to an extremely write-heavy workload for the logging system. Debugging a distributed system already presents significant challenges. Debugging a distributed system \u2014 in this case, a distributed cache \u2014 without logs or traces for cache state changes could be impossible.<\/span><\/p>\n

Despite these challenges, we improved TAO\u2019s cache consistency, by one measure, from 99.9999 to 99.99999999 over the years. In the rest of the post, we will explain how we did it and highlight some future work.\u00a0<\/span><\/p>\n

Reliable consistency observability<\/span><\/h2>\n

To solve cache invalidation and cache consistency, the first step involves measurement. We want to measure cache consistency and sound an alarm when there are inconsistent entries in the cache. The measurement can\u2019t contain any false positives. Human brains can easily tune out noises. If any false positives existed, people would quickly learn to ignore it and the metric would lose trust and become useless. We also need the measurement to be precise, as we talk about measuring up to more than 10 nines of consistency. If a consistency fix is landed, we want to assure we can quantitatively measure its improvement. <\/span><\/p>\n\n

To solve the measurement problem, we built a service called Polaris. For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn\u2019t matter at all. Based on this principle, Polaris focuses on measuring the violations of client-observable invariants.<\/span><\/p>\n

At a high level, Polaris interacts with a stateful service as a client and assumes no knowledge of the service internals. This allows it to be generic. We have dozens of Polaris integrations at Meta. \u201cCache should eventually be consistent with the database\u201d is a typical client-observable invariant that Polaris monitors, especially in the presence of asynchronous cache invalidation. In this case, Polaris pretends to be a cache server and receives cache invalidation events. For example, if Polaris receives an invalidation event that says \u201cx=4 @version 4,\u201d it then queries all cache replicas as a client to verify whether any violations of the invariant occur. If one cache replica returns \u201cx=3 @version 3,\u201d Polaris flags it as inconsistent and requeues the sample to later check it against the same target cache host. Polaris reports inconsistencies at certain timescales, e.g., one minute, five minutes or 10 minutes. If this sample still shows as inconsistent after one minute, Polaris reports it as an inconsistency for the corresponding timescale.<\/span><\/p>\n

This multi-timescale design not only allows Polaris to have multiple queues internally to implement backoff and retries efficiently, but it\u2019s also essential for preventing it from producing false positives.<\/span><\/p>\n

Let\u2019s take a look at a more interesting example: Say Polaris receives an invalidation with \u201cx=4 @version 4.\u201d But when it queries a cache replica, it gets a reply saying <\/span>x<\/span> doesn\u2019t exist. It\u2019s not clear whether Polaris should flag this as an inconsistency. It\u2019s possible that <\/span>x<\/span> was invisible at version 3, the version 4 write is the latest write on the key, and it\u2019s indeed a cache inconsistency. It\u2019s also possible that there\u2019s a version 5 write that deletes the key <\/span>x<\/span>, and perhaps Polaris is just seeing a more recent view of the data than what\u2019s in the invalidation event.<\/span><\/p>\n

To disambiguate between these two cases, we would need to bypass cache and check what\u2019s in the database. Queries that bypass cache are very compute-intensive. They also expose the database to risks \u2014 not surprisingly because protecting the database and scaling a read-heavy workload is one of the most common use cases for caches. So, we can\u2019t send too many queries to the system that bypasses the cache. Polaris solves this problem by delaying performing the compute-intensive operation until an inconsistent sample crosses the reporting timescale (e.g., one minute or five minutes). Real cache inconsistencies and racing write operations on the same key are rare. As a result, retrying the consistency check (before it crosses the next timescale boundary) helps remove most of the demand to perform these cache bypass queries.<\/span><\/p>\n

We also added a special flag to the query that Polaris sends to the cache server. So, in the reply, Polaris would know whether the target cache server has seen and processed the cache invalidation event. This bit of information enables Polaris to distinguish between transient cache inconsistencies (usually caused by replication\/invalidation lag) and \u201cpermanent\u201d cache inconsistencies \u2014 when a stale value is in cache indefinitely after processing the latest invalidation event.\u00a0<\/span><\/p>\n

Polaris produces a metric that looks like \u201cN nines of cache writes are consistent in M minutes.\u201d At the beginning of the post, we mentioned that by one measure we improved TAO\u2019s cache consistency from 99.9999 percent to 99.99999999 percent. Polaris provided these numbers for the five minute timescale. In other words, 99.99999999 percent of cache writes are consistent within five minutes. Less than 1 out of 10 billion cache writes would be inconsistent in TAO after five minutes.<\/span><\/p>\n

We deploy Polaris as a separate service so that it will scale independently from the production service and its workload. If we want to measure up to more nines, we can just increase Polaris throughput or perform aggregation over a longer time window.\u00a0<\/span><\/p>\n

Consistency tracing<\/span><\/h2>\n

In most diagrams, we use one simple box to represent cache. In reality, it looks more like the following, even after omitting many dependencies and data flows: <\/span><\/p>\n\n

Caches can fill from different upstreams at different points in time, within or across regions. Promotions, shard moves, failure recoveries, network partitions, and hardware failures can all potentially trigger bugs that lead to cache inconsistencies.\u00a0<\/span><\/p>\n

However, as mentioned earlier, logging and tracing every cache data change is almost impractical. But what if we only log and trace cache mutations where and when cache inconsistencies can get introduced (or cache invalidations can possibly be mishandled)? Within this massive and complex distributed system, where a single flaw in any component can lead to cache inconsistencies, is it possible to find a place where most if not all cache inconsistencies get introduced?\u00a0<\/span><\/p>\n

Our task becomes finding a simple solution to help us manage this complexity. We want to assess the entire cache consistency problem from a single cache server\u2019s perspective. At the end of the day, an inconsistency has to materialize on a cache server. From its perspective, it cares about only a few aspects:<\/span>
\n<\/span><\/p>\n

Did it receive the invalidate?<\/span>
\nDid it process the invalidate correctly?<\/span>
\nDid the item become inconsistent afterwards? <\/span><\/p>\n

\u00a0<\/p>\n\n

This is the same example we explained at the beginning of the post, now illustrated on a space-time diagram. If we focus on the cache host timeline at the bottom, we see that after a client write, there\u2019s a window in which both the invalidation and the cache fill can race to update the cache. After a while, the cache will be in a quiescent state. Cache fills can still happen in high volume in this state, but from a consistency perspective, it holds less interest, given there are no writes and it\u2019s reduced to a static cache.\u00a0<\/span><\/p>\n

We built a stateful tracing library that logs and traces cache mutations in this small purple window, where all the interesting and complicated interactions trigger bugs that lead to cache inconsistencies. It covers cache evictions, and even the absence of the log can tell us if the invalidate event never arrives. It\u2019s embedded into a few major cache services and throughout the invalidation pipeline. It buffers an index of recently modified data, used to determine whether subsequent cache state changes should be logged. And it supports code tracing, so we\u2019ll know the exact code path for every traced query.\u00a0<\/span><\/p>\n

This methodology has helped us find and fix many flaws. It offers a systemic and much more scalable approach to diagnosing cache inconsistencies. It has proved to be very effective.\u00a0<\/span><\/p>\n

A real bug we found and fixed this year<\/span><\/h2>\n\n

In one system, we version each piece of data for ordering and conflict resolution. In this case, we observed \u201cmetadata=0 @version 4\u201d in the cache, while the database contained \u201cmetadata=1 @version 4.\u201d The cache stayed inconsistent indefinitely. This state should have been impossible. Pause for a second and consider: How would you approach this problem? How nice would it be if we got the complete timeline of every single step that led to the final inconsistent state?<\/span><\/p>\n

Consistency tracing provided exactly the timeline we needed. <\/span><\/p>\n\n

In the system, a very rare operation updates two tables of the underlying database transactionally \u2014 the metadata table and the version table. <\/span>\u00a0<\/span><\/p>\n

Based on consistency tracing, we know the following happened:<\/span><\/p>\n

The cache tried to fill the metadata with version.<\/span>
\n\u00a0<\/span>In the first round, the cache first filled the old metadata.<\/span>
\nNext, a write transaction updated both the metadata table and the version table atomically.<\/span>
\nIn the second round, the cache filled the new version data. Here, the cache fill operation interleaved with the database transaction. It happens very rarely because the racing window is tiny. You might be thinking, \u201cThis is the bug.\u201d. No. Actually, so far everything worked as expected because cache invalidation is supposed to bring the cache to a consistent state.<\/span>
\nLater, cache invalidation came during an attempt to update the cache entry to both the new metadata and the new version. This almost always works, but this time it didn\u2019t.\u00a0<\/span>
\nThe cache invalidation ran into a rare transient error on the cache host, which triggered the error handling code.<\/span>
\nThe error handler dropped the item in cache. The pseudocode looks like this:<\/span><\/p>\n

drop_cache(key, version);<\/p>\n

It says drop the item in cache, if its version is less than specified. However, the inconsistent cache item contained the latest version. So this code did nothing, leaving stale metadata in cache indefinitely. This is the bug. We simplified the example quite a bit here. The actual bug has even more intricacy, with database replication and cross region communication involved. The bug gets triggered only when all steps above occur and happen specifically in this sequence. The inconsistency gets triggered very rarely. The bug hides in the error handling code behind interleaving operations and transient errors.\u00a0<\/span><\/p>\n

Many years ago, finding the root cause of such a bug would take weeks from someone who knew the code and the service inside out, if they were lucky enough to find it at all. In this case, Polaris identified the anomaly and fired an alarm immediately. With information from consistency tracing, it took on-call engineers less than 30 minutes to locate the bug.\u00a0<\/span><\/p>\n

Future cache consistency work<\/span><\/h2>\n

We\u2019ve shared how we made our caches more consistent with a generic, systemic, and scalable approach. Looking ahead, we want to get the consistency of all our caches as close to 100 percent as physically possible. Consistency for disaggregated secondary indices poses an interesting challenge. We are also measuring and meaningfully improving cache consistency at read time. Finally, we are building a high-level consistency API for distributed systems \u2014 think of C++\u2019s std::memory_order, but for distributed systems.<\/span><\/p>\n

The post Cache made consistent: Meta\u2019s cache invalidation solution<\/a> appeared first on Engineering at Meta<\/a>.<\/p>\n

Engineering at Meta<\/p>","protected":false},"excerpt":{"rendered":"

Caches help reduce latency, scale read-heavy workloads, and save cost. They are literally everywhere. Caches run on your phone and in your browser. For example, CDNs and DNS are essentially geo-replicated caches. It\u2019s thanks to many caches working behind the scenes that you can read this blog post right now. Phil Karlton famously said, \u201cThere… Continue reading Cache made consistent: Meta\u2019s cache invalidation solution<\/span><\/a><\/p>\n","protected":false},"author":0,"featured_media":0,"comment_status":"","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":""},"categories":[7],"tags":[],"class_list":["post-596","post","type-post","status-publish","format-standard","hentry","category-technology","entry"],"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":496,"url":"https:\/\/fde.cat\/index.php\/2021\/10\/26\/kangaroo-a-new-flash-cache-optimized-for-tiny-objects\/","url_meta":{"origin":596,"position":0},"title":"Kangaroo: A new flash cache optimized for tiny objects","date":"October 26, 2021","format":false,"excerpt":"What the research is:\u00a0 Kangaroo is a new flash cache that enables more efficient caching of tiny objects (objects that are ~100 bytes or less) and overcomes the challenges presented by existing flash cache designs. Since Kangaroo is implemented within CacheLib, Facebook\u2019s open source caching engine, developers can use Kangaroo\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":299,"url":"https:\/\/fde.cat\/index.php\/2021\/08\/31\/caching-with-the-salesforce-commerce-sdk\/","url_meta":{"origin":596,"position":1},"title":"Caching with the Salesforce Commerce SDK","date":"August 31, 2021","format":false,"excerpt":"Co-written by Brian\u00a0RedmondEvery e-commerce application is going to need caching. For some of our customers, millions of shoppers may look at the same product information and, if you have to request that information from the service every time, your application will not scale. This is why we built the Commerce\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":458,"url":"https:\/\/fde.cat\/index.php\/2021\/09\/20\/cachelib-facebooks-open-source-caching-engine-for-web-scale-services\/","url_meta":{"origin":596,"position":2},"title":"CacheLib, Facebook\u2019s open source caching engine for web-scale services","date":"September 20, 2021","format":false,"excerpt":"Caching plays an important role in helping people access their information efficiently. For example, when an email app loads, it temporarily caches some messages, so the user can refresh the page without the app retrieving the same messages. However, large-scale caching has long been a complex engineering challenge. Companies must\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":606,"url":"https:\/\/fde.cat\/index.php\/2022\/07\/14\/owl-distributing-content-at-meta-scale\/","url_meta":{"origin":596,"position":3},"title":"Owl: Distributing content at Meta scale","date":"July 14, 2022","format":false,"excerpt":"Being able to distribute large, widely -consumed objects (so-called hot content) efficiently to hosts is becoming increasingly important within Meta\u2019s private cloud. These are commonly distributed content types such as executables, code artifacts, AI models, and search indexes that help enable our software systems. Owl is a new system for\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":479,"url":"https:\/\/fde.cat\/index.php\/2021\/09\/29\/switch-it-up\/","url_meta":{"origin":596,"position":4},"title":"Switch It Up!","date":"September 29, 2021","format":false,"excerpt":"It is vital that a microservice striving for high availability have at its disposal several choices on how to rollback changes when unforeseen production issues occur. A very interesting article comes to mind from O\u2019Reilly, Generic Mitigations, where the theme is to restore service functionality FIRST and FAST\u200a\u2014\u200aand THEN root\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":497,"url":"https:\/\/fde.cat\/index.php\/2021\/10\/28\/carbonj-a-high-performance-high-scale-drop-in-replacement-for-carbon-cache-and-carbon-relay\/","url_meta":{"origin":596,"position":5},"title":"CarbonJ: A high performance, high-scale, drop-in replacement for carbon-cache and carbon-relay","date":"October 28, 2021","format":false,"excerpt":"The Problem In 2015, Salesforce Commerce Cloud (which was then called Demandware) was running a typical open source Grafana\/Graphite\/Carbon stack to store and visualize time series metrics of the Java application clusters powering our e-commerce business. Our JVM clusters at the time produced around 500k time series metrics per\u00a0minute. Even\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts\/596","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/comments?post=596"}],"version-history":[{"count":0,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts\/596\/revisions"}],"wp:attachment":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/media?parent=596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/categories?post=596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/tags?post=596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}