分布式

etcd 使用 Raft 为复制状态的变化确定顺序。副本可以暂时落后，共识不表示每个成员在每一瞬间都保存相同字节。领导者协调复制，投票多数决定能否继续推进。判断操作是否成功时，应区分选举、提交、本地应用与客户端收到确认，不能把这些阶段压缩成一个含义不明的“已经写入”。 每个任期的领导者与投票限制 候选人需要多数票，每位投票者在同一任期最多投一票。日志新旧也参与判断，任期更大并不意味着日志落后的候选人就能取得所有选票。随机选举超时可以减少反复平票。任期排列领导权尝试，不衡量经过的时间，也不能单独证明某个成员曾经发生网络分区。 对于当前任期的条目，领导者复制到多数后可以推进提交；旧任期条目会随着当前任期条目提交而间接提交，不能只数旧条目已有多少副本就完整解释 Raft 规则。在协议的存储与故障假设内，后续领导者保留已提交条目。多数持久数据同时丢失，或恢复到旧备份，是另一类灾难恢复问题，不能用共识安全性代替备份。 选举期间，进展会暂停到领导者建立。客户端请求可能等待、超时或失败，取决于截止时间和连接情况。超时不能证明提议从未提交。应用需要合适的重试或事务设计，不能把每次失败响应都解释成可以重复非幂等业务效果的许可。诊断时还应区分服务端是否提交与客户端是否知道结果。 数投票者，不是数进程 包含 N 位投票者的配置，需要 floor(N/2)+1 形成多数。三位允许一位不可用，四位仍只允许一位，却需要三位参与；五位和六位都容忍两位失效。与前一个奇数相比，偶数配置没有增加可容忍失效数，不过受控成员变更期间可能暂时经过偶数配置。这个算术描述稳定投票配置，不意味着成员可以随意删改。 learner 接收复制但不投票，因此加入它不会改变投票仲裁数；追赶检查通过后的提升才改变计数。这样避免立即依赖一份刚加入的空副本投票，但追赶流量仍消耗资源，可能影响可用性。仲裁数不变，不保证加入 learner 绝不引起超时或促成选举；容量、网络与磁盘负载仍需观察。 坏掉的样子 缺少可达多数时，集群无法正常推进写入。serializable 读取可以使用某个成员的本地状态，因此可能返回旧值；linearizable 读取需要建立当前状态的协调，不能理解成只是给本地读取换了名字。它也不要求每次读都追加一个日志条目，所以把所有线性一致读直接称为复制写入，会掩盖实际实现和性能差异。 网络分区中的少数派不能独立提交另一段冲突历史。分区恢复的具体行为取决于配置。etcd 3.5 默认启用 pre-vote，以减少失联成员重新加入时的扰动，因此恢复分区并不必然引发更高任期选举和写入中断。应检查配置、时序与日志，不能断言每个孤立成员都会不断提升正式任期，也不能仅凭某个较大值推导全部故障经过。 丢失一个跟随者时，剩余投票者可能仍足够继续服务，但落后会减少冗余，也会影响本地读取。不能等到多数消失才重视它。端点探测失败同样可能来自客户端路由、TLS、权限、超时或活动告警，而不等于投票者已死亡。客户端可达性与成员之间的仲裁通信，是两种需要分别检查的观察。 复制之后，仍须判断提交。依据原文绘制机制；模型值与原文报告的观察不代表本次运行测试。 快速验证 下面的 Python 3 算术用例不联系任何集群。它打印投票门槛，并检查 learner 不参与计数的区别，不实现领导者选举或日志复制。用这个小实验先验证配置算术，再把结果与真实成员清单对应，避免把进程总数直接当成投票者数量。 def quorum(voters): return voters // 2 + 1 for voters in (1, 2, 3, 4, 5, 6): required = quorum(voters) print(f"voters={voters}, quorum={required}, tolerated={voters-required}") assert quorum(3) == 2 and quorum(4) == 3 assert 2 < quorum(4) # Neither side of a 2+2 partition has a majority. # A learner replicates data but is not included in the voting count. voters, learners = 3, 1 assert quorum(voters) == 2 print("PASS: adding a learner leaves the voting quorum unchanged") 一至六名投票者的输出仲裁数依次是一、二、二、三、三、四。四位投票者分成二加二时，两侧都不构成多数；三位投票者再加一位 learner，仍需要两票。PASS 只证明这些计算，不证明真实集群在故障中的行为，更不替代日志持久化和网络分区测试。 ...

