Memory Order浅析（以LevelDB中的跳表为例）

零、引言

最近一直在看LevelDB， 里面的跳表的实现在某种意义上是LockFree的，利用CAS实现了更高效*以及高并发的内存数据结构。 具体的分析暂且不表，本文的目的在于解决一直没想明白的std::memory_order。当然也不仅限于c++中的概念，应该在别的语言也有类似的不同隔离程度的内存屏障原语。
通过本文可以： 1. 了解多线程中的一致性模型 2. 加深对于内存一致性模型的理解，以及平时该咋用 3：最后会通过LevelDB中的Skiplist的实例来分析为啥代码这么写

一、理论部分

一些简单的名词概念（狗都不看部分）

放在开头单纯方便下文中有不懂的地方可以Look Up

Program Order（程序次序）

对于单个线程上操作，对同一个对象，先写后读，如果其中没有别的写，则读必定能读到该次写入

这个定义看上去很trival，但是考虑到现代的CPU的乱序执行和编译器可能进行的指令重排，这一点其实对于程序的执行的正确性是最大的保证

Sequential Consistence(顺序一致性)

这玩意的定义不同的地方有不同的定义，我给出一个我倾向的比较好懂的、形式化的定义：

对于一个执行历史，存在一个等价的 历史，其满足： 1.对于这次执行的结果是满足程序次序的* 2. 并且该历史是合法的**

这里的定义很多，我依次给出他们的解释。当然如果形式化的定义不好理解，我后面也有对应的例子

  • 等价的: 涉及到的指令完全相同。 也就是我们可以随意进行指令重排
  • 合法的:这一点是顺序一执行的关键, 该历史中涉及的所有共享对象的读写是满足一致的，即满足写后紧接着的读都能读到最新的写入

下面给出几个例子：

H为执行的历史， P、Q分别为两个CPU。x为涉及的对象，初始值为0

首先明确一点，我们的定义不仅针对每一个原子的读、写操作，因此一般而言我们可以将一个操作分为invocation阶段和response阶段。

  • H = P write(x,1), Q read(x), Q ok(0), P ok()
  • H = P write(x,1) , P ok(), Q read(x), Q ok(0)
  • H = P write(x,1), Q read(x), P ok(), Q ok(0), P read(x), P ok(0)
  • H = P write(x,1), Q read(x), P ok(), Q ok(2)

Sequential Consistency

其中1 2是顺序一致的，3 4不是。具体验证的方法可以如同图中找到一条连线串起来所有的相同对象的读写操作，并且观察是否符合程序次序和合法性。

关于内存一致性(Coherent)

下述文字摘自wiki百科，经过个人的翻译。 以及部分来自于知乎用户 【Furion W】的回答

1.在处理器 P 对位置 X 的读取中，在同一处理器 P 对 X 的写入之后，在 P 的写入和读取指令之间没有另一个处理器对 X 的写入，X 必须始终返回值P写的

  • 条件1要求系统提供我们在单处理器中已熟知的程序次序(program order)。
  1. 在处理器 P1 对位置 X 的读取中，在另一个处理器 P2 对 X 的写入之后，在两次访问之间没有任何处理器对 X 进行的其他写入，并且读取和写入充分分离，X 必须始终返回 P2 写入的值。
  • 条件2要求写结果「最终」对别的处理器可见。
  1. 必须对相同位置的写入进行排序。换句话说，如果位置 X 接收到两个不同的值 A 和 B，按此顺序，从任何两个处理器，处理器永远不能将位置 X 读取为 B，然后将其读取为 A。位置 X 必须看到具有值 A 和B 按此顺序。举个例子，如果值 1 先被写入，值 2 后被写入，那么处理器不能先读到值 2, 然后再读到值 1.
  • 性质3要求系统提供写[串行化](write serialization). 若这一性质不被满足，程序错误可能会被引发：考虑 P1 先写 P2 后写的情况，如果存在一些处理器先看到P2的写结果，后看到 P1 的值，那么这个处理器将无限期地保持P1写入的值。

虽然上述性质可以充分保证系统[coherence]的达成，但它仍然未对写操作何时对读操作可见进行描述：考虑P1先写P2后读的情况，如果写读操作间隔很短，P2可能无法获得P1写入的值。

二、std::memory_order

在c++标准库中，一共定义了6个不同的内存次序，他们分别为

std::memory_order_relaxed, std::memory_order_consume, std::memory_order_acquire,std::memory_order_release, std::memory_order_acq_rel,std::memory_order_seq_cst

虽然共有 6 个选项,但它们表示的是三种内存模型:

  • sequential consistent(memory_order_seq_cst),
  • relaxed(memory_order_relaxed).
  • acquire release(memory_order_consume, memory_order_acquire, memory_order_release, memory_order_acq_rel),

接下来，我们会从宽松到严格依次阐述含义：

memory_order_relaxed

如同名称所描述的一样，这是最「宽松」的内存序。具体的体现在

  • 只保证了当前线程上的程序次序——保证能读到最新的写，但是对其余的指令重排并不做额外保证
  • 用另一句话说，多线程环境下并不能保证多线程中的synchronized-with关系
  • 还是用一个例子来说明
1
2
3
4
5
6
/ Thread 1:
r1 = y.load(std::memory_order_relaxed); // A
x.store(r1, std::memory_order_relaxed); // B
// Thread 2:
r2 = x.load(std::memory_order_relaxed); // C 
y.store(42, std::memory_order_relaxed); // D

