先聊一个挺有意思的现象如果你现在去搜索引擎里输入“ABD”大概率会看到安卓刷机、WiFi 棒子进入 ABD 模式、中兴盒子密码计算器这类内容。这些内容里的 ABD 其实是安卓的 ADBAndroid Debug Bridge只是大小写容易被忽略。而本文要讲的则是分布式系统领域另一个经典缩写由 Attiya、Bar-Noy 和 Dolev 提出的 ABD 算法。这个算法在 quorum 复制的基础上用非常朴素的两轮消息就能在一个只支持消息传递的异步系统里模拟出“可线性化的共享内存寄存器”。很多做后端开发的同学第一次听到它会误以为这是一种共识算法或者觉得它和 Raft、Paxos 是同一类东西。实际上ABD 是一种“几乎共识但不是共识”的算法。本文将围绕这一点展开拆解 ABD 的读流程、写流程、标签设计以及 quorum 复制的边界条件并给出一个可以直接运行的 Python 模拟器。如果你是一名后端开发、中间件研发或者正在学习分布式理论的开发者这篇文章会很有帮助。文中不会只讲理论还会包含完整的代码示例、故障场景、常见问题和工程建议方便你照着验证和扩展。1. 背景与核心概念1.1 从多副本复制说起先从一个最简单的问题开始为什么要引入 quorum 复制假设我们有一份数据需要保存到多台机器上最直观的做法是“全量写”。每次写入都要等所有副本都成功才返回这样的好处是读任何一台机器都能拿到最新数据但坏处也很明显只要有一台机器慢或者宕机整个系统就不能写了。另一种做法是“主从复制”。选一个主节点负责写其他从节点同步数据。主节点故障时需要重新选举选举过程本身又涉及一致性问题。那么能不能不选主也不要求全部节点都成功而是“多数派成功就算成功”这就是 quorum 复制的核心思想。quorum 这个词翻译成“法定人数”在分布式系统中通常指“能代表整个系统做出决策的最少节点集合”。最常用的 quorum 是多数派 quorum即 ( n/2 1 )n 为节点总数。只要每次读、写操作都能保证与多数派节点交互那么任意一次读和一次写之间必然会共同覆盖至少一个节点。这个公共节点上存有最新的版本标记因此我们能判断出谁新谁旧。ABD 算法正是这种 quorum 思想的一个经典实现。它解决的问题是在没有共享物理内存、只靠网络消息传递的分布式系统里如何让所有客户端看起来像是在读写一块“共享内存”。这块内存被称为原子寄存器atomic register或者叫线性化寄存器linearizable register。1.2 ABD 是共识吗这是本文最关键的一个辨析。共识consensus问题可以简单描述为多个进程需要对某一个值达成一致并且一旦确定就不能再反悔。典型的共识算法有 Paxos、Raft、ZAB 等。而 ABD 要解决的问题并不相同。它没有让所有进程对“未来应该写什么值”做一次投票也没有产生一个唯一的、所有人都认可的提案。它只保证每次读写操作在系统全局中有一个确定的时刻发生这个时刻可以线性排列一旦某次读返回了某个值后续所有读操作看到的值不会再退回旧版本并发读写看起来像按某个串行顺序依次执行。所以 ABD 给出的是一种“操作全序”的感觉。从结果上看它让多副本看起来像单一副本很像共识带来的效果但它并不需要共识中的提案和决定流程。这也是为什么很多文章形容 ABD 是“almost consensus”几乎共识。1.3 适用场景ABD 的适用场景通常包括需要实现一个分布式的共享变量如分布式锁的后端存储、分布式计数器在不需要强一致日志的情况下需要一次读、写均达到线性一致性作为更大系统的基石比如实现分布式共享内存抽象教学、竞赛和面试中用来理解 quorum 复制的最佳示例。当然ABD 也有自己的边界例如它不处理拜占庭故障不保证写者之间的协作顺序也不适合需要日志顺序复制的场景。这些边界我们会在第 5 节详细展开。2. 环境准备与模拟器设计2.1 运行环境本文的模拟器使用 Python 编写不依赖任何第三方库也不需要安装额外的中间件。建议环境如下Python 3.6 及以上版本操作系统不限Windows / macOS / Linux 均可需要支持 threading 模块这是 Python 标准库的一部分。如果你的机器上已经有 Python直接在命令行中运行即可。没有的话可以从 Python 官网下载安装注意勾选“Add Python to PATH”。2.2 模拟器结构我们用“进程内模拟”的方式简化网络通信。真实分布式系统中节点之间通过消息传递交互模拟器中我们直接用 Python 对象列表表示节点用线程锁保护节点状态用异常表示操作失败。项目结构如下abd-demo/ ├── abd_simulator.py # 核心模拟器 └── test_abd.py # 运行各种场景实际演示时我们会把大部分代码写在同一个文件中方便直接复制运行。2.3 符号约定为了后续讲解方便先约定几个符号( n )节点总数( q )quorum 大小通常是 ( n/2 1 )( tag )版本号通常由一个递增整数和客户端唯一标识组成( query )第一阶段客户端向节点查询当前 tag 和 value( propagate )第二阶段客户端把某个 ( (tag, value) ) 写回给节点。3. 核心原理quorum 读写的关键拆解3.1 多数派为什么能保证不读旧值假设系统有 5 个节点写操作要求至少 3 个节点确认那么写操作完成后至少 3 个节点持有最新值。下一次读操作如果也要求读取至少 3 个节点那么这 3 个节点里一定至少有一个节点持有最新值。这个结论来自集合论如果写集合大小为 ( W )读集合大小为 ( R )节点总数为 ( n )当 ( W R n ) 时必有 ( W \cap R \neq \emptyset )。多数派情况下( W R n/2 1 )所以 ( W R n 2 n )。因此读写 quorum 必然相交。这个相交节点是算法的“见证人”。只要它参与了上一次写就能在下一次读时告诉客户端最新版本号即使其他节点都还是旧值客户端也能从版本号判断出谁才是最新值。3.2 两轮往返query 与 propagateABD 算法可以拆成两个操作来看。写操作的流程客户端向所有节点发送查询请求获取每个节点当前保存的 tag客户端从回复中选出最大的 tag记为 ( maxTag )生成新 tag比如 ( newTag (maxTag.version 1, clientId) )向所有节点广播 ( (newTag, value) )等到至少 quorum 个节点确认写入即可返回成功。读操作的流程客户端向所有节点发送查询请求获取每个节点当前保存的 tag 和 value从返回结果中选出 tag 最大的 ( (tag, value) )把这个 ( (tag, value) ) 写回给所有节点读修复返回 value。注意读操作不只是“读”它还会把读到的值传播给其他节点这样可以避免后续读操作再次读到旧值。这个步骤称为读修复read repair有的资料也叫 propagation。3.3 Tag单调递增的版本号Tag 是 ABD 算法中最关键的设计之一。因为没有全局时钟不同客户端并发写时无法准确判断谁的事件先发生。所以必须有人为的编号规则。常见的做法是用一个整数版本号保证单调递增用客户端标识如客户端 ID、节点 ID、UUID打破相同版本号下的平局。比如元组 ( (version, owner) )比较时先看 versionversion 相同再看 owner。由于 owner 是全局唯一的任何两个不同客户端生成的 tag 都可以排序而且不会相同。这样即使两个客户端同时从 ( version 1 ) 出发一个生成Tag(2, A)另一个生成Tag(2, B)全局也能比较出谁大谁小。节点比较 tag 后只会接受比自己当前 tag 更大的值从而避免旧值覆盖新值。3.4 为什么读操作需要写回假设没有写回这一轮会出现什么情况考虑一个 5 节点系统写操作写到了节点 1、2、3。之后客户端读到了节点 1 的最新值返回给用户。但由于节点 4 和节点 5 还是旧值下一次读如果恰好选到了节点 2、4、5理论上还是会读到旧值。读操作是 quorum 读按理说第二次读的 quorum 集合和写 quorum 集合一定相交不会出现这种“读到旧值”的情况。但问题是读返回后客户端没有义务继续保证未来。如果系统之后发生节点故障导致新值所在节点全部不可用那么系统可能整体退回到旧值这就不满足原子寄存器的“读不倒退”要求。所以读操作在拿到最大 ( (tag, value) ) 后需要把它写回给足够多的节点最好是写回所有可达节点。这样即使后续读 quorum 发生变化也能保证最新版本始终存在于多数派中。这也是读操作比写操作多出“修复”这一语义的原因。4. 完整实战用 Python 写一个 ABD 模拟器4.1 创建核心文件在任意目录下新建文件abd_simulator.py。以下代码是完整的模拟器可以直接复制运行。# abd_simulator.py import threading import time from collections import namedtuple # Tag 表示版本号(version, owner) # version 是整数owner 是客户端标识用于打破并发写时的平局 Tag namedtuple(Tag, [version, owner]) class Node: def __init__(self, node_id): self.node_id node_id self.tag Tag(0, ) self.value None self.alive True self._lock threading.Lock() def query(self): with self._lock: if not self.alive: return None return self.tag, self.value def apply_write(self, tag, value): with self._lock: if not self.alive: return False # 拒绝旧 tag避免旧值覆盖新值 if tag self.tag: self.tag tag self.value value return True return False def set_alive(self, alive): with self._lock: self.alive alive class Storage: def __init__(self, node_count5): self.nodes [Node(i) for i in range(node_count)] self.quorum node_count // 2 1 def _query_all(self): replies [] for node in self.nodes: r node.query() if r is not None: replies.append(r) if len(replies) self.quorum: raise RuntimeError(not enough alive nodes, cannot form quorum) return replies def _propagate(self, tag, value): acks 0 for node in self.nodes: if node.apply_write(tag, value): acks 1 return acks def write(self, value, client_iddefault-writer): # 第一阶段查询所有节点找到当前最大值 replies self._query_all() max_tag max(replies, keylambda item: item[0])[0] new_tag Tag(max_tag.version 1, client_id) # 第二阶段写入所有节点至少 quorum 确认 acks self._propagate(new_tag, value) if acks self.quorum: raise RuntimeError( fconcurrent write detected or nodes failed, fonly got {acks} acks, need {self.quorum} ) return new_tag def read(self, client_iddefault-reader): # 第一阶段查询到足够多的节点取其中版本最高的一个作为本次读 quorum replies self._query_all() # 这里取前 quorum 个回复作为本次读集合实际系统可以选择任意 quorum quorum_replies replies[: self.quorum] max_tag, max_value max(quorum_replies, keylambda item: item[0]) # 第二阶段尽力写回修复旧节点 self._propagate(max_tag, max_value) return max_value def show_nodes(self): for node in self.nodes: print( fnode {node.node_id}: alive{node.alive}, ftag{node.tag}, value{node.value} )这段代码的核心逻辑和原理解析一一对应。Node.query模拟网络中的查询请求Node.apply_write模拟节点接收写入并做 tag 比较Storage._query_all模拟客户端收集多数派回复Storage._propagate模拟客户端广播写入Storage.write包含写操作的两个阶段Storage.read包含读操作的两个阶段。4.2 编写测试脚本再新建一个文件test_abd.py内容如下# test_abd.py from abd_simulator import Storage def demo_sequential(): print( 场景1: 顺序读写 ) storage Storage(5) tag storage.write(hello) print(write ok, tag , tag) value storage.read() print(read value , value) tag2 storage.write(world) print(write ok, tag , tag2) value2 storage.read() print(read value , value2) def demo_single_node_down(): print(\n 场景2: 单节点故障 ) storage Storage(5) storage.write(reset) storage.nodes[0].set_alive(False) print(after node 0 down:) storage.show_nodes() tag storage.write(after-failure) print(write ok, tag , tag) value storage.read() print(read value , value) def demo_majority_down(): print(\n 场景3: 多数派故障 ) storage Storage(5) storage.write(reset) for node in storage.nodes[:3]: node.set_alive(False) try: storage.write(will-fail) except RuntimeError as e: print(write expected fail:, e) try: storage.read() except RuntimeError as e: print(read expected fail:, e) for node in storage.nodes: node.set_alive(True) if __name__ __main__: demo_sequential() demo_single_node_down() demo_majority_down()然后在命令行中执行python test_abd.py预期输出类似下面这样具体 tag 中的 owner 前缀可能不同 场景1: 顺序读写 write ok, tag Tag(version1, ownerdefault-writer) read value hello write ok, tag Tag(version2, ownerdefault-writer) read value world 场景2: 单节点故障 after node 0 down: node 0: aliveFalse, tagTag(version2, ownerdefault-writer), valueworld node 1: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello node 2: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello node 3: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello node 4: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello write ok, tag Tag(version2, ownerdefault-writer) read value after-failure实际上不同场景中节点保存的 value 会因为初始化顺序不同而略有差异这不影响理解。4.3 运行并观察结果第一个场景顺序读写。写一个值读一个值。此时所有节点上的 tag 都是新写入的 tag读操作返回最新值。第二个场景我们把节点 0 标记为不可用。这时还剩 4 个节点quorum 仍然是 3因此读写都能正常完成。这说明 quorum 复制天然具备一定的容错能力。第三个场景我们挂掉 3 个节点只剩 2 个可用节点。由于 ( 2 3 )无法凑齐多数派此时写操作会抛错读操作同样会抛错。这表明 quorum 复制的可用性边界大多数节点不可用时系统选择不可用而不是返回可能错误的数据。你可以自己在模拟器里继续验证比如在读写过程中动态恢复节点观察读修复是否能把旧节点更新到最新 tag。4.4 并发写冲突演示为了观察 tag 在并发写中的作用可以增加一个并发场景。创建一个新文件test_concurrent.py# test_concurrent.py import threading from abd_simulator import Storage def demo_concurrent_write(): storage Storage(5) results [] def worker(name): for i in range(20): try: tag storage.write(f{name}-{i}, client_idname) results.append((name, tag)) except RuntimeError as e: results.append((name, conflict)) t1 threading.Thread(targetworker, args(writer-a,)) t2 threading.Thread(targetworker, args(writer-b,)) t1.start() t2.start() t1.join() t2.join() print(写结果数量:, len(results)) print(前 10 条:, results[:10]) print(\n最终节点状态:) storage.show_nodes() if __name__ __main__: demo_concurrent_write()运行后你可能会看到部分写操作出现conflict这是因为两个 writer 同时基于旧 tag 生成新 tag后写的旧 tag 可能被部分节点拒绝。最终节点上的 tag 会收敛到同一个最大值而不会出现某个节点保留旧值、整体数据混乱的情况。5. 边界与误区ABD 为什么叫 almost consensus5.1 线性化与共识的差异ABD 提供的是线性化linearizability而不是共识。线性化可以这样理解系统给每个操作一个唯一的、合法的时间点这个时间点与真实时间一致并且所有操作都遵循一个全局顺序。读者可能关心的“最终值是什么”在线性化语义下等价于“最后一个写操作是什么”。共识则要求进程对一个值达成一致并且一旦决定就不再改变。ABD 并没有“提案”和“决定”的过程。两个客户端可以同时写不同的值最后哪个值留下取决于 tag 的比较结果。这更像是“谁版本大谁赢”而不是“大家协商一个值”。所以 ABD 被称为 almost consensus是因为它在外界看来像共识所有读取到的值都来自一个全局一致的顺序。但它的内部机制里没有投票、没有法定人数选举、没有领导者也没有明确的价值决定过程。5.2 多数派故障的后果ABD 的可用性边界非常清晰如果无法凑齐 majority quorum整个寄存器不可用。这在 CAP 理论中体现为发生网络分区时如果分区两侧都没有足够节点凑齐多数派系统只能选择“不可用”。相反如果有某一侧凑齐了多数派这一侧可以继续读写另一侧则只能等待分区恢复。更微妙的情况是当分区恢复时少数派节点上的旧值会被读修复覆盖不会出现两个分区各自保留不同值的“脑裂”问题。5.3 ABD 与 Paxos/Raft 的对比为了帮你更直观地建立坐标系我整理了一个对比表维度ABDPaxos / Raft核心问题单寄存器的读写线性化多个进程对一个值达成共识操作类型read / writepropose / decide是否需要 leader不需要Raft 通常需要 leaderPaxos 有 proposer顺序保证操作全序日志条目全序处理节点故障崩溃停机崩溃停机工程复杂度较低较高典型系统共享内存抽象、NoSQL quorum 机制分布式日志复制、选主、状态机复制从中可以看到ABD 实际上是一种比共识更轻量、更基础的一致性原语。它虽然没有共识那样的“决定能力”但在很多场景下已经够用。5.4 quorum 复制的其他边界除了多数派故障quorum 复制还有几个容易被忽视的边界第一quorum 只保证读到“某个版本”的最新值不保证单节点读取。如果你绕过 quorum 只读一个节点可能读到旧值。第二读修复是尽力而为的。如果修复还没传播到少数派节点此时发生新的写操作旧节点可能在下次读时被选中但 quorum 相交仍能保证读到最新值。可如果读操作不是 quorum 读而是单节点读就无法保证。第三所有节点都故障或数据本身被逻辑删除时quorum 也无力回天。quorum 复制不能代替备份它只保证多数派中的副本可用不保证数据在地域灾难等极端情况下不丢失。6. 常见问题与排查思路下面汇总了几个实际使用或学习 ABD 算法时容易遇到的问题。问题现象常见原因排查与解决思路写入偶尔失败提示 concurrent write detected两个客户端并发写其中一个基于旧 tag 生成新 tag被多数节点拒绝在客户端增加重试机制重新查询最新 tag 后再次写入单节点读到旧值没有使用 quorum 读或读到了尚未被读修复覆盖的单节点严格使用 quorum 读或先执行一次 read 触发写回再返回给上层应用节点重启后数据回退tag 没有持久化重启后 tag 从初始值开始将 ( (tag, value) ) 一起持久化到本地磁盘恢复时读取持久化的 tag并发写导致日志混乱没有区分写者身份tag 生成缺少唯一标识使用(version, client_id)元组作为 tag并在比较时先比 version再比 client_id网络分区恢复后少数派节点迟迟不更新没有触发读修复或读修复只作用于当前读路径后台定期执行读修复任务把最大 tag 广播给所有节点节点不可达但写操作报成功客户端只检查单节点回复没有确认 quorum写操作必须统计 ack 数量只有 ack quorum 才算成功所有节点都是新值但读返回旧值可能读请求只发给了少数节点或者少数节点间 tag 不一致检查读操作是否从多数派节点收集数据并确认节点内存中的 tag 已更新这些问题的根因大多可以归结为一点没有理解或实现“版本号 quorum 相交”两个核心机制。7. 工程实践与最佳实践建议学完一个算法最终要落到工程实践上。以下建议适用于在真实系统里实现类似 quorum 复制机制的开发者。7.1 版本号设计要全局唯一且可比较不要把 tag 简化成一个普通整数。如果两个客户端同时从版本 1 开始谁先生成版本 2如果只是整数系统无法区分两个“版本 2”。所以在生产系统中建议使用以下结构tag (logical_time, node_id_or_uuid)比较顺序是 logical_time 优先其次是 node_id。比如可以定义成class Tag implements ComparableTag { final long version; final String owner; Override public int compareTo(Tag o) { int c Long.compare(this.version, o.version); if (c ! 0) return c; return this.owner.compareTo(o.owner); } }这样可以保证无全局时钟的情况下任意两个 tag 都能比较出大小。7.2 写操作必须加超时和重试真实网络环境下节点不可达不是直接返回 false而是长时间超时。因此写操作需要设置合理的 RPC 超时时间
ABD算法详解：基于quorum复制的线性化寄存器与几乎共识
先聊一个挺有意思的现象如果你现在去搜索引擎里输入“ABD”大概率会看到安卓刷机、WiFi 棒子进入 ABD 模式、中兴盒子密码计算器这类内容。这些内容里的 ABD 其实是安卓的 ADBAndroid Debug Bridge只是大小写容易被忽略。而本文要讲的则是分布式系统领域另一个经典缩写由 Attiya、Bar-Noy 和 Dolev 提出的 ABD 算法。这个算法在 quorum 复制的基础上用非常朴素的两轮消息就能在一个只支持消息传递的异步系统里模拟出“可线性化的共享内存寄存器”。很多做后端开发的同学第一次听到它会误以为这是一种共识算法或者觉得它和 Raft、Paxos 是同一类东西。实际上ABD 是一种“几乎共识但不是共识”的算法。本文将围绕这一点展开拆解 ABD 的读流程、写流程、标签设计以及 quorum 复制的边界条件并给出一个可以直接运行的 Python 模拟器。如果你是一名后端开发、中间件研发或者正在学习分布式理论的开发者这篇文章会很有帮助。文中不会只讲理论还会包含完整的代码示例、故障场景、常见问题和工程建议方便你照着验证和扩展。1. 背景与核心概念1.1 从多副本复制说起先从一个最简单的问题开始为什么要引入 quorum 复制假设我们有一份数据需要保存到多台机器上最直观的做法是“全量写”。每次写入都要等所有副本都成功才返回这样的好处是读任何一台机器都能拿到最新数据但坏处也很明显只要有一台机器慢或者宕机整个系统就不能写了。另一种做法是“主从复制”。选一个主节点负责写其他从节点同步数据。主节点故障时需要重新选举选举过程本身又涉及一致性问题。那么能不能不选主也不要求全部节点都成功而是“多数派成功就算成功”这就是 quorum 复制的核心思想。quorum 这个词翻译成“法定人数”在分布式系统中通常指“能代表整个系统做出决策的最少节点集合”。最常用的 quorum 是多数派 quorum即 ( n/2 1 )n 为节点总数。只要每次读、写操作都能保证与多数派节点交互那么任意一次读和一次写之间必然会共同覆盖至少一个节点。这个公共节点上存有最新的版本标记因此我们能判断出谁新谁旧。ABD 算法正是这种 quorum 思想的一个经典实现。它解决的问题是在没有共享物理内存、只靠网络消息传递的分布式系统里如何让所有客户端看起来像是在读写一块“共享内存”。这块内存被称为原子寄存器atomic register或者叫线性化寄存器linearizable register。1.2 ABD 是共识吗这是本文最关键的一个辨析。共识consensus问题可以简单描述为多个进程需要对某一个值达成一致并且一旦确定就不能再反悔。典型的共识算法有 Paxos、Raft、ZAB 等。而 ABD 要解决的问题并不相同。它没有让所有进程对“未来应该写什么值”做一次投票也没有产生一个唯一的、所有人都认可的提案。它只保证每次读写操作在系统全局中有一个确定的时刻发生这个时刻可以线性排列一旦某次读返回了某个值后续所有读操作看到的值不会再退回旧版本并发读写看起来像按某个串行顺序依次执行。所以 ABD 给出的是一种“操作全序”的感觉。从结果上看它让多副本看起来像单一副本很像共识带来的效果但它并不需要共识中的提案和决定流程。这也是为什么很多文章形容 ABD 是“almost consensus”几乎共识。1.3 适用场景ABD 的适用场景通常包括需要实现一个分布式的共享变量如分布式锁的后端存储、分布式计数器在不需要强一致日志的情况下需要一次读、写均达到线性一致性作为更大系统的基石比如实现分布式共享内存抽象教学、竞赛和面试中用来理解 quorum 复制的最佳示例。当然ABD 也有自己的边界例如它不处理拜占庭故障不保证写者之间的协作顺序也不适合需要日志顺序复制的场景。这些边界我们会在第 5 节详细展开。2. 环境准备与模拟器设计2.1 运行环境本文的模拟器使用 Python 编写不依赖任何第三方库也不需要安装额外的中间件。建议环境如下Python 3.6 及以上版本操作系统不限Windows / macOS / Linux 均可需要支持 threading 模块这是 Python 标准库的一部分。如果你的机器上已经有 Python直接在命令行中运行即可。没有的话可以从 Python 官网下载安装注意勾选“Add Python to PATH”。2.2 模拟器结构我们用“进程内模拟”的方式简化网络通信。真实分布式系统中节点之间通过消息传递交互模拟器中我们直接用 Python 对象列表表示节点用线程锁保护节点状态用异常表示操作失败。项目结构如下abd-demo/ ├── abd_simulator.py # 核心模拟器 └── test_abd.py # 运行各种场景实际演示时我们会把大部分代码写在同一个文件中方便直接复制运行。2.3 符号约定为了后续讲解方便先约定几个符号( n )节点总数( q )quorum 大小通常是 ( n/2 1 )( tag )版本号通常由一个递增整数和客户端唯一标识组成( query )第一阶段客户端向节点查询当前 tag 和 value( propagate )第二阶段客户端把某个 ( (tag, value) ) 写回给节点。3. 核心原理quorum 读写的关键拆解3.1 多数派为什么能保证不读旧值假设系统有 5 个节点写操作要求至少 3 个节点确认那么写操作完成后至少 3 个节点持有最新值。下一次读操作如果也要求读取至少 3 个节点那么这 3 个节点里一定至少有一个节点持有最新值。这个结论来自集合论如果写集合大小为 ( W )读集合大小为 ( R )节点总数为 ( n )当 ( W R n ) 时必有 ( W \cap R \neq \emptyset )。多数派情况下( W R n/2 1 )所以 ( W R n 2 n )。因此读写 quorum 必然相交。这个相交节点是算法的“见证人”。只要它参与了上一次写就能在下一次读时告诉客户端最新版本号即使其他节点都还是旧值客户端也能从版本号判断出谁才是最新值。3.2 两轮往返query 与 propagateABD 算法可以拆成两个操作来看。写操作的流程客户端向所有节点发送查询请求获取每个节点当前保存的 tag客户端从回复中选出最大的 tag记为 ( maxTag )生成新 tag比如 ( newTag (maxTag.version 1, clientId) )向所有节点广播 ( (newTag, value) )等到至少 quorum 个节点确认写入即可返回成功。读操作的流程客户端向所有节点发送查询请求获取每个节点当前保存的 tag 和 value从返回结果中选出 tag 最大的 ( (tag, value) )把这个 ( (tag, value) ) 写回给所有节点读修复返回 value。注意读操作不只是“读”它还会把读到的值传播给其他节点这样可以避免后续读操作再次读到旧值。这个步骤称为读修复read repair有的资料也叫 propagation。3.3 Tag单调递增的版本号Tag 是 ABD 算法中最关键的设计之一。因为没有全局时钟不同客户端并发写时无法准确判断谁的事件先发生。所以必须有人为的编号规则。常见的做法是用一个整数版本号保证单调递增用客户端标识如客户端 ID、节点 ID、UUID打破相同版本号下的平局。比如元组 ( (version, owner) )比较时先看 versionversion 相同再看 owner。由于 owner 是全局唯一的任何两个不同客户端生成的 tag 都可以排序而且不会相同。这样即使两个客户端同时从 ( version 1 ) 出发一个生成Tag(2, A)另一个生成Tag(2, B)全局也能比较出谁大谁小。节点比较 tag 后只会接受比自己当前 tag 更大的值从而避免旧值覆盖新值。3.4 为什么读操作需要写回假设没有写回这一轮会出现什么情况考虑一个 5 节点系统写操作写到了节点 1、2、3。之后客户端读到了节点 1 的最新值返回给用户。但由于节点 4 和节点 5 还是旧值下一次读如果恰好选到了节点 2、4、5理论上还是会读到旧值。读操作是 quorum 读按理说第二次读的 quorum 集合和写 quorum 集合一定相交不会出现这种“读到旧值”的情况。但问题是读返回后客户端没有义务继续保证未来。如果系统之后发生节点故障导致新值所在节点全部不可用那么系统可能整体退回到旧值这就不满足原子寄存器的“读不倒退”要求。所以读操作在拿到最大 ( (tag, value) ) 后需要把它写回给足够多的节点最好是写回所有可达节点。这样即使后续读 quorum 发生变化也能保证最新版本始终存在于多数派中。这也是读操作比写操作多出“修复”这一语义的原因。4. 完整实战用 Python 写一个 ABD 模拟器4.1 创建核心文件在任意目录下新建文件abd_simulator.py。以下代码是完整的模拟器可以直接复制运行。# abd_simulator.py import threading import time from collections import namedtuple # Tag 表示版本号(version, owner) # version 是整数owner 是客户端标识用于打破并发写时的平局 Tag namedtuple(Tag, [version, owner]) class Node: def __init__(self, node_id): self.node_id node_id self.tag Tag(0, ) self.value None self.alive True self._lock threading.Lock() def query(self): with self._lock: if not self.alive: return None return self.tag, self.value def apply_write(self, tag, value): with self._lock: if not self.alive: return False # 拒绝旧 tag避免旧值覆盖新值 if tag self.tag: self.tag tag self.value value return True return False def set_alive(self, alive): with self._lock: self.alive alive class Storage: def __init__(self, node_count5): self.nodes [Node(i) for i in range(node_count)] self.quorum node_count // 2 1 def _query_all(self): replies [] for node in self.nodes: r node.query() if r is not None: replies.append(r) if len(replies) self.quorum: raise RuntimeError(not enough alive nodes, cannot form quorum) return replies def _propagate(self, tag, value): acks 0 for node in self.nodes: if node.apply_write(tag, value): acks 1 return acks def write(self, value, client_iddefault-writer): # 第一阶段查询所有节点找到当前最大值 replies self._query_all() max_tag max(replies, keylambda item: item[0])[0] new_tag Tag(max_tag.version 1, client_id) # 第二阶段写入所有节点至少 quorum 确认 acks self._propagate(new_tag, value) if acks self.quorum: raise RuntimeError( fconcurrent write detected or nodes failed, fonly got {acks} acks, need {self.quorum} ) return new_tag def read(self, client_iddefault-reader): # 第一阶段查询到足够多的节点取其中版本最高的一个作为本次读 quorum replies self._query_all() # 这里取前 quorum 个回复作为本次读集合实际系统可以选择任意 quorum quorum_replies replies[: self.quorum] max_tag, max_value max(quorum_replies, keylambda item: item[0]) # 第二阶段尽力写回修复旧节点 self._propagate(max_tag, max_value) return max_value def show_nodes(self): for node in self.nodes: print( fnode {node.node_id}: alive{node.alive}, ftag{node.tag}, value{node.value} )这段代码的核心逻辑和原理解析一一对应。Node.query模拟网络中的查询请求Node.apply_write模拟节点接收写入并做 tag 比较Storage._query_all模拟客户端收集多数派回复Storage._propagate模拟客户端广播写入Storage.write包含写操作的两个阶段Storage.read包含读操作的两个阶段。4.2 编写测试脚本再新建一个文件test_abd.py内容如下# test_abd.py from abd_simulator import Storage def demo_sequential(): print( 场景1: 顺序读写 ) storage Storage(5) tag storage.write(hello) print(write ok, tag , tag) value storage.read() print(read value , value) tag2 storage.write(world) print(write ok, tag , tag2) value2 storage.read() print(read value , value2) def demo_single_node_down(): print(\n 场景2: 单节点故障 ) storage Storage(5) storage.write(reset) storage.nodes[0].set_alive(False) print(after node 0 down:) storage.show_nodes() tag storage.write(after-failure) print(write ok, tag , tag) value storage.read() print(read value , value) def demo_majority_down(): print(\n 场景3: 多数派故障 ) storage Storage(5) storage.write(reset) for node in storage.nodes[:3]: node.set_alive(False) try: storage.write(will-fail) except RuntimeError as e: print(write expected fail:, e) try: storage.read() except RuntimeError as e: print(read expected fail:, e) for node in storage.nodes: node.set_alive(True) if __name__ __main__: demo_sequential() demo_single_node_down() demo_majority_down()然后在命令行中执行python test_abd.py预期输出类似下面这样具体 tag 中的 owner 前缀可能不同 场景1: 顺序读写 write ok, tag Tag(version1, ownerdefault-writer) read value hello write ok, tag Tag(version2, ownerdefault-writer) read value world 场景2: 单节点故障 after node 0 down: node 0: aliveFalse, tagTag(version2, ownerdefault-writer), valueworld node 1: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello node 2: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello node 3: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello node 4: aliveTrue, tagTag(version1, ownerdefault-writer), valuehello write ok, tag Tag(version2, ownerdefault-writer) read value after-failure实际上不同场景中节点保存的 value 会因为初始化顺序不同而略有差异这不影响理解。4.3 运行并观察结果第一个场景顺序读写。写一个值读一个值。此时所有节点上的 tag 都是新写入的 tag读操作返回最新值。第二个场景我们把节点 0 标记为不可用。这时还剩 4 个节点quorum 仍然是 3因此读写都能正常完成。这说明 quorum 复制天然具备一定的容错能力。第三个场景我们挂掉 3 个节点只剩 2 个可用节点。由于 ( 2 3 )无法凑齐多数派此时写操作会抛错读操作同样会抛错。这表明 quorum 复制的可用性边界大多数节点不可用时系统选择不可用而不是返回可能错误的数据。你可以自己在模拟器里继续验证比如在读写过程中动态恢复节点观察读修复是否能把旧节点更新到最新 tag。4.4 并发写冲突演示为了观察 tag 在并发写中的作用可以增加一个并发场景。创建一个新文件test_concurrent.py# test_concurrent.py import threading from abd_simulator import Storage def demo_concurrent_write(): storage Storage(5) results [] def worker(name): for i in range(20): try: tag storage.write(f{name}-{i}, client_idname) results.append((name, tag)) except RuntimeError as e: results.append((name, conflict)) t1 threading.Thread(targetworker, args(writer-a,)) t2 threading.Thread(targetworker, args(writer-b,)) t1.start() t2.start() t1.join() t2.join() print(写结果数量:, len(results)) print(前 10 条:, results[:10]) print(\n最终节点状态:) storage.show_nodes() if __name__ __main__: demo_concurrent_write()运行后你可能会看到部分写操作出现conflict这是因为两个 writer 同时基于旧 tag 生成新 tag后写的旧 tag 可能被部分节点拒绝。最终节点上的 tag 会收敛到同一个最大值而不会出现某个节点保留旧值、整体数据混乱的情况。5. 边界与误区ABD 为什么叫 almost consensus5.1 线性化与共识的差异ABD 提供的是线性化linearizability而不是共识。线性化可以这样理解系统给每个操作一个唯一的、合法的时间点这个时间点与真实时间一致并且所有操作都遵循一个全局顺序。读者可能关心的“最终值是什么”在线性化语义下等价于“最后一个写操作是什么”。共识则要求进程对一个值达成一致并且一旦决定就不再改变。ABD 并没有“提案”和“决定”的过程。两个客户端可以同时写不同的值最后哪个值留下取决于 tag 的比较结果。这更像是“谁版本大谁赢”而不是“大家协商一个值”。所以 ABD 被称为 almost consensus是因为它在外界看来像共识所有读取到的值都来自一个全局一致的顺序。但它的内部机制里没有投票、没有法定人数选举、没有领导者也没有明确的价值决定过程。5.2 多数派故障的后果ABD 的可用性边界非常清晰如果无法凑齐 majority quorum整个寄存器不可用。这在 CAP 理论中体现为发生网络分区时如果分区两侧都没有足够节点凑齐多数派系统只能选择“不可用”。相反如果有某一侧凑齐了多数派这一侧可以继续读写另一侧则只能等待分区恢复。更微妙的情况是当分区恢复时少数派节点上的旧值会被读修复覆盖不会出现两个分区各自保留不同值的“脑裂”问题。5.3 ABD 与 Paxos/Raft 的对比为了帮你更直观地建立坐标系我整理了一个对比表维度ABDPaxos / Raft核心问题单寄存器的读写线性化多个进程对一个值达成共识操作类型read / writepropose / decide是否需要 leader不需要Raft 通常需要 leaderPaxos 有 proposer顺序保证操作全序日志条目全序处理节点故障崩溃停机崩溃停机工程复杂度较低较高典型系统共享内存抽象、NoSQL quorum 机制分布式日志复制、选主、状态机复制从中可以看到ABD 实际上是一种比共识更轻量、更基础的一致性原语。它虽然没有共识那样的“决定能力”但在很多场景下已经够用。5.4 quorum 复制的其他边界除了多数派故障quorum 复制还有几个容易被忽视的边界第一quorum 只保证读到“某个版本”的最新值不保证单节点读取。如果你绕过 quorum 只读一个节点可能读到旧值。第二读修复是尽力而为的。如果修复还没传播到少数派节点此时发生新的写操作旧节点可能在下次读时被选中但 quorum 相交仍能保证读到最新值。可如果读操作不是 quorum 读而是单节点读就无法保证。第三所有节点都故障或数据本身被逻辑删除时quorum 也无力回天。quorum 复制不能代替备份它只保证多数派中的副本可用不保证数据在地域灾难等极端情况下不丢失。6. 常见问题与排查思路下面汇总了几个实际使用或学习 ABD 算法时容易遇到的问题。问题现象常见原因排查与解决思路写入偶尔失败提示 concurrent write detected两个客户端并发写其中一个基于旧 tag 生成新 tag被多数节点拒绝在客户端增加重试机制重新查询最新 tag 后再次写入单节点读到旧值没有使用 quorum 读或读到了尚未被读修复覆盖的单节点严格使用 quorum 读或先执行一次 read 触发写回再返回给上层应用节点重启后数据回退tag 没有持久化重启后 tag 从初始值开始将 ( (tag, value) ) 一起持久化到本地磁盘恢复时读取持久化的 tag并发写导致日志混乱没有区分写者身份tag 生成缺少唯一标识使用(version, client_id)元组作为 tag并在比较时先比 version再比 client_id网络分区恢复后少数派节点迟迟不更新没有触发读修复或读修复只作用于当前读路径后台定期执行读修复任务把最大 tag 广播给所有节点节点不可达但写操作报成功客户端只检查单节点回复没有确认 quorum写操作必须统计 ack 数量只有 ack quorum 才算成功所有节点都是新值但读返回旧值可能读请求只发给了少数节点或者少数节点间 tag 不一致检查读操作是否从多数派节点收集数据并确认节点内存中的 tag 已更新这些问题的根因大多可以归结为一点没有理解或实现“版本号 quorum 相交”两个核心机制。7. 工程实践与最佳实践建议学完一个算法最终要落到工程实践上。以下建议适用于在真实系统里实现类似 quorum 复制机制的开发者。7.1 版本号设计要全局唯一且可比较不要把 tag 简化成一个普通整数。如果两个客户端同时从版本 1 开始谁先生成版本 2如果只是整数系统无法区分两个“版本 2”。所以在生产系统中建议使用以下结构tag (logical_time, node_id_or_uuid)比较顺序是 logical_time 优先其次是 node_id。比如可以定义成class Tag implements ComparableTag { final long version; final String owner; Override public int compareTo(Tag o) { int c Long.compare(this.version, o.version); if (c ! 0) return c; return this.owner.compareTo(o.owner); } }这样可以保证无全局时钟的情况下任意两个 tag 都能比较出大小。7.2 写操作必须加超时和重试真实网络环境下节点不可达不是直接返回 false而是长时间超时。因此写操作需要设置合理的 RPC 超时时间