golang中的缓存一致性、内存序、内存屏障与CAS原理

CPU缓存架构

现代处理器一般是多核架构，并且为了平衡CPU和内存的速度差距，还引入了多级Cache。

 

CPU Cache 是由很多个 Cache Line 组成，每个Cache Line大小为64KB。Cache Line 是 CPU从内存读写数据的基本单位，每次从Cache中读取一个完整的Cache Line进行操作。（空间局部性原理）

我们期望 CPU 读取数据时，都是尽可能地从CPU Cache中读取，⽽不是每⼀次都要从内存中获取数据；如果数据写⼊ Cache 之后，内存与 Cache 相对应的数据将会不同，需要把 Cache 中的数据同步到 内存⾥的。

Cache Line从Cache写回内存由两种方案：

• 写直达 Writer Through，把数据同时写入内存和Cache中；性能较差
• 写回 Writer Back，新的数据仅仅被写⼊ Cache Block ⾥，只有当修改过的 Cache Line被换出时才需要写到内存中，减少数据写回内存的频率；性能较好 实际上，在CPU和L1 Cache之间还存在Store Buffer，也会用于缓存Cache Line，它的作用和影响在下面介绍。

Cache缓解了内存访问的延迟问题，但也带来了Cache一致性的问题： 当多个核心同时加载同一个Cache Line到Cache时，如果其中一个对Cache Line中的数据做了修改，另外一个CPU并不能察觉，还在使用旧的值进行操作，即不同核心的Cache出现了不一致。

CPU缓存一致性 Cache coherence

MESI

多个CPU是使用总线进行通信的，可以基于总线通信实现Cache的强一致性。目前使用较多的是MESI协议或一些优化协议。

基本思想是这样子的：

1. 当只有CPU0从内存加载某个Cache Line到Cache时，这个Cache Line是Exclusive状态；
2. 当这个Cache Line又被CPU1加载，更改状态为Shared；
3. 这时CPU0要修改Cachel Line中的某个变量， 就把状态改为Modified，并且Invalidate其他Cache中的这个Cache Line，其他的Cache再去读这个变量，达到一致。

Cache Line有4种不同的状态:

• 独占 Exclusive (E)：缓存行只在当前缓存中，但是干净的（clean）–缓存数据同于主存数据。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态。
• 共享 Shared (S)：缓存行也存在于其它缓存中且是干净的。缓存行可以在任意时刻抛弃。
• 已修改 Modified (M)：缓存行是脏的（dirty），与主存的值不同。如果别的CPU内核要读主存这块数据，该缓存行必须回写到主存，状态变为共享(S).
• 无效Invalid (I)：缓存行是无效的

MESI协议解决了多核环境内存多层级带来的问题，CPU核心对本地Cache的修改可以被其它核心观测到，使得 cache 层对于 CPU 来说是透明的。

MESI的不足及解决

性能下降

CPU修改Cache Line中的变量时，会通过总线发送Invalidate信息给远程CPU，等到远程CPU返回ACK，才能进行继续修改。如果远程的CPU比较繁忙，甚至会带来更大的延迟。

使用Store buffer

在CPU和L1Cache之间引入Store buffer来对写操作进行优化。写操作写到Store Buffer后就返回，等CPU的Invalidate消息返回后再异步写进Cache Line。对写操作有明显的优化，但也带来CPU内存一致性的问题（出现内存重排）。

CPU 从Cache中读取前都需要先扫描它自己的 Store buffer 来确认是否存在相同的 line，因为有可能当前 CPU 在这次操作之前曾经写入过 cache，但该数据还没有被刷入过 cache(之前的写操作还在 store buffer 中等待)。

注意，虽然 CPU 可以读取其之前写入到 本地Store buffer 中的值，但其它 CPU 并不能在该 CPU 将 Store buffer 中的内容 flush 到 Cache 之前看到这些值。即 Store buffer 是不能跨核心访问的，CPU 核心看不到其它核心的 Store buffer。

使用Invalidate queue

为了缓存Invalidation 消息，CPU 实现了 Invalidate queue。在Invalidate请求到达时，可以马上进行响应，但可以不马上处理，消息只是会被推进一个 invalidation 队列，并在之后尽快处理(但不是马上)。

因此CPU 可能并不知道在它 Cache 里的某个 Cache Line 是 Invalid 状态的，因为 Invalidation 队列包含有收到但还没有处理的 Invalidation 消息。CPU 在读取数据的时候，并不像 Store buffer 那样提取读取 Invalidate Queue。