在relaxed的语义下，这行代码「有可能」产生 r1 = r2 = 42的结果，因为CPU的乱序执行顺序有可能为 D -> C -> A -> B （仅仅是偏序关系中的一种可能结果，因为两个CPU执行时间其实是会Overlap的）

那我们该何时用这个关系呢？

结合上std::atomic， memory_order_relaxed保证了读、写的原子性，当我们希望仅仅对某一个变量进行「原子」的更新并且对其上下文涉及到的对其余变量的副作用不关心时就可以用这个关系。 因为其最大限度的保证了编译器的优化空间。 然后题外话：俺们组的Cpp标准是必须用memory_order_relaxed，目的应该是不影响性能，但是不确定会不会有奇奇怪怪的后果产生…

memory_order_release & memory_order_acquire

其实acquire & release是定义了第二种内存模型，也正如开头提到的，它有着「更强」的一致性。具体体现在其对于副作用的「可见性」上。

不同于relaxed次序，release和acquire的关系更像一个mutex，而它们的名字也暗示了这个关系，随后甚至可以以后的例子中附上一个用atomic以及release-acuquire关系实现自旋锁的一个例子【挖个坑】。

一般的，我们在写入的时候使用release, 在读取的时候使用acquire

  • release：在保证了单线程的程序次序的基础上，与acquire同步 保证了happened-before关系——即保证了在执行完带有release的写操作之后，该语义保证了在此原子存储之前的所有写入，在多线程环境下是可见的。
  • Acquire ：synchronized-with release，保证了在读取到release的值后，当前线程所有的读取都能读到release之前的所有写（或者最新的写）
  • 例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int data;
std::atomic<std::string*> ptr;

void producer(){
    std::string* p  = new std::string("Hello");
    assert(data != 42); // probably fires
    ptr.store(p, std::memory_order_release);
}
 
void consumer(){
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_acquire)))
        ;
    data = 42;
    assert(*p2 == "Hello"); // never fires
}

那我们该何时用这个关系呢？

release-acquire关系在一定程度上获得了更强的一致性，而带来的后果则是编译器一定的优化损耗、一定程度上的缓存失效——强制去内存中读取最新的值。

实际上release-acquire还有更多的传递性的特性，但是碍于本文的篇幅以及本人的能力这里就先不提了。

memory_order_seq_cst

有了前面两个的铺垫，顺序一致的内存序就很好理解的，无非是更强的读写一致性。而实现上，参考sequential consistency的定义，需要保证对象的全局合法性，因此我们需要在store的时候阻止先前的读写重排到该指令之后， 在load的时候阻止之后的读写重排到之前。

三、LevelDB中的跳表

如果事先对跳表的概念不熟悉，可以自行参考 Wiki

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);

  // Our data structure does not allow duplicate insertion
  assert(x == nullptr || !Equal(key, x->key));

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (nullptr), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since nullptr sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.store(height, std::memory_order_relaxed);
  }

  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    // NoBarrier_SetNext() suffices since we will add a barrier when
    // we publish a pointer to "x" in prev[i].
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
                                              Node** prev) const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != nullptr) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}
// Accessors/mutators for links.  Wrapped in methods so we can
// add the appropriate barriers as necessary.
Node* Next(int n) {
    assert(n >= 0);
    // Use an 'acquire load' so that we observe a fully initialized
    // version of the returned Node.
    // acquire的语义可以保证当SetNext执行完毕之后, Next永远可以见到原子的新的
    // next_[n]
    return next_[n].load(std::memory_order_acquire);
}
void SetNext(int n, Node* x) {
    assert(n >= 0);
    // Use a 'release store' so that anybody who reads through this
    // pointer observes a fully initialized version of the inserted node.
    next_[n].store(x, std::memory_order_release);
}

// No-barrier variants that can be safely used in a few locations.
Node* NoBarrier_Next(int n) {
    assert(n >= 0);
    return next_[n].load(std::memory_order_relaxed);
}
void NoBarrier_SetNext(int n, Node* x) {
    assert(n >= 0);
    next_[n].store(x, std::memory_order_relaxed);
}

这里我们需要分析的是下面四个辅助函数中不同的内存序的选择对实现跳表的multithread-safety的作用。

实现跳表lock free的关键

我认为这里可以无锁进行读写的关键点在于读的时候是从上往下的， 而写的时候是从下往上的。这样确保了一点，在保证先前的写都能被concurrent-reader读到的情况下，上层的Node被读到了，就能保证下层的相同Node一定也存在跳表中。 确保这一点的就是release-acquire内存序！

  • 在SetNext中的next_[n].store(x, std::memory_order_release) 保证了第30行中x的next指针的可见性
  • 在Next中的next_[n].load(std::memory_order_acquire)保证了若读到最新的next_[n]，则能看到先前调用的NoBarrier_SetNext的结果。

关于max_height_ 的更新

注意到在上述代码的23行中，我们是先更新了max_height_，再更新的Node。 有人可能会担心（比如我），这样难道不会导致读写不一致的情况出现吗？ 但我要说的是，其实并不会。因为Level DB实现的是对外顺序一致性。

而具体的分析思路如下（仅对skiplist而言）：

因为下面atomic store的原子性, 所以一个并发执行的读者在看max_height_的时候只有
1: 得到旧值, 此时读者「有可能」会读到新的Node,取决于SetNext有没有执行，只要执行了一次

即，设置了最小level的那层，就能够查到最新的数据
2: 得到新值，如果没有执行下面的Set，则会直接jump到下一层。 如果设置了值，则能够找到
期望的Node