分布式系统,程序语言,算法设计

微软提出的无锁 B 族树 —— Bw-Tree

概述

Bw-tree 是 2013 年微软发表的相关论文提出的数据结构。考虑到多核机器和 SSD 日趋普及,结合两大存储引擎 B+-tree 和 LSM-tree 特点,提出了一种 latch-free、delta update、log structured 的 B族树 —— Bw-tree。

由于上述论文在实现细节上语焉不详,cmu 几个作者在 2015 年时实现了一版基于内存的 Bw-tree,然后又发表了一篇论文,补充了一些实现上的细节,并将代码开源在了 github 上,称为 open bwtree

例行地总结下(太长不看版),Bw tree 的主要特点有:

  1. 总体分三层:bwtree 索引层,缓存控制层和 Flash 存储层。
  2. bwtree 在整体上是一棵 B+ 树,同时借鉴了 B-link 树的思想,每个节点存在一个指向右兄弟的 side pointer。
  3. bwtree 在单个树节点上表现为类似 LSM-tree 的 Log-Structure,每个逻辑节点由 a base node + a delta records chain 组成。
  4. bwtree 实现 latch-free 的核心数据结构叫 Mapping Table,通过 CAS 进行 installing 操作,修改一个 mapping entry 可以同时完成多个逻辑指针的修改。
  5. bwtree flash 层也使用 Log-Structure Store (append only)对逻辑页的物理存储(base page 和 delta record)进行管理。

作者:木鸟杂记 https://www.qtmuniao.com/2021/10/17/bwtree-index, 转载请注明出处

缘起

新数据结构的设计往往是为了适应硬件的变化。那么近些年,硬件层面有什么变化趋势呢?一方面,在单核性能压榨到极致后(摩尔定律失效),单机多核架构成为一个主要发展方向,但传统基于锁控制并发的数据结构难以充分利用多核性能。这是因为,过多的锁会导致频繁的等待和上下文切换。另一方面,闪存(Flash)的价格越来越便宜,逐渐成为主力存储类型。但闪存有其独特读写特点:顺序写比随机写快几倍,随机读并发要远强过传统磁盘。

flash 读写性能对比

针对上述两个观察,微软设计出了 bwtree。bwtree 在内存中使用无锁结构进行增量更新:

  1. 无锁结构能够减少上下文切换,提高并行吞吐。
  2. 增量更新避免了原地更新引发的 cache miss。

在外存中使用 Log Structure Store 管理物理数据存储:

  1. 追加写能够充分利用闪存顺序写速度快、吞吐高的特点。
  2. 虽然可能带来更多随机读,但正好闪存随机读并发更高。

架构

bwtree 的架构图如下:

bwtree 架构图

bwtree 总体上分三个层次,逻辑上的 Bw-tree 索引层,物理上的 Log Structured Store 存储层和沟通两者的中间缓存层。缓存层使用一个核心数据结构——映射表(Mapping Table),记录 Page ID 到物理指针的映射,并控制数据在内存和闪存间移动。

Bw-tree 索引

Bw-tree 对外提供 record(key value)级别的接口,整体结构如下图。

Bw-tree 的节点(Node)是弹性可变的,由一个基础节点(a base node) 和一个增量记录链(a delta records chain)组成。所有对节点的修改,包括插入(insert)、更改(modify)和删除(delete) ,都会以增量记录(delta record)的形式追加到链表头

Bw-tree 中指针包括两种:节点内的物理指针(Physical link)和节点间的逻辑指针(Logical link)。逻辑指针即 page id,需要配合 Mapping Table 使用,因为后者记录了 page id 到物理指针的映射。物理指针,在内存中表现为 pointer,在闪存上表现为文件系统 or 块存储上的地址。Bw-tree 节点,如果在内存中,便通过内存指针链接到一块;如果刷到闪存上,就会通过物理地址串在一起。Bw-tree 节点间的逻辑指针,即 page id,是能够进行 CAS 方式进行并发控制的关键,后面会详细说原因。

:下图中的 Delta node 叫法不太科学,叫 Delta record 更合理些,因为其保存的信息粒度比 node 细要一些,一般就是单个 record 级别。

cmu 论文中 bwtree 索引示意图

Delta record 是 Bw-tree 中很重要的一个数据结构。主要有两种类型,一种是针对叶子节点(Leaf Node)的 kv 增量修改;一种是针对中间节点(Inner Node)的树结构修改。Delta record 中有几个比较重要的字段:low Key,high Key 和 side pointer。

我们不妨站在设计者的角度考虑一下,delta record 应该包含哪些信息?简单罗列下:

  1. 包含必要的增量信息(kv 值),使之能 apply 到原节点。
  2. 包含一些冗余信息(low key,high key),使之对查找进行优化。
  3. 包含一些指向(借鉴 B-link 的 side pointer),使之能够在树结构调整时不影响并发的扫描。

