Building a Bw-Tree Takes More Than Just Buzz Words

两个贡献，一个是Bw-Tree的实现教程，并且提出了新的优化策略。第二个则是发现BwTree并不如其他使用锁的并发数据结构更快

Introduction

Lock-free的数据结构实现的难点：
1. 需要明白所有的race conditions
2. 并发线程的同步点通常不会放到算法中，导致人们实现出错，最后变成了busy-waiting loop
3. 需要保证所有的读者全部离开后才能回收内存（在mit os中提到过linux在使用RCU的时候，会等待一个时间上限再去清理）
4. 原子操作会成为performance bottleneck

BwTree的思想就是通过间接层，将逻辑标识符映射到物理地址中，从而避免锁。每个线程通过追加delta record到modification log中来实现修改。后续的操作就必须重放这些delta record来获得当前的状态

间接层和delta record有两个优势：
1. 通过将global state变成atomic steps来避免锁的开销
2. 由于是追加delta record而不是修改，会减少cache invalidation的次数，从而获得更小的同步开销

BwTree Essentials

BwTree和其他的基于B+Tree的区别就是BwTree避免了直接修改树上的节点（因为会导致cache invalidation）。他为每个节点都维护了一个delta chain，从而可以让BwTree通过CAS来更新。indirection layer的作用就是可以让我们原子的更新对树节点的引用（比如孩子节点和祖父节点都指向父亲节点，我们可以通过间接层原子的让他们都指向新的父亲节点）

每一个节点都有一个逻辑ID，节点在指向其他节点的时候会用这个逻辑ID。当一个线程需要他的物理地址的时候，就会去MappingTable中查。MappingTable允许我们通过CAS来更新节点的地址

Base Nodes and Delta Chains

一个逻辑节点在BwTree中有两个部分，一个base node，以及一个delta chain

这里有两种类型的base node：
1. inner base node，存储的是有序的（key， NodeID）的数组
2. leaf based node，存储的是有序的（key， Value）的数组
（和b树一样）

最开始的时候，BwTree有两个节点，一个空的叶子节点，以及一个inner节点，指向了叶子节点。

Base Node是不可变的

delta chain是一个单向链表，存储的是按序排的针对base node的修改历史

base node和delta record都存储了可以表示那个时刻状态的元信息

这样我们就不需要一步一步重放操作来获得最新状态。（但是当需要数据的时候应该还是需要重放，这里只是保存了状态而已）

线程在修改数据的时候，会追加delta record，再修改mapping table让他指向新的delta record

Mapping Table

BwTree借用了BlinkTree的设计，每个节点有两个入指针，一个是从父亲来的，一个是从左兄弟来的。在更新的时候我们需要进行原子的修改这些指针，所以要么使用transactional memory，或者multi-wrod CAS

而BwTree通过用间接层来避免这些问题。从而允许一次CAS来完成原子修改

当CAS失败的时候，这次操作就会重启。每次重启都会从树根开始重新遍历。虽然更复杂的重启协议是可能的，但是我们认为从树根开始遍历简化了实现。并且我们要遍历的节点很可能会在cache中

他提了一点就是这里的Mapping Table只关注了BwTree的实现。实际上他也可以支持log-structured updates。（这里我不太明白，可能需要再去研究一下log-structured相关的细节。他的意思可能是LSM中一个数据会在多层出现，我们通过只修改间接层从而可以直接修改多层数据）

Consolidation and Garbage Collection

当delta chain增长的时候，worker每次来就需要重新遍历并重建当前的状态。为了防止过长的delta chain，worker会周期性的压缩delta chain并重组成一个新的base node。

在压缩的最开始，线程首先把logical node的base node复制到他的私有内存中，然后开始应用delta chain。接着他会更新MappingTable中的指针，指向新的logical node。最后当所有的线程都离开老的节点的时候，我们就可以回收他的内存

Structural Modification

和B+树一样，Bw树也会出现overflow或者underflow的情况。从而导致了splitting以及merging

核心思想就是利用特殊的delta record来表示内部结构的变化

