服务端缓存

笔者介绍透明多级分流系统的逻辑脉络，是以流量从客户端中发出为起始，以流量到达服务器集群中真正处理业务的节点为终结，探索该过程中与业务无关的通用组件。很难清楚界定清楚服务端缓存到底算不算与业务逻辑无关，不过，既然本章以“客户端缓存”为开篇，那“服务端缓存”作为结束，倒是十分合适的，在这一节里，笔者所说的“缓存”，均特指服务端缓存。

为系统引入缓存之前，第一件事情是确认你的系统是否真的需要缓存。很多人会有意无意地把硬件里那种常用于区分不同产品档次、“多多益善”的缓存（如 CPU L1/2/3 缓存、磁盘缓存，等等）代入软件开发中去，实际上这两者差别很大，在软件开发中引入缓存的负面作用要明显大于硬件的缓存：从开发角度来说，引入缓存会提高系统复杂度，因为你要考虑缓存的失效、更新、一致性等问题（硬件缓存也有这些问题，只是不需要由你去考虑，主流的 ISA 也都没有提供任何直接操作缓存的指令）；从运维角度来说，缓存会掩盖掉一些缺陷，让问题在更久的时间以后，出现在距离发生现场更远的位置上；从安全角度来说，缓存可能泄漏某些保密数据，也是容易受到攻击的薄弱点。冒着上述种种风险，仍能说服你引入缓存的理由，总结起来无外乎以下两种：

请注意，缓存虽然是典型以空间换时间来提升性能的手段，但它的出发点是缓解 CPU 和 I/O 资源在峰值流量下的压力，“顺带”而非“专门”地提升响应性能。这里的言外之意是如果可以通过增强 CPU、I/O 本身的性能（譬如扩展服务器的数量）来满足需要的话，那升级硬件往往是更好的解决方案，即使需要一些额外的投入成本，也通常要优于引入缓存后可能带来的风险。

有不少软件系统最初的缓存功能是以 HashMap 或者 ConcurrentHashMap 为起点演进的。当开发人员发现系统中某些资源的构建成本比较高，而这些资源又有被重复使用的可能性时，会很自然地产生“循环再利用”的想法，将它们放到 Map 容器中，下次需要时取出重用，避免重新构建，这种原始朴素的复用就是最基本的缓存了。不过，一旦我们专门把“缓存”看作一项技术基础设施，一旦它有了通用、高效、可统计、可管理等方面的需求，其中要考虑的因素就变得复杂起来。通常，我们设计或者选择缓存至少会考虑以下四个维度的属性：

缓存的吞吐量只在并发场景中才有统计的意义，因为不考虑并发的话，即使是最原始的、以 HashMap 实现的缓存，访问效率也已经是常量时间复杂度，即 O(1)，其中涉及到碰撞、扩容等场景的处理属于数据结构基础，这里不展开。但 HashMap 并不是线程安全的容器，如果要让它在多线程并发下能正确地工作，就要用 Collections.synchronizedMap 进行包装，这相当于给 Map 接口的所有访问方法都自动加全局锁；或者改用 ConcurrentHashMap 来实现，这相当于给 Map 的访问分段加锁（从 JDK 8 起已取消分段加锁，改为 CAS+Synchronized 锁单个元素）。无论采用怎样的实现方法，线程安全措施都会带来一定的吞吐量损失。

进一步说，如果只比较吞吐量，完全不去考虑命中率、淘汰策略、缓存统计、过期失效等功能该如何实现，那也不必选择，JDK 8 改进之后的 ConcurrentHashMap 基本上就是你能找到的吞吐量最高的缓存容器了。可是很多场景里，以上提及的功能至少有部分一两项是必须的，不可能完全不考虑，这才涉及到不同缓存方案的权衡问题。

根据 Caffeine 给出的一组目前业界主流进程内缓存实现方案，包括有 Caffeine、ConcurrentLinkedHashMap、LinkedHashMap、Guava Cache、Ehcache 和 Infinispan Embedded 的对比，从Benchmarks中体现出的它们在 8 线程、75%读操作、25%写操作下的吞吐量来看，各种缓存组件库的性能差异还是十分明显的，最高与最低的相差了足有一个数量级，具体如图 4-12 所示。

图片来自Caffeine

