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

UDS-UDS Conflicts.在启用eADR的PM系统中，NBTree中的UDS-UDS冲突可以在不增加额外开销的情况下得到解决。如上所述，更新和删除是原子完成的，不会暴露中间状态。使用eADR，这些修改被原子地持久化。因此，提交的顺序以及并发更新和删除的可见性始终保持不变，搜索操作始终读取最新提交的数据。此外，UDS的操作不会被其他线程放弃，这极大地提高了NBTree在高竞争负载下的可扩展性。
4.2 Structural Modifcation Operations 当一个keyvalue数据项插入到一个完整的叶子节点中时，就会发起结构修改操作(Structural modification operations, SMOs)。SMO的传统过程是将完整的老叶结点中的条目复制到新分配的叶子结点中，然后用新的叶子结点替换旧的叶子结点。然而，由于复制阶段不能原子完成，对旧叶子节点的无锁并发修改可能不会同步到新的叶子节点，从而导致丢失更新异常。此外，由于旧的叶子节点和新的叶子节点之间的不一致，无锁搜索可能会读取脏的或过期的数据。表1显示了NBTree用于解决潜在异常并促进无锁访问的方法。在NBTree中，SMO被划分为3个阶段(复制阶段、同步阶段和链接阶段)。在每个阶段，使用不同的方法来处理SMO叶子上的并发操作。

对于UD (update/delete)操作，NBTree通过SMO的同步阶段和写时同步技术解决丢失更新异常。对于搜索操作，NBTree使用读时同步(sync-on-read)来防止脏读和陈旧读异常。本文还提出了协作式SMO，使并发插入能够协作地完成SMO。
表1 The approaches employed during diferent phases of SMO to facilitate lock-free leaf node operations.
Three-phase SMO.与传统的B -树SMO仅包含复制阶段和链接阶段不同，NBTree增加了一个同步阶段，以避免复制阶段的UD操作导致的丢失更新异常。下面，我们将描述每个阶段的过程。在复制阶段，SMO将整个叶子节点中键为非零的有效数据项复制到新的叶子节点中。如图3所示，如果有效条目的数量超过某个阈值(默认情况下是叶节点容量的一半)，NBTree会分配两个新的叶节点。否则，只分配一个新的叶子节点。然后，NBTree将键值对分发到新的叶子节点并构建它们的元数据层;最后，NBTree将旧叶子节点中的copy_ptr设置为表示第一个新叶子节点的地址。在sync阶段，NBTree将丢失的UD操作同步到新的叶子节点。在复制阶段，并发的UD操作仍然写入旧的叶子节点。由于复制阶段不能在原子指令中完成，因此那些UD操作，例如图3中的Update(2,s)，可能还没有迁移到新的叶子节点。