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

然而，UD操作发生在复制阶段之后(例如update(8,y)， delete(3))仍然可能丢失。为避免丢失更新异常，UD操作需要调用写时同步(sync-on-write)方法主动同步修改。通过写时同步和三阶段SMO，我们确保NBTree在崩溃后始终保持一致的状态，包括所有提交的操作。正如我们前面提到的，SMO的持久性点是在链接阶段，当新的叶子节点通过将自己链接到键值层来替换PM中的旧叶子节点时。如果崩溃发生在持久性点之前，旧的叶子节点将保留在键值层。在SMO期间，任何修改都必须首先对旧的叶子节点进行操作。因此，如表3所示，在SMO期间，老叶节点始终保存最新提交和未提交的操作。旧的叶子节点中未提交的操作不会导致不一致，因为在丢弃新的叶子节点后，战斗中的写时同步是不必要的。如果在持久性点之后发生崩溃，新的叶子节点将链接到键值层。
此时，在copy阶段提交的所有UD操作都已经同步到sync阶段的新叶子节点。对于发生在复制阶段之后的UD操作，它们只在写入到新的叶子节点时才被提交。因此，新的叶子会在持久性点之后保存最新提交的操作。此外，在eADR的支持下，新的leaf保持了一致性，因为写时同步是原子的。总而言之，每当崩溃发生时，具有最新提交操作的一致的leaf将继续存在。SMO线程(sync阶段)和UD线程(sync-on-write阶段)可以同时将相同的值同步到新的叶子进程中。NBTree可以使用每个条目值的最高两位来序列化这些同步。

Sync-on-read.为了处理可能存在的旧叶子节点和新叶子节点之间的不一致，查找操作采用读时同步(sync-on-read)的方法将对应的键值从旧叶子节点同步到新叶子节点。具体来说，NBTree同时在新叶节点和旧叶节点中搜索目标键。如果返回的结果不同，搜索操作会更新或删除新叶子节点中的键值，以匹配旧叶子节点中的键值。读时同步的开销与写时同步的开销一样低。读时同步(Sync-on-read)保证无锁的并发搜索返回键值项的最新版本。在SMO的同步阶段，如果不执行读时同步操作，从旧或新叶子节点读取数据都可能导致旧读或脏读异常。如表3所示，在同步阶段，old leaf可能是脏的，因为正在进行的写时同步可能没有提交UD操作。同时，由于SMO线程可能还没有完成复制阶段中发生的最新修改的同步，因此新的叶子可能已经过时。
为了解决这个问题，搜索操作使用读时同步(sync-on-read)将最新的键值从旧的叶子节点同步到新的叶子节点。它确保新的叶子节点中的目标键值对既最新又干净，然后返回搜索结果。不在同步阶段的叶子节点上的搜索操作可以直接读取正确的值，而无需调用sync-on-read方法。表3显示了读取的目标，它是一个叶子节点，其中保存了最新的和干净的键值对。在复制阶段，传入的读取转到旧的叶子节点，它既是最新的也是干净的，因为并发的UD操作直接在复制阶段提交。在同步阶段之后，读取转到新的叶子节点。这是因为之前在复制阶段发生的UD操作已经同步到新的叶子节点，而之后的UD操作一旦在eADR支持的新叶子节点中可见，就会提交。