这种并发读写的场景中，吞吐量受多方面因素的共同影响，譬如，怎样设计数据结构以尽可能避免数据竞争，存在竞争风险时怎样处理同步（主要有使用锁实现的悲观同步和使用CAS实现的乐观同步）、如何避免伪共享现象（False Sharing，这也算是典型缓存提升开发复杂度的例子）发生，等等。其中第一点尽可能避免竞争是最关键的，无论如何实现同步都不会比直接无须同步更快，笔者下面以 Caffeine 为例，介绍一些缓存如何避免竞争、提高吞吐量的设计。

缓存中最主要的数据竞争源于读取数据的同时，也会伴随着对数据状态的写入操作，写入数据的同时，也会伴随着数据状态的读取操作。譬如，读取时要同时更新数据的最近访问时间和访问计数器的状态（后文会提到，为了追求高效，可能不会记录时间和次数，譬如通过调整链表顺序来表达时间先后、通过 Sketch 结构来表达热度高低），以实现缓存的淘汰策略；又或者读取时要同时判断数据的超期时间等信息，以实现失效重加载等其他扩展功能。对以上伴随读写操作而来的状态维护，有两种可选择的处理思路，一种是以 Guava Cache 为代表的同步处理机制，即在访问数据时一并完成缓存淘汰、统计、失效等状态变更操作，通过分段加锁等优化手段来尽量减少竞争。另一种是以 Caffeine 为代表的异步日志提交机制，这种机制参考了经典的数据库设计理论，将对数据的读、写过程看作是日志（即对数据的操作指令）的提交过程。尽管日志也涉及到写入操作，有并发的数据变更就必然面临锁竞争，但异步提交的日志已经将原本在 Map 内的锁转移到日志的追加写操作上，日志里腾挪优化的余地就比在 Map 中要大得多。

在 Caffeine 的实现中，设有专门的环形缓存区（Ring Buffer，也常称作 Circular Buffer）来记录由于数据读取而产生的状态变动日志。为进一步减少竞争，Caffeine 给每条线程（对线程取 Hash，哈希值相同的使用同一个缓冲区）都设置一个专用的环形缓冲。

从 Caffeine 读取数据时，数据本身会在其内部的 ConcurrentHashMap 中直接返回，而数据的状态信息变更就存入环形缓冲中，由后台线程异步处理。如果异步处理的速度跟不上状态变更的速度，导致缓冲区满了，那此后接收的状态的变更信息就会直接被丢弃掉，直至缓冲区重新富余。通过环形缓冲和容忍有损失的状态变更，Caffeine 大幅降低了由于数据读取而导致的垃圾收集和锁竞争，因此 Caffeine 的读取性能几乎能与 ConcurrentHashMap 的读取性能相同。

向 Caffeine 写入数据时，将使用传统的有界队列（ArrayQueue）来存放状态变更信息，写入带来的状态变更是无损的，不允许丢失任何状态，这是考虑到许多状态的默认值必须通过写入操作来完成初始化，因此写入会有一定的性能损失。根据 Caffeine 官方给出的数据，相比 ConcurrentHashMap，Caffeine 在写入时大约会慢 10%左右。

有限的物理存储决定了任何缓存的容量都不可能是无限的，所以缓存需要在消耗空间与节约时间之间取得平衡，这要求缓存必须能够自动或者由人工淘汰掉缓存中的低价值数据，由人工管理的缓存淘汰主要取决于开发者如何编码，不能一概而论，这里只讨论由缓存自动进行淘汰的情况。笔者所说的“缓存如何自动地实现淘汰低价值目标”，现在被称为缓存的淘汰策略，也常称作替换策略或者清理策略。

缓存实现自动淘汰低价值数据的容器之前，首先要定义怎样的数据才算是“低价值”？由于缓存的通用性，这个问题的答案必须是与具体业务逻辑是无关的，只能从缓存工作过程收集到的统计结果来确定数据是否有价值，通用的统计结果包括但不限于数据何时进入缓存、被使用过多少次、最近什么时候被使用，等等。由此决定了一旦确定选择何种统计数据，及如何通用地、自动地判定缓存中每个数据价值高低，也相当于决定了缓存的淘汰策略是如何实现的。目前，最基础的淘汰策略实现方案有以下三种：

