存算分离的B+树论文整理

1

An, Hang, Fang Wang, Dan Feng, Xiaomin Zou, Zefeng Liu, and Jianshun Zhang. “Marlin: A concurrent and write-optimized b+-tree index on disaggregated memory.” In Proceedings of the 52nd International Conference on Parallel Processing, pp. 695-704. 2023.

本文主要解决了在存算分离（Disaggregated Memory）架构下，B+树分布式索引并发写入性能低、同步开销大、可扩展性差的问题。现有方案多采用基于RDMA CAS的粗粒度独占锁，导致高并发写入时同步冲突严重，尾延迟高，吞吐量低。

核心 insight：

• 传统的独占锁（如RDMA CAS实现）会极大限制并发，尤其在高冲突场景下，导致性能崩溃。
• 存算分离架构下，必须用更细粒度、更高效的同步机制，充分利用RDMA原语，提升并发写入能力。
• 通过区分不同类型操作（IDU与SMO），并采用多态锁机制，可以兼顾一致性与高并发。

具体方法：

• RDMA-IDU-friendly并发算法： 对于同一叶节点的不同entry，多个IDU（Insert/Update/Delete）操作可并发进行，不再用独占锁，而是用RDMA CAS原子性地修改Di-pointer，实现细粒度同步。
• 三态节点锁（Spear）： 设计了基于RDMA FAA的三态锁，区分节点空闲、IDU共享、SMO独占三种状态。IDU可共享锁，SMO需独占锁，避免IDU和SMO互相干扰，提升并发性和公平性。
• 关键路径压缩： 通过乐观合并操作，将原本串行的6次RDMA操作压缩为3批次，减少网络往返次数和CQ轮询时间，降低写入延迟。
• 叶节点结构优化： 叶节点entry中的数据指针（Di-pointer）指向最新数据，entry无序存储，避免Insert/Delete时的移动操作，进一步提升写入效率。

三态锁（Spear）是 Marlin 论文提出的一种专为存算分离架构下 B+树并发控制设计的节点锁机制。它的核心思想是：

用一个整数变量，通过原子加减操作（RDMA FAA），区分节点的三种状态，实现高效的并发写入与结构修改操作的协调。

三态锁的三种状态

• S0：初始状态 锁值为 0，节点空闲，无任何操作进行。
• S1：IDU 共享状态 锁值 ≥ 1，表示有一个或多个 IDU（Insert/Update/Delete）操作正在进行，多个写操作可以并发执行。
• S2：SMO 独占状态 锁值 < -T（T为阈值），表示有结构修改操作（SMO，如分裂/合并）独占节点，其他操作需等待。

这里作者似乎没有细说锁的具体使用细节，但可以推测：

• 所有的加锁/解锁操作都通过 RDMA FAA 原子操作实现，不存在与其他节点的网络通信开销。
• 客户端可以通过RDMA FAA的返回值判断当前锁的状态，从而判断加锁是否成功
• 如果RDMA FAA返回的值表示当前的加锁操作需要等待，客户端应该自己回退，修复锁值，然后稍后重试

---

2

未完待续。。。