探索CPU的缓存架构，及引申到缓存系统的设计（二）
当前版本的多核共享缓存的MESI协议
而当上文所说在多核心时访问缓存的时候，就会存在数据不同步的问题：
这里有一个在多核环境下的典型场景：某个核心Core1把数据A从0改成1，Core1把数据A存在自己的L1缓存中，这时刚好Core2的L1缓存也缓存了数据A，但其值仍然为0，若这时Core2对数据A进行操作，就是操作了过期的数据A，如表1-3所示。
多核心下缓存操作过期数据示例
为了解决这一问题，人们提出了MESI协议，它是一种缓存一致性协议（cache cohere protocol），把缓存单元（cache line）的状态分为：修改过（M，Modified）、独占（E，Exclusive）、共享（S，Shared）、无效（I，Invalid），并通过这些状态来控制数据的写和同步。
MESI协议是处理器设计时内部支持的，通过标志位及版本号来标记缓存单元（cache line），如在Intel在2017年的手册中MESI的状态表中描述的，每个缓存单元（64bit）各自维护两个flag的标记位来记录MESI的协议等的状态信息，而其关系如表下所示，表中的“去系统总线”的意思是开始异步写内存数据。
Intel 在2017的文档中的MESI 共享状态表
Intel 在2017的文档中的MESI 共享状态表翻译
MESI协议的状态转换
我们把MESI协议的变换关系总结为表：
MESI协议的状态转换
为了更清晰描述，我们在下面画出整体的状态图，描述M E S I 之间的转换关系，主要关注状态的变更。
我们可以认为MESI协议的文字描述如下:
状态从Invalid开始，Read Miss 变成 Exclusive ，Write Miss 变成Modified，当其它核心有数据时Read Miss 变成 Shared。
在Exclusive下的读缓存，不会改变状态，写缓存会使自身状态变为Modified，当侦测到其它核心上的当前缓存的地址的读操作，状态会变成Shared，侦测到其它核心上的当前缓存的地址的写操作，状态会变成Invalid。
在Modified下的读缓存，不会改变状态，当侦测到其它核心上的当前缓存的地址的读操作，状态会变成Shared，侦测到其它核心上的当前缓存的地址的写操作，状态会变成Invalid。
在Shared下的读缓存，不会改变状态，写缓存会使自身状态变为Modified，当侦测到其它核心上的当前缓存的地址的读操作，不会改变状态，侦测到其它核心上的当前缓存的地址的写操作，状态会变成Invalid。
笔者画的MESI的状态变化的概览
从无状态/初始时/Invalid 开始进行的变化
Exclusive 相关的变化图
Modified相关的变化图
Shared相关的变化图
Invalid相关的变化图
MESI协议的举例
看了上面的流程图后，我们再从一个例子来看看MESI协议的实际操作，以Modified这个状态为例，现在多核心CPU的实现是：当一个核心对一个缓存单元的数据进行修改，使状态变为Modified，这时当其他核心也要操作此缓存单元对应的数据地址时，当前核心会向打算使用此数据的核心发送信号，通知其改变缓存单元的状态，并且会触发一次异步的内存回写，同时把修改过的数据直接传送给要操作此数据的核心。这时如果对方是读操作，则自己的状态变为Shared，对方的状态是Shared；如果对方是写操作，则自己的状态变为Invalid，对方的状态是Modified。如下两表。
多核心的缓存数据同步的问题（其他核心读）
多核心的缓存数据同步的问题（其他核心写）
而如果当前核心的一个缓存单元的状态是S，则在侦测到其他核心写缓存单元对应的数据时，会使此缓存单元的状态变为I；如果当前核心要再次操作之前缓存单元映射的内存地址的数据，则会再次执行另一次缓存载入的操作。如下两表。
多核心的缓存数据同步的问题（无缓存的核心写）
多核心的缓存数据同步的问题（S的核心写）
MESI协议的其它讨论
但是AMD的实现细节和INTEL略有不同，如下图所示是AMD的MOESI的一个状态变更图（2013的文档），它和Intel一样，也是通过侦测其他核心对内存的操作倾向来更新缓存单元的状态，并通知其他核心。这里AMD多加了个Owner的状态，该状态是Modified的升级，唯一不同的是允许在其他核心中有Shared状态，而Modified是独占状态（不允许其它核心有Shared的状态）。
AMD文档中的MOESI的状态变化图
另外看一些之前的文档表示Intel根据MESI拓展出了MESIF协议，增加了一个Share的中间状态F（Forward），表示在此状态时数据可以再被传给其他核心，但现在Intel文档中只有MESI了，应该是已经不再使用了。
CPU对内存的分类
其实处理器还对内存进行了策略分类，上面介绍的是在默认的内存类型下的情况（Write Back）,如上所述的MESI协议结合这个内存类型后，基本可以解决CPU使用的绝大部分场景。
但是CPU在某些使用场景下，对缓存和内存的一致性有不同程度的强需求，因此，CPU厂商针对CPU的使用场景设计了不同的内存类型，比如从不使用缓存，到只有读使用缓存，再到读写都使用缓存（Write Back）等各种类型。
这些类型对我们参看分布式系统中遇到的问题，应该还是有很多借鉴意义的，而且有这些内存类型的缓存才是完整的一个缓存系统，所有也希望大家能了解一下这些，下面按Intel的文档列出分类：
1. UC：Strong Uncacheable不可缓存，不可预测读（speculative read），分类位UC的内存读写都不会被缓存，这里主要对应有内存映射的IO设备的内存
a). AMD对应的名称：Uncacheable (UC)
2. UC-：Uncacheable，不可缓存，不可预测读，同UC ，不过类型被可变为WC
a). AMD名称：近似Cache Disable (CD)
3. WC：Write Combining，不可缓存，可预测读，同UC-，但就是可以缓存多个写请求后批量提交。
a). 在AMD对应的名称：同名，同时对应AMD的Uncacheable (UC)
b). 在AMD还有一个WC+ Write Combining plus的类型，这个对应AMD的CacheDisable (CD)
4. WT ：Write-through 读操作可缓存，可预测读，可缓存多个写请求后批量提交。但是写缓存miss时或缓存单元状态位无效时不刷新写缓存，直接写内存；若写操作能命中缓存时，在写缓存的同时也写内存（through to）。
a). 在AMD对应的名称：同名
5. WB ：Write-back默认模式，读写操作可缓存，可预测读，可缓存多个写请求后批量提交。写操作写缓存后不主动提交到内存，当回写操作发生时（write back）才把数据写回内存。回写操作发生的条件是缓存满后新分配内存，写旧的缓存单元到内存，或MESI在同步数据时。
这个模式适用于绝大多数的系统和应用程序。
a). 在AMD对应的名称：同名
6. WP ：Write protected读操作可缓存，可预测读。但是写操作直接写内存（propagated to），同时使所有核心的缓存单元变成失效状态。
a). 在AMD对应的名称：同名
对于这些类型，我们可以参考下面表格来对比他们的相同和不同。
Intel在2017手册中列的内存类型对比
翻译Intel在2017手册中列的内存类型对比
这里AMD文档上的一些技术细节和Intel不完全一样，不过比较这两个的区别现在不是本文重点，就不详细罗列了。
处理器的MESI协议加上这些内存类型，就可以按照人们流行的2/8原则解决缓存问题了：80%的情况由默认内存类型解决，虽说这个20%也不简单，而20%的情况由定义的另外80%的内存类型解决。
简单引申到系统的缓存架构及讨论
上面主要描述了CPU的缓存架构，CPU需要通过定义内存类型，以及一致性协议来解决其遇到的多核心下的性能和一致性等问题。
其实解决多个核心间的协同工作，这一点也和我们在系统缓存架构上要面对的一些问题相似，如缓存架构的高并发，高可用，可伸缩等这些。
我们认为，CPU的寄存器和CPU周期同步其实也可以理解为是运算单元一部分，而L1缓存，则可认为是分布式节点中的本地内存，L2和L3缓存则可以认为是共用的Redis这样的通用缓存，内存则可以认为是数据库与Elasticsearch这些真正的数据源。如表.
从CPU架构到系统架构的对应关系
参照CPU的设计思路，其实系统上最理想的状态是：我们也大量使用分布式节点的内存做缓存，或更多依赖本地的内存进行一些计算，但是这里也有一些问题和挑战：
第一个就是持久性问题，如果使用缓存的话，如何解决数据的持久性问题，这个一般需要直接访问持久化层，如数据库，或消息队列，它们返回成功就认为成功。但在一些高性能要求的环境下，也可以通过主从强一致协议来完成，就是写事务由主开始，主发送事务给从，所有的从都返回收到数据给主，然后主返回成功，而在这个过程中都是内存操作，所有的主从通过异步写数据来保证同步，如下图。
理想的缓存系统的设计
再一个就是同CPU多核间的脏数据问题，这个可以仍然把缓存分成不同大小的缓存块，然后也参考MESI协议给每个缓存的数据体包装一层，标记一个状态位，以及版本号，思路还是多利用Client的内存进行计算，使用外部的内存进 51 34857 51 17844 0 0 7499 0 0:00:04 0:00:02 0:00:02 7497同步。
缓存块数据结构的设计
而缓存的高并发需求，也可以看作纯网络I/O的问题。我们曾经做过测试，MySQL可以在命中内存索引的情况下达到10万每秒的QPS，而Redis大致也是同样的表现。
其它的一些提升性能的办法如在Scaling Memcache at Facebook的论文中提到：对所有缓存的依赖进行分析，然后把所有没有依赖关系的缓存访问变成并行执行，把有依赖关系的保留串行执行。比如要获取一个商品的信息，同时获取商品的类目、城市、门店、优惠卷等信息，对这些缓存信息可以进行并行访问，而由于商品的类型不同，可能具体的字段也不同，所以只能串行获得商品的类型，这样可递归生成一个缓存的查询树，根据这个查询树来访问缓存。如图。
并发执行读缓存的示意图
缓存做可伸缩方案时需要修改其分片策略，比如Hash从mod 5变为mod 10时需要一个对应的策略，有些类似于Redis的Hash扩容，不过变成了在分布式环境下扩容，步骤如下。
（1）先分配mod10的主片和从片的空间。
（2）标记当前的数据版本号，开始双写，同时写旧的主片和新的主片。
（3）从标记的数据版本号向前异步地迁移数据。
（4）在数据迁移完成，切换读到新的片，随后关闭旧片的写入。
（5）迁移完成，可以删除旧片。
在扩容时同样可以参照REIDS集群，预置缓存槽，然后分配缓存槽给对应的实例。但是一致性Hash认为存在一些问题，比如会出现热点，又如大量的访问只在其中一部分Hash段上出现。现在，Redis的集群用配置缓存槽可以解决这些问题。
另外，Facebook的一个模型是通过MySQL的数据复制同步两个大的数据中心，并同时维护两个本地的缓存池的
对于更新缓存数据，Facebook也提出一个很好的缓存模式，比如上面提到的MySQL等主流数据工具的事务成功都不是实际的数据持久化成功，而是在写日志成功时就认为是事务成功。所以，我们也可以根据MySQL的事务日志来更新缓存的信息，这样可以更好地解决缓存失效的问题。
这里我们抛砖引玉一的讨论了一下缓存系统的架构设计，也希望介绍的CPU的缓存的架构的这些内容能对大家在设计和使用缓存中有所帮助，后续我们也希望有机会做出我们新的缓存中间件。
推荐一起学习《分布式服务架构：原理、设计与实战》一书，它是一本不可多得的理论与实践相结合的架构秘籍，是作者多年工作经验积累的结晶。京东购买请扫描下方二维码。
如果你想成为优秀的架构师
在【云时代架构】精品群免费进！
我在【云时代架构】技术社区，你在哪里？
还等什么，赶快加入【云时代架构】技术社区！
请猛扫下面二维码。
云时代架构
做互联网时代最适合的架构
开放、分享、协作
快速关注，请猛扫下面二维码！
简书博客 云时代架构