Bw-Tree：在新硬件平台上的新B-Tree

ARS 与 Bw-Tree

nosql数据库从本质上说，都属于ARS（Atomic Record Stores，“原子记录存储”）。

最常见的“原子记录存储”一种实现就是朴素的Hash表：通过一个特定的key，来读写一条独立的数据记录。

一些基于key-value（键-值）模型的nosql的内部实现正是使用了Hash表，例如Redis¹、memcache、Riak等。

而有一些nosql数据库为了支持高效的key-sequential（键-序列）查找，采用了tree-based²数据结构进行数据存储，所以B-Tree成为了一些数据库（both nosql and sql）的首选。

本文介绍了一种基于新型硬件的高性能ARS实现，其核心技术有：

1. 页式内存管理
2. Bw-Tree，一种基于B-Tree的树存储结构
3. 基于日志的存储管理

在现代硬件上的Bw-Tree

现代多核CPU

多核CPU带来了高并发，但是同时也引入了锁竞争和缓存失效问题。

为了讲解锁竞争，这里我们举一个经典的例子：多线程计数器。

我们都知道，如果不使用锁来保护计数器变量的话，那么最终的结果几乎不可能是正确的。多个线程中，只能有唯一一个线程可以持有锁，其它的线程都需要等待。这样就影响到了程序的并发度。

这里一些高级玩家会提到CAS（compare-and-swap）命令。CAS翻译成中文就是“比较并交换”，用在多线程编程中实现数据交换操作。详情请见：比较并交换

缓存失效产生于两种场景。一是上文提到的锁争用，即每次锁争用都会让当前线程陷入内核态，产生上下文切换，导致CPU缓存的失效。二是缓存一致性协议导致的缓存行失效，即多个CPU在共享一个共同的主存资源时，为了保证缓存中的数据一致性，在主存资源被修改后，相应的缓存行也会失效。

Bw-Tree为了解决以上的问题，使用了以下两个措施。

1. 无锁数据结构
   避免了系统阻塞在锁上，更避免了由于锁争用导致的缓存失效以及上下文切换。

2. 增量更新
   使用增量更新而不是原地更新，避免修改共享的主存资源，规避缓存一致性产生的缓存失效问题。

现代存储设备

数据库系统的一个重要瓶颈就是IO性能。SSD（固态硬盘）提供了比传统机械 硬盘更好的读写性能，虽然表面上缓解了问题，但是IO仍然可能是整个系统的瓶颈。

所以，Bw-Tree使用大内存做为读缓存，同时采用append-only结构保存写信息。因为不论是SSD还是机械硬盘，顺序读写的性能都非常出色。

Bw-Tree的页式存储结构

映射表（Mapping Table）

上文中我们提到了缓存一致性（cache coherance），简单来说，就是当我们修改多个CPU共享的内存资源时，会导致缓存的失效，进而影响指令的执行效率。

Bw-Tree使用页式（paginated）存储管理与映射表解决了这个问题。Bw-Tree以“页”做为存储的单元，每一页都有一个PID。页的物理位置可以存储在主存上，也可以存储在磁盘上。

映射表将PID所代表的映射到页所在的具体物理位置。所以当页的物理位置发生改变时，仍然保持PID一致，不需要对Bw-Tree的结构进行任何修改。

增量修改（Delta Updating）

假设我们现在有数据D，当有修改请求delta到来时，我们可以将数据D原地修改为D'。也可以使用增量更新的方法将其保存为delta + D的形式。

增量更新看起来比原地更新耗费了更多的内存，但其优势也非常明显。一是修改不需要对页加锁，可以使用CAS无锁方法安全的更新共享资源。二是不需要修改页内存，不会导致现有cache失效。

当增量过多时，Bw-Tree会自动合并增量和页内存，这个过程同样是无锁的。

弹性虚拟页（Elastic Virtual Pages）

B+-Tree，图片来源：B+ Trees Visualization

B+-Tree的特性有：

1. 所有记录都在叶子节点（节点也被称为页）上，并且是顺序存放的
2. 每个非叶子节点包含关键字（references）与孩子指针
3. 叶子节点有一个指向左右兄弟的指针，方便顺序遍历数据

Bw-Tree在B+-Tree的基础上添加了：

