微软提出的无锁 B 族树 —— Bw-tree
2023-09-26 20:55:58
Bw-tree是2013年由微软提出的数据结构，设计初衷考虑到了多核机器和SSD的普及趋势，结合了B+-tree和LSM-tree的特点。该数据结构具有无锁、增量更新和日志结构化的特点。随后，CMU团队在2015年实现了一版本基于内存的Bw-tree，详细描述了实现细节，并将其开源在GitHub上，命名为open bwtree。
Bw-tree的主要特点包括：
- 无锁结构进行增量更新
- 在外存使用Log Structure Store管理物理数据存储
Bw-tree架构图如下所示，分为逻辑上的Bw-tree索引层、物理上的Log Structured Store存储层和沟通两者的中间缓存层。缓存层使用映射表记录Page ID到物理指针的映射，并控制数据在内存和闪存间的移动。
Bw-tree索引提供record级别的接口，整体结构如下图所示。Bw-tree的节点由基础节点和增量记录链组成。对节点的修改以增量记录形式追加到链表头，节点内使用物理指针和节点间逻辑指针进行链接。逻辑指针通过映射表控制并发控制。
Bw-tree中delta record是关键数据结构，包含针对叶子节点和中间节点的修改信息。主要字段有low Key、high Key和side pointer等。
单节点操作包括更新、查询和合并，其中更新操作引入增量记录，查询从头遍历增量链至基础节点，合并是节点内的紧凑化。
树结构变化包括分裂与合并，微软论文中称为SMO，通过多步CAS操作完成调整。中间节点修改增量是一些特殊增量，与叶子节点的增量不同。
冲突处理包括Bw-tree与DBMS事务管理模块协同，通过help-along协议解决冲突。缓存管理主要功能包括映射表更新和增量下刷。
闪存层使用重写方式进行垃圾回收，待读功能允许单节点更新与树结构调整冲突的解决。
为了深入理解Bw-tree的存储和事务部分，需要参考微软的另外两篇论文，关于这些内容的详细描述将在后续的文章中提供。
我是青藤木鸟，一个热爱摄影的分布式系统程序员，欢迎关注我的公众号：“木鸟杂记”。更多关于分布式系统、架构、学习资源和存储面试经验的文章，敬请期待。
热门标签
