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 cache或phantom 那么不需要落盘（这里先列出所有的type值：insert、cache(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)，并且没有看到具体的实现，有一点可惜，希望后面能开源出来吧