缓存是万恶之源
缓存在降低延迟和负载方面非常有效，但它也引入了一些正确性相关的问题，本文介绍了如何避免常见缓存问题的方法。
插图来自 Jeremy Nguyen/ 艺术指导 Sarah Kislak
缓存的实践在降低延迟和负载方面是有效的，但它引入了一些糟糕的正确性相关问题。这几乎是一个自然规律，一旦你引入了反规范化，它会偏离真理的源头就是迟早的事了。缓存的瞬态性使得问题很难调试，并且使问题变得更加神秘。这就是说，如果你可以在没有缓存的情况下承受性能和负载，那么出于对世界上所有美好事物的热爱，就不要添加它了。不过，在某些情况下，你的客户无法忍受较长的延迟，并且你的记录系统也无法承受相应的负载，那你就要不得不与缓存“恶魔”（你认为memcached中的“ d”代表什么意思）达成协议了。
在 Box，我们与“恶魔”发生过冲突，为了驯服它，我们依赖了许多业界众所周知的策略以及一些技巧，我们很乐意为社区工具带贡献一些力量。由于缓存最常用于优化重读环境中的延迟和负载，因此在本文中，我们将避免直写缓存的变化，而将重点放在读取时填充缓存上。
在较高的层次上，如果需要的话，读操作在从记录系统中读取值之前，会先在缓存中查找该值。
缓存在未命中时进行填充。写操作负责使陈旧缓存值失效。
正如计算机科学的一句谚语所言，缓存失效是最困难的部分。 要弄清楚给定的记录系统突变会使哪些缓存键过时，通常不是一件容易的事情。尽管这可能非常繁琐，但是相对而言，它比较容易重现和测试。另一方面，与并发相关的缓存一致性问题要微妙得多。熟悉分布式系统的读者可能会注意到，在上述缓存系统中可能会出现的这样的几个问题：
在高流量的读取情况下，写操作（从而导致缓存值失效）会导致大量的读冲击记录系统，以将值重新加载到缓存中。
并发读写操作会导致陈旧值无限期地存储在缓存中。考虑如下的操作顺序，例如：
这些步骤的序列化会在缓存中产生一个持久的陈旧值：在写操作更改记录系统并使受影响的缓存值失效之前，读操作会先写入它所读取的值。
上述两个并发问题的规范解决方案是由 2013 年 Facebook 的一篇著名的论文《在 Facebook 弹性伸缩 Memcache》中提出的。引入“租约”（“lease”）的概念，并将其作为每个缓存的键锁，以防止突发流量和陈旧值集。它依赖于通用缓存系统的两个操作：
atomic_add（key，value）：当且仅当key尚未设置时，才为key设置所提供的值。否则，操作失败。在 Memcached 中，它被实现为add，而在 Redis 中则被实现为SETNX。
atomic_check_and_set（key，expected_value，new_value）：当且仅当key刚好与expected_value关联时，才为所提供的key设置new_value。在 Memcached 中，它被实现为cas。不幸的是（也令人惊讶的是），Redis 中没有具有这样语义的命令，但是可以通过一个简单的 Lua 脚本来弥补这一功能的不足。
有了这些概念，我们的读操作实现可以修改成如下形式：
读操作实现的修正，以防突发流量和陈旧值保护。
这种方法能使缓存有效地保护记录系统以免遭突发流量的冲击。在缓存未命中的情况下，只有一个幸运的请求能够成功添加租约并与真实源交互，而其他请求将被降级为轮询租约，直到幸运的请求将其计算出来的值填充完缓存为止。
这种机制还可以保护我们免受上述竞争状况的影响。当记录系统发生突变，并且读操作从真实源中获取数据并将其放入缓存的过程中产生了缓存无效，就会发生缓存中毒。该模型可以防止读操作毒害缓存，因为如果写操作更改了缓存下面的记录，则其原子检查和设置就会失败。
尽管它暂时感到困惑，但不幸的是，缓存“恶魔”确实有更多的锦囊妙计。考虑这样一个用例：数据始终被频繁地读取，但是部分数据也会被频繁地周期性写入：
读操作 1 徒劳地等待读操作 3 和读操作 2 填充感兴趣的缓存键时，会经历一段荒谬的延迟。
在冗长的写操作过程中，可能会出现一种病态的情况，读操作最终会轮流获得租约，并查询记录系统，结果却被一个写操作清除了。实际上，这会序列化来自真实源的读取，但不会消除重复数据，最终会导致过高的读延迟和超时，因为读需要等待轮流从真实源中获取所需的值。
我们在 Box 的分布式关系数据服务中遇到了这个问题，并想出了一些与之相关的解决方案。我们最终采用的方法是基于这样一种观点：任何正在等待租约的读操作都可以安全地使用持有租约的读操作检索到的值，即使租约最终被写操作清除，并且atomic_check_and_set失败。实际上，如果某个读操作遇到了另一个读操作的租约，则该读操作必须在写操作清除缓存值之前到达，因此在确认写操作之前，这两个读操作都可以返回由租约持有者检索到的值，而不会牺牲读写（read-after-write）一致性。为了利用这一观点，除了执行atomic_check_and_set尝试将根据真实源计算出来的值存储到缓存中之外，获得租约的读操作还需将该值存储在缓存的其他位置，从而可以被等待租约的读操作发现。
使用流程图来说明该算法会变得复杂且难以阅读，但下面是执行该算法的代码片段。该代码片段是用 Java 过程编写的，旨在使高级方法更加清晰明了，而没有考虑错误处理、编译时的安全性、可维护性等。
public class LookasideCache { private CacheCluster cacheCluster; private LeaseUtils leaseUtils; /** * 使用 lookaside 缓存读取某个值 * * @param key 要返回谁的值 * @param sourceOfTruthComputation 如果有必要的话， * 用于从真实源中获取值的函数。 * 计算被认为是昂贵的 * 并且会加大真实数据存储源的负载。 * * @return a byte[] 表示与查找 key 相关联的值。 */ public byte[] read(byte[] key, FunctionsourceOfTruthComputation) { return read(key, sourceOfTruthComputation, Collections.EMPTY_SET); } /** * 用于上述 read 方法的私用辅助方法，允许我们在堆栈上携带之前看到的租约集 * */ private byte[] read( byte[] key, FunctionsourceOfTruthComputation, SetpreviouslySeenLeases ) { // 首先查找所提供的 key 以及以前看到的所有租约。 ListcacheKeysToLookUp = new ArrayList<>(); cacheKeysToLookUp.add(key); for (Lease previouslySeenLease : previouslySeenLeases) { cacheKeysToLookUp.add(previouslySeenLease.getNonce()); } ListvaluesFromCacheServer = cacheCluster.get(cacheKeysToLookUp); byte[] valueForKey = valuesFromCacheServer.remove(0); // 检查该值是否隐藏在我们前面看到的某个租约的后面。 for (byte[] valueForPreviouslySeenLease : valuesFromCacheServer) { if (valueForPreviouslySeenLease != null) { return valueForPreviouslySeenLease; } } if (valueForKey == null) { // 我们试着获取该 key 的租约。 Lease newLease = leaseUtils.createNew(); boolean leaseAddSucceeded = cacheCluster.atomicAdd(key, newLease.getNonce()); if (leaseAddSucceeded) { // 我们设法获取该 key 的租约，这意味着需要我们去寻找真实源， // 然后用真实源里的值填充缓存。 byte[] valueFromSourceOfTruth = sourceOfTruthComputation.apply(key); boolean checkAndSetSuccceeded = cacheCluster.atomicCheckAndSet( key, newLease.getNonce(), valueFromSourceOfTruth ); // 让我们使用租约的 nonce 作为 key， 并将我们计算的值与之关联。 cacheCluster.set(newLease.getNonce(), valueFromSourceOfTruth); return valueFromSourceOfTruth; } else { // 另一个请求比我们先获得了租约。让我们重试。 return read(key, sourceOfTruthComputation, previouslySeenLeases); } } else if (leaseUtils.isCacheValueLease(valueForKey)) { // 另一个缓存请求持有该 key 的租约， // 让我们给它一些时间来填满混存，然后再重试。 sleep(100); previouslySeenLeases.add(leaseUtils.fromCacheValue(valueForKey)); return read(key, sourceOfTruthComputation, previouslySeenLeases); } else { // 从缓存服务中获取值，然后返回。 return valueForKey; } } private void sleep(int millis) { try { Thread.sleep(millis); } catch (InterruptedException e) { System.err.println('Sleep interrupted.'); e.printStackTrace(); } }}interface CacheCluster { /** * 从缓存集群获取键的列表。 * @param keys 要从缓存集群中获取键 * @return byte[] 列表表示与提供的键相关联的值 * 返回的列表将与提供的键列表并行， * 换句话说，与某个键关联的值在返回列表中的位置与键在键列表中的位置相同。 * 返回列表中的空值表示缓存未命中。 * 虽然这不是一个好的设计 API 的方法 * 但对于这个算法的高层演示，它能很好的运行。 */ Listget(Listkeys); /** * 设置值与缓存集群中所提供的键的关联关系 */ void set(byte[] key, byte[] value); /** * 当且仅当键尚未被设置时，为该键设置所提供的值。 * 否则，操作失败。 * @return 如果操作成功且设置了值，则返回 true，否则返回 false。 */ boolean atomicAdd(byte[] key, byte[] value); /** * 当且仅当键刚好与 expectedValue 相关关联时，为所提供的键设置 valueToSet。 * @return 如果操作成功且设置了值，则返回 true，否则返回 false。 */ boolean atomicCheckAndSet(byte[] key, byte[] expectedValue, byte[] valueToSet);}interface Lease { byte[] getNonce();}interface LeaseUtils { Lease createNew(); Lease fromCacheValue(byte[] nonce); boolean isCacheValueLease(byte[] value);}“恶魔”已经被这种方法困扰了一段时间了，因为我们一直在使用这种算法的变体来处理 Box 的分布式关系数据层的每秒数百万次的请求。作为“恶魔”最忠实的客户之一，我们希望这篇与“恶魔”打交道的概述能帮助你在性能和一致性的斗争取得胜利。