cache之多核一致性(二) - 总线上没有秘密
前面的文章讲到了cache(高速缓存)的读写一致性，这主要是基于单核的角度讨论的，在单核系统中，cache line中的数据是primary memory(主存/内存)中对应位置的数据的一个拷贝(副本)，“cache一致性”就是cache和内存之间的数据一致性。
而在多核系统中(限定于只有一级local cache的情况)，每个CPU(processor/core)的cache line中的数据都是它们共享的内存中对应位置的数据的一个拷贝，因此多核系统的“cache一致性”既包括cache和内存之间的一致性，还包括各个CPU的cache之间的一致性，也就是说，对内存同一位置的数据，不同CPU的cache line不应该有不同(或者说不一致)的值。
靠什么一致？
CPU从内存中读取数据到cache line的操作被称为"load"，而将cache line中的数据写回到内存对应位置的操作则被称为"store"。在硬件设计中，cache属于CPU的一部分，而CPU和内存之间是通过bus(总线)相连的，因此不管是"load"还是"store"操作，都需要经过总线的传输，总线的一次传输被称为"transcation"。
总线被多个CPU所共享，某个CPU对总线的访问，都能被挂接在同一总线上的其他CPU“看到”。比如现在有两个CPU，分别是P1和P2，它们都从内存X的位置读取(load)了数据到各自的cache line(假设值为8)，然后P2往自己的cache line写入了一个新的数据(假设为13)，那么接下来如果P1再读取这条cache line，得到的数据将是P2写入的值(13)，内存X位置的值也将变成13。
这种机制被称为Write Propagation，也就是一个CPU对内存某个位置的数据的改动好像propagate(传播)到其他CPU对应的cache line上一样。不过，要想维护cache一致性，光有write propagation是不够的，还需要Transaction Serialization。
假设现在总线上有4个CPU，分别是P1, P2, P3和P4，它们从内存读取了一个共享变量S到各自的cache line后，P1在自己的cache line中将S修改为10，接下来P2在自己的cache line中将S修改为20，如果只有write propagation，那么P3看到的可能是P1对S的改动在P2之后，P3读取S得到的值就是10，而P4看到的是P1对S的改动在P2之前，P4读取S得到的值将是20，这就出现了不一致。
所以，需要保证各个CPU对内存同一位置的store和load的操作是序列化的(sequenced)，也就是store和load的顺序应该和线程执行的顺序一致，即transaction serialization。
又是“看到”，又是“传播”，这些拟人化的词听起来好像很悬乎，那它在现代计算机中到底是如何实现的呢？
怎样看到？
实现的方式大致说来有两种，一种是"Snooping"，一种是"Directory-based"。
广而告之
Snooping机制采用广播的形式，也就是当一个CPU修改了cache line之后，将广播通知到总线上其他所有的CPU。收听广播是需要耳朵(或者收音机)的，对于CPU来说这个“耳朵”就是一个硬件单元(所以应该叫“听到”更合适)，它会负责监听总线上所有transactions的广播。
广播的方式虽然简单，但要时刻监听总线上的一切活动，可得累个够呛，而且CPU之间共享的内存数据毕竟只占少数，大部分监听可以说都是白费力气，所以又引入了一个用于过滤的snoop filter，过滤的标准就是看自家的CPU有没有缓存这个transaction涉及到的内存位置，或者说有没有对应的cache line。那怎么判断有没有呢？识别cache line的标准，自然是tag比对啦(参考这篇文章)。
过滤之后接收方的工作减轻了，可广播还一直在那儿呢，每个CPU产生的总线transaction，都要广播给其他的每个CPU，这得多消耗总线带宽(bandwidth)啊。假设CPU的个数是N，那么需要的总线带宽就是 。所以啊，如果总线上CPU的数目比较少还好(2到8个)，这按平方的增长速度，多了总线可就吃不消了。
这同时也说明，总线的带宽是系统中可容纳CPU数目的限制条件之一。这里稍微展开说一下，因为cache是被设计在CPU一侧的，现代CPU大部分的数据访问操作(90%)都可以直接通过cache完成，不需要和内存交互，所以cache的出现除了提高CPU访问数据的效率，又极大的节约了总线带宽，进而使系统可容纳的CPU数目增加。当然，维护cache一致性需要一些额外的总线transaction，这稍稍降低了实际的节约量。
精准投放
与Snooping机制采用广播的方式不同，Directory-based机制采用的是点对点的方式进行传播(就像打电话一样)，每个总线transaction只会发给感兴趣的CPU。何谓感兴趣？就是拥有这个transaction所涉及内存位置对应的cache line。说起来容易，那怎么知道哪些CPU“感兴趣”呢？既然都叫directory-based，靠的就是一个ditectory，所有CPU的cache line的信息，都被记录在这个directory(电话簿)里。
还是假设CPU的个数为N，在最理想的情况下，所有的共享数据都只被2个CPU共享，那么需要的总线带宽就是 ，比起snoop模式少了很多。而在最坏的情况下，所有的共享数据被所有的CPU共享，需要的总线带宽就是
，比起snoop模式来说完全没有优势。
不过，在大多数时候，数据共享的情况远不可能那么普遍，所以directory-based模式通常是比snoop模式更节省总线带宽的，尤其是在CPU数目较多的场景(>64)。带宽是节省了，但付出的代价是directory本身的开销，和每次transactions前都要查询directory所造成的延迟(latency)。带宽和延迟之间的矛盾，无处不在。
以上讨论都是基于的UMA系统，而在NUMA系统中，不同node的CPU之间不再是通过共享的总线相连，而是通过基于消息传递(message‐passing)的interconnect相连：
这时如果还想使用snooping机制，就需要去模拟总线的行为，但是这会相当复杂。举个嵌入式方面的例子，早期单片机的I2C接口比较少，所以有些工程师会用普通的GPIO线去模拟I2C的协议，达到和使用I2C总线类似的效果，但实现复杂不说，通信效率也比不上真实的硬件I2C总线。
所以，在NUMA系统中，通常的选择都是基于directory-based模式来维护cache的一致性。
好，现在其他CPU已经看到了，那它们看到之后会做什么呢，请看下文分解。
参考：
《现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术》
https://en.wikipedia.org/wiki/Cache_coherence