SMO（structural modification protocol）的操作有两个阶段，一个是logical phase，用来追加特殊的delta record来通知其他的线程这里会有一个SMO，以及一个physical phase，用来实际执行SMO（即split或者merge，然后通过CAS来替换掉老的节点）

尽管BwTree是lock-free的，但是如果CAS失败的话线程仍然无法make progress（比如在这个两阶段操作中，我们不能假设是同一个线程在做，否则就会阻塞其他的线程的进度）。一个解决这个的方法就是合作执行multi-stage的SMO，也被称为help-along protocol。线程必须在节点被遍历之前帮助完成SMO的未完成阶段

（我怎么感觉他这块说的都好迷幻，应该看一下BwTree之前的文章）

Missing Components

Non-unique Key Support

在遍历的过程中，BwTree会停在第一个匹配搜索键的地方。但是这样是无法支持non-unique key的

我们在遍历的时候维护两个集合，S_{present}和S_{deleted}。S_{present} contains the values that are already known to be present. S_{deleted} contains the value that are known to be deleted

如果发现了一个insert record，键为K，值为V，并且V不属于S_{deleted}，我们就会把V加入到S_{present}中。

如果发现了delete record，并且V不属于S_{present}，他就会把V加入到S_{deleted}中

更新操作是通过删除后插入来完成的。当遇到最后的base的时候，最终构建出的节点就是S_{present} \cup (S_{base} - S_{deleted})

这里的查找是针对叶子节点单个K的，不是这个K的record会被忽略掉

Iteration

直接在BwTree上进行遍历是非常困难的，因为我们很难定位当前迭代器的位置。并且还需要处理SMO以及并发插入删除的问题

我们的迭代器不直接放在树节点上。每个迭代器都会维护一个只读的logical node的副本。

当迭代器移动的时候，如果当前的副本用完了，我们就会通过low key或者high key来重新遍历一次

Mapping Table Expansion

每个线程都会访问Mapping Table，所以不让他成为bottleneck是很关键的

Mapping Table就是一个数组。动态增长的方法就是使用Lazy allocation。我们提前分配好虚拟空间，当实际使用的时候再分配物理内存

而对于Shinking的情况，没有很好的方法，我们只能阻塞住worker thread，然后重构索引

（我在想他们的logical id是怎么复用的？用free list吗？个人猜想是先放到free list中，但是不用。每过一段时间冻结free list，然后再用free list中的内容）

Component Optimization

Delta Record Pre-allocation

Delta Chain in Bw-Tree is a linked list of delta records that is allocated on the heap. 遍历这个Delta chain会变得很慢，因为局部性很差。并且大量的并发内存分配会导致分配器的争用，从而导致了bottleneck

我们会在base node中提前分配delta record

base node会在高地址的边缘。而delta record会从高到低进行分配（利用pre-fetch）

每个链也会维护一个allocation marker，指向的是最后一个delta record。当worker需要一个slot的时候，他就会减少这个marker（和栈类似），如果预先分配好的区域满了，他就会触发压缩操作

delta record不会删除，所以没有free-list的问题。图中的交错是因为并发的操作导致的，比如第一个线程先分配了空间，但是是后面才append到链中（如果这里失效了，他会放弃掉这段内存吗？因为前面说了当CAS失败的时候要重新遍历，但是重新遍历有可能我们就不会回到相同的node了，是不是只有split/merge的情况才需要重新遍历呢？）

Garbage Collection

之前的BwTree用的是Epoch-based GC，每过一段时间他会在一个全局的链表上追加一个epoch object。每个线程在访问索引之前必须先在epoch object上注册自己

让线程结束操作以后，他就会把自己从epoch object上移除。所有的删除操作都会被加入到当前epoch的garbage list中，当所有的线程都离开这个epoch的时候，我们就可以安全的回收garbage list中的对象

（这样可以安全的保证吗？我感觉在这个操作结束之前的epoch都可能出问题，而不是只有开始的epoch。貌似文章中说了，在操作完成的时候，把删除的对象加入到当前epoch，而不是他进入的那个epoch，所以应该没问题。我们只要保证epoch是按序删除的就行）

