《BzTree》解读(2)

“《BzTree》解读(1)”,上一篇讲到了叶子节点的删除操作,下面从更新操作继续讲。

叶子节点的操作

更新操作

针对于存放的记录是指针还是Inline payloads,会有不同的方法,Paper里面没有说这两种payload是如何来区分的,看起来对于某一个Node,里面的记录要么是Pointer,要么是Inline payloads

更新的记录是指针

需要读到对应的Record metadata entry,确保没有被删除掉;还要读到Status word,确保Node不是frozen状态的。那么就需要执行一个包含三个wordPMwCAS操作:

  • Record storage block中的指针的修改
  • Record metadata entry,防止有并发的删除
  • Status word,防止有并发的对frozen的操作

更新的记录是Inline payloads

对于inline存放的记录,和insert一样,需要预留空间,然后写入一个update_payload,这个update_payload可以是一个完整的payload,也可以是一个差值对于一个Node,相同的key可能会有多个值存放,那么查找一个key,基本上需要把unsorted key space遍历一遍了。需要关注一下读的Benchmark的数据。

还有一个Upsert操作,Paper里面提得比较少,如果存在就是Update,如果不存在就是Insert

读操作

找到对应的叶子节点后,也分两种情况:如果是Pointers,首先对sorted key space做二分的查找(如果key不存在或者被删除了),然后对unsorted key space做顺序的扫描;如果是Inline payload,先对unsorted key space做从后向前的扫描,再对sorted key space做二分的查找。

读只会返回它在叶子节点中找到的最新的记录(也就是说不支持MVCC),会忽略Nodefrozen状态,也会忽略Record metadata entryvisible被重置的节点。

顺序扫描

语义和leveldb中是一样的,通过begin_key找到叶子节点,进行到一个叶子节点的时候,迭代器会构造出response array,把valid的节点排序好(这个和Pena目前的做法是一样的)。把叶子节点的快照拷贝出来之后,迭代器就会退出它的epoch,这样就不会阻塞住memory garbage collection了。找下一个叶子节点的时候,会从树的根再找一次(这样操作起来的效率可能比较低,需要去看一看rangeBenchmark)。

节点重组

前面可以看到叶子节点内会有未排序的部分,也会有逻辑删除的部分,这样会影响查找的效率。节点重组可能由两个条件来触发:

  • Free space的空间达到阈值。这个空间可能通过Node SizeRecord CountBlock Size计算得到。
  • Delete size达到阈值。

当需要对节点N进行重组时,首先需要执行PMwCAS操作,这个操作只包括一个word(虽然只包含了一个word,但是依然需要执行PMwCAS,和其它操作遵循一样的规则):

  • Status word,设置节点的frozen状态

操作步骤如下:

A. 首先需要遍历节点N中所有有效的记录,计算出他们的总大小
B. 分配一个新的节点N',配备上一些Free space,将节点N中所有的记录拷贝到节点N'
C.节点N'可见需要替换节点N的父节点节点P中对应的指针(节点P 位置可以在查询 过程中保存下来),如果节点P已经是frozen的了,那么需要从根节点重新找下来
D. 替换节点P中对应的指针需要一个PMwCAS操作,这个操作会涉及到两个word

  • 替换节点P节点N对应的指针,对于内部节点而言,记录都是pointer,不会是inline payloads
  • 设置节点PStatus word,避免有并发的frozen

重组过程中的并发

这里有点意思了,前面提到了线程在执行更新时如果遇到frozen状态的叶子节点,会尝试找到新的叶子节点,这时候如果再次命中frozen的叶子节点的时候,这个线程会尝试自己来做重组的操作,最终只有一个会成功。虽说如此,但是从整体来看,节点重组的操作还是会对更新有阻塞的效果。

前面讲到了,在有节点的分裂和合并时,内部节点都会生成新的拷贝,以Copy-on-Write的方式进行更新。

分裂和合并

BzTree把此类操作称之为structure modification operations(SMOs)SMOs操作的优先级要比单记录的操作优先级要高,只会由更新的线程来执行,读线程是不会触发的。

节点分裂

节点分裂分成两阶段:第一阶段会准备SMOs操作需要的空间;第二阶段会把新的节点加入到索引当中。

Preparation

这一阶段,首先调用PMwCAS设置节点Nfrozen标志。然后新建3个节点,其中原来的节点N分裂成节点N'节点O节点P'是在节点P 的基础上去掉节点N,加上节点N'节点O

Installation

第二阶段,需要在节点G使用节点P'来替换节点P。这里需要执行PMwCAS,涉及到3个word

  • 设置 节点Pfrozen标志
  • 节点G替换节点P的指针为节点P'
  • 设置节点GStatus word,避免有并发的frozen

节点合并

如果需要删除节点N,首先需要找到它的一个兄弟节点来吸收节点N剩下的记录。 首先会先尝试使用节点N的左兄弟节点节点L节点L需要和节点N属于同一个父节点之下,然后也需要足够小;如果不行,就尝试右兄弟节点。如果满足不了条件,就先不干了。

和分裂类似,合并也分为两阶段,看图,这里就不赘述了。

最后

到这里,BzTree的所有相关操作都介绍完了。基于NVMlock-free的数据结构,之前有NVC-Hashmap,但是基于Btree还是头一回见。当然,这和微软之前在BwTree上的积累还是有很大的关系的。

这篇Paper除了整体问题的解决上很有意思,而且引入PMwCAS这一点也很厉害,极大地简化了模型。从Paper的描述上来看,性能比BwTree还要好,而且维护成本也会低很多。

PMwCAS、还有BzTree的节点操作都有cooperative的思想在里面,和之前线程阻塞等待某些操作完成不同,这些被blocked的线程会尝试自己来完成这些工作,这个在之前backgroud里面是很难去理解的,会直观地觉得除了浪费计算资源外,不会有效率上的提升,但是从测试结果上来看,BzTree的性能非常优异。