谣言

节点不断与随机伙伴交换并转发状态。最终状态一致，也容忍消息在中途被丢弃。 各转各、互转告 每一轮每个节点挑一个随机的同伴交换已知状态,唯一的事实靠反复传播抵达所有人,而不是借一次单点广播。因为每次甩到的伙伴不同,信息像几何级数一样铺开:一轮往往能让知道的人数约翻一倍,于是一个小型集群里一条新成员条目——往往只要几轮就能扩散到每个人。交换通常是双向的,两条互为镜像的对话一次带两边,这让网络的成本对称又划算。它换来的是「最终一定周到」的随机保证,而不是「这一条必须按序送到」的强承诺。 没有中心也收敛 收敛不是由某个协调者来保证,而是全体随机接触涌现出来的结果,所以系统没有一个必须存活的单点。成员数和集合规模随时可变也能扛:节点加入、离开,无需有人更新一本中心目录。代价是「最终」而不是「立即」:足够轮次之后大家才看到同一份状态,而收敛时间大致取决于一轮消息来返的耗时。集群越大,越要保持每一轮的接触成本跟集群规模近似成对数而不是线性,才不至于把传播变成内耗。 丢一条消息并不致命 丢一条消息不会终止协议——这份事实还会在之后的随机配对里被另一个节点重新拾起,并再次向前转。一次失败只是把收敛拖延到下一个握手轮,而不是把状态的传播掐灭。因为状态是被不断往前复制,而不是被某个点消耗掉,所以单个节点的失陪无损全局。这也解释了为什么平时把心跳轮做得足够短很有用:收敛更快,而且一个迟到加入的节点,很快就能被任意一个熟知的邻居重新带起来。 坏掉的样子 网络分区不会让流言停下来，只会把它劈成两半。两侧各自在内部继续交换、各自收敛出不同的成员视图，于是两边都相信自己才是健康的那一半。链路恢复时，真正决定哪些写入能活下来的是合并规则：如果只比物理时钟、谁新听谁的，在失败侧接受的写入会被悄悄丢掉。生产系统因此要用版本向量或墓碑（tombstone）来配合流言：分区愈合时做调和，而不是截肢。 另一种坏法正好相反：网络没有分区，但一个慢节点看起来像死了。一次长时间的垃圾回收停顿，或者被打满的链路，会让心跳迟到超过怀疑超时，集群于是把活节点判成死节点，把它负责的数据范围复制一遍，等它再次应答又要把这些活儿撤销。SWIM 式的 suspicion 机制正是为此而生：先扩散怀疑、迟宣布死亡，并给被怀疑者用更高的 incarnation 编号反驳的机会，而不是把一次错过的心跳当成判决。 第三种坏法是修复流量本身。当大批节点同时重新加入，或者心跳轮间隔设得太激进，每个节点都向所有人拉全量状态，修复流量就会变成反熵风暴。正确做法是先对摘要：先比较版本摘要，只补缺失的条目，再加上抖动和有界扇出。从磁盘镜像恢复的老节点绝不能带着清零的计数器重新加入：版本号更小的旧副本会正确落败，但计数器被重置的旧副本反而可能覆盖更新的状态，所以版本号在重启之间必须单调递增。 快速验证 把下面程序保存为 check_gossip.py，运行 python3 check_gossip.py。它模拟 20 个节点，每个节点维护一份带版本号的键值映射；更新先写入 0 号节点，之后每一轮每个节点随机挑选一个对等节点做 push-pull 交换，双方按 key 保留版本号更高的一方。固定随机种子只让每次运行的配对可复现，不改变协议本身。程序逐轮打印知道更新的节点数，并在 12 轮后断言全部收敛。 import random NODES = 20 ROUNDS = 12 SEED = 7 random.seed(SEED) # Each node holds a versioned map: key -> (version, value). nodes = [{} for _ in range(NODES)] nodes[0]["config"] = (1, "blue") def merge(a, b): 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 history = [] for round_no in range(1, ROUNDS + 1): for i in range(NODES): peer = random.randrange(NODES) if peer == i: continue # Push-pull: both sides adopt the union, highest version wins. united = merge(nodes[i], nodes[peer]) nodes[i] = dict(united) nodes[peer] = dict(united) informed = sum(1 for state in nodes if state.get("config") == (1, "blue")) history.append(informed) print(f"round {round_no}: {informed}/{NODES} nodes know the update") assert history[-1] == NODES, f"gossip did not converge: {history}" assert all(state.get("config") == (1, "blue") for state in nodes) print(f"PASS: all {NODES} nodes converged within {ROUNDS} rounds: {history}") 在这个种子下，传播接近几何级数：第一轮约四分之一节点知道，第三轮接近全部，第四轮 20 个节点全部收敛。如果把每轮配对改成只联系固定邻居，收敛会明显变慢甚至停滞，这正好对应分区或配置错误的集群。上述断言在 macOS、CPython 3.12 下运行通过。这个模型省略了 suspicion 超时、墓碑过期和带宽限制，只能用来理解收敛，不能当作成员关系的实现。 ...