缓存淘汰策略直接影响缓存的命中率，没有一种策略是完美的、能够满足全部系统所需的。不过，随着淘汰算法的发展，近年来的确出现了许多相对性能要更好的，也更为复杂的新算法。以 LFU 分支为例，针对它存在的两个问题，近年来提出的 TinyLFU 和 W-TinyLFU 算法就往往会有更好的效果。

仅靠以上简单的、有限的介绍，你不一定能完全理解 TinyLFU 和 W-TinyLFU 的工作原理，但肯定能看出这些改进算法比起原来基础版本的 LFU 要复杂了许多。有时候为了取得理想的效果，采用较为复杂的淘汰策略是不得已的选择，Caffeine 官方给出的 W-TinyLFU 以及另外两种高级淘汰策略ARC（Adaptive Replacement Cache）、LIRS（Low Inter-Reference Recency Set）与基础的 LFU 策略之间的对比，如图 4-13 所示。

图 4-13 几种淘汰算法在搜索场景下的命中率对比（图片来自Caffeine）

在搜索场景中，三种高级策略的命中率较为接近于理想曲线（Optimal），而 LRU 则差距最远，Caffeine 官方给出的数据库、网站、分析类等应用场景中，这几种策略之间的绝对差距不尽相同，但相对排名基本上没有改变，最基础的淘汰策略的命中率是最低的。对其他缓存淘汰策略感兴趣的读者可以参考维基百科中对Cache Replacement Policies的介绍。

一般来说，一套标准的 Map 接口（或者来自JSR 107的 javax.cache.Cache 接口）就可以满足缓存访问的基本需要，不过在“访问”之外，专业的缓存往往还会提供很多额外的功能。笔者简要列举如下：

至此，本节已简要介绍了缓存的三项属性：吞吐量、命中率和扩展功能，笔者将几款主流进程内缓存方案整理成表 4-4，供读者参考。

表 4-4 几款主流进程内缓存方案对比

相比起缓存数据在进程内存中读写的速度，一旦涉及网络访问，由网络传输、数据复制、序列化和反序列化等操作所导致的延迟要比内存访问高得多，所以对分布式缓存来说，处理与网络有相关的操作是对吞吐量影响更大的因素，往往也是比淘汰策略、扩展功能更重要的关注点，这决定了尽管也有 Ehcache、Infinispan 这类能同时支持分布式部署和进程内嵌部署的缓存方案，但通常进程内缓存和分布式缓存选型时会有完全不同的候选对象及考察点。我们决定使用哪种分布式缓存前，首先必须确认自己需求是什么？

分布式缓存与进程内缓存各有所长，也有各有局限，它们是互补而非竞争的关系，如有需要，完全可以同时把进程内缓存和分布式缓存互相搭配，构成透明多级缓存（Transparent Multilevel Cache，TMC），如图 4-14 所示。先不考虑“透明”的话，多级缓存是很好理解的，使用进程内缓存做一级缓存，分布式缓存做二级缓存，如果能在一级缓存中查询到结果就直接返回，否则便到二级缓存中去查询，再将二级缓存中的结果回填到一级缓存，以后再访问该数据就没有网络请求了。如果二级缓存也查询不到，就发起对最终数据源的查询，将结果回填到一、二级缓存中去。

尽管多级缓存结合了进程内缓存和分布式缓存的优点，但它的代码侵入性较大，需要由开发者承担多次查询、多次回填的工作，也不便于管理，如超时、刷新等策略都要设置多遍，数据更新更是麻烦，很容易会出现各个节点的一级缓存、以及二级缓存里数据互相不一致的问题。必须“透明”地解决以上问题，多级缓存才具有实用的价值。一种常见的设计原则是变更以分布式缓存中的数据为准，访问以进程内缓存的数据优先。大致做法是当数据发生变动时，在集群内发送推送通知（简单点的话可采用 Redis 的 PUB/SUB，求严谨的话引入 ZooKeeper 或 Etcd 来处理），让各个节点的一级缓存自动失效掉相应数据。当访问缓存时，提供统一封装好的一、二级缓存联合查询接口，接口外部是只查询一次，接口内部自动实现优先查询一级缓存，未获取到数据再自动查询二级缓存的逻辑。