False Sharing

由于CPU以64KB的Cache Line为最小单位从内存中加载数据，可能会出现这样的问题：

假设变量a和b位于同一个Cache Line中，当前CPU0和CPU1都将这个Cache Line加载到Cache，CPU0只修改变量a，CPU1只读取变量b。

当CPU0修改a时，CPU1的Cache Line会变为Invalid状态，即使CPU1并没有修改b，这会导致CPU1从内存中重新加载Cache Line中的所有变量，影响性能。这就是False Sharing。

字节填充

并发RMW操作不安全

MESI协议无法保证并发场景下RMW操作（Read-Modify-Write操作，如CAS/ADD等需要先读取再计算最后写回）的安全性。

例如两个线程都执行 i++。假如 i 的初值为 0，当 RMW 执行 Read 操作的时候，CPU0 cache 还是 Shared 状态，等到 CPU 修改了寄存器，寄存器需要写入到 cache 的时候，CPU1 已经完成写入操作，CPU0 cache 状态已经变成了 Invalid，需要重新从内存中加载Cache Line后继续写入。这时 CPU0 的 i 值 1 会覆盖掉 CPU1 的自增结果，导致两个 i++ 操作之后，结果还是 1。

使用LOCK前缀指令可以解决这个问题。

无法解决内存重排

内存重排

需要使用内存屏障 memory barrier解决。

LOCK前缀指令

X86 CPU 上具有锁定一个特定内存地址的能力，当这个特定内存地址被锁定后，就可以阻止通过系统总线读取或修改这个内存地址。这种能力需要显式在某些汇编指令上使用LOCK前缀获得。

当使用 LOCK 指令前缀时，它会使 CPU 宣告一个 LOCK# 信号，这样就能确保在多处理器系统或多线程竞争的环境下互斥地使用这个内存地址。指令执行完毕，锁自动释放。

支持使用LOCK前缀的指令有ADD/OR/AND/SUB/INC/NOT等，另外XCHG/XADD自带LOCK效果。

另外，Intel在原有总线锁的基础上做了一个很有意义的优化：如果要访问的内存区域在lock前缀指令执行期间已经在处理器内部的缓存中被锁定（即包含该内存区域的缓存行当前处于独占或以修改状态），并且该内存区域被完全包含在单个缓存行（cache line）中，那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定，其它处理器无法读/写该指令要访问的内存区域，因此能保证指令执行的原子性。这个操作过程叫做缓存锁定（cache locking），缓存锁定将大大降低lock前缀指令的执行开销。但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时，仍然会锁住总线。

假设两个CPU核心都持有相同的Cache Line，且各自状态为S, 这时如果要想执行 LOCK 指令，成功修改内存值，就首先需要把S转为E或者M, 则需要向其它核心 Invalidate 这个地址的Cache Line，则两个core都会向总线发出 Invalidate这个操作。总线会根据特定的设计协议仲裁是CPU0还是CPU1能赢得这个invalidate，胜者完成操作, 失败者需要接受结果并Invalidate自己对应的Cache Line，再读取胜者修改后的值继续执行。

通过LOCK前缀，可以使RMW类的操作具备原子性：

Unlocked increment:

1. Acquire cache line, shareable is fine. Read the value.
2. Add one to the read value.
3. Acquire cache line exclusive (if not already E or M) and lock it.
4. Write the new value to the cache line.
5. Change the cache line to modified and unlock it.

Locked increment:

1. Acquire cache line exclusive (if not already E or M) and lock it.
2. Read value.
3. Add one to it.
4. Write the new value to the cache line.
5. Change the cache line to modified and unlock it.

除此之外，LOCK指令还有禁止该指令与之前和之后的读和写指令重排序、把Store Buffer中的所有数据刷新到内存中的功能，是实现内存屏障的方式之一。

内存重排

下面两个goroutine执行时，会出现几种可能的结果：

var x, y int
go func() {
    x = 1 // A1
    fmt.Print("y:", y, " ") // A2
}()
go func() {
    y = 1                   // B1
    fmt.Print("x:", x, " ") // B2
}()

很显然的几种结果：

 

y:0 x:1
x:0 y:1
x:1 y:1
y:1 x:1

令人意外的结果：

x:0 y:0
y:0 x:0

