一文读懂CPU缓存一致性的实现

　　话不多说，本文大纲
　　CPUCache的数据写入
　　随着时间的推移，CPU和内存的访问性能相差越来越大，于是就在CPU内部嵌入了CPUCache（高速缓存），CPUCache离CPU核心相当近，因此它的访问速度是很快的，于是它充当了CPU与内存之间的缓存角色。
　　CPUCache通常分为三级缓存：L1Cache、L2Cache、L3Cache，级别越低的离CPU核心越近，访问速度也快，但是存储容量相对就会越小。其中，在多核心的CPU里，每个核心都有各自的L1L2Cache，而L3Cache是所有核心共享使用的。
　　我们先简单了解下CPUCache的结构，CPUCache是由很多个CacheLine组成的，CPULine是CPU从内存读取数据的基本单位，而CPULine是由各种标志（Tag）数据块（DataBlock）组成，你可以在下图清晰的看到：
　　我们当然期望CPU读取数据的时候，都是尽可能地从CPUCache中读取，而不是每一次都要从内存中获取数据。所以，身为程序员，我们要尽可能写出缓存命中率高的代码，这样就有效提高程序的性能，具体的做法，你可以参考我上一篇文章如何写出让CPU跑得更快的代码？（opensnewwindow）
　　事实上，数据不光是只有读操作，还有写操作，那么如果数据写入Cache之后，内存与Cache相对应的数据将会不同，这种情况下Cache和内存数据都不一致了，于是我们肯定是要把Cache中的数据同步到内存里的。
　　问题来了，那在什么时机才把Cache中的数据写回到内存呢？为了应对这个问题，下面介绍两种针对写入数据的方法：写直达（WriteThrough）写回（WriteBack）
　　写直达
　　保持内存与Cache一致性最简单的方式是，把数据同时写入内存和Cache中，这种方法称为写直达（WriteThrough）。
　　在这个方法里，写入前会先判断数据是否已经在CPUCache里面了：如果数据已经在Cache里面，先将数据更新到Cache里面，再写入到内存里面；如果数据没有在Cache里面，就直接把数据更新到内存里面。
　　写直达法很直观，也很简单，但是问题明显，无论数据在不在Cache里面，每次写操作都会写回到内存，这样写操作将会花费大量的时间，无疑性能会受到很大的影响。
　　写回
　　既然写直达由于每次写操作都会把数据写回到内存，而导致影响性能，于是为了要减少数据写回内存的频率，就出现了写回（WriteBack）的方法。
　　在写回机制中，当发生写操作时，新的数据仅仅被写入CacheBlock里，只有当修改过的CacheBlock被替换时才需要写到内存中，减少了数据写回内存的频率，这样便可以提高系统的性能。
　　那具体如何做到的呢？下面来详细说一下：如果当发生写操作时，数据已经在CPUCache里的话，则把数据更新到CPUCache里，同时标记CPUCache里的这个CacheBlock为脏（Dirty）的，这个脏的标记代表这个时候，我们CPUCache里面的这个CacheBlock的数据和内存是不一致的，这种情况是不用把数据写到内存里的；如果当发生写操作时，数据所对应的CacheBlock里存放的是别的内存地址的数据的话，就要检查这个CacheBlock里的数据有没有被标记为脏的：如果是脏的话，我们就要把这个CacheBlock里的数据写回到内存，然后再把当前要写入的数据，先从内存读入到CacheBlock里（注意，这一步不是没用的，具体为什么要这一步，可以看这个回答（opensnewwindow）），然后再把当前要写入的数据写入到CacheBlock，最后也把它标记为脏的；如果不是脏的话，把当前要写入的数据先从内存读入到CacheBlock里，接着将数据写入到这个CacheBlock里，然后再把这个CacheBlock标记为脏的就好了。
　　可以发现写回这个方法，在把数据写入到Cache的时候，只有在缓存不命中，同时数据对应的Cache中的CacheBlock为脏标记的情况下，才会将数据写到内存中，而在缓存命中的情况下，则在写入后Cache后，只需把该数据对应的CacheBlock标记为脏即可，而不用写到内存里。
　　这样的好处是，如果我们大量的操作都能够命中缓存，那么大部分时间里CPU都不需要读写内存，自然性能相比写直达会高很多。
　　为什么缓存没命中时，还要定位CacheBlock？这是因为此时是要判断数据即将写入到cacheblock里的位置，是否被其他数据占用了此位置，如果这个其他数据是脏数据，那么就要帮忙把它写回到内存。
　　CPU缓存与内存使用写回机制的流程图如下，左半部分就是读操作的流程，右半部分就是写操作的流程，也就是我们上面讲的内容。
　　缓存一致性问题
　　现在CPU都是多核的，由于L1L2Cache是多个核心各自独有的，那么会带来多核心的缓存一致性（CacheCoherence）的问题，如果不能保证缓存一致性的问题，就可能造成结果错误。
　　那缓存一致性的问题具体是怎么发生的呢？我们以一个含有两个核心的CPU作为例子看一看。
　　假设A号核心和B号核心同时运行两个线程，都操作共同的变量i（初始值为0）。
　　这时如果A号核心执行了i语句的时候，为了考虑性能，使用了我们前面所说的写回策略，先把值为1的执行结果写入到L1L2Cache中，然后把L1L2Cache中对应的Block标记为脏的，这个时候数据其实没有被同步到内存中的，因为写回策略，只有在A号核心中的这个CacheBlock要被替换的时候，数据才会写入到内存里。
　　如果这时旁边的B号核心尝试从内存读取i变量的值，则读到的将会是错误的值，因为刚才A号核心更新i值还没写入到内存中，内存中的值还依然是0。这个就是所谓的缓存一致性问题，A号核心和B号核心的缓存，在这个时候是不一致，从而会导致执行结果的错误。
　　那么，要解决这一问题，就需要一种机制，来同步两个不同核心里面的缓存数据。要实现的这个机制的话，要保证做到下面这2点：第一点，某个CPU核心里的Cache数据更新时，必须要传播到其他核心的Cache，这个称为写传播（WritePropagation）；第二点，某个CPU核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串行化（TransactionSerialization）。
　　第一点写传播很容易就理解，当某个核心在Cache更新了数据，就需要同步到其他核心的Cache里。而对于第二点事务的串行化，我们举个例子来理解它。
　　假设我们有一个含有4个核心的CPU，这4个核心都操作共同的变量i（初始值为0）。A号核心先把i值变为100，而此时同一时间，B号核心先把i值变为200，这里两个修改，都会传播到C和D号核心。
　　那么问题就来了，C号核心先收到了A号核心更新数据的事件，再收到B号核心更新数据的事件，因此C号核心看到的变量i是先变成100，后变成200。
　　而如果D号核心收到的事件是反过来的，则D号核心看到的是变量i先变成200，再变成100，虽然是做到了写传播，但是各个Cache里面的数据还是不一致的。
　　所以，我们要保证C号核心和D号核心都能看到相同顺序的数据变化，比如变量i都是先变成100，再变成200，这样的过程就是事务的串行化。
　　要实现事务串行化，要做到2点：CPU核心对于Cache中数据的操作，需要同步给其他CPU核心；要引入锁的概念，如果两个CPU核心里有相同数据的Cache，那么对于这个Cache数据的更新，只有拿到了锁，才能进行对应的数据更新。
　　那接下来我们看看，写传播和事务串行化具体是用什么技术实现的。
　　总线嗅探
　　写传播的原则就是当某个CPU核心更新了Cache中的数据，要把该事件广播通知到其他核心。最常见实现的方式是总线嗅探（BusSnooping）。
　　我还是以前面的i变量例子来说明总线嗅探的工作机制，当A号CPU核心修改了L1Cache中i变量的值，通过总线把这个事件广播通知给其他所有的核心，然后每个CPU核心都会监听总线上的广播事件，并检查是否有相同的数据在自己的L1Cache里面，如果B号CPU核心的L1Cache中有该数据，那么也需要把该数据更新到自己的L1Cache。
　　可以发现，总线嗅探方法很简单，CPU需要每时每刻监听总线上的一切活动，但是不管别的核心的Cache是否缓存相同的数据，都需要发出一个广播事件，这无疑会加重总线的负载。
　　另外，总线嗅探只是保证了某个CPU核心的Cache更新数据这个事件能被其他CPU核心知道，但是并不能保证事务串行化。
　　于是，有一个协议基于总线嗅探机制实现了事务串行化，也用状态机机制降低了总线带宽压力，这个协议就是MESI协议，这个协议就做到了CPU缓存一致性。
　　MESI协议
　　MESI协议其实是4个状态单词的开头字母缩写，分别是：Modified，已修改Exclusive，独占Shared，共享Invalidated，已失效
　　这四个状态来标记CacheLine四个不同的状态。
　　已修改状态就是我们前面提到的脏标记，代表该CacheBlock上的数据已经被更新过，但是还没有写到内存里。而已失效状态，表示的是这个CacheBlock里的数据已经失效了，不可以读取该状态的数据。
　　独占和共享状态都代表CacheBlock里的数据是干净的，也就是说，这个时候CacheBlock里的数据和内存里面的数据是一致性的。
　　独占和共享的差别在于，独占状态的时候，数据只存储在一个CPU核心的Cache里，而其他CPU核心的Cache没有该数据。这个时候，如果要向独占的Cache写数据，就可以直接自由地写入，而不需要通知其他CPU核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。
　　另外，在独占状态下的数据，如果有其他核心从内存读取了相同的数据到各自的Cache，那么这个时候，独占状态下的数据就会变成共享状态。
　　那么，共享状态代表着相同的数据在多个CPU核心的Cache里都有，所以当我们要更新Cache里面的数据的时候，不能直接修改，而是要先向所有的其他CPU核心广播一个请求，要求先把其他核心的Cache中对应的CacheLine标记为无效状态，然后再更新当前Cache里面的数据。
　　我们举个具体的例子来看看这四个状态的转换：当A号CPU核心从内存读取变量i的值，数据被缓存在A号CPU核心自己的Cache里面，此时其他CPU核心的Cache没有缓存该数据，于是标记CacheLine状态为独占，此时其Cache中的数据与内存是一致的；然后B号CPU核心也从内存读取了变量i的值，此时会发送消息给其他CPU核心，由于A号CPU核心已经缓存了该数据，所以会把数据返回给B号CPU核心。在这个时候，A和B核心缓存了相同的数据，CacheLine的状态就会变成共享，并且其Cache中的数据与内存也是一致的；当A号CPU核心要修改Cache中i变量的值，发现数据对应的CacheLine的状态是共享状态，则要向所有的其他CPU核心广播一个请求，要求先把其他核心的Cache中对应的CacheLine标记为无效状态，然后A号CPU核心才更新Cache里面的数据，同时标记CacheLine为已修改状态，此时Cache中的数据就与内存不一致了。如果A号CPU核心继续修改Cache中i变量的值，由于此时的CacheLine是已修改状态，因此不需要给其他CPU核心发送消息，直接更新数据即可。如果A号CPU核心的Cache里的i变量对应的CacheLine要被替换，发现CacheLine状态是已修改状态，就会在替换前先把数据同步到内存。
　　所以，可以发现当CacheLine状态是已修改或者独占状态时，修改更新其数据不需要发送广播给其他CPU核心，这在一定程度上减少了总线带宽压力。
　　事实上，整个MESI的状态可以用一个有限状态机来表示它的状态流转。还有一点，对于不同状态触发的事件操作，可能是来自本地CPU核心发出的广播事件，也可以是来自其他CPU核心通过总线发出的广播事件。下图即是MESI协议的状态图：
　　MESI协议的四种状态之间的流转过程，我汇总成了下面的表格，你可以更详细的看到每个状态转换的原因：
　　总结
　　CPU在读写数据的时候，都是在CPUCache读写数据的，原因是Cache离CPU很近，读写性能相比内存高出很多。对于Cache里没有缓存CPU所需要读取的数据的这种情况，CPU则会从内存读取数据，并将数据缓存到Cache里面，最后CPU再从Cache读取数据。
　　而对于数据的写入，CPU都会先写入到Cache里面，然后再在找个合适的时机写入到内存，那就有写直达和写回这两种策略来保证Cache与内存的数据一致性：写直达，只要有数据写入，都会直接把数据写入到内存里面，这种方式简单直观，但是性能就会受限于内存的访问速度；写回，对于已经缓存在Cache的数据的写入，只需要更新其数据就可以，不用写入到内存，只有在需要把缓存里面的脏数据交换出去的时候，才把数据同步到内存里，这种方式在缓存命中率高的情况，性能会更好；
　　当今CPU都是多核的，每个核心都有各自独立的L1L2Cache，只有L3Cache是多个核心之间共享的。所以，我们要确保多核缓存是一致性的，否则会出现错误的结果。
　　要想实现缓存一致性，关键是要满足2点：第一点是写传播，也就是当某个CPU核心发生写入操作时，需要把该事件广播通知给其他核心；第二点是事物的串行化，这个很重要，只有保证了这个，才能保障我们的数据是真正一致的，我们的程序在各个不同的核心上运行的结果也是一致的；
　　基于总线嗅探机制的MESI协议，就满足上面了这两点，因此它是保障缓存一致性的协议。
　　MESI协议，是已修改、独占、共享、已失效这四个状态的英文缩写的组合。整个MSI状态的变更，则是根据来自本地CPU核心的请求，或者来自其他CPU核心通过总线传输过来的请求，从而构成一个流动的状态机。另外，对于在已修改或者独占状态的CacheLine，修改更新其数据不需要发送广播给其他CPU核心。