1. low/high key，用来标明本节点以及子节点的数据范围
2. 每个节点（包括叶子节点和中间节点）都有一个side pointer指向其右面的兄弟节点

范围查询

由于Bw-Tree的数据都分布在叶子节点，并且叶子节点之间可以通过兄弟指针进行遍历。

我们使用游标（cursor）来标记当前检索的位置。并且使用缓存当前页上符合条件的记录。这样可以加速逐条遍历操作（"next-record" functionality）。

逐条遍历操作是原子的，但是逐条遍历某一段数据则不是原子的。如果读写同时发生在同一页，则我们会根据事务的同步级别来决定是否需要重建检索缓存。

垃圾回收

无锁数据结构导致的一个结果，是我们无法显式的让某个页失效。这意味着，一些线程会持有过时的数据，所以在删除这些过时的数据时要非常小心。

所以这里引入了“代”（epoch）的概念，每一个线程执行每一个操作都在某一个代中，并且这一代中的所有数据以及过时数据都不会被删除。当某一代中所有线程操作都被执行完毕后，这一代就会结束，其中的过时数据就会被安全的回收。

Bw-Tree的结构改变

Bw-Tree的结构会在某些操作下进行改变，以维护其性质。结构改变的操作仍然是无锁的。

为了方便理解，我们假设结构改变的写操作不是并发的。

节点分裂

当某线程发现Bw-Tree中某个节点的大小超出了系统设定的阈值后，在执行完其预定的任务后，就会触发节点的分裂操作。

节点分裂分为两步执行，每一步都是原子的：

1. 子节点分裂
2. 子节点更新后，向上更新父节点

子节点分裂

上图是Bw-Tree中的一部分，现在我们想分裂PQ节点为P和Q两个子节点。即大于某个值KP的数据全部迁移到新节点Q。

节点分裂的操作如下：

1. 先拷贝Q中的数据到一个新的数据页Q'，这一步并不会影响到其它的线程。

1. 在P节点，使用CAS操作，添加分裂的信息Δ，标明该节点已经分裂，其中包含着KP的信息，所以当查询的Key大于KP时，会跳转到新节点Q'进行查询。

父节点更新

同样，父节点的更新仍然是采用增量修改的模式。

我们在父节点使用CAS操作添加一条修改增量（index term delta record）。当查询请求落在Q节点的范围内时，会直接跳转到Q'节点。

更新合并

使用增量更新可以减少数据更新、节点分裂时的时间开销，从而避免失败的分裂操作（failed splits）。

但是最终，我们仍会将产生的更新增量合并成一条完整的记录，以避免过多的空间浪费和指针跳转。

子节点合并

在Bw-Tree数据减少时，我们为了避免过多的指针跳转，需要进行节点合并。节点合并比节点分裂复杂一点，所以需要一系列的原子操作来进行。

1. 删除节点

删除节点时使用标记删除，仍然是CAS操作，添加一个删除增量（remove node delta）到Q。之后所有的读写请求全部转发到其左兄弟P。

这里有个猜测，在Q中原有的数据仍然是要到Q节点进行访问的。论文里没有说，通过常识推断一下应该如此。

1. 合并子节点

在P节点之前用CAS操作添加合并增量（node merge delta）。合并增量将P节点和Q节点从逻辑上合为一个，并且负责转发读写请求。

父节点更新

这个就非常简单，就是CAS操作在父节点标记删除Q节点的Key即可。

序列化结构修改

上面的Bw-Tree结构修改的实现都基于一个假设：数据库的同步机制会处理好数据更新冲突问题。

同步机制包括数据库系统的锁管理器（lock manager）、事务管理组件（transactional component）；或者是采用弃疗方案，允许随机交叉写。

但是在Bw-Tree内部，我们需要序列化树的结构修改（俗称排队）。当一个SMO操作遇到了未完成的SMO操作时，当前线程会等待之前的SMO操作完成后再继续当前操作。

这样的方案可能会形成一个“SMO栈”，但是这种场景比较少见，实现起来也比较简单。

缓存管理

缓存层负责内存与SSD磁盘之间的读、写回以及换页操作。缓存层为Bw-Tree层提供了逻辑页的抽象。

Bw-Tree使用PID访问逻辑页，当逻辑页位于磁盘中时，缓存层先把页读取到内存中，再使用CAS操作将PID指针从磁盘偏移量指向内存偏移量。

