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