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