关于rust:Datenlord-Rust-语言无锁数据结构的内存管理

119次阅读

共计 2710 个字符，预计需要花费 7 分钟才能阅读完成。

正如大家所熟知的，无锁数据结构在并发拜访中往往具备更好的拜访效率和并发度。无锁数据结构的性能劣势次要来自于以下两点：

1、数据结构的锁设计往往比拟粗粒度，在很多能够并发拜访的状况下，访问者被锁阻塞，无奈实现并发拜访。

2、无锁数据结构拜访不须要进行上下文切换，有锁数据结构在并发度高的时候往往会触发操作系统上下文切换。

然而无锁数据结构也带来了新的问题，即内存治理问题。举个例子：当线程 A 读取一块数据的时候，线程 B 要开释该数据块。在有锁数据结构中，这两个操作被串行了起来；无锁数据结构因为不足锁的爱护，这两个操作可能同时进行。为了保障线程 A 拜访数据的正确性，线程 B 的开释操作必须要延后执行，直到 A 实现了读取操作。为了达到上述延后开释内存的目标，大家个别采纳下列的几种办法：

1、语言自身的 GC 反对，如带有虚拟机 runtime 的语言，如 Java。
2、援用计数（Reference Count)。
3、基于代际的内存开释机制（Epoch-Based Reclamation)，本文之后简称 EBR。

语言自身的 GC 机制一方面有语言的限度，另外一方面全局的 GC 往往会造成肯定的性能损失，程序执行 Latency 不稳固。援用计数自身的性能开销不可漠视，特地是在读取操作较多的场景下，仅仅为了爱护数据安全，每次读取都须要进行计数减少，读完了再进行计数缩小，高并发的状况下效率不乐观。EBR 则躲避了上述问题，一方面不须要语言层面的规约，另外一方面执行效率也绝对更好。这里为大家简略介绍一下 EBR, 更加具体的解释请参见论文《Practical lock-freedom》。

在 EBR 的概念中有代际（Epoch）的概念，Epoch 为数字，其代表了以后处于第几世代，该数字枯燥递增。全局具备一个 Global Epoch, 代表全局以后是第几世代。每个线程的每次数据结构的拜访都蕴含一个 Epoch，即 Local Epoch，示意以后线程处在第几代。有了这些概念咱们来看一下上面的例子，就可能了解 EBR 的工作原理了。

如下图中的例子，线程 A 和 B 并发地拜访无锁数据中的内存块，自上而下为工夫的流逝方向。在工夫点 1 之前 Global Epoch 为 0。

工夫节点 1：线程 A 发现没有其余线程正在发给拜访该数据结构，将 Global Epoch 加 1，变成 1。同时线程 A Local Epoch 设置为 1.

工夫节点 2：线程 B 删除数据块 M，因为 B 发现只有线程 A 在拜访数据结构，且 A 的 Epoch 和 Global Epoch 相等，都是 1。线程 B 将 Global Epoch 再加 1，变成 2。B 线程 Local Epoch 和 Global Epoch 同步，也为 2. 因为 Epoch 的删除操作是延后的，须要放到一个收集器里，于是数据块 M 被放到收集器中，标记为 Epoch 1，意味着这个数据只有可能在 Epoch 1 中被应用，从 Epoch 2 开始数据结构中在没有数据块 M（被线程 B 删除）。

工夫节点 3：线程 B 拜访数据块 N，发现 Global Epoch 为 2，线程 A 的 Epoch 为 1，则 B 标记本人的 Local Epoch 为 2，与 Global Epoch 统一。

工夫节点 4 和 5：线程 A 和 B 都示意本人曾经完结了数据拜访，不再被数据结构追溯。

工夫节点 6：线程 A 也开始拜访数据块 N，以后 Global Epoch 为 2，且没有其余线程拜访该数据块，则线程 A 减少 Global Epoch 到 3，标记本人 Local Epoch 为 3。同时线程 A 发现收集器中有一个 Epoch 为 1 的数据块 M，比以后 Global Epoch 相差了两个世代，能够被删除，数据块 M 被开释。

工夫节点 7：线程 A 示意本人完结了数据拜访，不再被数据结构追溯。

通过下面的例子咱们不难发现，被拜访的数据只可能存在于两个 Epoch 中，一个为以后 Epoch，即 Global Epoch，另一个为前一个 Epoch，即（Global Epoch – 1）。所有被标记了更早 Epoch 的数据都能够被删除，即收集器中被标记为小于（Global Epoch – 1）的数据块。

剖析一下 EBR 的算法，咱们可能发现其性能优越性的根本原因在于数据回收的粗粒度治理。在 Reference Count 的办法中，并发度越高，对 Counter 的批改就越密集，竞争越大，性能越差。在 EBR 中，并发度高会造成简直所有线程都处于一个 Epoch，并不需要对 Global Epoch 进行批改，也就防止了这方面的竞争，性能也就更好。当然 EBR 也存在其本身的问题，当某些起因导致一个拜访操作无奈完结时，则 Global Epoch 永远无奈向前推动，也就永远无奈触发垃圾回收，内存泄露就不可避免了。

综上所述，即便存在一些缺点，EBR 极好的性能劣势使其成为了高性能无锁数据结构实现的首选。

通过上述对 EBR 的剖析，咱们不难看出，EBR 须要晓得数据拜访起始点，配合起始点管制 Epoch 的迭代。其余语言有本人的封装和实现办法，而 Rust 的生命周期的概念则从语言层面提供了帮忙。基于这个劣势，Rust 语言天生适宜实现 EBR，并且曾经有了一个成熟的实现版本，即 crossbeam epoch。这里不会对该实现做源码级的剖析，而是会尝试将框架 API 和 EBR 的相干概念进行对应，帮忙大家了解。这里是示范代码，是无锁数据结构应用 epoch 最简略的办法：

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

第一行示意以后线程开始拜访拜访该数据结构，可能是读取可能是写入。第二行示意，提早开释一块内存，具体何时开释，由 EBR 算法来决定。当整个代码块执行实现，示意退出数据结构拜访，guard 的 drop 办法会将以后线程从监测的队列中登记。
再例如，Datenlord 中实现和应用的无锁 Hashmap, cuckoohash，其接口为:

{let guard = pin();
    let value = map.get(&key, &guard);
    /// ... Use the value
}

第一行和后面的例子相似，第二行的语义为从 map 中寻找 key 对应的 value，获取 value 的援用，其生命周期不超过 guard 的生命周期。通过生命周期的办法，咱们限定了 value 援用的应用范畴为 guard 的存活范畴。

本文简略介绍了 Epoch-Based Reclamation 内存治理办法，并且从接口层面介绍了 Rust 的实现和应用。同时本文也剖析了 EBR 在性能上的优越性，以及 Rust 语言从语言实现的劣势。之后咱们还会从 crossbeam epoch 的实现细节给大家带来深刻的 Rust EBR 实现的剖析。

正文完