paper-osdi26-hu-guanzhou

Bodega：通过响应者名册租约支持随处、随时的本地线性一致读（OSDI 2026）

原题：Bodega: Localized Linearizable Reads at Anywhere Anytime via Roster Leases

一句话总结：Bodega 将租约保护对象从单次写入改为变化较少的响应者名册，要求写入覆盖全部指定响应者，并让受并发写干扰的读在本地等待提交；在五站点 WAN、10% 写入的实验中，吞吐上限约为 6,000 请求/秒，而 Leader Leases 约为 1,800 请求/秒，代价是写延迟受最慢响应者约束，故障后可能等待数秒租约过期。

问题与动机

跨地域复制降低相关故障造成数据丢失的风险，却让每次共识往返都承担 WAN 延迟。对于配置存储、协调服务和数据库元数据，读请求需要满足线性一致性：必须观察到调用开始前已完成的相关写入。直接读取附近副本的旧值不能满足这一要求。

现有路线各有边界。MultiPaxos 的普通读经过共识；领导者租约（Leader Leases）允许领导者直接读，但远端客户端仍需访问领导者。EPaxos 和 PQR 将通信缩短到附近法定人数，仍需跨节点交互。Quorum Leases 能把读租约授予跟随者，但写入触发租约撤销和恢复，因此即使写比例不高，本地读也可能频繁退回领导者。

Bodega 将“谁可以本地读”独立为协议元数据。它允许为每个键或键范围选择多个响应者，不依赖外部成员协调器。标题中的“随时”应理解为稳定配置下并发写不必导致客户端重定向，而非故障、租约切换和日志落后时都能立即本地返回。

关键观察 / 隐含假设

• 观察 1：低写比例不代表读租约几乎不受干扰。 图 9、图 11 显示，Quorum Leases 在 0% 写入时接近本地读理想状态，在 10% 写入时却接近 Leader Leases。决定干扰的是相关写的到达频率及租约失效窗口，而不只是全局读写比例。
  • 依赖假设：同一键的读写有足够重叠，且远程重定向代价大于短暂等待。
  • 可能失效场景：极少冲突或只有领导者附近客户端时，Bodega 相对已有租约方案的收益缩小。
• 观察 2：收到写入后等待其提交，通常比让客户端另找节点更快。 图 12 的单次写干扰中，Quorum Leases 的读延迟升到约 40 ms；Bodega 在本地保留请求，并将受影响窗口缩短到约 25 ms。
  • 依赖假设：领导者与响应者之间通常健康，提交通知能及时到达。
  • 可能失效场景：领导者失效、拥塞或长时间调度暂停会延长等待，需要客户端超时后向其他节点重复发送读请求。
• 假设 1：名册的变化频率低于数据写入频率。 租约可以在后台长期续期，不为每次写重新建立本地读权限。证据强度中等：正常配置和一次主动切换有实测，频繁故障主要用模拟覆盖。
• 假设 2：响应者覆盖成本可以接受。 每次写必须收到所有相关响应者的确认。图 17、图 18 直接呈现更多本地读机会与更高写延迟的交换；远端或缓慢响应者可能让成本远大于论文默认拓扑。
• 假设 3：时钟速率漂移有界，健康多数派最终可以通信。 协议不要求各节点时间戳同步，但租约安全性依赖正确的计时边界；活性还依赖故障检测、租约过期和稳定多数派。完全异步网络中的无条件进展不在保证范围内。

核心方法

将领导者和响应者统一为名册

名册（roster）记录当前领导者，以及每个键范围对应的响应者（responder，即获准本地回答读请求的副本）。领导者隐式成为所有键的响应者。每份名册绑定唯一、递增的提案编号（ballot）；即使内容相同，不同编号也代表不同版本。这样，领导者更换和读权限调整共用同一个版本化元数据机制（§3.1）。

写入先覆盖响应者，读请求按日志状态处理

