只有登录用户才可以评论
今天聊一个特别硬核的话题——微软研究院搞出来的一个叫BF-Tree的东西，说白了就是让数据库跑得更快的黑科技。这玩意儿是用Rust写的，作者是个叫zhihanz的工程师，把整个实现过程掰开了揉碎了讲了一遍。我看完觉得挺有意思，给你们翻译翻译，什么叫"用Rust手搓一个比内存还大的数据库索引"。
你们用过数据库吧？数据量小的时候啥事没有，往内存一塞，查询快得飞起。但一旦数据比内存还大，麻烦就来了。
传统数据库用的是B树索引，叶子节点固定4KB一个。你改一条100字节的记录，得先把整个4KB从磁盘读进内存，改完再写回去。这叫"写放大"——实际改了100字节，磁盘写了4096字节，放大40倍。就像你为了修厨房一盏灯，把整个房子重新装修了一遍。
更坑的是缓存。4KB的页作为缓存单位，太糙了。现实里数据访问是极度不均匀的，80%的请求可能只打向33%的数据。但问题是，这33%的热数据散落在各个4KB页里，每个页可能只有3条记录是热的，另外37条是凉的。缓冲池没办法，只能把整个4KB都缓存下来。这就好比你为了冰箱里三瓶可乐，把整个双开门冰箱都搬进了卧室。
微软那帮人算了一笔账：10万条热数据，每条100字节，实际热数据就10MB。但缓冲池得缓存10万个4KB页，400MB。内存就这么被浪费了，能缓存的键范围少了，更多请求得去敲磁盘，慢得要死。
他们的脑洞是：如果磁盘页大小等于记录大小，写放大和缓存浪费不就都没了？BF-Tree就是这个思路——在磁盘页前面加个小 buffer，叫"mini-page"，64字节到4096字节不等，只装值得缓存的记录。
想象一个40条记录的磁盘页，3条热。传统做法：缓存整个4KB。BF-Tree做法：搞个256字节的mini-page，只装这3条。写操作直接怼mini-page，不用碰磁盘。读操作先查mini-page，miss了再去磁盘页找。
mini-page有三个绝活：
缓冲写入。十条写同一个键范围，传统B树得写十次4KB，BF-Tree就在内存里攒着，mini-page满了或者被淘汰了，一次性合并回磁盘。写放大从40倍降到2倍。
缓存热记录。读miss了，可以把那条记录单独提进mini-page当干净缓存。不想要了直接扔，不用写磁盘。一条热记录就占它本身那么大地方，不是4KB。
按需长大。一个键范围读得多了，mini-page从128字节长到256、512、2048，最后到4096变成完整内存页。范围扫描照样有局部性优势。
关键是这玩意儿大小不固定。冷的键范围128字节意思一下，热的给2KB。同样32MB内存，覆盖的键范围比固定4KB的缓冲池多得多。
这里开始硬核了。BF-Tree没用Rust默认的内存分配器，自己手搓了一个。
为啥？四个原因：
要连续内存。所有mini-page得塞一个大数组里，指针就是数组偏移，计算简单。
要按尺寸回收。256字节的块死了，下一个256字节的分配直接 reuse，不用跟系统 allocator 扯皮。系统 allocator 可能把你释放的256字节拆成两半，或者跟隔壁合并成512，不适合。
每块要元数据。8字节头，记录状态和大小。系统 allocator 的元数据不对外开放。
要淘汰顺序。FIFO淘汰，老的先死。系统 allocator 不管这个。
所以BF-Tree启动时跟系统要一大块连续内存（默认32MB，2的幂次），之后自己管自己。全局 allocator 再也不打扰。
三个指针管这个环形缓冲区：
head_addr
evicting_addr
tail_addr
head <= evicting <= tail，新分配往前拱tail，淘汰从head往前啃。
head <= evicting <= tail
这里有个很巧的设计。指针不是物理偏移，而是单调递增的逻辑地址。32MB容量，mask是0x1FFFFFF，逻辑地址0x3000100映射到物理偏移0x1000100。
0x1FFFFFF
0x3000100
0x1000100
为啥不直接用物理偏移？并发环境下多个线程原子更新head和tail，物理偏移会wrap around（到头了回0），出现ABA问题：线程A读tail=100，线程B分配一堆把tail又干到100，A的CAS成功但实际上缓冲区状态完全变了。逻辑地址永远递增，两个地址相等只可能是同一个分配。
物理内存到头了怎么办？剩余空间不够分配，写个tombstone标记跳过，从0重新开始。最多浪费4096字节。
每个分配前面8字节头，包含大小和状态。状态是核心：
两个RAII guard管状态转换：
CircularBufferPtr，分配时返回。持有期间状态是NotReady，Drop时CAS到Ready——"发布"这块内存。如果中间panic了，Drop照样跑，不会卡在NotReady。
TombstoneHandle，回收时获取。CAS从Ready抢到BeginTombstone，获得独占权。Drop时回退到Ready——安全网，万一回收流程崩了，块还能用。
成功回收时，要 suppress TombstoneHandle的Drop，否则它会把状态改回Ready，跟你想要的FreeListed/Tombstone冲突。用std::mem::forget，安全函数，Rust里泄漏内存不是UB。
std::mem::forget
128字节装不下了，要长成256字节。流程：
跟淘汰器竞争？CAS只会有一个赢家。赢家拷贝数据，输家重试。
空闲列表是侵入式的——死块的数据区直接当链表节点用，不额外分配。按尺寸分类，128的死块进128的桶，下次alloc(128)直接捞。
内存满了，alloc返回Full，调用线程自己当淘汰器。没有后台线程，谁需要空间谁去腾。
两阶段协议，三个指针：
第一阶段（持环形缓冲区锁）：evicting_addr往前拱一块，放锁。
第二阶段（不持锁，慢操作）：
第三阶段（持锁）：head_addr往前拱过所有Evicted块。
磁盘IO要毫秒级，第二阶段不持环形缓冲区锁，其他线程还能分配。页表锁只卡同一个叶子页的写入者。
Copy-on-access：缓冲区前10%是"copy-on-access区"，老的、快死的。任何操作碰到这区的块，直接拷贝到tail，相当于"救"它一命。不是真LRU，不用每次访问都更新链表——那玩意儿并发下是锁灾难。只救濒死的，大部分操作零开销。
内节点：seqlock。读之前快照版本号，读完再查。变了就重试。写锁用bit 1标记，获取释放各加2，完整写周期版本+4。读远多于写，让读线程承担重试成本。
页表项：自定义RwLock，支持try_upgrade。读锁持有中想升级写锁？标准库不支持。这里用AtomicU32编码：0未锁，bit 0写者等待，偶数>=2是读者计数，MAX是写锁。try_upgrade CAS 2到MAX，成功就升级，失败返回读锁继续用。
错误类型驱动重试：
没有最大重试次数。CircularBufferFull淘汰完就好；NeedRestart下次遍历时aggressive_split=true，沿途预分裂满的节点；Locked指数退避，先自旋后yield。
随机线程测试不靠谱，OS调度几乎不会踩到那个纳秒级窗口。
Shuttle接管调度，每个同步点决定下一个跑谁。同样测试跑几千次不同调度。
BF-Tree的做法：全代码走crate::sync模块，根据feature flag换std::sync或shuttle::sync。生产零开销，测试时全面替换。
crate::sync
std::sync
shuttle::sync
PCT调度器：聚焦少抢占的调度，因为大多数bug只需几次线程切换就能触发。4个调度器各跑4000轮，16000种调度探索。
找到bug？保存调度文件，replay_from_file精确复现。设断点，单步看竞态条件怎么发生的。
自旋等待的地方插yield_now()，给Shuttle切线程的机会。
263行unsafe，总共14000行Rust。unsafe集中在环形缓冲区指针运算、锁实现、LeafNode布局。树逻辑、重试循环、状态机、增长淘汰协议全是safe Rust，靠guard保证。
几个通用模式：
RAII guard管状态机。Drop永远做保守安全的事（发布或回退），成功路径forget掉Drop，显式做前进转移。任何路径状态机都合法。
类型化错误当控制流。每种错误对应不同恢复策略，编译器强制穷举匹配。
编译时换测试基础设施。sync模块feature flag切换，生产零成本，CI系统测并发。
乐观读+锁验证。先无锁读，基于它做事，再锁下复查。变了就重试。淘汰回调、内节点遍历、读提升都用这模式。
这些模式在哪都通用——GPU缓冲区管理、网络包池、共享内存IPC、其他数据库引擎。数据结构变，所有权问题不变。
论文：BF-Tree: A Read-Write-Optimized Concurrent Larger-Than-Memory Range Index，VLDB 2024。
代码：Microsoft bf-tree on crates.io。
测试工具：AWS Labs shuttle on GitHub。
今天聊一个特别硬核的话题——微软研究院搞出来的一个叫BF-Tree的东西，说白了就是让数据库跑得更快的黑科技。这玩意儿是用Rust写的，作者是个叫zhihanz的工程师，把整个实现过程掰开了揉碎了讲了一遍。我看完觉得挺有意思，给你们翻译翻译，什么叫"用Rust手搓一个比内存还大的数据库索引"。
先说说为啥要搞这玩意儿
你们用过数据库吧？数据量小的时候啥事没有，往内存一塞，查询快得飞起。但一旦数据比内存还大，麻烦就来了。
传统数据库用的是B树索引，叶子节点固定4KB一个。你改一条100字节的记录，得先把整个4KB从磁盘读进内存，改完再写回去。这叫"写放大"——实际改了100字节，磁盘写了4096字节，放大40倍。就像你为了修厨房一盏灯，把整个房子重新装修了一遍。
更坑的是缓存。4KB的页作为缓存单位，太糙了。现实里数据访问是极度不均匀的，80%的请求可能只打向33%的数据。但问题是，这33%的热数据散落在各个4KB页里，每个页可能只有3条记录是热的，另外37条是凉的。缓冲池没办法，只能把整个4KB都缓存下来。这就好比你为了冰箱里三瓶可乐，把整个双开门冰箱都搬进了卧室。
微软那帮人算了一笔账：10万条热数据，每条100字节，实际热数据就10MB。但缓冲池得缓存10万个4KB页，400MB。内存就这么被浪费了，能缓存的键范围少了，更多请求得去敲磁盘，慢得要死。
他们的脑洞是：如果磁盘页大小等于记录大小，写放大和缓存浪费不就都没了？BF-Tree就是这个思路——在磁盘页前面加个小 buffer，叫"mini-page"，64字节到4096字节不等，只装值得缓存的记录。
mini-page这玩意儿怎么玩
想象一个40条记录的磁盘页，3条热。传统做法：缓存整个4KB。BF-Tree做法：搞个256字节的mini-page，只装这3条。写操作直接怼mini-page，不用碰磁盘。读操作先查mini-page，miss了再去磁盘页找。
mini-page有三个绝活：
缓冲写入。十条写同一个键范围，传统B树得写十次4KB，BF-Tree就在内存里攒着，mini-page满了或者被淘汰了，一次性合并回磁盘。写放大从40倍降到2倍。
缓存热记录。读miss了，可以把那条记录单独提进mini-page当干净缓存。不想要了直接扔，不用写磁盘。一条热记录就占它本身那么大地方，不是4KB。
按需长大。一个键范围读得多了，mini-page从128字节长到256、512、2048，最后到4096变成完整内存页。范围扫描照样有局部性优势。
关键是这玩意儿大小不固定。冷的键范围128字节意思一下，热的给2KB。同样32MB内存，覆盖的键范围比固定4KB的缓冲池多得多。
自己造轮子：环形缓冲区分配器
这里开始硬核了。BF-Tree没用Rust默认的内存分配器，自己手搓了一个。
为啥？四个原因：
要连续内存。所有mini-page得塞一个大数组里，指针就是数组偏移，计算简单。
要按尺寸回收。256字节的块死了，下一个256字节的分配直接 reuse，不用跟系统 allocator 扯皮。系统 allocator 可能把你释放的256字节拆成两半，或者跟隔壁合并成512，不适合。
每块要元数据。8字节头，记录状态和大小。系统 allocator 的元数据不对外开放。
要淘汰顺序。FIFO淘汰，老的先死。系统 allocator 不管这个。
所以BF-Tree启动时跟系统要一大块连续内存（默认32MB，2的幂次），之后自己管自己。全局 allocator 再也不打扰。
三个指针管这个环形缓冲区：
head_addr：最老存活数据evicting_addr：正在淘汰的边界tail_addr：下次分配位置head <= evicting <= tail，新分配往前拱tail，淘汰从head往前啃。逻辑地址 vs 物理地址
这里有个很巧的设计。指针不是物理偏移，而是单调递增的逻辑地址。32MB容量，mask是
0x1FFFFFF，逻辑地址0x3000100映射到物理偏移0x1000100。为啥不直接用物理偏移？并发环境下多个线程原子更新head和tail，物理偏移会wrap around（到头了回0），出现ABA问题：线程A读tail=100，线程B分配一堆把tail又干到100，A的CAS成功但实际上缓冲区状态完全变了。逻辑地址永远递增，两个地址相等只可能是同一个分配。
物理内存到头了怎么办？剩余空间不够分配，写个tombstone标记跳过，从0重新开始。最多浪费4096字节。
六状态机：一个块的一生
每个分配前面8字节头，包含大小和状态。状态是核心：
两个RAII guard管状态转换：
CircularBufferPtr，分配时返回。持有期间状态是NotReady，Drop时CAS到Ready——"发布"这块内存。如果中间panic了，Drop照样跑，不会卡在NotReady。
TombstoneHandle，回收时获取。CAS从Ready抢到BeginTombstone，获得独占权。Drop时回退到Ready——安全网，万一回收流程崩了，块还能用。
成功回收时，要 suppress TombstoneHandle的Drop，否则它会把状态改回Ready，跟你想要的FreeListed/Tombstone冲突。用
std::mem::forget，安全函数，Rust里泄漏内存不是UB。增长路径：mini-page长大
128字节装不下了，要长成256字节。流程：
跟淘汰器竞争？CAS只会有一个赢家。赢家拷贝数据，输家重试。
空闲列表是侵入式的——死块的数据区直接当链表节点用，不额外分配。按尺寸分类，128的死块进128的桶，下次alloc(128)直接捞。
淘汰：mini-page的死法
内存满了，alloc返回Full，调用线程自己当淘汰器。没有后台线程，谁需要空间谁去腾。
两阶段协议，三个指针：
第一阶段（持环形缓冲区锁）：evicting_addr往前拱一块，放锁。
第二阶段（不持锁，慢操作）：
第三阶段（持锁）：head_addr往前拱过所有Evicted块。
磁盘IO要毫秒级，第二阶段不持环形缓冲区锁，其他线程还能分配。页表锁只卡同一个叶子页的写入者。
Copy-on-access：缓冲区前10%是"copy-on-access区"，老的、快死的。任何操作碰到这区的块，直接拷贝到tail，相当于"救"它一命。不是真LRU，不用每次访问都更新链表——那玩意儿并发下是锁灾难。只救濒死的，大部分操作零开销。
并发控制：乐观锁和版本号
内节点：seqlock。读之前快照版本号，读完再查。变了就重试。写锁用bit 1标记，获取释放各加2，完整写周期版本+4。读远多于写，让读线程承担重试成本。
页表项：自定义RwLock，支持try_upgrade。读锁持有中想升级写锁？标准库不支持。这里用AtomicU32编码：0未锁，bit 0写者等待，偶数>=2是读者计数，MAX是写锁。try_upgrade CAS 2到MAX，成功就升级，失败返回读锁继续用。
错误类型驱动重试：
没有最大重试次数。CircularBufferFull淘汰完就好；NeedRestart下次遍历时aggressive_split=true，沿途预分裂满的节点；Locked指数退避，先自旋后yield。
怎么测并发：Shuttle
随机线程测试不靠谱，OS调度几乎不会踩到那个纳秒级窗口。
Shuttle接管调度，每个同步点决定下一个跑谁。同样测试跑几千次不同调度。
BF-Tree的做法：全代码走
crate::sync模块，根据feature flag换std::sync或shuttle::sync。生产零开销，测试时全面替换。PCT调度器：聚焦少抢占的调度，因为大多数bug只需几次线程切换就能触发。4个调度器各跑4000轮，16000种调度探索。
找到bug？保存调度文件，replay_from_file精确复现。设断点，单步看竞态条件怎么发生的。
自旋等待的地方插yield_now()，给Shuttle切线程的机会。
收尾
263行unsafe，总共14000行Rust。unsafe集中在环形缓冲区指针运算、锁实现、LeafNode布局。树逻辑、重试循环、状态机、增长淘汰协议全是safe Rust，靠guard保证。
几个通用模式：
RAII guard管状态机。Drop永远做保守安全的事（发布或回退），成功路径forget掉Drop，显式做前进转移。任何路径状态机都合法。
类型化错误当控制流。每种错误对应不同恢复策略，编译器强制穷举匹配。
编译时换测试基础设施。sync模块feature flag切换，生产零成本，CI系统测并发。
乐观读+锁验证。先无锁读，基于它做事，再锁下复查。变了就重试。淘汰回调、内节点遍历、读提升都用这模式。
这些模式在哪都通用——GPU缓冲区管理、网络包池、共享内存IPC、其他数据库引擎。数据结构变，所有权问题不变。
论文：BF-Tree: A Read-Write-Optimized Concurrent Larger-Than-Memory Range Index，VLDB 2024。
代码：Microsoft bf-tree on crates.io。
测试工具：AWS Labs shuttle on GitHub。