让非对称 RDMA 锁恢复公平的 FARLock（OSDI 2026）
原题：FARLock: Asymmetric RDMA Locking Made Fair
一句话总结：现有非对称 RDMA 锁用本地队列和远程队列消除本地请求的 loopback，却会打乱到达顺序；FARLock 用跨两条队列的 ticket 顺序和 MCS 式 handover 恢复 FIFO，在 10 节点集群上降低尾延迟，并让 Sherman 的查询尾延迟最多降低 14×。
问题与动机
RDMA 锁可以让远程请求通过 RNIC 直接操作锁所在节点的内存。问题在于，RNIC 的原子操作与远端 CPU 的普通访问之间没有共同的原子性保证。若本地线程也访问同一个锁，就必须把本地操作绕回 RNIC；这会把约 100 ns 的本地访问拖到微秒级。
ALock 将本地请求和远程请求放入两条队列，避免本地请求使用 loopback。但两类请求交替交接锁，后来到达的请求可能插队，早到的远程请求因此产生很高的等待时间。论文的核心目标是同时保留非对称路径和严格的先到先服务。
关键观察 / 隐含假设
- 观察 1：不公平的跨队列重排会放大尾延迟。 在 12 个本地请求先于 12 个远程请求到达的受控实验中，ALock 交替服务两类请求，处理顺序与到达顺序脱钩（图 3、图 9）。
- 依赖假设：锁竞争足够高，且临界区服务时间差异会让跨节点 handover 成为主要成本。
- 可能失效场景：低竞争或本地、远程请求比例接近时，重排造成的额外等待可能不再主导总延迟。
- 观察 2：公平锁的主要本地成本来自 loopback，而非 FIFO handover。 MCS 和 ticket 锁保持公平，但本地请求也经过 RNIC；FARLock 在相同公平语义下显著降低本地延迟（图 7）。
- 依赖假设：本地 CPU 原子和内存访问明显快于 RDMA，且锁状态能安全暴露给远程 RNIC。
- 假设 1：同类请求可以在各自队列中保持顺序，再用一个双方互斥协议分配全局 ticket。 FARLock 用 Peterson lock 协调本地队列头和远程队列头；该结论依赖内存读写的可见性和节点故障不发生。
- 证据强度：强；第 4 节给出了队列、ticket 和 handover 的协议，但故障恢复未覆盖。
核心方法
FARLock 保留本地、远程两条 MCS 风格队列。请求先用 XCHG 入队，再沿同类队列传递前驱的 ticket 状态。请求入队后才申请全局 ticket，因此同一队列内的队列顺序与 ticket 顺序一致。释放者递增 ticket_owner，并经 qgrant 把锁交给同类队列中的后继者。
两条队列之间不能靠普通 CPU/RDMA 原子操作直接协调。FARLock 只让两条队列的队头竞争 Peterson lock：本地队头用本地读写，远程队头用 RDMA 读写，随后分别更新同一个全局 ticket 计数器。这样本地请求的获取路径无需访问 RNIC，同时所有请求仍按 ticket 顺序获得锁。
在高竞争时，FARLock-G 允许连续的同类请求共享一个 ticket。组头获取 Peterson lock，随后把 ticket 和剩余预算沿队列传递，组尾才释放该互斥协议。组内顺序仍由队列 handover 保证，所以减少了协调开销但不改变跨类型的全局顺序。
论文还给出乐观读者扩展。读者读取独立的版本字段；奇数表示写者正在临界区，读者重试；读完后检查版本未改变。读路径不写远程内存，但读者与写者之间的公平性让位于写者优先。
设计取舍
- 取舍 1： 两条队列降低本地延迟，但引入了 ticket、Peterson lock、前驱确认和释放握手，协议状态多于普通 MCS。
- 取舍 2： 分组降低 Peterson lock 和 RNIC 往返次数，却需要为本地、远程队列分别选择组大小；实验显示远程分组过大反而可能降低吞吐（图 11）。
- 边界条件： 设计假定 queue node 在后继消费前不会被回收，并未提供节点故障处理。网络分区、进程崩溃或失联持锁者可能使自旋等待无法结束。
实验与结果
- 在 10 台 CloudLab 节点、Mellanox FDR CX3、56 Gbps InfiniBand 上，节点各运行 12 个线程；远程临界区约 5 µs，本地临界区约 100 ns（§5.1）。
- 高竞争下，FARLock 的本地尾延迟最多比 MCS 和 ticket 锁低 62×，比 ALock 低 8×；相对 test-and-set（TS）低 55–5898×（图 7）。
- 受控到达顺序实验中，FARLock 的最后一个远程请求最高等待时间为 135.30 µs；ALock 的重排使最后一个本地请求成为尾延迟来源（图 9）。
- 本地吞吐最高比 MCS、TS、ticket 锁高 891×；在 1 个锁和 10 个锁时，分别比 ALock 高 11.9× 和 2×（图 10）。
- 将 FARLock 接入 Sherman，在 uniform 更新负载下本地尾延迟降低 11–14×、远程降低 1.7–6×；Zipfian（θ=0.99）下分别降低 3.6–11× 和 1.8–3.5×，吞吐基本相当（图 12）。
论断—证据表
| 论断 | 证据 | 评测边界 | 置信度 |
|---|---|---|---|
| FARLock 同时保留非对称本地路径和 FIFO 公平性 | 协议不变量与受控顺序实验（§3–§4、图 9） | 单锁、两节点受控请求；未测故障 | 强 |
| 避免 loopback 能显著降低本地尾延迟 | 多竞争度微基准（§5.2、图 7–8） | 10 节点、FDR、固定临界区比例 | 强 |
| 公平性可改善真实索引系统的查询尾延迟 | Sherman 集成实验（§6、图 12） | 40 GB 内存服务器、随机更新、两种 key 分布 | 中到强 |
| 分组能减少协调成本且不破坏公平性 | 分组吞吐和尾延迟实验（§5.4、图 10–11） | 组大小主要测试 5 和 20；参数适应性有限 | 中 |
批判性分析
论证链条
论文的链条基本闭合：RNIC/CPU 非对称性解释了 loopback 成本，ALock 的受控实验展示了重排对尾延迟的影响，FARLock 再以队列顺序和 ticket 顺序连接两类请求。FARLock 的“到达顺序”实际是成功入队及随后分配 ticket 的顺序；并发请求在 XCHG 和队列链接之间的线性化细节决定了这个定义，论文给出了协议但没有用独立线性化证明展开所有内存可见性情形。
假设压力测试
评测把本地临界区设为 100 ns、远程设为 5 µs，这能突出非对称性，却未覆盖本地临界区较长、远程请求占绝大多数或跨多个锁热点不均衡的情况。FARLock 依赖 Peterson lock 的两方互斥；节点崩溃和网络故障可能留下未完成握手。论文将故障处理留作未来工作。
实验可信度
基线包含 TS、MCS、ticket、ALock 及其批处理版本，覆盖公平与非公平设计；测试重复三次并报告了标准差范围。Sherman 集成提供了真实系统级验证。不过硬件是较老的 FDR/CX3 平台，结论对新一代 RNIC、PCIe 和拓扑的外推仍需重新测量。读写扩展也没有给出完整的读写混合基准。
系统性缺陷
实现状态和握手字段较多，queue node 回收、线程取消、超时和可观测性会增加运维成本。自旋协议可能长期占用 CPU。乐观读者允许读者重试，但论文未系统评估读者饥饿、版本溢出或异常中断后的处理。
局限与后续工作
- 局限 1： 未处理持锁节点或请求者故障；应在节点失联、请求取消和 queue node 回收场景下验证安全性与活性。
- 局限 2： 分组参数按工作负载手工设定；可测量动态本地/远程到达率、临界区长度与尾延迟，并验证自适应组大小是否优于固定参数。
- 局限 3： 读者扩展只提出协议；后续应在读多写少、写多读少和高冲突版本检查下报告吞吐、重试率与 P99/P99.9 延迟。
相关
- 相关概念：RDMA、MCS-Lock、Ticket-Lock、Peterson-Lock、Tail-Latency
- 同类系统：ALock、Sherman、ShiftLock、DSLR
- 同会议：OSDI-2026