bwtree 逻辑节点

下面来通过一些典型的场景来串一下上述设计。常见的场景有两个,一是只针对单个节点的修改(追加包含 kv 的 delta record),一般是针对叶子节点;一是针对树结构的大范围修改,一般是由于新增或者删除太多引发的子树的分裂与合并,叶子节点和中间点都会涉及。

单节点操作

对于单个节点的操作主要包含更新(插入、删除、更改),查询(点查,范围查)和合并(consolidation)。其中,更新操作都是通过引入增量记录来完成,点查会从头开始遍历增量链直到基础节点,范围查会提前准备好节点对应的 kv vector,合并本质上是节点内的 compact。

单个节点改变一般只发生在叶子节点上,其类型都是对于单条记录(一个 kv)的修改操作引起的,包括:插入、删除、更改。Bw-tree 将这些修改做成一条 delta record,追加到节点内的修改链上,之后修改映射表中的链表头指向,完成修改。

bwtree 单节点操作

如上图 a,增量修改 Page P 时,其步骤如下:

  1. 在内存中新申请一个增量记录(图中 △D)。
  2. 给其赋值,包含增量信息(如修改类型、待修改 KV),查找优化信息(如 low key,high key)以及指向当前增量链的物理指针。
  3. 通过 CAS 操作,修改 Mapping Table 中对应项进行 installing,使之指向新的增量链的头。

对于单节点,为了释放空间,还会进行合并操作(consolidating),如上图 b,步骤如下:

  1. 在内存中新申请一个页。
  2. 将增量记录和基础页合并,拷贝到新申请的页中。
  3. 通过 CAS 操作,修改 Mapping Table 中对应项进行 installing。

合并操作有点类似于 LSM-tree 中的 compact,只不过粒度更小。

树结构变化

树结构变化,微软论文中称为SMO(index structure modification operation),包括分裂(split)与合并(merge)。由于一次树结构调整,难以通过单个 CAS 操作来完成,因此 Bw-tree 将其分解为多步。但为了保证调整中间状态时节点的对外可见性,Bw-tree 借鉴了 B-link tree 的思想:

  1. 每个节点维护了一个右指针(side pointer),指向右边兄弟节点。
  2. 每次分裂,只允许向右边分裂。

其作用在于,即使新分裂的节点的索引没有加入父节点,仍然可以通过前驱节点的右指针来访问到。

即,虽然子节点分裂了,但藕断丝连,仍然通过指针串在一起。

此外,不同于叶子节点的 kv 修改增量,中间节点的修改增量是一些特殊增量,下面会详细介绍。

树结构调整包括节点分裂(node split)和合并(node merge)。

节点分裂。

bwtree 节点分裂过程)Untitled

如上图,分裂 Page P,分为两个阶段:child split(对应上图 a、b),parent Update(对应上图 c),每个阶段使用一个 CAS 操作将修改对外可见

  1. 创建 Page Q 。容纳 Page P 的右半部分 kv 值,并将其 side pointer 逻辑指向 Page P 右兄弟 Page R。此时,Page Q 对外不可见,即通过 Bw-tree 根节点不可达。
  2. 安装分裂增量(Split Delta)。为了将 Page Q 对外可见,Bw-tree 引入了一个特殊增量记录:分裂增量。该分裂增量包含原 Page P 中的 split key,用以查找时在 Page P 和 Q 间进行路由;同时记录下 Page Q 作为其 side pointer。最后通过 CAS 操作,将分裂增量安装到映射表中。
  3. 安装索引增量(Index Entry Delta)。Page Q 从 Page Q 分裂后,需要在父节点添加一个 index entry,指向新增的节点 page Q。Bw-tree 通过引入索引增量,来完成这个操作。索引增量中除了包含 SplitKey-PQ 和 Pointer-PQ 外,还包含一个 SplitKey-QR,这样落在 [SplitKey-PQ, SplitKey-QR] 间的查询就可以直接路由到 Page Q 上。

虽然图中各种指针看起来眼花缭乱,但理清他们只需要把握几个特点:

  1. 实线是真实物理指针,虚线是逻辑指针,即 Page ID。
  2. 节点内的物理指针在增量记录创建时完成,Mapping Table 中物理指针通过 CAS 操作来更新。
  3. 更新完 Mapping Table 中的记录后,图中的虚线指针就随之改变了指向。

节点合并

bwtree 节点合并过程

