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

因此，在同步阶段，NBTree利用ca将错过的UD操作同步到新的叶子节点。链接阶段用新的叶子节点替换NBTree中的旧叶子节点。NBTree首先通过改变前一个叶子节点的next指针，将新的叶子节点链接到keyvalue层和元数据层的单链表中。然后，NBTree将新的叶子节点安装到父节点。
Sync-on-write.在SMO复制后阶段，UD操作采用一种写时同步(sync-on-write)的方法来解决丢失更新异常，该方法主动地将旧叶子节点的修改同步到新叶子节点。具体来说，对于更新，在修改了旧叶子节点中的键值后，它会在新的叶子节点中重新搜索目标键。如果新的分支中对应的值不是最新的，NBTree会使用CAS将最新的更新同步到新的分支中。在eADR的支持下，ca可以原子性地修改和持久化同步。与更新操作类似，如果新的叶子节点包含目标键，删除操作也会在新的叶子节点中重新执行。NBTree对写时同步的开销很低，因为它只在新的叶子节点上进行一次额外的搜索和一个CAS原语。在SMO复制后阶段，写时同步(sync-on-write)可以防止无锁的UD操作遭受丢失更新异常。如图3所示，在复制阶段，发生在旧叶子节点上的任何UD操作(例如update(2,s))将在SMO的sync阶段同步到新的叶子节点。