Bodega 沿用 MultiPaxos 写流程，但提交条件同时要求多数派确认与全部相关响应者确认。于是，只要名册稳定，已经向客户端确认的同键写必然到过每个响应者。

领导者直接返回最新已提交值。非领导者响应者检查本地日志中包含该键写入的最高槽位：若已提交，立即回答；否则将读挂在该槽位上，执行乐观等待（optimistic holding）。该槽位提交后释放读请求，不因后续持续写入而不断推迟等待目标。客户端超过等待超时后，可用相同请求 ID 向另一响应者或领导者重发读，并采用最早回复（§3.2）。

可选的提前接受通知（early accept notifications）让跟随者把接受结果同时发给响应者，减少等待领导者转发提交通知的时间。正文 §3.2 描述响应者收齐多数派接受通知即可判断值将被选定；该优化增加写入消息量，作者建议写流量较大时关闭。

用全互联租约稳定名册，并检查旧日志边界

每个节点同时充当租约授予者和持有者。授予者在采用新名册前，必须撤销旧租约或等待其过期。响应者持有同一名册的多数派有效租约后，利用多数派交集排除同时存在另一份稳定名册（§3.3）。租约续期附带在心跳中，普通写不撤销名册租约。

持有多数租约并不等于数据已经追平。 Guard 消息还携带授予者曾接受的最高日志槽位。式 (1) 要求存在一个由有效授予者组成的多数派，响应者已连续提交到其中每个授予者报告的安全阈值。这个检查覆盖旧名册下可能完成的写入，防止落后副本仅因取得新租约就返回旧值。检查失败时走普通共识路径。该条件已对照 PDF 第 8 页核验。

将切换和控制开销移出正常读路径

主动切换通常先撤销再激活租约，无故障时约两个消息轮次；联系不到旧持有者时则必须等待过期。默认 WAN 设置为 120 ms 心跳、约 1,200 ms 故障检测、约 2,500 ms 租约。名册未变化时，轻量心跳仅携带编号，避免重复发送可能达数十 KB 的完整名册（§3.3、§5）。

Summerset 实现还提供简单自动策略：某键超过 95% 请求为读时，把靠近该键超过 20% 读请求的服务器加入响应者。论文重点是名册机制，没有系统评估该阈值策略的稳定性与最优性。集群成员变更则先稳定一份无响应者的名册，再执行原协议的重配置。

设计取舍

• 用写入覆盖换本地读。 读可以只访问附近节点，写却不能绕过该键的任何响应者；多数派健康并不意味着当前名册下的写能够立即完成。
• 用等待换掉重定向。 健康网络下减少读请求往返，但需要挂起集合、超时和重复请求管理。论文没有量化突发拥塞时挂起请求的内存与排队上限。
• 用较长租约换后台稳定性。 续期不进入每次写的关键路径，但故障切换可出现秒级停顿，不能把无故障切换的 75 ms 套用到故障恢复。
• 用可配置性避免一律全副本写。 只为热点读键和合适站点开启权限可以减轻写成本；配置策略又必须平衡客户端位置、写比例、尾延迟与名册切换频率。
• 全互联控制通信有规模边界。 轻量心跳减少消息大小，并不消除全互联租约关系随副本数平方增长的潜在成本；五节点实验不足以证明大规模控制开销仍可忽略。

实验与结果

评测使用五站点真实 CloudLab WAN，以及五台同型机器用 netem 模拟 Google Cloud RTT 的 GEO 集群；各节点公网 NIC 为 1 Gbps。微基准为 50 个客户端、每站点 10 个，1,000 个 8 B 键、128 B 值、均匀访问。比较协议在同一 async Rust/tokio 框架 Summerset 中实现，包含 MultiPaxos、Leader Leases、EPaxos、PQR 与 Quorum Leases 的变体。

