面向实践的无锁自适应基数树（OSDI 2026）
原题：ARCTIC: a practical lock-free adaptive radix tree
一句话总结：现有索引通常难以同时提供高吞吐、无锁进展和有序范围扫描；ARCTIC 将边元数据移入父边、用 128-bit CAS 与冻结式节点替换实现原地更新，并在 Chameleon 双路 40 核机器上相对 ART 在 YCSB 七类键分布上取得最高 7.7× 几何平均吞吐提升，在 RocksDB 和 Turso 中分别取得最高 1.40× 和 1.12× 端到端提升，但扫描故意只提供非线性化语义。
问题与动机
内存索引处在键值存储、数据库和缓存的请求关键路径。哈希表吞吐高，却不适合有序范围扫描；skiplist 支持有序访问，但高层节点的缓存局部性和争用限制扩展；ART 的缓存效率较好，却依赖节点级锁。论文把目标定为三个同时成立的性质：高吞吐、lock-free，以及高效的 range/prefix scan。
ARCTIC 基于 ART，但不采用 RCU 或额外映射表来规避并发更新。论文希望把结构修改操作（SMO）压缩为单个原子状态转换，保留紧凑布局和原地更新。它还需要解决 C/C++ 风格手动内存管理下的安全回收问题，因此提出与键空间相关的 hazard keys。
关键观察 / 隐含假设
- 观察 1：ART 的边压缩更新需要同时修改父边和子节点头部。 插入导致边扩展时，ART 的两个位置需要协调；ARCTIC 的布局把边字节和类型信息移到父边，使常见 SMO 可以由一次 128-bit CAS 完成（图 1、图 4、§3.2–§3.3）。
- 依赖假设：目标硬件提供高效的 16B 原子加载和 CAS。
- 可能失效场景：缺少 128-bit 原子指令的平台需要改用锁或多字协议，论文的无锁与性能结论不能直接外推。
- 观察 2：更新通常只需修改最终边，节点级锁会制造不必要的横向和纵向争用。 YCSB-A 中 ARCTIC 平均每次操作只有 0.5 个相关缓存一致性事件，相对 DashMap、FB⁺-tree、Wormhole 和 ART 的几何平均降低分别为 2.6×、3.0×、3.8× 和 1.2×（§4.1）。
- 依赖假设：工作负载以点更新为主，且多个线程访问的键不会长期集中到同一条最终边。
- 可能失效场景：极端热点键或需要频繁结构收缩的删除工作负载仍可能集中争用同一位置。
- 假设 1：键不能是另一个键的前缀。 这是所有该类前缀树实现所依赖的结构前提；整数键和 C 风格字符串自然满足，其他变长键需要加入哨兵字节（§2.2）。
- 证据强度：强。论文的遍历正确性和唯一前缀不变量都显式依赖它。
- 假设 2：非线性化扫描足以满足上层系统。 ARCTIC 的范围和前缀扫描保证不重复、按字典序返回，并覆盖扫描开始前已插入且扫描结束前未删除的键，但不保证线性化（§3.7）。
- 证据强度：中。LSM compaction 通常在无写入时扫描，数据库也可由 MVCC 提供更强语义，但这不是所有用户的默认条件。
核心方法
ARCTIC 将逻辑压缩边直接表示为 16B 结构，边中包含压缩字节、冻结位、子节点类型和指针或值。Node3、Node15、Node47、Node256 均采用 2 的幂大小；Node3 恰好占一条 cache line，Node256 占一页，减少类型判断、分配和伪共享开销（图 5）。这回应了边扩展必须原子化以及硬件布局应可预测的观察。
对于边扩展，系统先在本地构造中间节点，再用一次 CAS 替换原边。对于节点扩展、压缩、边压缩和删除，系统统一采用节点替换：线程先冻结节点内所有可 CAS 位置，使其不可变，再依据冻结后的内容确定性地构造替代节点并 CAS 完成摘链与链接。冻结位解决了“线程已经读到节点、另一线程将其摘链、前一线程仍写入”的竞态。CAS 因冻结失败时，当前线程帮助完成替换，而不是等待原线程，保持 lock-free。
Node47 的头部无法一次 CAS 更新。ARCTIC 增加 last 字段，把数组与长度之间的中间状态变成可由其他线程帮助修复的状态；写线程在追加前先帮助恢复一致性，再 CAS len/last，最后更新数组。读线程不检查这两个字段，因此中间状态不会被读路径观察。
遍历是 wait-free 的，不回溯，也不与冻结交互。插入和删除只在最终边执行 CAS；遇到边不匹配、缺少子节点或节点映射时才执行相应 SMO。优化包括失败前不维护回溯栈、整数键原生字节表示、以及用 SIMD/SWAR 加速节点头部查找。
Hazard keys 用一次发布的操作键近似 hazard pointers：退休分配记录其前缀，若前缀是某线程 hazard key 的前缀则暂不回收。它避免了每次指针解引用都发布和校验指针，也不像 EBR 那样让一个停顿线程阻塞全局回收，但回收效率依赖键分布。
设计取舍
- 原地更新 vs. 复制更新：原地更新减少间接寻址、缓存和分配压力；代价是冻结、帮助和节点替换协议更难验证。
- hazard keys vs. hazard pointers/EBR：hazard keys 的常规访问成本低于 hazard pointers，对线程停顿比 EBR 更局部；代价是高偏斜分布可能使大量退休对象长期无法回收，且每个退休前缀仍需匹配线程键。
- 扫描性能 vs. 一致性语义：系统提供 wait-free 扫描和有序结果，却放弃线性化。依赖上层 LSM 无写扫描或 MVCC 才能安全使用。
- 硬件原子性 vs. 可移植性：128-bit CAS 是正确性的要求，16B 原子加载则是获得合理性能的要求；这限制了平台覆盖范围。
实验与结果
- 在两路 Intel Xeon Platinum 8380、共 80 个物理核、128 GiB DDR4 的 Chameleon 机器上，ARCTIC 在 80 线程、七种键分布的 YCSB 几何平均吞吐相对 ART 从 YCSB-C 的 1.3× 到 YCSB-A 的 7.7×（§4.1、图 7）。
- YCSB-A 中 ARCTIC 平均每操作 0.5 个缓存一致性事件；相对 DashMap、FB⁺-tree、Wormhole、ART 的几何平均降低为 2.6×、3.0×、3.8×、1.2×（§4.1）。
- ARCTIC 在 80 线程后继续保持吞吐，而部分锁实现出现下降，支持其在超额订阅下的 lock-free 进展论断；但这是固定 100M 操作、线程数最高 160 的实验边界（图 7）。
- 用 ARCTIC 替换 RocksDB 默认 skiplist memtable 后，100M 个随机 20B 键、400B 值的 bulk load 最高达到 1.40×；替换 Turso 的两个 skiplist 后，多写事务基准最高达到 1.12×（§4.2、表 3）。更高线程数时端到端收益被其他瓶颈稀释。
- 在 rand-u64、Zipf 0.99、100 线程的 SMR 压力测试中，hazard keys 相对 EBR/Hyaline 将峰值未回收对象降低 5.6×–19×；在 80 线程理想条件下，YCSB-A/B 吞吐相对 crossbeam-epoch 下降 7.2%/6.3%（§4.3、图 9）。
- 消融显示，optimistic traversal 主要帮助插入（seq-u64 约 1.3×、随机整数约 1.2×），原生整数键改善所有操作；SIMD 对稠密 Node256 的收益很小，扫描受内存带宽限制，三项优化合计低于 1.05×（§4.4、图 10）。
论断—证据表
| 论断 | 证据 | 评测边界 | 置信度 |
|---|---|---|---|
| ARCTIC 能在高并发点操作中超过 ART 及若干锁实现 | YCSB 吞吐与缓存一致性计数（§4.1、图 7） | 双路 40 核 Intel、100M 操作、六类工作负载和六类键分布 | 强 |
| 冻结和帮助协议支持 lock-free 进展 | CAS-F 帮助路径、形式化不变量与 80–160 线程吞吐（§3.5、§3.8、图 7） | 只给出证明草图；未覆盖故障注入、任意调度和更大集群 | 中 |
| hazard keys 在低到中等偏斜下兼顾吞吐和回收效率 | 与 crossbeam-epoch、seize 的峰值垃圾和吞吐比较（§4.3、图 9） | rand-u64、Zipf 参数有限，结果依赖前缀分布 | 中 |
| 集成索引能改善真实系统端到端吞吐 | RocksDB/Turso 替换 skiplist 的 bulk-load 测试（§4.2、表 3） | 两个系统、写密集基准，其他瓶颈在高并发时主导 | 中 |
批判性分析
论证链条
论文的主链条较闭合：ART 的多位置 SMO 导致锁争用，重新布局后可用单个宽 CAS 表达；冻结使节点替换前内容稳定，帮助机制避免等待；实验则显示点更新和超额订阅下的收益。Hazard keys 是另一条独立链条，收益来自逻辑键与可达指针之间的前缀关系。
“第一个超过锁实现的无锁有序索引”仍受基线选择和硬件影响。论文排除了面向 RDMA 的索引，也没有与所有高性能锁耦合 B+-tree 在相同实现基础上比较。结果支持“在所测配置上实用”，不足以推出所有数据库工作负载都更快。
假设压力测试
字符串键深度随键长线性增加；论文明确观察到 ARCTIC 的字符串读性能随树深下降。长 URL、长邮箱或高比例前缀共享会改变节点深度和回收保护范围。极端 Zipf 偏斜下 hazard keys 可能保留对象 indefinitely，论文的图 9 已显示其相对优势随偏斜减弱。
系统依赖 128-bit 原子操作。论文在 x86 和支持 LSE 的 ARM 上给出硬件背景，但实验只使用 Intel 双路机器。NUMA 拓扑、跨 socket CAS、不同 allocator 和未来 CPU 的原子指令成本可能改变结果。
扫描非线性化是数据库集成的潜在边界。论文用 LSM 无写扫描和 MVCC 作为可接受场景，但没有展示并发写入下上层如何消费扫描结果，也没有提供线性化快照选项。
实验可信度
YCSB 覆盖读、更新、插入和扫描，并加入 IPv4、Twitter ID、邮箱、URL 等真实来源键分布；线程数超过物理核数也能检验进展保证。RocksDB 和 Turso 集成使索引微基准与端到端结果相互印证。
不足是实验集中于单机、固定 100M 操作和有限模型化工作负载。没有报告 P99、功耗、分配器替换、长时间内存增长或故障恢复。扫描结果主要给吞吐，没有针对非线性化语义的正确性压力测试。对删除和频繁节点压缩的代价也缺少独立基准。
系统性缺陷
节点冻结和递归帮助增加了实现与验证复杂度；论文给出正确性和 lock-free 的证明草图，但没有说明形式化验证或生产诊断工具。hazard keys 需要依据请求键扫描退休对象，线程数量增加后回收器本身的成本可能上升。索引只支持不允许前缀嵌套的键编码，API 使用者必须承担编码约束。论文未讨论故障恢复、持久化、跨进程共享和运行时可观测性。
局限与后续工作
- 局限 1：128-bit CAS 限制了硬件与平台可移植性；应在 ARM、不同 NUMA 机器和不具备宽原子操作的平台上分别测量性能与替代协议成本。
- 局限 2：hazard keys 对键分布敏感；可验证的后续方向是实现 hazard key 与 EBR 的混合回收器，测量 Zipf 1.1–1.5、突发热点和停顿线程下的内存上界。
- 局限 3：范围扫描非线性化；应增加可选快照或与 MVCC 版本过滤结合的实现，并比较其尾延迟和内存成本。
- 局限 4：删除、节点压缩和长时间运行的内存行为覆盖不足；应运行混合插入/删除、持续数小时的生产 trace，并报告 P99、峰值内存和恢复时间。