预写日志协议与日志序列号（LSN）

• 日志序列号（LSN）

插入或修改Bw-Tree的增量都会被打上日志序列号。日志序列号由事务子系统产生。

在页的刷写增量（flush delta）中，记录着最后被刷入（flush）磁盘的日志序列号。

• 事务日志协调

事务子系统维护着一个“最大写入日志序列号”（End of Stable Log, ESL）。事务子系统通过ESL来限制数据管理子系统的持久化进度，也就是说，数据管理子系统只能持久化事务号小于ESL的事务。这保证了预写日志协议的因果性。

数据管理子系统通过向事务子系统反馈最后刷写的事务序号以提供反馈。当事务子系统想要向前移动“事务重做指针”（Redo-Scan-Start-Point, RSSP）时，会向事务子系统发送请求。当事务序号大于RSSP，且小于ESL的所以事务全部刷写到磁盘之后，数据管理子系统会向事务子系统发送ACK信号。最后事务子系统向前移动RSSP，已经落盘的事务信息抛弃。

• Bw-Tree的结构修改

我们将Bw-Tree的结构修改（SMO）封装成为一个系统事务。由于Bw-Tree的结构修改是无锁的，所以会有多个线程操作同一页的情况。

将SMO视做事务，允许我们并发的执行SMO操作，当且仅当某一个SMO操作“胜出”时，才将事务提交。

将页写回日志式存储（LSS）

• 页封装（Page Marshalling）

我们如果要将页写回LSS，首先要先逻辑页转化成线性顺序存储的结构，便于我们将其存储到磁盘。

然后我们要将页的状态设定为“锁定”（captured），以防止后续的修改破坏预写日志协议。

• 增量刷写（Incremental Flushing）

当刷写页面时，缓存管理器只会刷写ESL之前的数据记录。这样的好处有：

1. 减少磁盘的使用
2. 避免产生过多的磁盘垃圾

3. 避免SSD的写入放大开销

4. 刷写操作

使用双Buffer进行磁盘刷写，可以避免线程等待IO操作。

在刷写操作完成之后，我们会更新mapping table，将页指针改变成磁盘的偏移量。并将内存中的页换出。

缓存管理器会监视系统内存的使用情况，如果内存不够用，就将一部分页从自动内存中换出。

性能

我们的对手

• BerkeleyDB

性能良好的独立存储引擎。我们使用C语言实现版本，内置存储引擎为B-Tree。

运行模式为性能较好的“无事务模式”，支持一写多读。

在整个实验中，我们将BerkeleyDB的缓存开到足够大，全部使用主存进行存储与查询操作。

• SkipList

无锁的跳表实现。

测试数据集

• XBox Live
  网游数据。Key的平均大小是94Bytes，Value的平均大小是1.2K。读写比大概是7.5: 1
• 商业数据库的备份流
  总共有27M数据块，去重后有12M。读写比为2.2：1，Key是20Bytes的SHA1哈希值，Value是44Bytes的元信息。
• 综合KV数据
  8Bytes整数Key，8Bytes整数Value。读写比从5：1。

比赛项目

增量链长度阈值对性能的影响

增量链长度阈值影响触发页合并（consolidation）的频率。从图中我们做出如下推测：

1. 增量链长度较短时，读写性能好，但页合并开销大
2. 增量链长度转长时，读写开销大，页合并开销小

系统的整体性能就在这两个因素下面取一个平衡。

无锁环境下的更新失败

数据中我们可以看出，Bw-Tree写入失败（Failed Updates）是非常少的。但是“综合”数据集的“页拆分失败”和“页合并失败”明显高于其它数据集。

这是因为“综合”数据集中的数据都比较小，更新起来比较快，所以会导致比较多的线程竞争。

与传统B-Tree的比较

Bw-Tree明显胜出，其原因有：

1. Bw-Tree是无锁的，所以并发程度更高
2. Bw-Tree对CPU cache更加友好

Bw-Tree与无锁跳表比较

Bw-Tree仍然明显胜出，其原因归于Bw-Tree更友好使用了CPU cache。

缓存性能

Bw-Tree的优势有：

1. 与跳表相比不需要过多的指针跳转
2. 内存使用更加高效

后续（201026）

到了新组之后，发现了一个使用BW-Tree的存储引擎。不过已经即将废弃了（挥手