出现这两种意外结果的原因就是内存重排 Memory Reordering。

编译器重排CPU重排

编译器重排

对于下面的代码片段

X = 0
for i in range(100):
    X = 1
    print X

编译器有可能优化为下面的样子

X = 1
for i in range(100):
    print X

单独看来这两种方式的执行结果是一样的。假如另一个CPU核心指令了这样的指

X = 0

上面两种情况的输出就不一样了。

甚至下面的代码，编译时也有可能交换对变量a和变量b的赋值顺序，导致结果不同

int a, b;
int foo()
{
    a = b + 1;
    b = 0;
    return 1;
}

编译器是有可能为了性能考虑修改赋值顺序的。在多核场景下，不能轻易判断两个程序是否等价。

CPU重排

由于CPU Store Buffer的存在，CPU0对一个变量的赋值操作可能无法被另一个核心观察到，造成出现上面内存重排的另外两种令人意外的结果。这是CPU重排现象的一种原因。

另外，CPU还有流水线、分支预测的特性，也有可能导致CPU重排。他们的目的都是最大化提高CPU利用率。

内存重排会导致并发程序在多核场景下出现意想不到的结果，这些是MESI协议解决不了的。需要使用内存屏障技术。

CPU内存一致性模型

CPU内存一致性模型讨论的是，在引入StoreBuffer等机制后，指令流的定义顺序与CPU实际执行顺序的一致性问题。

目前有多种内存一致性模型：

• 顺序存储模型SequentialConsistency
• 完全存储定序TotalStoreOrder
• 部分存储定序PartStoreOrder
• 宽松存储模型RelaxMemoryOrder

以下面的例子为例介绍这几种模型的处理方法

 

顺序存储模型SC

多核心会完全按照指令流的顺序执行代码。上面例子的执行顺序是

S1 S2 L1 L2

• C1与C2的指令虽然在不同的CORE上运行，但是C1发出来的访问指令是顺序的，同时C2的指令也是顺序的
• 虽然这两个线程跑在不同的CPU上，但是在顺序存储模型上，其访问行为与UP（单核）上是一致的 所以在顺序存储模型上是不会出现内存访问乱序的情况。

完全存储定序TSO

TSO会利用StoreBuffer提高CPU利用率，并且严格按照FIFO的顺序将StoreBuffer中的Cache Line写入主存。

S1：store flag= set
S2：load r1=data
S3：store b=set

在顺序存储模型中，S1肯定会比S2先执行。

但是加入了Store Buffer之后，S1将指令放到了Store Buffer后会立刻返回，这个时候会立刻执行S2。S2是read指令，CPU必须等到数据读取到r1后才会继续执行。这样很可能S1的store flag=set指令还在Store Buffer上，而S2的load指令可能已经执行完（特别是data在Cache上存在，而flag没在Cache中的时候。这个时候CPU往往会先执行S2减少等待时间）。

加入了store buffer之后，内存一致性模型就发生了改变。

完全存储定序TSO要求，严格按照FIFO的次序将数据发送到主存（先进入Store Buffer的指令数据必须先于后面的指令数据写到存储器中），这样S3必须要在S1之后执行。

Store-Load 乱序

部分存储定序PSO

地址相关指令

这里的地址相关指令，指多个指令操作的地址相同或者有前后关联。例子中L1和L2就是地址无关指令。

Store-Store乱序

S2 L1 L2 S1

由于S2可能会比S1先执行，从而会导致C2的r2寄存器获取到的data值为0。

宽松存储模型RMO

在PSO的模型的基础上，更进一步的放宽了内存一致性模型，不仅允许Store-Load，Store-Store乱序。还进一步允许Load-Load，Load-Store乱序。只要是地址无关的指令，在读写访问时都可以打乱所有Load/Store的顺序，这就是宽松内存模型（RMO）。

RMO内存模型里乱序出现的可能性会非常大，这是一种乱序随处可见的内存一致性模型。

内存屏障

芯片设计人员为了尽可能的榨取CPU的性能，引入了乱序的内存一致性模型，这些内存模型在多线程的情况下很可能引起软件逻辑问题。

顺序存储一致性模型

对于TSO和PSO模型，内存屏障只需要在Store-Load/Store-Store时需要（写内存屏障），最简单的一种方式就是内存屏障指令必须保证Store Buffer数据全部被清空的时候才继续往后面执行，这样就能保证其与SC模型的执行顺序一致。

