Lessons from BF-Tree: Building a Concurrent Larger-Than-Memory Index in Rust
3 months ago
- #database
- #concurrency
- #performance
- BF-Tree采用可变大小的迷你页（64-4096字节）设计，相比传统4KB页缓存可降低写入放大和内存浪费
- Rust实现采用六状态机的环形缓冲分配器，通过RAII守卫、乐观锁和确定性并发测试确保可靠性
- 迷你页具备三重功能：写缓冲、热记录缓存、扫描负载动态扩容，根据访问模式优化内存使用
- 该设计将内存表示与磁盘格式解耦，使BF-Tree能针对工作集而非物理页布局进行优化
- 基准测试显示：BF-Tree点查询比B树/LSM快2倍，写入比B树快6倍，扫描比RocksDB快2.5倍
- 通过CircularBufferPtr和TombstoneHandle等RAII守卫管理生命周期状态，确保安全转换和内存回收
- 并发控制采用内节点的乐观版本锁，页表项使用支持try_upgrade的自定义读写锁，最大限度减少竞争
- 测试阶段使用Shuttle进行系统性并发测试，通过探索线程交错执行来发现难以复现的bug
- 核心模式包括：状态机的RAII守卫、控制重试流程的类型化错误、可编译期切换的测试基础设施