NBTree: a Lock-free PM-friendly Persistent B -Tree for eADR-enab(4)

启用了eaddr的PM系统预留了更多的能量，使它们能够在断电后将CPU缓存中的数据推送到PM，从而将持久性域扩展到包括CPU缓存。与ADR相比，eADR具有以下优点。第一个是减少PM写开销。使用eADR，不再需要同步的ush指令，从两个方面降低了PM写开销。(1)减少关键路径上的延迟。在此之前，fush指令和内存屏障导致了关键路径的高延迟。(2)节省PM写带宽。延迟写PM会增加CPU缓存中的写命中率和写合并，从而减少PM写。第二个是促进无锁设计。eADR支持数据结构的原子性修改和持久化，为PM的无锁设计提供了便利。大多数无锁数据结构依赖于原子CPU硬件原语，例如CAS。然而，在基于adr的PM系统中，这些原语可以原子性地修改数据，但不能确保它们的持久性，因为CPU缓存是不稳定的。线程很可能读取CPU高速缓存中的未持久化数据，从而导致脏读异常。
使用eADR，可以确保CPU缓存中全局可见的数据被持久化。因此，可以原子地修改和持久化数据。

2.2 The Design Challenges of Lock-free Persistent Data Structures 在PM中设计无锁数据结构(LFD)并非易事，因为它们不仅需要处理微妙的竞态条件(如易失性索引)，还需要确保写入在任何依赖的读取之前被持久化。以下两个硬件限制使我们无法在PM中设计高效的lfd。(1)内存加载和存储的原子性粒度为1个字，即8个字节。许多lfd中使用的原子性CPU硬件原语，例如比较与交换(compare-and-swap, CAS)，只能原子性地修改一个字。然而，在非平凡的数据结构中，一个操作需要读写多个单词。因此，lfd很可能将中间状态暴露给并发线程。此外，当一个线程正在执行一个操作时，数据结构可能会被其他线程更改。这些问题可能会导致更新丢失、读取过期和读取不一致等异常。
(2)基于adr的PM系统不支持原子原语对数据进行修改和持久化。更新首先被发送到CPU缓存，然后使用fush指令和内存屏障进行持久化。由于CPU缓存中的全局可见数据是不稳定的，其他线程很容易读取非持久化数据，从而导致脏读异常。在下面的例子中，我们将使用持久化的B -树来指定上述异常是如何发生的。