Raft 选主需要当前配置中投票成员的严格多数。在成员集合固定、每个服务器每任期最多持久记录一票的前提下，两个候选者不能同时赢得同一个任期，因为它们的多数集合必有交集，而交集中的投票者不能支持两个人。这是关于选举结果的保证，不是说所有节点在每个时刻都知道当前主是谁，也不是说任何形式的领导者选择都只能使用这一种算法。 每个任期最多一个赢家 分母是配置中的全部投票者，不是此刻能够联系上的机器。五个投票者需要三票，即使现在只有两台互通，也不能把门槛降成两台中的多数。学习节点和不参与投票的副本不会自动扩大分母。成员变化必须采用安全的重配置协议；若两侧自行改写成员名单，即使各自都声称满足多数，也已经破坏原先的交集依据。 每任期一票与多数算术同样重要。服务器应在回复投票之前，可靠保存当前任期和已投对象，避免重启后忘记旧票又支持另一个候选者。来自同一成员的重复响应不能算成额外选票。这里也假定成员身份正确、消息来自相应节点；这种崩溃故障模型不等于已经解决恶意成员伪造身份与消息的问题。 权限不同于本地相信自己有权限 多数分区可以在新任期选出主，同时孤立旧主仍然以为自己领导着较早任期。基本 Raft 在得知更高任期时退回跟随者，并不是收到不到心跳回复就必定立刻退位。某些实现增加了法定人数检查，但那是需要单独确认的机制，不能把产品的额外行为写成所有 Raft 系统的共同前提。 少数派不能独自提交新的客户端命令。选举限制、日志匹配与提交规则共同保护跨任期的复制状态，单靠票数并不足以保证任意外部写入安全。如果业务工作者凭过去取得的主身份操作另一套存储，还可能需要由资源端执行围栏检查。要求线性一致的读取也应遵守协议的当前权限检查，不能只看到本机主标志就认为结果足够新。 任期与计时器承担不同职责 任期是长度不固定的逻辑时代，不是一个持续固定秒数的租约。跟随者正常收到有效主的心跳时，通常不会发起新选举；收不到则触发怀疑，并可能在超时后竞选。失去消息不能证明旧机器已经停止执行。Raft 的安全性论证并不要求各机器的墙钟完全同步，不能把任期编号解释成全局时间片。 随机化选举超时有助于打破候选者反复同时起跑、瓜分选票的对称。要持续推进，仍需及时通信和足够处理能力。节点过载、网络延迟或过于激进的超时，即使没有永久分区，也可能引起任期快速变化、主位抖动和写延迟上升。应根据延迟与调度观察选择参数，不能认为超时越短就越安全。 坏掉的样子 四个投票者需要三票，分成二对二时两侧都无法推进。三个和四个投票者都只能容忍一个不可用成员，因此增加第四个并没有换来第二次故障的余量；五个投票者可以容忍两个。奇数配置改善的是这一成本与容错关系，而偶数配置仍然具备多数集合相交的安全性质，并非天然会发生脑裂。 少数侧可以收到甚至暂存请求，但不能把新的、尚未提交的命令报告为已经提交成功。客户端超时也会留下结果不确定性：操作可能已经在另一侧提交，只是响应没有到达。因此，安全重试还依赖应用契约，需要时使用请求去重；不能把所有不可用错误都当作没有产生任何效果的证据。 候选者还必须拥有足够新的日志。Raft 比较最后一条日志的任期，再比较其索引，而不是简单选最长日志。即使数出了多数票，删掉新鲜度限制仍可能破坏领导者完整性。下面的票箱实验特意没有实现日志限制，所以不能拿运行通过来宣称已经实现可靠共识，更不能据此替代真实系统的故障测试。 同一任期，五票需三票。依据原文绘制机制；模型值与原文报告的观察不代表本次运行测试。 快速验证 保存为 majority.py，运行 python3 majority.py。脚本使用共享的内存票箱、固定成员身份和显式任期，并对重复响应去重。它不启动网络服务、不创建持久化日志，所有输入都由实验明确给出。这样既能观察多数门槛，也能检查同任期重复请求和下一任期之间的区别。 def quorum(size): if size < 1: raise ValueError("at least one voter is required") return size // 2 + 1 class Ballots: """Fixed membership, unique votes, and in-memory per-term voting only.""" def __init__(self, size): self.size = size quorum(size) self.terms = [0] * size self.voted_for = [None] * size def elect(self, candidate, term, reachable): nodes = sorted(set(reachable)) if not 0 <= candidate < self.size or term < 1: raise ValueError("invalid candidate or term") if any(not 0 <= node < self.size for node in nodes): raise ValueError("unknown voter") votes = [] for node in nodes: if term < self.terms[node]: continue if term > self.terms[node]: self.terms[node] = term self.voted_for[node] = None if self.voted_for[node] in (None, candidate): self.voted_for[node] = candidate votes.append(node) return len(votes) >= quorum(self.size), votes assert [quorum(n) for n in (3, 4, 5)] == [2, 3, 3] cluster = Ballots(5) assert cluster.elect(0, 1, [0, 1, 2]) == (True, [0, 1, 2]) assert cluster.elect(3, 1, [3, 4]) == (False, [3, 4]) assert cluster.elect(3, 1, range(5)) == (False, [3, 4]) assert cluster.elect(0, 1, [0, 1, 2]) == (True, [0, 1, 2]) print("one winner per term; repeated same-candidate requests preserve votes") assert cluster.elect(3, 2, range(5)) == (True, list(range(5))) assert cluster.elect(0, 1, range(5)) == (False, []) print("a newer term can elect another candidate; older requests are rejected") even = Ballots(4) assert not even.elect(0, 1, [0, 1])[0] assert not even.elect(2, 1, [2, 3])[0] assert not Ballots(5).elect(0, 1, [0, 0, 0])[0] print("2-2 split stalls; repeating one voter cannot manufacture a majority") print("PASS: fixed-membership ballot rules only; no replicated log or network") 预期打印四行确认。三节点侧当选，两节点侧落选；即使后来能够联系全部节点，第二个候选者也不能拿走本任期已经投出的票。新任期可以选出另一候选者，之后旧任期请求被拒；四节点二对二无法产生赢家，同一身份出现三次也仍然只有一票。重复向原候选者确认已有票不会制造第二次投票。 ...

