《BzTree》解读(1)

BzTree这篇Paper开头一部分介绍了PMwCAS,这部分的内容有些难以理解,中间这部分介绍了和B-tree相关的数据结构。

节点的布局

Node既包含了Leaf Node,也包含了Internal Node,当然,这两者的布局有些细节上是不同的。

这里相对枯燥一点,比较有意思的是下一部分讲节点操作的部分,当然,这里是理解下一部分的基础。

整体布局

大体来说,节点包含了四部分内容:

  • Header,节点相关的一些元信息,Header本身是定长的,占用了128 bytes
  • Record metadata array,里面包含了很多Record metadata entry,每一个entry代表一个记录,从上向下增长的
  • Free space,空闲的空间,除去其它三个部分的空间。
  • Record storage block,记录存储块,真正存放记录的地方,从下往上增长的

各部分的详细布局

Header的布局,这里Status Word的含义还没有讲具体的应用。

HeaderStatus word的布局,这里的Control可以参考之前对PMwCAS介绍,表示RDCSSPMwCASDirty,所以刚好是3位Frozen需要看后面的内容才能理解具体的含义。

Record metadata entry的布局,和Status word类似,Control也是用于PMwCAS控制的,Visible需要看后面的内容理解具体的含义。和Status Word一样,Record metadata entry的大小是64 bytes,刚好是一个word。这里面的Offset是相对于Node开始的偏移,所以一个Node的大小上限看起来是64M

Ok,基本的数据结构布局了解了,下面就会讲在操作的时候,是如何利用Node中的各个字段,以及和PMwCAS的结合来让BzTree成为一个无锁的Btree的。

这里先提一下叶子和中间节点的区别:中间节点的Status word中是没有Block SizeDelete Size的,原因是中间节点是immutable的,而叶子节点不是。中间节点只存放有序的key,不包含free space;叶子节点,包含了free space来缓存插入(如果叶子节点直接存放了记录的payload,也会更新)。这就意味着叶子节点即包含了有序的记录,也包含了无序的记录。采用这种方法的原因是,大量的修改操作在发生在叶子节点的,所以叶子节点快速地in-place保存记录的更新非常重要。另外,中间节点读多写少,所以全量的更新是可以容忍的。

叶子节点的操作

这里会描述如何对叶子节点进行无锁的读写。对于写,基本思想是借助PMwCAS来原子地操作节点和记录的元数据,包括为写入的数据预留空间和让写入的记录对其它线程可见。读的话,不会被写操作block住。

插入操作

操作步骤

首先会通过LeafSearch之类的方法找到对应的叶子节点,对叶子节点的操作如下:

A. 检查Status word中的frozen,如果被设置了,说明这个叶子节点已经被删除掉了,那么需要再从Root出发找到正确的叶子节点

B. 如果Status wordfrozen没有被设置,那么就需要执行一个PMwCAS操作来预留空间了,要操作两个word

  • Status word[Record Count, Block Size] => [Record Count++, Block Size+r],假设r是需要插入的条目的大小
  • Record metadata entry:对offset翻转最高位,将剩下的27 bits的内容设置为global index epoch。这里最高位翻转,表示对应的offset上的内容并没有被实际用到。那么恢复的时候就可以做相应的操作。

这里操作成功了,就代表插入条目所需要的空间就都已经保存好了。

C. 将需要插入的条目的内容写入到Record storage block中,前面的操作可以知道[Block Size, Block Size+r)的这一片区域已经预留好了。将Record metadata entry中的visible设置为0这个在第B步就直接做掉好了?)。这里可能会涉及到把Record对应的内容从cpu cache中刷回。

D. 再次检查Status wordfrozen位,如果被设置上了,需要abort之后重试。这里abort之后,而且几步做的操作,需不需要回滚?需要看什么情况下这里是frozen的。

E. 到了这一步,需要再执行一次PMwCAS,同样是包含两个word

  • Record metadata entry:设置offset,将visible设置为1。这个非常容易理解了。
  • Status word:尝试将Status word设置成读到的值,这是为了检测是否有并发的线程会将这个值改成frozen如果这个时候有并发会怎么样?

并发问题

BzTree使用了乐观机制来探测对相同key的并发写入,插入操作首先在sorted key space中搜索对应的key,如果找不到,就需要顺序扫描unsorted key space。如果看到visible没有被设置而且allocation epoch和当前的global index epoch相同,这就意味有一个in-progress的插入。如果看到visible没有被设置而且allocation epoch和当前的global index epoch不同,那么这个entry要么是被删除了,要么或者在从之前的宕机中恢复。
插入的操作并不会等待in-progress的插入变得可见,而是设置一个运行时的recheck标志,然后继续执行插入。在预留空间的PMwCAS失败的时候,也会设置recheck,因为并发的预留操作可能也是针对同一个key的。
在设置自己的visible标志之前,如果recheck标志被设置了,会再扫描一遍在这个插入操作位置之前的unsorted key space。如果遇到一个重复的key,会清空自己在record storage block中的内容,然后将offset设置为0。如果在这个扫描中遇到了in-progress的操作,那么必须要等这些操作完成

删除操作

删除操作需要执行一个PMwCAS操作,需要操作两个word

  • Record metadata entry:重置visible,设置offset0(重置了visible,为啥还要设置offset0?)
  • Status word,增加Delete Size,加上Record metadata entry中的Total Length

如果失败了就需要重试;如果Node被设置为frozen,需要重新在BzTree 中找到对应的immutableNode。增加delete size可以让BzTree决定是否需要做consolidation

最后

下一篇会继续介绍节点的其它操作和树结构的改变。休息一下,马上回来。