李勇_内核块设备缓存的高性能Btree索引设计与实现5.pdf

1、Linux内核块设备缓存的高性能Btree索引设计与实现Coly Li Bcache子系统maintainer飞牛NAS内核架构师2025年12月13日我是谁Linux内核bcache维护者，飞牛NAS内核架构师。曾作为第一位工程师加入并创建了淘宝Linux内核组（现阿里云Linux操作系统团队前身）以Bcache子系统为例Bcache是Linux内核中的块设备缓存系统，可以在使用慢速机械硬盘存储数据的同时，将热数据缓存在高速固态硬盘中，能够明显提高随机数据的访问性能。Bcache虚拟设备后端块设备卸载SSD挂载可用的缓存模式-回写-写透-写绕过-不缓存缓存系统中首先要有一个方法来确定数据对象

2、是否已经被缓存。Linux内核中，目前性能最好的是Bcache子系统使用的基于LSM(Log-Structured Merge-Tree)改进的Btree索引实现。Bcache对LSM-Tree的改进Bcache对LSM-Tree的改进，主要考虑的场景是，1，为了优化IO效率，单节点中索引key的数量大（超过1万个是常见的）2，充分利用到CPU cacheline的性能特性需要应对的挑战有，1，对于Btree节点中的key的检索，不能用传统的线性查找。2，要考虑到新key的插入，过期key的失效。3，构建一个平衡二叉树（进行二分查找）并不总是能够成功的。4，二分查找在内存中的前后跳跃对于CPU

3、缓存并不友好。接下来会介绍Bcache是如何组织了一个在存储和索引两方面都高效的Btree，来进行缓存数据查找。索引key的数据机构 bkeyBcache定的key数据结构定义在drivers/md/bcache/bcache_ondisk.h中23 struct bkey 24 _u64 high;25 _u64 low;26 _u64 ptr;27;struct bkey数据结构直接存储在高速缓存设备的元数据bucket中，同时直接被读取到内存中建立Btree节点进行索引。在Btree中用读IO请求的LBA检索bkey-low，来确定数据是否被缓存。如果被缓存则根据ptr0指示的LBA从高

4、速缓存设备上将已缓存数据读出返回给上层。1）缓存副本数量（固定为单副本）2）数据校验和标志位3）数据是否为脏4）数据大小5）后端磁盘设备编号被缓存数据块对应在后端（磁盘）设备上的LBA被缓存数据块在高速缓存设备（固态硬盘）上的LBA（ptr0)和数据块校验和(ptrn)写时复制的分配策略Bcache中分配数据和元数据的基本单位都是bucket，通常大小为128KB 1MB。Btree节点在固态硬盘上和在内存中都是占用一个bucket的大小。对于数据：新的缓存数据被追加写入到一个bucket中，直到这个bucket被写满再分配新的。对于Btree节点：空间也是追加式的分配，除非该节点key数量过

5、多（超过2/3桶空间）要被分裂。当上层文件系统对某个已缓存的数据进行修改时，Bcache不会修改已经缓存的旧数据块，而是将新的数据副本追加写入到某一个数据bucket中；同样会产生新的bkey并插入到对应btree节点的unwritten bset中。Btree节点的样子Bcache的数据分配以bucket为单位，通常大小为128KB 1MB。这也是一个Btree节点的大小。一个Btree节点中包括多个Bset，一个Bset中包含多个Bkey。这些数据结构以相同的格式既保存在存储介质上，也读取到内存中直接使用。struct btree_node头部空闲空间Bset头部struct bkey一个

6、Bset的样子在一个Bset中的所有的Bkey都是严格增序。内存中的Bset分为两类：written和unwritten一旦某一个Bset被刷新到了高速块设备上，他就是written bset。Bkey的插入和删除操作，只能在unwritten的bset上进行。当一个bset很大时，常用的二分查找就会变慢。因此bcache为每一个bset创建了一个辅助查找树来加速bset中特定key的查找。在Linux内核中这是Bcache的小创新，稍后会着重介绍。struct bset头部当Btree节点中有多个Bset时多个bset中可能会含有相同缓存数据的bkey，由于新的插入删除操作只能在最后的unw