流言协议通过反复联系对等节点来传播信息。一部分交换丢失时，只要仍有节点保留该状态，后续联系就可能再次传播它。但最终收敛需要前提：有关节点必须最终可达，更新不能提前消失，合并规则也必须能够处理实际产生的状态。随机选择伙伴本身，并不保证所有节点在某个固定截止时间之前达成一致。 区分传播与状态调和 节点可以主动推送状态、拉取对方状态，也可以双向交换。这是协议设计选择，并非每条流言消息都必须具有对称结构。在连通良好的成员集合中，每个节点每轮只联系少量伙伴，就可能让一条小更新快速扩散。常见的对数级传播估计属于特定概率模型，不能用一次网络来回耗时直接推导最坏收敛期限，也不能把每轮联系几个节点误解成整份状态的传输成本恒定。 成员流言也不会自动让应用写入一致。Dynamo 使用流言维护成员信息，用向量时钟表达对象版本，再用 Merkle 树反熵修复副本差异。这些机制承担不同职责。成员协议中的 incarnation 编号用于区分同一个成员的状态代次，并不是任意业务数据都可以直接采用的因果版本。理解职责分离，比把所有最终一致行为统称为流言更有助于定位故障。 下面的模型明确假定每个键只有一个写者，版本严格递增。对它播种的单条更新，保留更大版本已经足够。如果相同版本却包含不同内容，当前规则只保留先看到的一方，结果就会依赖合并顺序。真实系统必须说明如何处理并发、重复投递、删除和重启身份，不能用传播最终到达的证据替代这些合并契约。 坏掉的样子 持续的网络分区会阻止更新跨越互不连通的组件。每一侧继续重复内部交换，也无法补上不存在的通信路径。恢复连接后，只有所需状态仍然存在，调和才有机会继续。删除同样需要明确表示和保留期限：墓碑过早到期，可能让旧副本重新带回被删除内容。版本向量描述版本关系，墓碑记录删除事实，两者作用不同，也不会自动保证所有业务写入都被完整保留。 运行缓慢或暂停的节点可能看起来已经故障。SWIM 将故障检测与感染式传播分开，并通过怀疑阶段给被怀疑成员一个使用较新代次进行反驳的机会。这是在其假设下减少误判，并非在任意长延迟下都能精确判断死亡。数据重新复制和归属迁移属于外围系统的策略，不能说每次传播怀疑都会必然触发一次重新分片或自动撤销已经完成的迁移。 修复本身也消耗资源。全量状态交换、过于频繁的轮次，以及大量节点同时重返集群，都可能压满链路或接收端。限制扇出、增量交换和控制恢复速率能够帮助减压，但开销还取决于状态大小，不能只数每轮联系了几台机器。重启版本必须遵守具体实现的身份规则：计数器归零可能让新声明显得陈旧，或造成相同身份的歧义；较小版本不会因为“重启过”就自然覆盖较大版本。 没有连通路径，流言无法越过。依据原文绘制机制；模型值与原文报告的观察不代表本次运行测试。 快速验证 保存为 check_gossip.py，使用 python3 check_gossip.py 执行。它只使用 Python 标准库，不打开网络连接。二十个字典代表节点，每次扫描顺序访问节点，并做双向合并。固定种子使当前运行时的选择可复现；一条消息可以在同一次扫描中经过多个连续联系，因此这不是所有节点同步发送、同步接收的真实网络轮次模拟器。 import random NODES, ROUNDS, SEED = 20, 12, 7 def merge(a, b): # One writer per key, with strictly increasing versions in this fixture. merged = dict(a) for key, (version, value) in b.items(): if key not in merged or version > merged[key][0]: merged[key] = (version, value) return merged def spread(peer_for, nodes=None): rng = random.Random(SEED) if nodes is None: nodes = [{} for _ in range(NODES)] nodes[0]["config"] = (1, "blue") history = [] for _ in range(ROUNDS): # Sequential contacts: knowledge can travel several hops in one sweep. for i in range(NODES): peer = peer_for(i, rng) if peer == i: continue united = merge(nodes[i], nodes[peer]) nodes[i], nodes[peer] = dict(united), dict(united) history.append(sum(state.get("config") == (1, "blue") for state in nodes)) return nodes, history random_peer = lambda i, rng: rng.randrange(NODES) nodes, history = spread(random_peer) assert history[-1] == NODES assert all(a <= b for a, b in zip(history, history[1:])) print("random contacts:", history) # A fixed hub is connected; fixed contacts do not inherently prevent convergence. _, hub = spread(lambda i, rng: 0) assert hub[0] == NODES print("fixed hub after one sweep:", hub[0]) # Two disconnected peer sets retain different views until contacts can cross. partitioned, split = spread(lambda i, rng: (i // 10) * 10 + rng.randrange(10)) assert split[-1] == 10 and all(not node for node in partitioned[10:]) _, healed = spread(random_peer, partitioned) assert healed[-1] == NODES print("partition:", split[-1], "after healing:", healed[-1]) # Dissemination alone cannot repair an ambiguous concurrent-write merge rule. a, b = {"config": (2, "red")}, {"config": (2, "green")} assert merge(a, b) != merge(b, a) print("equal-version conflict is order-dependent: not a multi-writer merge") print("PASS: dissemination, topology, partition, and merge controls") 随机联系产生的知情节点数依次为五、十四、十九，第四次扫描达到二十，后续保持不变。这复现了原先记录于 macOS、CPython 3.12 的单更新结果，但只能说明这个输入和调度，不是其他随机种子或线上集群的收敛概率界限。当前模型补充明确的反例，不再仅凭一次成功就推断任意拓扑和故障条件下的可靠性。 ...

