Bf-Tree

Bf-Tree(f代表faster) 是VLDB 2024上发布的一个B树的变种,它提出了两个关键的点:variable-length mini page 和 variable-length buffer pool,面向SSD和短键值优化,旨在减少写放大,提高缓存效率。它在论文中高亮了测试的性能数据“对于scan操作,它比RocksDB的快2.5倍,对于写操作,它比B-Tree快6倍,对于点查询比B-Tree和LSM-Tree都要快2倍“(米式对比法?)

背景

B-Tree的问题是:1. 对于点查询,会将整个叶子节点加载到缓存中,尽管整个节点中只有少量的几个记录是热点,这就导致缓存的效率很低;2. 对于写入,总是按照固定大小的页整个一起写,这会导致写放大

LSM-Tree的问题是:对于范围查询,需要遍历所有层级找到记录后再进行合并输出结果

基于此,这里提出了一个关键的想法:把缓存的页和硬盘的页分开,不要一一对应,缓存的页进是硬盘页中的热点部分,是硬盘页的子集,这里把它叫做 mini page。基于这个想法,这里将其转化为一种新的数据结构:Bf-Tree

mini page在Bf-Tree中有两个重要的作用:1. 缓存高频访问记录;2. 暂存最近的更新。为了管理mini page,Bf-Tree中又提出了一种基于ring-buffer的buffer pool,负责:1. 现在mini page的内存占用为设定值;2. 管理内存的分配和释放;3. 鉴别hot和cold的mini page;4. 和硬盘中的叶子页面交互,确保一致性和完整性

Bf-Tree的架构

和常规的B树类似,Bf-Tree也分为Inner和Leaf节点,不同的是,这里加入了一个mapping table,inner page的最后一层指向的是 mapping table的位置(类似BwTree),映射的值可以是mini page也可以是leaf page。其中mini page由 buffer pool管理,而leaf page位于硬盘上。以上映射可以看出,一个leaf page要么没有mini page,要么只有一个mini page

mini 页

前面提到了mini page的两个重要的作用,这里就展开说说

缓冲写记录

首先,如果leaf没有对应的mini page,那么需要创建一个,以开始mini page大小就是cache line的大小(例如64字节),这个mini page就可以用来存放记录了。但如果它满了,那么按照2的倍数扩大,直到它能容纳新的记录。当然mini page有大小的上界(例如 4KB),如果到达了上界(或是需要被淘汰时),就需要将mini page和 leaf page合并(可能会导致分裂)

简单来说,mini page缓存了leaf page中的部分值,写操作先作用在mini page上,当触发条件时,和leaf page合并落盘

缓存热记录

对于点查询操作,首先在mini page中进行二分,如果找到了那就直接返回,如果没有找到,那就需要到leaf page中查找,查找的结果会插入到mini page中,同时为了避免mini page被冷记录塞满,只有1%的记录会插入到mini page中

mini 和 leaf 页的布局

这里mini和leaf page的布局是一致的,区别在于mini page的长度是可变的,而leaf page是固定长度(4KB)。它们的布局由一个 node meta 和 若干个 kv meta 加 record 组成,其中 node meta描述了node的大小,页类型(mini 还是 leaf),是否需要分裂,键值的个数以及leaf page的物理位置(48位)等信息(后续会再次提到);剩余的部分和 slotted page布局类似,不过kv meta中存放了一些用于优化的字段(后面优化部分会讲)

mapping table

或许是受到了BwTree的启发,Bf-Tree也使用一个映射表来关联page id到mini page或leaf page(文章也提到可以使用pointer swizzling,见前面的leanstore)不同的是,这里的物理地址中的16位用作了页面的读写锁,实际的地址只有48位(这种机制在使用pointer swizzling就完全依赖指针的实际位宽为48位了)

内部节点

常规的B树系统中是不区分内部节点和叶子节点的,它们都使用同一套映射机制(buffer manager),通过page id找到物理地址,这就造成了一个问题:访问最频繁的内部节点每次都需要经过映射,成为一个瓶颈(leanstore使用swip解决这个问题)

在Bf-Tree中直接将内部节点pin在内存中(注意,Bf-Tree是面向main memory的),内部节点间直接使用指针连接而不经过映射,这样buffer pool仅缓存leaf page中的热记录。当然将内部节点都pin住并非强制的,在内存有限时还是可以退化为常规做法

同时,Bf-Tree在内部节点访问上采用乐观的蟹型锁(latch crabbing or coupling)有效的减小锁竞争。并且采用类似顺序锁的机制确保读不被写阻塞

buffer pool

和mini page一样,buffer pool也是变长的,这个特点会带来几个问题:1. 如何管理mini page;2. 如何鉴别冷热mini page;3. 并发的分配和淘汰内存。这几个问题的除了第二个,剩下的和内存分配器的功能是重合的,因此,实际只需要解决第二个问题,其他问题借鉴内存分配器即可

circular buffer

Bf-Tree设计了一个circular buffer来解决这个问题,将一块内存区域划通过三个指针head、second chance和tail划分为两个部分,其中 head 到 second chance占10%为A,second chance到tail占90%为B。这样位于A和B两个区域的mini page有了不同的修改策略,位于A区域的,当需要修改时,需要将数据拷贝到tail位置(copy-on-access),而B区域的,则直接原地更新。当buffer塞满时,靠近head的mini page就会被剔除,这样tail就能继续增加了

这里强行解释下second chance是什么,如果没有这个东西,那么所有的更新都是原地的,挨着head的mini page就应该被淘汰,但是这个mini page很可能是高频访问的。有了这个东西,那么这个mini page是高频访问的话,那么它应该被拷贝到tail处,就远离了head,因此不会被淘汰。这其实就是我们熟知的second chance算法。

