引用hardwaresofton · 2018-11
“To be fair CASPaxos[2] included gryadka[3] which is in JS.”
指出 CASPaxos 论文自带的 gryadka 实现就是用 JS 写的
复制状态而非日志的无等待线性一致寄存器
CASPaxos 是在不可靠异步网络中无等待、线性一致的多写多读寄存器,支持包括 compare-and-set(CAS)在内的任意更新操作,相当于一个通过应用任意用户函数来改变值的复制状态机。与复制命令日志的 Multi-Paxos 和 Raft 不同,它复制的是状态,从而避免相关复杂性、降低写放大,并提高磁盘操作的并发度和硬件利用率。论文描述了算法、证明了其安全性,并评估了基于它的键值存储原型。
评论者引用它说明 Paxos 的读-改-写(RMW)变体就叫 CASPaxos,也提到论文附带的实现 gryadka 是用 JavaScript 写的。
CASPaxos 建立在 Paxos 的法定人数思想上,先看法定人数交集的放宽,再看同属单寄存器共识的 Bizur,便于对比 CASPaxos 复制状态而非日志的做法。
说明 Paxos 两个阶段的法定人数只需相交,CASPaxos 的分析依赖这类法定人数理解。
读法定人数交集的核心观察:阶段一与阶段二的法定人数只需彼此相交。
同样是按键独立达成共识、不依赖全局日志的算法,可与 CASPaxos 对照。
读按桶独立共识的设计与它如何避免全局日志。
复制状态而非日志的线性一致寄存器,支持任意更新函数。
读两阶段协议(准备与接受)、寄存器的 CAS 变更函数以及正确性证明。
“To be fair CASPaxos[2] included gryadka[3] which is in JS.”
“In case anyone wants to read more about the RMW variant, this is called CASPaxos: CASPaxos”