一致性哈希限制成员变化时的数据放置变化，但它本身不搬运数据、不让副本达成一致，也不把单个热键的请求自动分散。经典顺时针哈希环把键交给哈希位置之后遇到的第一个节点点位；如果位置恰好相等，就归该点，超过最大点位则绕回最小点位。理解这个查找方向，是判断迁移范围的前提。 先把归属区间画对 一个点拥有的是前驱之后到自身为止的区间，即 (前驱, 当前点]。假设 A 位于 20，B 位于 50，C 位于 80，那么 B 负责大于 20 且不大于 50 的位置；超过 80 的键绕回 A。这不是从 B 到其后继 C 的弧段，左右端点是否包含也不是可以随意改变的细节。 在 35 加入 D，它从顺时针后继 B 手中取得大于 20 到 35 的位置；移除 B，则将 B 原来负责的区间交给 C。未受影响的点位保持原位置及归属，这才是算法有用的性质。仅说“移动一小段弧”还不够，因为原来某段弧可能就占据整个环的很大一部分。 作为对照，直接用 hash(key) 对节点数量取模来选择数组下标，新增节点会改变除数，很多键随之选到别的下标。四个等容量且平衡的节点扩到五个时，理想哈希环大约需要迁移五分之一的键，但真实迁移比例取决于点位与键分布，不能把这个比例当成所有部署都成立的保证。 ...

