管理 Mini-Page Memory：Bf-Tree 背后的 Buffer Pool

Source: Dev.to

你好，我是Maneshwar。 我正在开发 FreeDevTools online——一个免费、开源的中心，汇集所有开发工具、作弊代码和 TLDR，集中在一个地方，让开发者无需在网络上四处搜索即可找到并使用所需的资源。

回顾

昨天我们研究了 mini‑pages 和 pinned inner nodes 如何重塑 B‑Tree 的执行路径，使热点记录保持在 CPU 附近，并将争用从关键路径中移除。

今天我们聚焦于一个不太显眼但同样关键的部分：

Bf‑Tree 如何管理 Mini‑Page 内存

一旦 Mini‑Page 存在，真正的挑战就开始了：它们是 可变大小、可变更 且 高度并发 的。传统的基于页面的缓冲池根本不适用。

本文将逐步说明 Bf‑Tree 如何为 Mini‑Page 设计 专用缓冲池，以及为什么 环形缓冲区 成为合适的抽象。

为什么 Mini‑Pages 需要不同的缓冲池

Mini‑pages 不是 固定大小的磁盘页。它们：

• 动态增长和收缩
• 经常被访问和修改
• 仅在内存中存在，直到被驱逐

这些特性带来了三个根本性挑战：

1. 内存管理 – 在避免碎片的同时跟踪每个 mini‑page 的精确位置。
2. 热度感知的驱逐 – 决定哪些 mini‑pages 保持在内存中，哪些被刷新到磁盘。
3. 大规模并发 – 允许多个线程安全地分配、驱逐和回收内存，同时仍能饱和 SSD 带宽。

传统的分配器和 LRU‑style 缓冲池在这里会遇到困难。Bf‑Tree 采用了不同的方式。

核心思想：用于小页面的循环缓冲区

Bf‑Tree 将所有小页面存储在 大型循环缓冲区 中。

• 分配 → 在 尾部 追加
• 回收 → 从 头部 移除

当缓冲区填满时，驱逐线性向前移动。该设计受 FASTER 的混合日志 启发，但针对小页面和 B‑Tree 语义进行了适配。

好处

• 分配快速且顺序进行。
• 驱逐可预测。
• 碎片化最小化。

一个天真的循环缓冲区会过于激进地驱逐热点小页面，因此 Bf‑Tree 进一步细化了设计。

三个区域，而非一个：保护热点小页

为了避免频繁访问的小页被驱逐，循环缓冲区使用 三个移动指针 进行划分：

• 尾部地址
• 二次机会地址
• 头部地址

这些指针形成了两个逻辑区域：

原位更新区域（约 90 %）

• 小页可以直接修改。
• 热点小页倾向于停留在此。
• 大多数更新发生在该区域。

访问时复制区域（约 10 %）

• 即将被驱逐的小页位于此。
• 访问时，它们会 复制到尾部，从而获得一次“二次机会”。

该机制防止热点小页向头部漂移并被驱逐，无需复杂的 LRU 记录。

处理增长、收缩和复用

Mini‑pages 在吸收写入时经常会改变大小。Bf‑Tree 通过 多个空闲列表（按大小类别分组）来处理：

1. 分配 一个新的 mini‑page 当页面增长或收缩时。
2. 复制 内容到新的分配。
3. 将 旧的内存 归还 到相应的空闲列表。

这使得分配快速，并随时间减少碎片化。

循环缓冲区 API：简约而足够

缓冲池提供了一个针对小页面量身定制的精简 API。

分配

内存从以下来源获取：

• 空闲列表（如果有匹配大小的），或
• 尾部（通过前移）。

如果尾部过于接近头部，分配将失败并触发驱逐。

驱逐

驱逐总是从靠近头部的位置开始：

1. 将脏记录合并回磁盘上的叶子页。
2. 更新映射表。
3. 头指针前移。

多线程可以并发驱逐，但指针的前移保持有序。

释放

释放的内存会返回到对应大小的空闲列表以供重用。
没有分页，没有每页锁，没有 LRU 队列。

性能关键优化

因为该缓冲区位于热点路径上，若干底层优化至关重要。

最小碎片化

• 小页紧密相连。
• 每次分配仅携带 8 字节的元数据。
• 不需要对齐到页边界，从而保持内存密集且可预测。

大页用于TLB效率

小页可能跨越 4 KB 边界。为避免过多的页表遍历：

• 循环缓冲区使用 大页 作为后备。
• 这显著降低了 TLB 压力。

并行驱逐与有序进度

驱逐必须顺序推进头指针，但工作本身可以并行：

• 线程并行驱逐小页。
• 只有在所有之前的驱逐完成后，头指针才向前移动。

这在保持正确性的同时，仍然利用了并行 I/O。

为什么这种设计有效

Mini‑pages 已经改变了 叶子节点 的行为。这个缓冲池确保它们能够扩展。

整体设计：

• 避免分配器碎片化。
• 保持热点 mini‑pages 常驻，无需 LRU 开销。
• 支持大规模并发。
• 高效地将冷数据流式写入磁盘。

最重要的是，它与 Bf‑Tree 的理念保持一致：

将关注点分离，并独立优化每条路径。

• 内部节点： 快速、固定、无争用的遍历。
• 叶子页： 稳定的磁盘结构。
• Mini‑pages： 灵活、可适应的内存工作集。

缓冲池将所有部分结合在一起，为 Bf‑Tree 的 mini‑page 架构提供高性能、低争用的基础。

# FreeDevTools

`r` pool is what makes that separation viable in practice.

[![FreeDevTools](https://media2.dev.to/dynamic/image/width=800,height=,fit=scale-down,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fo5e57lh7rtwwwe2d694n.png)](https://hexmos.com/freedevtools/)

👉 **Check out:** [FreeDevTools](https://hexmos.com/freedevtools/)

Any feedback or contributions are welcome!  
It’s online, open‑source, and ready for anyone to use.

⭐ **Star it on GitHub:** [FreeDevTools](https://github.com/HexmosTech/FreeDevTools)