按年被提到
20182018 · 3 次2026
系统、数据库与网络›分布式共识·arXiv:1802.07000 · cs.DC

CASPaxos: Replicated State Machines without logs

CASPaxos:无日志的复制状态机
Denis Rystsov · 2018

复制状态而非日志的无等待线性一致寄存器

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2018-02-21 · 最近 2022-01-07
4不同的人
3活跃月份
4讨论串
10被引(OpenAlex)

CASPaxos 是在不可靠异步网络中无等待、线性一致的多写多读寄存器,支持包括 compare-and-set(CAS)在内的任意更新操作,相当于一个通过应用任意用户函数来改变值的复制状态机。与复制命令日志的 Multi-Paxos 和 Raft 不同,它复制的是状态,从而避免相关复杂性、降低写放大,并提高磁盘操作的并发度和硬件利用率。论文描述了算法、证明了其安全性,并评估了基于它的键值存储原型。

HN 为什么提它

评论者引用它说明 Paxos 的读-改-写(RMW)变体就叫 CASPaxos,也提到论文附带的实现 gryadka 是用 JavaScript 写的。

方法难度 4 / 5约 45 分钟经得起时间
读之前最好知道
1Paxos 共识算法
2Raft 与复制日志
3线性一致性(linearizability)
4异步网络与故障模型

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

CASPaxos 建立在 Paxos 的法定人数思想上,先看法定人数交集的放宽,再看同属单寄存器共识的 Bizur,便于对比 CASPaxos 复制状态而非日志的做法。

  1. 1
    Flexible Paxos: Quorum intersection revisited灵活的 Paxos:重新审视法定人数交集 · 2016

    说明 Paxos 两个阶段的法定人数只需相交,CASPaxos 的分析依赖这类法定人数理解。

    读法定人数交集的核心观察:阶段一与阶段二的法定人数只需彼此相交。

  2. 2

    同样是按键独立达成共识、不依赖全局日志的算法,可与 CASPaxos 对照。

    读按桶独立共识的设计与它如何避免全局日志。

  3. 3
    CASPaxos: Replicated State Machines without logsCASPaxos:无日志的复制状态机 · 2018 · 就是这篇

    复制状态而非日志的线性一致寄存器,支持任意更新函数。

    读两阶段协议(准备与接受)、寄存器的 CAS 变更函数以及正确性证明。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用hardwaresofton · 2018-11

“To be fair CASPaxos[2] included gryadka[3] which is in JS.”

指出 CASPaxos 论文自带的 gryadka 实现就是用 JS 写的
Writing Network Drivers in Go [pdf]原评论 ↗
引用grogers · 2022-01

“In case anyone wants to read more about the RMW variant, this is called CASPaxos: CASPaxos”

向想了解 RMW 变体的人介绍它叫 CASPaxos
被提交为 story · 2 次