（第二个思考是他们为什么回避对单个node进行refcnt呢？这样最后一个人负责删除他就好了，可能是为了防止写元数据导致的cache invalidation）

这种中心化的方法会导致scalability的问题。因为cache coherence这时候会变成瓶颈

OpenBwTree用了一种去中心化的方法。

索引自己维护了global epoch。每个线程自己维护了本地的epoch，以及他删除的对象列表。

在开始操作的时候，线程会把当前的全局epoch复制到本地的epoch中。当他完成操作的时候，他会再次将全局epoch复制到本地epoch中，并且把garbage打上最新的global epoch的标记（表示所有小于这个epoch的线程都有可能访问到他）。然后开始GC。他会收集其他线程的local epoch，并且删除所有小于最小local epoch的那些对象。

线程的local epoch表示的就是这个线程目前的操作正在那个epoch。如果所有人都高于garbage的epoch，就可以安全的回收

这样其实是分散了争用。之前用的是计数器。这里是维护的本地的watermark，从而获得全局最小。然后我们回收小于全局最小的对象。并且这里的删除分摊到了每个线程中

（思考，其实是一种去中心化的维护watermark的方法。因为在中心化的实现中，我们完全可以用一个sorted-list来维护当前的active-operation的epoch，每次结束操作就把他产生的garbage打上最新epoch的标记，然后把自己从sorted-list中移除。这样的话垃圾回收器只要读第一个节点就可以，但是对于注册这个操作来说，他可能会引起争用，同时lock-free的双向链表也不清楚有没有。所以这个方法是写慢，但是读快。而去中心化之后，每个人其实相当于都遍历了一遍链表才能获得global minimum，读虽然慢了，但是他的写很快，并且没有争用。这么想的话其实lsm tree也有这个思路，加快写（通过append only），但是代价就是读变慢）

Fast Consolidation

consolidation分为两个阶段，第一个阶段是复用之前的non-unique key的方法来找到那些元组被删掉了，那些被插入了。然后第二个阶段则是把插入的新元组和之前的老节点做一次2路归并，从而生成新的base-node

insert record和delete record在作用于base node的时候，会存储一个offset字段，用来表示这次操作会作用到哪里。然后我们用Spresent和Sdeleted来将base node划分成若干个片段。再用这些片段和insert record做归并

（我在想维护这些segment的overhead难道不大么，直接sort感觉会更好一些）

Node Search Shortcuts

当节点很大的时候，我们一次二分搜索可能会跨越多个cache line，从而导致效率不高

我们通过micro-indexing来减少节点内的搜索

这里是减少了最后的base node的扫描范围

因为之前的insert以及delete record记录的都是当前的Key对应在base node的偏移量。所以当我们在路上比较的时候就可以顺便获取base node中值的范围。从而在最后一步实现快速的查找

Evaluation

这里写几个我感觉比较有意思的点吧

从这个图大概可以看出来，BwTree的效率不高可能是因为访存太多，也就是memory footprint太大导致的。

这里也显示了，在HC（high contention）的情况下，abort rate是1000%，所以一次操作会abort10次才能成功，所以导致了大量的footprint。反而降低了lock-free的优势。因为本身lock-free的算法就是在高争用情况下保证可以make progress

表现最好的ART拥有相当高的局部性

这样看起来是BwTree的结构导致的他表现的不好，比如更多的Branch，更多的预测失败等

所以可能BwTree更适合在flash中，而非memory中。因为他的优势在于append-delta，所以cache invalidation的优化不能弥补更多的memory footprint带来的开销。但是flash中比较偏向这种结构，也就是log-structured形式。所以可能BwTree在flash中表现的会更好

最后他有一个performance decompisition，基本上把BwTree的feature都关掉，然后比较性能

但是结果是即便把feature都关掉，BwTree还是比B+Tree慢一些。原文说: Even Read-only operations perform considerable bookkeeping to maintain the consistency of the tree, limiting its performance.

这里我不太明白他的都维护了什么东西，但是可能就是因为为了latch-free所维护的各种信息吧，导致了高开销