缓存有助于减少延迟，提高读取密集型工作负载的可扩展性，并节省成本。实际上缓存无处不在，它在您的手机和浏览器中运行。例如，CDN和DNS本质上是地理复制缓存。正是由于许多缓存在幕后工作，您现在正在阅读本文。PhilKarlton有句名言：“计算机科学中只有两个难题：缓存失效和命名。”如果您曾经处理过无效的缓存，那么您很可能遇到过缓存不一致这一恼人的问题。在Meta，我们运营着世界上一些最大的缓存，包括TAO和Memcache。多年来，我们将TAO的缓存一致性提高了一个档次，从99.9999%（六个九）到99.99999999%（十个九）。我们相信我们现在有一个有效的解决方案来弥合缓存失效方面的理论与实践之间的差距。这篇博文中的原则和方法广泛适用于大多数（如果不是全部的话）缓存服务。无论您是在Redis中缓存Postgres数据，还是具体化分散数据，都是如此。我们希望帮助减少工程师必须处理的缓存失效数量，并帮助加强缓存一致性。1.定义缓存失效和缓存一致性根据定义，缓存不是数据的真正来源（例如数据库）。缓存失效描述了当真实源中的数据发生变化时主动使陈旧缓存条目失效的过程。如果缓存失效处理不当，不一致的值可能会无限期地保留在缓存中。缓存失效涉及必须由缓存本身以外的程序执行的操作。某些程序（例如，客户端或公共/子系统）需要告诉缓存数据已更改的位置。仅依靠TTL来维持有效性的缓存不在本文的讨论范围之内。在本文的其余部分，我们将假设存在缓存失效。为什么这个看似简单的过程被认为是计算机科学中的难题？下面是一个如何引入缓存不一致的简单示例。缓存首先尝试从数据库中填充x。但是有人在“x=42”到达缓存主机之前将x设置为43。缓存失效事件“x=43”首先命中缓存主机，将x设置为43。“x=42”到达缓存，将x设置为42。现在数据库中的“x=43”和数据库中的“x=42”缓存。有很多方法可以解决这个问题，其中之一就是维护一个版本字段。这样我们就可以解决冲突，因为旧数据不应覆盖新数据。但是，如果缓存条目“x=43@version=2”在“x=42”到达之前变得无效怎么办？在这种情况下，缓存的数据仍然是错误的。缓存失效的挑战不仅来自失效协议的复杂性，还来自监控缓存一致性以及如何确定缓存不一致的原因。设计一致性缓存与操作一致性缓存非常不同，就像设计Paxos协议与构建实际在生产中运行的Paxos非常不同一样。二、为什么我们要关心缓存一致性我们必须要解决复杂的缓存失效问题吗？在某些情况下，缓存不一致几乎与数据库数据丢失一样严重。从用户的角度来看，这甚至与数据丢失没有区别。让我们看一下缓存不一致如何导致裂脑的另一个例子。Meta公司使用消息将他们的数据从用户的主存储映射到TAO。它经常移动以使用户触手可及。每次你向某人发送消息时，都会查询TAO以找出消息的存储位置。很多年前，当TAO的一致性很差的时候，有些TAO的replicas在re-moving之后会出现数据不一致的情况，如下例所示。想象一下，在将Alice的主要消息存储从区域2切换到区域1之后，Bob和Mary都向Alice发送消息。当Bob向Alice发送消息时，系统查询TAO副本中Bob居住地附近的区域，并将消息发送到区域1。当Mary向Alice发送消息时，系统向TAO副本中查询区域close到Mary居住的地方，命中不一致的TAO副本，并将消息发送到区域2。Bob和Mary将他们的消息发送到不同的区域，并且两个区域都没有Alice消息的完整副本。3.缓存失效模型理解缓存失效的困难尤其具有挑战性。让我们从一个简单的模型开始。缓存的核心是一种有状态服务，它将数据存储在可寻址的存储介质中。分布式系统本质上是一个状态机。如果每个状态转换都正确执行，我们就有了一个按预期工作的分布式系统。否则系统会出问题。所以，关键问题是：对于有状态服务，什么在改变数据？静态缓存有一个非常简单的缓存模型（例如，简化的CDN接近这个模型）。数据是不可变的。没有主动缓存失效。对于数据库，数据仅在写入（或复制）时发生变化。我们通常对数据库的每个状态更改都有日志。每当发生异常时，日志可以帮助我们了解发生了什么，缩小问题范围，找出问题所在。构建一个容错的分布式数据库（这已经很困难）有其独特的挑战。这些只是简化的模型。对于像TAO和Memcache这样的动态缓存，数据在读取（缓存填充）和写入（缓存失效）路径上都会发生变化。这种组合使多个竞争条件成为可能，而缓存失效是一个难题。缓存中的数据不是持久化的，这意味着有时对解决冲突很重要的版本信息会被清除。结合所有这些特性，动态缓存创造了超出我们想象的竞争条件。此外，几乎不可能记录和跟踪每个缓存状态更改。通常引入缓存来扩展读取繁重的工作负载。这意味着大部分缓存状态变化来自缓存填充路径。以TAO为例。它每天为超过4亿次查询提供服务。即使有99%的缓存命中率，我们每天也会进行超过10万亿次缓存填充。记录和跟踪所有缓存状态更改可以将读取繁重的缓存工作负载转变为极其写入繁重的日志系统工作负载。调试分布式系统提出了巨大的挑战。在没有日志或缓存状态更改痕迹的情况下调试分布式系统几乎是不可能的。尽管存在这些挑战，多年来我们已经将TAO的缓存一致性从99.9999%提高到99.99999999%。在本文的其余部分，我们将解释我们是如何做到的，并强调一些未来的工作。4.一致性的可观察性为了解决缓存失效和缓存一致性问题，第一步涉及测量。我们想要测量缓存一致性并对缓存中不一致的条目发出警报。测量不能包含任何误报。人脑可以很容易地消除噪音。如果有任何误报，人们很快就会学会忽略它，测量就变得毫无用处。我们还需要精确测量，因为我们讨论的是测量超过10个9的一致性。如果修复已落地，我们希望确保我们可以定量衡量它带来的改进。为了解决测量问题，我们构建了一个名为Polaris的服务。有状态服务中的任何异常只有在客户端可以通过某种方式观察到它时才是异常。否则，根本无所谓。基于这一原则，Polaris专注于衡量违反客户可观察到的不变量的情况。在高层次上，Polaris作为客户端与有状态服务交互，并且不假定了解服务内部知识。这使它用途广泛。Meta有许多使用Polaris的服务。“缓存最终应该与数据库保持一致”是Polaris监控的一个典型的客户端可观察不变量，尤其是在异步缓存失效的情况下。在这种情况下，Polaris伪装成缓存服务器并接收缓存失效事件。例如，如果Polaris收到一个失效事件，比如“x=4@version4”，它会作为客户端查询所有缓存的副本，以验证是否发生了任何违反该不变量的情况。如果缓存副本返回“x=3@version3”，Polaris会将其标记为不一致，并重新等待稍后针对同一目标缓存主机检查样本。Polaris报告某些时间尺度上的不一致，例如一分钟、五分钟或十分钟。如果此样本在一分钟后仍显得不一致，则Polaris将其报告为相应时间刻度的不一致。这种多时间尺度的设计不仅允许Polaris内部拥有多个队列来有效地退避和重试，而且对于防止误报也很关键。让我们看一个更有趣的例子。假设Polaris收到“x=4@version4”的无效消息。但是当它查询缓存副本时，答复是x不存在。目前尚不清楚Polaris是否应将此标记为不一致。有可能x在版本3不存在，而版本4的write是对key的最新写入，这确实是缓存不一致。也有可能是第5版操作删除了x，也许Polaris只是在失效事件中看到了数据的更新视图。为了区分这两种情况，我们需要绕过缓存并检查数据库的内容。绕过缓存的查询计算量很大。它们还将数据库置于风险之中，因为保护数据库和扩展读取密集型工作负载是缓存最常见的用例之一。因此，我们不能绕过缓存发送太多查询。Polaris通过延迟计算密集型操作的执行来解决这个问题，直到不一致的样本跨越报告时间范围（例如一分钟或五分钟）。真正的缓存不一致和对同一键的竞争写入很少见。因此，在跨越下一个时间尺度边界之前不进行一致性检查有助于消除执行大多数数据库查询。我们还在Polaris发送到缓存服务器的查询中放置了一个特殊标志。因此，Polaris将知道目标缓存服务器是否已经看到并处理了缓存失效事件。这条信息让Polaris能够区分瞬态缓存不一致（通常由复制/验证滞后引起）和“永久”缓存不一致（旧版本也无限期地存在于缓存中）。Polaris还提供观察结果，例如“M分钟内N个9的缓存写入是一致的”。文章开头我们提到，通过一个改进，我们将TAO的缓存一致性从99.9999%提高到99.99999999%。Polaris提供5分钟时间刻度的指标。也就是说，99.99999999%的缓存写入在5分钟内是一致的。在TAO中，不到100亿分之一的缓存写入在5分钟内会出现不一致。我们将Polaris部署为一项单独的服务，以便它可以独立于生产服务及其工作负载进行扩展。如果我们想测量更多数据，我们可以增加Polaris的吞吐量或在更长的时间窗口上执行聚合。5.ConsistencyTracking在大多数图中，我们使用一个简单的方框来表示缓存。实际上，在省略了许多依赖项和数据流之后，它可能看起来像这样。缓存可以在同一区域内或跨区域的不同上游的不同时间点填充。升级、分片移动、故障回复、网络分区和硬件故障都可能触发导致缓存不一致的问题。然而，如前所述，记录和跟踪对缓存数据的每一次更改是不切实际的。但是，如果我们只在不一致的地方和时间记录和跟踪缓存突变（或者缓存失效可能被错误处理）怎么办？在这个庞大而复杂的分布式系统中，任何组件的缺陷都可能导致缓存不一致，是否有可能找到一个引入大部分（如果不是全部）缓存不一致的地方？我们的任务变成了找到一个简单的解决方案来帮助我们管理这种复杂性。我们想从单个缓存服务器的角度来评估整个缓存一致性问题。最后，不一致问题一定发生在缓存服务器上。从它的角度来看，它只关心几个方面。它收到无效消息了吗？它是否正确处理此失败消息？后来缓存不一致了吗？这就是我们在文章开头解释的例子，现在用时空图来说明。如果我们关注底部的缓存时间线，我们可以看到在客户端完成写入后，有一个窗口，其中无效和缓存填充都在竞争更新缓存。一段时间后，缓存将处于静止状态。在这种状态下，缓存的填充还是会发生很多，但是从一致性的角度来说，既然没有写入，就已经沦为静态缓存了，所以意义不大。我们构建了一个有状态的库，用于记录和跟踪这个紫色小窗口中的缓存突变，所有相关的复杂交互都会引发导致缓存不一致的问题。它涵盖了缓存过期，甚至没有日志可以告诉我们失效事件是否永远不会到来。它嵌入到几个主要的缓存服务中，并在整个失效管道中运行。它缓存最近修改的数据索引，用于决定后续的缓存状态变化是否应该被记录。它还支持代码跟踪，因此我们将知道每个跟踪查询的确切代码路径。这种方法帮助我们找到并修复了许多错误。它提供了一种系统化且更具可扩展性的方法来诊断缓存不一致。它已被证明是非常有效的。6、今年发现并修复的一个线上错误在一个系统中，我们对每条数据进行了版本排序和冲突解决。在这种情况下，我们在缓存中观察到“metadata=0@version4”，而数据库包含“metadata=1@version4”。缓存无限期地保持不一致。这种状态应该是不可能的。你会如何处理这个问题？如果我们能够获得导致最终不一致状态的每个步骤的完整时间表，那该有多好？一致性跟踪恰好提供了我们需要的时间表。在系统中，一个非常罕见的操作以事务方式更新了底层数据库的两个表——元数据表和版本表。从一致性跟踪中，我们知道发生了以下情况：1)缓存尝试添加版本数据和元数据。2）在第一轮中，缓存首先被旧的元数据填充。3)接下来，写入事务自动更新元数据和版本表。4）第二轮，缓存写入新版本数据。在这里，缓存填充操作与数据库事务交织在一起。因为比赛窗口很小，所以这种情况很少发生。您可能会想，“这是一个错误”。但实际上到目前为止一切都按预期工作，因为缓存失效应该使缓存恢复一致。5)后来，当尝试用新元数据和新版本更新缓存项时，我得到了缓存失效。这几乎总是有效，但这次不行。6)缓存失效在缓存主机上遇到罕见的瞬态错误，触发了错误处理代码。7)错误处理程序删除条目。伪代码看起来像这样。drop_cache（键，版本）；如果条目的版本低于指定版本，则将条目放入缓存。但是，不一致的缓存条目包含最新版本。所以这段代码什么都不做，并无限期地在缓存中留下陈旧的元数据。这是错误。我们在这里简化了很多示例。实际的bug更复杂，涉及数据库复制和跨区域通信。只有在上述所有步骤都发生时才会触发该错误，特别是按此顺序。很少出现不一致。该错误隐藏在交互式操作和瞬态错误背后的错误处理代码中。许多年前，如果有人对代码和服务了如指掌并且幸运的话，要找到这个错误的根本原因可能需要数周时间。在这种情况下，Polaris检测到异常并立即拉响了警报。值班工程师仅用了不到30分钟的时间，就从一致性轨迹的信息中找到了错误。7.未来的缓存一致性工作我们已经分享了我们如何通过一种通用的、系统的和可扩展的方法来增强我们的缓存一致性。展望未来，我们希望使所有缓存的一致性在物理上尽可能接近100%。去中心化二级指数的一致性提出了一个有趣的挑战。我们还在测量并有目的地提高读取时的缓存一致性。最后，我们正在为分布式系统构建高级一致的API，想想用于分布式系统的C++std::memory_order。
