https://zhuanlan.zhihu.com/p/151745863
在计算机系统设计实践中，我们常常会遇到下图所示架构：
为了解决单个存储器读吞吐无法满足要求的问题，常常需要在存储器上面增加一个或多个缓存。但由于相同的数据被复制到一个或多个地方，就容易引发数据一致性问题。不一致的数据可能出现在同级 Cache 之间 (Cache Coherence) 和上下级 Cache 之间。解决这些数据一致性问题的方案可以统称为 Cache Policies。从本质上看，所有 Cache Policies 的设计目的都可以概括为：在增加一级缓存之后，系统看起来和没加缓存的行为一致，但得益于局部性原理，系统的读吞吐量提高、时延减少。
本文将探讨三个场景：
在单核 CPU 中，只有一套 Cache，因此只要确保写入 Cache 中的数据也写入到 Memory 即可。
补充一些概念定义：数据在 Cache 与 Memory 之间移动的最小单位通常在 32 - 128 字节之间，Memory 中对应的最小单位数据称为 Cache Block，Cache 中与单个 Cache Block 对应的存储空间称为 Cache Line，在 Cache 中除了存储 Block 数据，还需要存储 Block 对应的唯一标识 T (Tag)，以及一个用于标记 Cache Line 是否有数据的有效位 V。完整对应关系如下图所示：
单核处理器下的 Cache Policy 要解决的问题可以被概括为：
CPU 从 Cache 中读到的数据必须是最近写入的数据
要满足定义，最简单的方式就是 Write-Through，即每次写入 Cache 时，也将数据写到 Memory 中。当之前写入的某数据 D 在某时刻被置换后，可以保证再次读入的数据是最近写入的数据。这里有个很明显的改进空间：只需要在数据 D 被置换前将其写入 Memory 即可。为此我们可以为每个 Cache Line 增加一个脏位 (Dirty Bit)，即：
当其被写入时置为 1；当其被置换时，如果脏位为 1，则写出到 Memory，否则直接丢弃即可。以上所述的 Cache Policy 就是 Write-Back Policy，也是目前在单核处理器中被广泛采用的 Cache Policy。
在多核 CPU 中，如果这些核共用一套缓存，由于单套 Cache 的吞吐跟不上，无法达到最佳性能。
这时候就需要在每个核上再加一级私有缓存：
假设在一个 4 核处理器中，内存地址 MA 处最开始存储着整数 0，这时每个核都需要完成一个 read-modify-write 的操作，如下所示：
如果不加任何协议，当 4 个核都完成相应的操作后，内存地址 MA 处可能存储着 1、2、3、4 中的任意值，这将影响并行计算的正确性。要保证并行计算的正确性，就必须保证每个核私有缓存之间的数据一致且永远是最新版本，可以想象，多核处理器上的各核之间必须遵守某种数据读写协议，才可能在获得多核计算力的同时维持计算的正确性，我们称这种数据读写协议为 Cache Coherence Protocols。
Cache Coherence 的要求：
要在多核 CPU 中实现 Cache Coherence，需要解决的根本问题是：让每个读操作在执行前能够获得所有最近的写操作历史。
从写操作传递信息的内容出发，可以将 Cache Coherence Protocols 划分为两类：Write-Update 和 Write-Invalidate。Write-Update 就是在写入数据时，将所有其它同级 Cache 中相同的 Cache Line 更新成最新数据；Write-Invalidate 就是在写入数据时，将所有其它同级 Cache 中相同的 Cache Line 标记为不合法。
从写操作传递信息的方式出发，可以将 Cache Coherence Protocols 划分为两类：Snooping 和 Directory。Snooping 将写数据的信息通过共享总线 (Shared Bus) 广播给其它同级 Cache，同时保证写操作的顺序一致；Directory 在内存中为每个 Cache Line 标记额外的元信息，每个 Cache Line 的读写控制分而自治，将写数据的信息通过点对点的方式传递。
任何一种 Cache Coherence Protocol 基本都可以从这两个维度被归类为以下四类：
Cache 中的每条 Cache Line，除了记录数据本身，额外使用 1 bit 标记 V 是否有效，以及若干 bits 用于存储 Cache Block 的唯一标识 T。多个核内部的 Cache 通过一条共享总线与 Memory 相连，如下图所示：
在原始的 Write-Update Snooping Example 中，我们采用 Write-Through 的方式，每当某个 Cache Line 写入数据时，都同时写穿到 Memory 中。本身 Memory 距离较远，读写数据时间长，就容易成为瓶颈，因此如果能够尽量使用类似 Write-Back 的策略，将数据保留在 Cache 中，用脏位 (dirty bit) 标记，等到其需要被替换时，再写入 Memory 中，就能优化该协议的整体性能。
总而言之：以上修改减少了读穿和写穿的频率，从而提高整体性能。
尽管增加 Opmization #1能减少读写 Memory 的资源消耗，但每次写数据时，依然要将信息发送到共享总线。大多数情况下，某 Cache Line T 对应的数据只有单个核会访问，因此如果能够提前识别其它核的 Cache 是否拥有该数据，避免向总线写入数据，就可以进一步提高整体性能。正因为此，我们可以尝试再加入一个共享标记位 (Shared Bit)，用于标记目标 Cache Line 是否同时存在于其它核的 Cache 中，如下图所示：
利用 Write-Update Snooping Example + Dirty Bit + Shared Bit 的结构，我们来看 Write-Invalidate Snooping 的工作模式。
与 Write-Update Snooping 不同，Write-Invalidatie Snooping 每次写入数据后，Cache 中 Cache Line T 的共享标记位 S 总是为 0，只有一个 Cache 中其对应的有效位 V 为 1，即全局只有一个 Cache 拥有有效数据。
Update 与 Invalidate 究竟二者谁更优异？这需要实际运行模式的检验，考虑以下 3 种常见场景：
尽管二者看起来各有千秋，在实践中普遍被采用的还是 Invalidate Coherence。原因在于：在多核 CPU 的运行时中，一个最频繁的操作就是将一个 Thread 从一个核移动到另一个核上运行。分析一下这种场景：
在 Write-Invalide Snooping Example 中，我们在每个 Cache Line 上使用了 3 个标记位：有效位 T、脏位 D 和共享位 S，一共可以表示 8 个状态。每个 Cache Line 真的需要 8 个状态吗？我们发现实际上每个 Cache Line 只需 3 个状态就足够实现 Write-Invalide Snooping Protocol：
其状态机如下图所示：
表示 3 个状态只需要 2 bits，这种更简单的 Write-Invalid Snooping Protocol 被称为 MSI。尽管 MSI 能达到目的，但它在多个场景下仍存在效率问题，因此也有相应的改进版本 MOSI、MOESI 被提出，这里不再赘述。
由于 Snooping 依赖基于共享总线的广播和监听，当 CPU 核数大于 8 个以后，共享总线就需要处理更多信号，解决更多冲突，成为瓶颈。因此抛弃广播网络、拥抱点对点网络通信是获得扩展性的前提。失去广播网络后，如何保证对同一个 Block 的写入顺序在各 CPU 核中保持一致，又重新成为难题。
Directory Protocols 正是为解决上述问题而被提出。要序列化对同一个 Block 的数据写入顺序，就必须将这些写入操作集中到一个节点上，但这并未要求对不同 Block 的写操作集中到一个节点上。于是我们可以将不同 Block 的控制权分散到不同分片中，这里的分片就是所谓的 Directory，每个 Directory 中包含若干个 Block 的控制信息。每个 Block 在 Directory 中记录的信息包含两个部分：
假设 CPU 中有 4 个核，每个核拥有私有 Cache，可以为每个 Block 记录 5 bits 信息：
这时整个架构如下图所示：
这种分片的思想也是解决分布式系统横向扩展性的利器，值得深思。
在 Web APP 开发中，通过引入缓存中间件 (redis/memcache) 来减少数据库压力是十分常见的做法，这时服务架构通常如下图所示：
如何从 Cache 和 DB 读取、写入数据就是 Cache/DB Architecture 下的 Cache Policy。与单核 CPU 中的 Cache Policy 不同，由于 Web APP 通常会部署在多个实例上，实践中几乎总是有多个进程在并行地增删改查数据。这时 Web APP 中不同进程写 Cache、写 DB 的顺序可以用 “一切皆有可能” 来概括。如果要保证二者之间数据的绝对一致，则必须要有分布式事务的支持，但无论是实现难度，还是分布式事务下的写性能下降，都不是开发者所期望的。因此在 Cache/DB Architecture 中，我们对 Cache Policy 的要求可以概括为：
最终一致性：在写入 DB 之后，经过足够长的时间后总能访问到最近写入的数据
经过简单分析，我们可以找到很多出现数据不一致的场景。
要实现 Cache/DB 中数据的最终一致，最简单的方式莫过于通过在 Cache 中为缓存数据设置过期时间，在经过这段时间后，会自动再次从数据库中重新加载数据，这样就能达到最终一致性。
这个方案的缺点也很明显，假如过期时间设置为 30 分钟，那么 Web APP 就需要容忍 30 分钟的数据不一致，这对很多服务来说几乎是无法接受的。当然，开发者可以把过期时间设短一些，但设得越短，读击穿到 DB 的频率也就越高，就和 Cache/DB Architecture 的初衷背道而驰。
Cache Aside 的读写逻辑如下：
这种方法适用于大多数场景，它通常也是实践中的标准做法。当然，这种做法也并非完美：
上述做法也可以被称为 Write-Invalidate，即写入 DB 之后将 Cache 中对应的数据置为失效状态。为什么不使用类似 Write-Update 的做法？这样还能够节省一次 DB 与 Cache 之间的网络 I/O。写入 DB 后直接写入 Cache 的做法存在一个致命的场景：A、B 进程同时写入数据，其执行顺序如下：
好家伙，这下好了…
Read Through 的读写逻辑如下：
这时候服务架构如下图所示：
Read Through 的核心问题在于 Cache 需要支持逻辑嵌入，然而一般这种做法会导致运维、部署都不方便。
Write Through 与 Read Through 类似，就是在写入时由 Cache 层负责写入 DB 中。这种方案的问题主要包括：
Double Delete 的读写逻辑如下：
其实它可以被理解成是 Cache Aside 的改进版，通过一段时间后的二次删除，避免因为并行问题导致 Cache 中的过时数据覆盖新写入数据的情况。
Write Behind 的读写逻辑如下：
这时候服务的架构如下图所示：
这种做法可以极大地提高读写吞吐量，但缺点也比较明显：
Write Behind 还有一种变体，就是将写入的顺序调换：
这时候服务的架构如下图所示：
相较于原版 Write Behind，由于 DB 在复制的过程中已经实现了类似的 MQ，因此只需要开发解析复制日志的 DB 中间件，伪装成 Slave 节点，即可实现相应流程。整个架构中无需引入额外的 MQ，减少部署、运维成本。
本节，我们从连接数的角度观察一下 Cache/DB Architecture 中不同 Cache Policies 的架构。假设各上游服务与下游服务建立的连接池为固定大小 N。
考虑服务会被部署多个副本，在 Cache Expiry、Cache Aside 以及 Double Delete 中，架构中各节点间的连接状态如下图所示：
每个服务实例都需要与 DB、Cache 建立 N 个连接，由于其它服务也需要访问相同的 DB、Cache 集群，这时候就会出现极高的连接数。
在 Read-Through、Wright-Through 以及 Write-Behind 中，架构中各节点的连接状态如下图所示：
每个服务实例都需要与 Cache 建立 N 个链接，Cache 与 MQ、MQ 与 DB 之间都只需要建立 N 个链接。
在 Write-Behind 的变体中，解析复制日志的中间件只需要与数据库建立 1 个连接即可，如下图所示：
本小节列举了多种 Cache Policies，通常最常用的并不是设计最复杂的，具体场景需要具体分析，也许最简单的做法就能满足需求。Less code, less bugs : )。