虽然,但是,除了解决淘汰的问题,还是要像内存分配器那样,将释放的内存按照大小划分为不同的类,串联成freelist,下次要分配时先从freelist上找,找不到在增加tail指针

接口

基本就是解决的三个问题的接口:alloc、dealloc和evict。其中evict有一点要注意,前面提到的需要将mini page和leaf page合并,然后将mapping table的地址缓存leaf page的,最后增加head指针

Bf-Tree核心操作

接下来介绍Bf-Tree和mini page相关的核心机制:Bf-Tree是如何将各个组件串联起来实现高效的读、写以及范围扫描的

Get

前面提到,内部节点的最后一层指向的page id可能对应这mini page或leaf page,在查找时如果发现是mini page并且能找到,那么就提前返回。否则,要么是leaf page还没有对应的mini page,要么是记录不在mini page中,这时就需要从leaf page中查找(如果没有mini page,那么mapping table的映射就是leaf page的地址,否则mini page的node meta中也有leaf page的地址),在找到记录时,有1%的概率将记录插入到mini page中或者创建mini page

Insert

插入的流程的前面部分和Get相似,如果没有mini page就创建一个,否则插入到mini page,然后返回,整个过程不涉及到IO操作。当mini page塞满时,尝试将扩大,这个过程会将mini page拷贝到新的内存地址,随后将记录插入的mini page中。如果在插入记录后mini page已经过大了(超过4KB),那么将和leaf page合并后落盘,合并过程会剔除mini page中冷记录和修改过的记录,当然可能还会触发leaf page的分裂

Range scan

简单来讲,就是允许经常被scan的整个leaf page的都缓存在buffer pool中以提高效率

Delete/Update

删除操作仅仅是对记录标记一个tombstone,目的是在后续查找时发现删除好提前返回而不用到leaf查找,真正的删除在mini page和leaf page合并时发生。更新和删除类似,但不会打标记。

mini page的操作

mini page合并

当mini page过大或者被two chance淘汰时就会触发合并。具体做法是:1. 找到对于的leaf page,2. 计算大小能否被leaf page 容纳,3. 如果能,直接将mini page记录插入(tombstone丢弃),否则先分裂leaf page,再将mini page记录插入到合适的leaf page,4. 回收mini page释放的内存

拷贝mini page到buffer pool的尾部

前面提到,second chance算法保留了热的mini page,但mini page中的记录或许不再是热的。那么在执行拷贝mini page到尾部时,就需要将mini page中的冷记录淘汰掉,这里需要借用kv meta中的 ref 位,如果置1就保留,否则就淘汰

ref这个位在被访问时置1,当淘汰开始时会将mini page中ref为0的都剔除,同时将剩余的记录的ref都置0

淘汰时还需要判断kv meta中的type字段,如果是read cachephantom 那么不需要落盘(这里先列出所有的type值:insertcache(read cache)、tombstone以及phantom,其中除了phantom都已经在前面提到过),其他的类型的记录就需要合并到leaf page,而热记录仍然保留在mini page中

leaf page分裂

和传统的B树一样,需要注意的是,在leaf page分裂后,需要使用split-key来判断mini page中的记录该插入到那个leaf page

处理消极查询

Bf-Tree的优点之一就是提高缓存效率,那么当要查找的key不存在时,就无法发挥优势了(所谓的缓存穿透?),因此Bf-Tree必须处理这种消极的查询。常规的bloom filter应用到Bf-Tree会使得设计十分复杂,因此Bf-Tree选择缓存这些不存在的key在mini page中,给它们一个phantom的类型,这样后续查询就不会到leaf page了。当然这只能算是稍微缓解了问题,毕竟大量的消极查询,会导致正常的查询也需要触发IO

快照、日志和恢复

日志就是常规的WAL。快照分为两种,一种是后台的任务重放WAL实现,另一种在线的需要暂停所有的写入实现。需要注意的是,由于Bf-Tree的内部节点直接有指针连接,因此在做快照时需要生产一个特殊的映射表(这里叫做 imap),将指针映射为物理地址(文件偏移)。在恢复时,分为两个步骤:1. 构建快照的内存表示,2. 重放WAL恢复到最新状态。首先通过imap恢复内部节点,然后重放WAL应用修改

性能优化

mini page

mini page的优化分为三个封面:范围查询,内存占用以及比较。

(这几个优化点和简直LeanStore一模一样)

buffer pool

内存碎片: 在分配的mini page前使用8个字节作用元数据,存放大小和状态,这个设计最小化了碎片产生(这个因果把人看懵了。前面提到buffer pool有不同大小类别的freelist,内存碎片应该是指部分内存分散在这些freelist里面并且地址不是连续的,这个才是问题吧?)

内存对齐:简单来说,变成的mini page是按照指针长度对其的(8字节),因此对于默认的系统页(4KB)大概率是会出现跨边界的情况,这就造成了额外的页表查询,这里的解法就是使用huge page,减少这种情况的发生,同时huge page也减少了TLB miss

并发淘汰: 前面提到在淘汰是需要剔除临近head指针的mini page然后好增加tail,为了支持并发,允许每个线程并发的开始淘汰,但必须按照顺序完成淘汰,换句话说,head指针只能在所有线程都完成淘汰后才能增加(这里缺乏细节)


个人认为减少写放大靠的是延迟写入,即先修改到mini page,累计到触发条件再落盘,相比于每修改一个记录就落盘应该是有正向影响的;而将单个记录作为热点缓存起来的想法配合变长的mini page才让人眼前一亮。不过文中缺失了一些细节(比如:copy-on-access时,如何确保mapping table找到新的mini page),并且没有看到具体的实现,有一点可惜,希望后面能开源出来吧