1. 并发写下仍保留本地读收益。 图 9、图 11 比较 0%、1%、10% 写入。Bodega 在响应者附近维持低读延迟，Quorum Leases 随写比例升高接近 Leader Leases；默认 WAN 配置中 SC 不是响应者，因此仍有 20% 客户端不能本地读。摘要汇总的平均读加速为 5.6–13.1 倍，不应解释成每个站点都达到这一倍数。
2. 吞吐—延迟曲线。 五站点 WAN、10% 写入的图 10 中，Leader Leases、PQR 加 Leader Leases、Quorum Leases 的吞吐上限分别约为 1,800、2,200、3,400 请求/秒，Bodega 约为 6,000 请求/秒。正文报告 Bodega 在该曲线比较中延迟约改善 1.5 倍；这与特定本地读的更大加速不是同一指标。
3. 单次写干扰。 图 12 中，每个开环客户端以 400 请求/秒读同一键，然后注入一次写。Quorum Leases 的受扰读延迟约为 40 ms，被动变体缩短了恢复窗口；Bodega 将干扰窗口压到约 25 ms，并本地完成受影响的读。横轴是读完成时间，不能将图形直接解释为请求到达时的延迟分布。
4. 故障恢复与主动切换。 图 16 的 WI 附近客户端以 400 请求/秒提交 50% 读负载。UT 响应者宕机立即阻塞写；约 1.1 秒后触发故障检测，再等待约 2.6 秒租约过期。后续无故障主动切换仅约 75 ms。图 15 的“最高 2.2 倍吞吐”来自模拟：每秒 0.5% 故障概率、1% 恢复概率，并预设故障后 3 秒零吞吐，不能替代真实故障注入结果。
5. 与生产服务的比较。 YCSB 使用 10,000 个键，覆盖 A/B/C/D/F；分别评估均匀分布下全响应者配置，以及各站点偏好不同热点的 Zipfian-0.99 分布、前 20% 热键配置。Bodega 在多数组合中接近默认 ZooKeeper 与允许旧读的 etcd，但纯读 C 中后两者读延迟约为 0.3 ms，Bodega 与 Quorum Leases 约为 1.2 ms，作者归因于 1 ms 请求批处理。均匀全覆盖配置下 Bodega 写延迟较高，因为必须等待所有副本（图 19）。这些生产服务模式的读语义并不等价于 Bodega。
6. 形式化证据。 §4 给出局部读线性一致性与写活性论证；附录 A 报告对 3 节点、允许 1 个失败、2 写加 2 读等有限输入进行模型检查，生成 4,274,883,464 个不同状态，耗时 43 小时，机器为 96 核、768 GiB 内存。这是作者报告，本文未重跑检查器。

论断—证据表

论断	证据	评测边界	置信度
并发写期间可继续在响应者本地完成线性一致读	§3.2–§4.3；图 9、图 11、图 12	需要稳定租约、日志安全阈值和写覆盖；不保证立即返回	强
读本地化能够缓解领导者吞吐瓶颈	图 10：约 6,000 对 1,800 请求/秒，分别为 Bodega 与 Leader Leases	五站点 WAN、10% 写、128 B 值；并非通用硬件吞吐极限	强
主动名册调整比故障触发恢复快	图 16：约 75 ms 主动切换，对比故障检测约 1.1 秒加过期等待约 2.6 秒	单响应者宕机与一次显式调整；未覆盖所有网络分区	强
较强读语义可接近弱一致读系统的性能	图 19：YCSB 多数组合接近旧读 etcd 与默认 ZooKeeper	实现栈不同；纯读延迟约 1.2 对 0.3 ms，仍有差距	中
租约交集和日志阈值支持安全性	式 (1)、§4.3、附录 A 的有限模型检查	有界时钟漂移；有限状态、形式模型与实际代码存在抽象差异	中

批判性分析

论证链条

论文把两个不同问题分开处理：名册租约证明读权限仍有效，日志状态证明返回值足够新。覆盖全部响应者的写提交条件将两者连接起来；旧名册的安全阈值则补上新加入响应者可能落后的漏洞。这条机制链能够解释 Quorum Leases 的干扰窗口为何可以缩短。