如上图,将 Page R 合并到 Page L ,分为三个阶段,每个阶段包含一个 CAS 操作:

  1. 标记删除(Marking for Delete):引入移除节点增量(Remove Node Delta),追加到 Page R ,然后通过 CAS 操作更新映射表中的 Page R 对应值,将 Page R 标记删除。但此时,Page R 仍然可以通过 Page L 的 side pointer 访问到,即移除节点增量只屏蔽了来自父节点的访问。
  2. 合并孩子节点(Merging Children):引入节点合并增量(Node Merge Delta,遵从论文中名字,但是和 Remove Node Delta 命名不对称啊,不知道有什么特殊考虑没)。该增量记录了到 Page L 和 Page R 的物理指针,然后通过 CAS 操作,更新映射表中 Page L 的值,即该增量是逻辑页 L 的一部分。
  3. 父节点更新(Parent Update)。引入索引删除增量(Index Term Delete Delta),追加到父节点,逻辑删除其中原先指向 Page R 的 key 和指针,然后通过 CAS 操作,更新映射表中父节点 P 的值。

从图 a 中可以看出,更新映射表中 Page R 的值安装 Remove Node Delta 时,同时修改了两条逻辑指向:

  1. Page L 指向 Page R 的 side pointer。
  2. 父节点 Page P 指向 Page R 的 child pointer。

这也是映射表与逻辑指针的意义所在:通过 CAS 修改一个映射表项,达到同时修改多个逻辑指向的目的。

处理冲突

如果有一个节点进行 SMO 操作的同时,另一个线程要进行单节点更新,但与 SMO 操作产生了冲突(比如操作同一个 Page),该如何解决冲突?

一般来说, Bw-tree 会作为一个存储引擎嵌入到 DBMS 中,DBMS 中的事务管理模块会尽量处理外部冲突,将多个 SMO 操作进行序列化(个人猜测)。然后 Bw-tree 来处理 SMO 操作与单节点更新的冲突。

Bw-tree 采用了一种叫 “the help-along protocol“ 的方案,即任何线程如果发现有 SMO 操作正在进行,就先去执行 SMO 操作,再去执行自己的操作(增删改查)。即:

  1. 将 SMO 的优先级提高以确定两类更新(SMO 与单节点更新)顺序。
  2. 所有线程遇到冲突的 SMO 时,不管是否属于本线程操作,都先去完成 SMO,这样总有一个线程完成 SMO 并得以继续,其他线程则直接放弃。

缓存管理(Cache Management)

bwtree 映射表

主要功能

缓存层主要功能有:

  1. 维护映射表(Mapping Table),保存逻辑 PID 到物理地址间的映射。物理地址可能是内存中的指针,也可能是闪存文件系统中的地址。
  2. 负责页面在内存和闪存之间移动,包括读取(reading)、交换(swapping)、下刷(flushing)。

映射表更新

所有对映射表更新都通过 latch-free 的 CAS 来完成,包括:

  1. 叶子节点和中间节点的追加增量记录造成的物理指针的变化。
  2. 页在闪存和内存间交换造成的内存指针和文件地址的替换。

增量下刷

引起缓存中的页下刷的原因有很多种,比如上层事务要求做检查点,比如内存使用达到阈值需要换出。之前提到,一个逻辑页包含一个基础页和一个增量链,并且增量链在阈值范围内还会不断延长,因此对一个逻辑页的下刷不是一次性完成的,也是增量进行的。为此 Bw-tree 又引入了一种特殊的下刷增量(flush delta),记录下刷点,并添加到逻辑页中。这样如果有修改,在下次下刷时,只需要下刷增连链之后的增量记录即可。

bwtree 存储结构和增量下刷

闪存层(Log-Structured Store,LSS)

闪存层和内存对应,都是增量刷盘,单个逻辑 page 的数据并不相连,page 内通过文件系统地址串起来。

会使用重写的方式进行垃圾回收,回收时可以将逻辑页的多个部分挪到一块,以减小之后的读放大。

待读

单独读微软的 bwtree 论文,存储和事务部分不太好读懂,是因为本论文只详细了描述了 bwtree 索引部分细节。至于存储和事务部分,得看微软套娃般的另外两篇论文,之后有机会我会再出两篇相关文章:

  1. 缓存层和闪存层:LLAMA: A Cache/Storage Subsystem for Modern Hardware,http://www.vldb.org/pvldb/vol6/p877-levandoski.pdf
  2. 事务相关:Deuteronomy: Transaction Support for Cloud Data,https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Deut-TC.pdf

参考

  1. 微软 2013 bwtree 论文: https://15721.courses.cs.cmu.edu/spring2017/papers/08-oltpindexes2/bwtree-icde2013.pdf
  2. 淘宝数据库内核月报 2018/11 期:http://mysql.taobao.org/monthly/2018/11/01

我是青藤木鸟,一个喜欢摄影的分布式系统程序员,更多有意思的文章,欢迎关注我的公众号:“木鸟杂记”。

wx-distributed-system-muniao-s.jpg