关于rust:Datenlord-Rust-无锁编程之Crossbeam-Epoch算法解析

作者 | 施继成

转自《Rust Magazine 中文精选》

上次的文章介绍了无锁数据结构的内存管理机制 EBR，该机制相较于其余的内存管理机制具备更高的执行效率。然而因为理念的复杂性，EBR 的实现并不容易，为每一个无锁数据结构从头实现 EBR 也无必要，因而很天然得大家会思考将 EBR 的核心理念 epoch 抽取进去变成库，让大家可能复用。Crossbeam-epoch 是一套成熟的被大家宽泛应用的 EBR 库，本文将从实现原理局部进行较为具体的解析，并且在此过程中进行。

Guard 只是最外层的壳

如前文所述，大家个别在和 Crossbeam-epoch 进行交互时仅仅应用 guard，如下所示：

/// delete data
{let guard = epoch::pin();
    guard.defer(move || mem.release());
}

/// get data for reading
{let guard = epoch::pin();
    let value = map.get(&key, &guard);
    /// ... Use the value
}

在读取数据的时候，guard 表演的角色仅仅是生命周期守护者，其确保获取进去的 data 援用（上述代码中的 value）生命周期肯定不长于 guard，当 guard 被销毁时，value 也肯定被销毁。删除数据过程中，guard 表演的角色要更简单一些，其负责将销毁函数注册到 defer 提早执行的队列中。至于该销毁函数何时被调用，则须要进一步深刻理解其外部实现细节。

Pin 到底做了什么

epoch::pin() 到底做了什么，官网的代码正文中给出了解释，行将以后的 thread pin 住，以便将堆上数据的指针放到栈上。该解释其实只解释了上述读取数据本分的内容，其底层执行的操作如下：

1. 将以后线程注册到 Global 收集器，该注册过程每个线程仅仅做一次。
2. 获取以后全局 Epoch 并设置到以后线程，示意在 pin 无效的这段时间，以后线程属于哪个 Epoch。
3. 记录以后线程曾经被 pin 的次数，当次数达到肯定数量，尝试让 Global 收集器推动 Epoch 增长，回收垃圾。
4. 减少 guard_count 计数，记录有多少 guard 被创立进去且还没有被销毁。

因为 pin() 能够重复调用，所以间断两次调用 epoch::pin() 也被容许。只是除了第一次调用，其余的调用都不会有任何作用，仅仅减少了 guard_count 计数。具体实现参见 internal.rs 文件中 Local struct 的 pin 办法。

这里提及的 Global 收集器负责所有资源的回收工作，其从各个线程收集须要回收的垃圾，并在适当的机会进行回收。

Epoch 推动

Epoch Number 须要不停向前迭代，在迭代的过程中，垃圾回收器将附属与老的 Epoch Number 的可回收垃圾回收掉。每次 Global 收集器想要回收垃圾时都会尝试推动 Epoch Number，满足下列条件则 Epoch Number 向前推动胜利：

1. 所有注册的线程都处于以后的 Epoch，即不存在线程处于上一个 Epoch。

如果条件不满足则 Epoch 推动失败。具体实现请参见 internal.rs 文件中 Global struct 的 try_advance 办法。

垃圾回收机制

如果所有的线程都将待回收的垃圾注册到 Global 收集器，那么会呈现十分微小的竞争关系，线程越多操作越频繁则性能影响越大。为了解决共享数据结构造成的竞争，每个线程都会保护本人的垃圾回收队列，队列长度为 62（神奇的 magic number，猜想和 CPU cache line 相干）。当队列被装满时，线程会将本地的队列中的数据对立挪动到到 Global 收集器，放到收集器的垃圾链表当中。这里值得注意的是，放入链表的除了垃圾回收函数，还有该垃圾产生的 Epoch Number，该数字被用于决定是否能够回收对应的垃圾。

垃圾回收的触发点有两个，一个被动一个被动。被动的触发点为 Guard 的 flush 办法，调用该办法则会使得 Global 收集器尝试收集垃圾链表中的垃圾。被动的触发点为 Guard 的 pin 办法，即 pin 每被调用 128 次会触发一次垃圾回收。

满足下列条件的垃圾能够被回收：

1. (Global Epoch Number) > ((Garbage Epoch Number) + 1)，即垃圾对应的 Epoch 至多比以后 Epoch 早两个世代。

具体实现请参见 internal.rs 文件中 Global struct 的 collect 办法。

外部数据结构

其外部数据结构值得一提有两个，一个 List，一个 Queue。List 被用于治理注册的线程，Queue 被用于治理期待被回收的垃圾。这两个数据结构的共同点是被多个线程同时操作，为了高效的实现，crossbeam 没有应用 Lock 来爱护数据结构，而是实现了外部的无锁数据结构。

List

List 有新元素插入方法，插入的办法就是将新元素插入到 List 的 head 地位，实现中应用了 CAS 原子操作。在多线程同时进行插入时，同一时间只有一个可能胜利，失败的操作会取得新的 header 值进行再次尝试。

List 删除操作并不真正移除元素，而是在该元素上进行标记，最初在某次 Iteration 过程中被真正删除，该删除操作也应用了 CAS 原子操作。如果有多个线程在尝试删除同一个元素，只有一个可能胜利。如果在删除某个元素时发现其前一个元素也被标记为可被删除，则告诉 Iteration 调用方须要重头再遍历一次。当然调用方能够依据状况重头遍历，还是留给其他人来解决。

具体实现请参见 list.rs 文件。

Queue

Queue 的插入和 List 相似，区别在于插入点为 tail。Queue 的删除操作叫做 pop，从 Queue 的 head 开始弹出数据，如果弹出数据出错则阐明有其余线程也在进行弹出操作，那么须要从新应用获取 head 的地位再次尝试。

那些从 List 和 Queue 中删除的元素如何解决呢？crossbeam 采纳了自举的办法，即也放入垃圾回收队列中，期待之后的某次操作触发垃圾回收。

总结

Crossbeam-epoch 给大家提供了一个极其不便的工具，将 epoch 的实现细节暗藏在库中，裸露给用户极其简略的接口，使得大家在实现无锁数据结构时更多关注数据结构的细节，将内存回收工作交给 Crossbeam-epoch 来解决即可。