但“本地完成”不等于“只付本地延迟”。收到尚未提交写的响应者仍在等待网络信息；故障与名册切换时还可能关闭本地路径。把正文中的条件删去，只保留标题的“anywhere anytime”，会夸大保证。

假设压力测试

远距离响应者、热点写集中和缓慢副本会同时抬高写确认时间与受干扰读的等待时间。图 13 已显示写比例提高到 50% 后收益减弱；对长期突发写、跨站热点迁移与不对称链路拥塞，还需要新的实验。作者在 §7 承认基于心跳的提案竞争会受部分网络分区影响，并提出预投票或透明重路由作为补充，而没有在本文完成这些机制的评测。

时钟漂移假设直接影响安全性，不能仅凭“无需时间戳同步”忽略它。实际部署需要确认虚拟机暂停、计时器异常及节点重启时的租约语义；本文没有给出覆盖这些情况的实测矩阵。

实验可信度

同框架实现多种协议、同时提供闭环与开环结果，比只对比不同产品更有助于隔离协议差异。真实 WAN 与模拟 GEO 也支持“网络往返主导”的解释。但仅五副本、有限键值规模和按站点均匀放置客户端，不能代表大集群或生产流量。

图 12 支持整体读路径的改进，但没有充分分离“仅乐观等待”和“再加提前接受通知”的独立收益、额外流量与过载拐点。图 19 的生产系统比较也混合了协议、语言运行时、批处理和一致性差异；作者关于 Java 运行时开销的归因没有独立消融支撑。正文 §5.3 将批处理描述为用于非本地读命令，而 §6.4 又用批处理解释 Bodega 纯读延迟，具体实现路径应通过代码或复现实验确认。

系统性缺陷

形式化规格提供了可审查材料，但不能直接当作实现正确性证书。附录 A 的文字报告使用 3 个提案编号，末尾所列配置却为 ConstMaxBallot = 2；此外，规格对提前返回读调用覆盖全部响应者的 WriteCommittable 条件，比正文“多数派通知即可”的表述更严格。规格还以 PrepareNotice 传递安全阈值，正文使用 Guard 消息。这些差异不直接证明协议错误，却要求复现时明确被验证的是哪一个版本与哪些优化。

挂起读的内存上限、重复请求放大、租约抖动告警和名册自动调整的稳定性没有完整量化。论文虽然说明日志快照和成员变更如何衔接，但没有展示完整生产协调服务所需的所有恢复、隔离与运维能力。

局限与后续工作

• 适用范围：面向 WAN、读占优势、非事务的键值操作；同数据中心、写主导或允许任意旧读的场景并非主要收益区间。不能把单键读保证外推为多键事务隔离。
• 响应者选择：比较静态配置与自动阈值策略，在站点热点迁移和慢节点注入下测量 P99 读写延迟、切换次数与恢复时间，检验局部读收益是否抵消写放大。
• 优化消融：分别关闭乐观等待和提前接受通知，记录网络字节数、每秒消息数、挂起读数量及饱和吞吐，确定额外广播的收益区间。
• 恢复压力测试：注入单向分区、领导者暂停和响应者慢故障，检查历史线性一致性及最坏不可用窗口，不能只汇报稳态平均吞吐。
• 形式模型对齐：统一正文、可运行规格与 Rust 实现中的通知阈值、租约计时和提案编号配置，重跑模型检查并公开配置与状态统计。

相关

• 概念：Linearizability、Distributed-Leases、State-Machine-Replication、Paxos。
• 对照路线：EPaxos 追求附近法定人数；Quorum-Leases 保护读权限但受写入撤销影响；Hermes 通过复制协议支持本地读，却依赖外部成员管理。Bodega 将读权限元数据纳入自身租约协议。
• 同会议：OSDI-2026。
• 原始资料：osdi26-hu-guanzhou.pdf、osdi26-hu-guanzhou；Summerset 研究代码。