而对于RMO，在PSO的基础上又引入了Load-Load与Load-Store乱序。RMO的读内存屏障就要保证前面的Load指令必须先于后面的Load/Store指令先执行，不允许将其访问提前执行。

memory barrier 是必须的。一个 Store Barrier 会把 Store Buffer flush 掉，确保所有的写操作都被应用到 CPU 的 Cache。一个 Read Barrier 会把 Invalidation Queue flush 掉，也就确保了其它 CPU 的写入对执行 flush 操作的当前这个 CPU 可见。

内存屏障类型

从上面来看，barrier 有四种:

• LoadLoad 阻止不相关的 Load 操作发生重排
• LoadStore 阻止 Store 被重排到 Load 之前
• StoreLoad 阻止 Load 被重排到 Store 之前
• StoreStore 阻止 Store 被重排到 Store 之前

内存屏障指令

Intel为此提供四种内存屏障指令：

• sfence ，实现Store Barrier。将Store Buffer中缓存的修改刷入L1 cache中，使得其他cpu核可以观察到这些修改，而且之后的写操作不会被调度到之前，即sfence之前的写操作一定在sfence完成且全局可见；
• lfence ，实现Load Barrier。 Flush Invalidate Queue，强制读取L1 cache，而且lfence之后的读操作不会被调度到之前，即lfence之前的读操作一定在lfence完成（并未规定全局可见性）；
• mfence ，实现Full Barrier。 同时刷新Store Buffer和Invalidate Queue，保证了mfence前后的读写操作的顺序，同时要求mfence之后的写操作结果全局可见之前，mfence之前的写操作结果全局可见；
• lock 用来修饰当前指令操作的内存只能由当前CPU使用，若指令不操作内存仍然有用，因为这个修饰会让指令操作本身原子化，而且自带Full Barrior效果；还有指令比如IO操作的指令、CHG等原子交换的指令，任何带有LOCK前缀的指令以及CPUID等指令都有内存屏障的作用。

X86-64下仅支持一种指令重排：Store-Load ，即读操作可能会重排到写操作前面，同时不同线程的写操作不保证全局可见，这个问题只能用mfence解决，不能靠组合sfence和lfence解决。

由此可见，LOCK指令即保证的RMW类操作的原子性，又有内存屏障的作用。

解决 cache coherence 的协议(MESI)并不能解决 CAS 类的问题。同时也解决不了 memory consistency，即不同内存地址读写的可见性问题，要解决 memory consistency 的问题，需要使用 memory barrier 之类的工具。

例子

var (
    lock     sync.Mutex
    instance *UserInfo
)

func getInstance() (*UserInfo, error) {
    if instance == nil {
        lock.Lock()
        defer lock.Unlock()
        if instance == nil {
            instance = &UserInfo{
                Name: "test",
            }
        }
    }
    return instance, nil
}

使用race检测，该代码第二个if处存在data race。

instance = &UserInfo{Name: "test"}

UserInfoName="test"instance

如果这个时候发生了乱序，可能会变成

UserInfoinstanceName="test"

if instance == nil

var flag uint32

func getInstance() (*UserInfo, error) {
   if atomic.LoadUint32(&flag) != 1 {
      lock.Lock()
      defer lock.Unlock()
      if instance == nil {
        // 其他初始化错误，如果有错误可以直接返回
 	instance = &UserInfo{
            Age: 18,
         }
         atomic.StoreUint32(&flag, 1)
      }
   }
   return instance, nil
}

atomic.Store

atomic.LoadUint32(&flag)

go run -race

附：true sharing带来的性能问题

golang目前有一个issue 17973 ，RWMutex的RLock方法在CPU核心数量变多时，性能下降严重

func (rw *RWMutex) RLock() {
    // ....
	if atomic.AddInt32(&rw.readerCount, 1) < 0 {
		// A writer is pending, wait for it.
		runtime_SemacquireMutex(&rw.readerSem, false)
	}

    // else 获取 RLock 成功
    // ....
}

原因在于对rw.readerCount变量的内存争用上。

在核心数增多时，单次atomic操作的成本上升，导致程序整体性能下降。

atomic.Add使用Lock指令构建内存屏障，同步刷新CPU Store Buffer防止出现CPU重排现象。超多核心场景下，MESI协议下某个核心等待其它CPU的操作响应，导致单个操作成本提高，影响多核性能。

参考链接