本节开篇就提到，缓存不是多多益善，它属于有利有弊，是真正到必须使用时才考虑的解决方案。本节将介绍使用几种常见的缓存风险及其应对办法。

缓存的目的是为了缓解 CPU 或者 I/O 的压力，譬如对数据库做缓存，大部分流量都从缓存中直接返回，只有缓存未能命中的数据请求才会流到数据库中，这样数据库压力自然就减小了。但是如果查询的数据在数据库中根本不存在的话，缓存里自然也不会有，这类请求的流量每次都不会命中，每次都会触及到末端的数据库，缓存就起不到缓解压力的作用了，这种查询不存在数据的现象被称为缓存穿透。

缓存穿透有可能是业务逻辑本身就存在的固有问题，也有可能是被恶意攻击的所导致，为了解决缓存穿透，通常会采取下面两种办法：

我们都知道缓存的基本工作原理是首次从真实数据源加载数据，完成加载后回填入缓存，以后其他相同的请求就从缓存中获取数据，缓解数据源的压力。如果缓存中某些热点数据忽然因某种原因失效了，譬如典型地由于超期而失效，此时又有多个针对该数据的请求同时发送过来，这些请求将全部未能命中缓存，都到达真实数据源中去，导致其压力剧增，这种现象被称为缓存击穿。要避免缓存击穿问题，通常会采取下面的两种办法：

缓存击穿是针对单个热点数据失效，由大量请求击穿缓存而给真实数据源带来压力。有另一种可能是更普遍的情况，不需要是针对单个热点数据的大量请求，而是由于大批不同的数据在短时间内一起失效，导致了这些数据的请求都击穿了缓存到达数据源，同样令数据源在短时间内压力剧增。

出现这种情况，往往是系统有专门的缓存预热功能，也可能大量公共数据是由某一次冷操作加载的，这样都可能出现由此载入缓存的大批数据具有相同的过期时间，在同一时刻一起失效。还有一种情况是缓存服务由于某些原因崩溃后重启，此时也会造成大量数据同时失效，这种现象被称为缓存雪崩。要避免缓存雪崩问题，通常会采取下面的三种办法：

缓存污染是指缓存中的数据与真实数据源中的数据不一致的现象。尽管笔者在前面是说过缓存通常不追求强一致性，但这显然不能等同于缓存和数据源间连最终的一致性都可以不要求了。

缓存污染多数是由开发者更新缓存不规范造成的，譬如你从缓存中获得了某个对象，更新了对象的属性，但最后因为某些原因，譬如后续业务发生异常回滚了，最终没有成功写入到数据库，此时缓存的数据是新的，数据库中的数据是旧的。为了尽可能的提高使用缓存时的一致性，已经总结不少更新缓存可以遵循设计模式，譬如 Cache Aside、Read/Write Through、Write Behind Caching 等。其中最简单、成本最低的 Cache Aside 模式是指：

读数据方面一般没什么出错的余地，但是写数据时，就有必要专门强调两点：一是先后顺序是先数据源后缓存。试想一下，如果采用先失效缓存后写数据源的顺序，那一定存在一段时间缓存已经删除完毕，但数据源还未修改完成，此时新的查询请求到来，缓存未能命中，就会直接流到真实数据源中。这样请求读到的数据依然是旧数据，随后又重新回填到缓存中。当数据源的修改完成后，结果就成了数据在数据源中是新的，在缓存中是老的，两者就会有不一致的情况。另一点是应当失效缓存，而不是去尝试更新缓存，这很容易理解，如果去更新缓存，更新过程中数据源又被其他请求再次修改的话，缓存又要面临处理多次赋值的复杂时序问题。所以直接失效缓存，等下次用到该数据时自动回填，期间无论数据源中的值被改了多少次都不会造成任何影响。

Cache Aside 模式依然是不能保证在一致性上绝对不出问题的，否则就无须设计出 Paxos 这样复杂的共识算法了。典型的出错场景是如果某个数据是从未被缓存过的，请求会直接流到真实数据源中，如果数据源中的写操作发生在查询请求之后，结果回填到缓存之前，也会出现缓存中回填的内容与数据库的实际数据不一致的情况。但这种情况的概率是很低的，Cache Aside 模式仍然是以低成本更新缓存，并且获得相对可靠结果的解决方案。