《大规模分布式计算深入解析》3.1 R+W>N:读写 quorum 的交集

证明固定成员的读写集合交集下界,展示部分写造成读回退的反例。

相交与线性一致

固定 N 个副本中,大小分别为 R、W 的集合至少重叠 max(0,R+W−N) 个。这说明一次读会碰到每次已完成写的某个成员。版本顺序、并发与读写协议才能确定读到的值。

flowchart LR
    W["写 v1,只到 A,仍未完成"] --> A["A=v1,B=C=v0"]
    A --> R1["R1 读 A/B,返回 v1"]
    R1 --> R2["R2 随后读 B/C,返回 v0"]
    R1 -. "如先同步写回多数派" .-> WB["R2 的读集合与写回集合相交"]

对三副本 R=W=2,一笔并发写只把 1 传播到 A,还未达到 W。读 A/B 取较新值 1,随后读 B/C 得到 0。两次读不重叠,同一写最多只能线性化一次,这段历史不可线性化。异步读修复来不及挡住后一次读。ABD 的单写者读协议在返回前将读到的版本写回多数派,多写者还要确保标签全序且能反映协议顺序。

验证

从卷七实验包 解包,运行 python3 protocol-counterexamples.py,观察两次读输出为 1 和 0,再手工加上读写回阶段。

一手资料

卷七目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图