向量为每个被跟踪的参与方记录进度。比较这些计数可以区分因果先后与并发，但如何调和并发值，仍然需要由应用决定。 单一时间戳不能证明因果 标量时间戳可以人为排出顺序，但单凭这个顺序不能证明因果关系。在参与者身份稳定、遵循事件时钟规则的前提下，每个进程为本地事件增加自己的分量；收到消息时，先逐项取最大值合并发送方上下文，再增加接收方自己的分量。后一项不能漏掉，否则接收事件可能与接收前的上下文混为一谈。这些规则记录信息怎样流动，不测量实际经过多少秒，也不会为完全没有交换信息的机器证明物理时间先后。 必须区分四种比较结果 比较需要检查全部分量，缺席的参与者按零处理。只有 A 每项都不大于 B，且至少有一项严格小于 B，才能说 A 严格先于 B。反向支配是后于，全部相同是相等；两边都不能支配对方时才是并发。不能看到“并非 A 先于 B”，就直接推导并发，因为 B 先于 A 和两者相等都还是可能结果。 例如 [A:2] 与 [A:2, B:1] 不是相等，前者严格先于后者。某一个槽位相同，不等于全部历史相同；相反，省略的零槽位与显式零槽位可以表示同一上下文。这里比较的是时钟记录的信息，不是业务数据正文，也不是两份数据在现实世界中看起来有多相似。 并发不替应用决定赢家 并发不会选出赢家，也不一定就是业务冲突。独立字段更新可能可以合并，不兼容的整值替换则可能需要保留兄弟版本或交给用户判断。确定性裁决可以有意丢弃一个值，但那是应用选择的政策，不是时钟发现了先后。相等只表示被编码的上下文相同；只有额外的事件身份契约，才能证明两份载荷确实对应同一事件，不能把向量直接当成正文校验和。 坏掉的样子 时钟大小随方案实际跟踪的身份集合增长。Dynamo 的分量标识协调写入的存储节点，并不是每个曾写过该键的客户端。短命参与者不断出现、重启后计数器归零，都需要专门处理；如果旧身份被复用而计数回退，真正的新操作反而可能看起来像旧历史。身份稳定是算法前提，不是无关紧要的实现细节。 裁掉一个分量，会丢失真实祖先关系。祖先 [A:2, C:4] 先于后代 [A:3, B:2, C:5]；从后代删去 C 后，剩下的向量却与祖先呈并发关系。缺席按零，适用于未见过某个参与者的语义，无法替主动遗忘的历史补回证据。Dynamo 论文明确提醒截断会使调和关系不精确。点版本向量采用不同因果表示，并不意味着普通向量的任意槽位都能安全删除。 只比较总和、最大值或旁边的墙钟，同样会丢信息。[A:2, B:1] 和 [A:1, B:2] 总和相同，却互不支配。后续写入应带回读取到的上下文，让存储知道它要替代哪些版本。省略上下文可能产生兄弟版本，具体取决于存储与现有版本，不能说每次都会产生。元数据保留和调和必须按照真实协议实现，不能由这几项算术断言替代。 ...

一个幂等键只能在服务定义的作用域与保留窗口内标记一次逻辑行动。重复同一段字符串，不是放之四海皆准的“恰好执行一次”保证。服务需要把身份关联到正确的主体与操作，协调竞争中的请求，并保存足够权威的信息，以便稍后认出已经处理的行动。键只是入口，真实保证取决于这条处理链。 图示依据 SQLite 实验，不是通用 API 契约。作用域与保留期由服务定义。未知不等于缺失；数据库原子性不覆盖外部副作用，也不承诺永久恰好一次。 作用域是身份的一部分 如果全局只按客户端提交的键查找，就可能把不同租户的行动合并，甚至把别人的已存结果返回给当前调用方。查找或重放之前仍须完成认证与授权。应把可信作用域、稳定的操作标识、客户端行动键一起作为查找身份，并保留各组件边界，避免直接拼接字符串产生歧义。 究竟哪些维度属于作用域，要由 API 契约决定。EC2 明确区分地域级与可用区级幂等；按其文档规则，相同客户端令牌在不同地域或可用区可能允许执行不同的行动。因此，把重试切换到另一个地域，并不自动保留全局去重保证，不能只检查令牌文本是否一致。 请求含义也需要约束。同一个作用域内，原键配上不同参数时，必须按照已经声明的冲突规则处理。下面的实验只对一个正整数量生成比较表示，不比较任意 HTTP 正文，不执行认证，也不认为对正文取个哈希，就能自动推断业务语义是否相同。 让业务效果与结果记录一起提交 先查记录、再独立写入，会出现竞争：两个工作进程都没看见旧记录，于是都执行了业务。如果两份业务效果已经发生，之后只有一个结果记录插入成功，那么结果表上的唯一键本身并不能消除之前的重复效果。需要保护的是业务修改与记忆结果之间的完整边界。 两者都位于同一个事务数据库时，可以放在一个事务中提交。示例先执行 SQLite BEGIN IMMEDIATE，再查询记录，并在同一事务里写入业务行与结果记录。SQLite 同时只允许一个写事务，因此竞争连接会被串行处理；复合主键也明确表达了去重所依赖的身份组成。 事务保护止于这个数据库。外部支付、邮件发送或消息投递，不会因为本地事务失败就自动撤销；这些效果需要自己的端到端投递与去重契约。把整个流程命名为“恰好一次”，并不能凭空补出跨越多个系统的原子性，评审时必须沿真实副作用检查边界。 保留期也是正确性边界 如果旧请求仍可能回来，而记住它的键已经过期，那次请求就可能重新执行。Stripe API v1 文档明确说明，记录清理后的同键请求会成为新请求；其至少二十四小时的保留说明属于该提供方，并不是所有服务通用的计时器，更不能解释成永久去重。 恢复窗口应与保留期一致，还要区分临时去重记录和长期业务唯一性规则。删除结果记录，不会撤销原来的订单。如果业务禁止这笔订单在任何时候被重新创建，就需要一个比短期重试缓存更持久的权威约束，不能把希望都放在键还没过期这件事上。 恢复较旧的记录数据库、清空状态或切换到独立存储，也可能忘记已经完成的行动。恢复方案应保留业务数据与操作记录之间的关系，不能只证明各自的文件还能读取，却没有验证它们是否对应同一批已提交事实。 坏掉的样子 提交成功后丢失响应，会让客户端不知道结果，但不会自动删除已存记录。提交前事务失败，则应同时不留下业务效果与成功记录。这是两种不同情况，需要不同证据，不能把“客户端看到了错误”直接等同于“服务器没有执行”。 数据库竞争、存储不可用或未知结果，也不能被当成“查不到旧记录”。看到操作仍在执行，不应自动放行第二份业务效果。需要明确重复请求是等待、得到执行中响应，还是走另一条已有文档的恢复路径；成功结果重放只是可能状态之一，不覆盖所有中间阶段。 快速验证 保存为 scope_check.py，用 Python 3.10 以上版本执行 python3 scope_check.py。未改动的实验已于 2026-10-18 在 Python 3.12.14、SQLite 3.53.1 上重新运行。标准库代码在私有临时目录创建数据库，结束后清理；每次尝试都打开自己的连接。租户与操作参数代表已经完成身份验证和路由解析的测试输入，不是客户端请求头的替代品。 ...