Gossip 协议

Gossip 是一类对等信息传播方法：节点周期性选择少量对端交换状态，让更新经过多次局部交互扩散。它减少对一个固定广播中心的依赖，但节点不会在同一时刻看到完全相同的信息。

因此，Gossip 适合传播成员、状态摘要或可收敛更新；不能单独授权唯一 leader 或保证所有节点按同一顺序处理命令。传播与共识解决不同问题。

两组分类不要混在一起

Push、Pull、Push-Pull 描述信息流向；Rumor Mongering 与 Anti-Entropy 描述传播和补齐策略。这是两组可组合的维度。

Rumor 通常把某条新更新传播有限次数后停止，以控制成本；Anti-Entropy 定期比较状态，补回偶然遗漏。Pull 一次就追上只有在对端拥有完整所需数据、传输成功且容量足够时才成立。

为什么早期传播很快

理想化模型里，已知更新的节点继续接触未知节点，传播初期覆盖数可快速增长。后期却会越来越多地选中已经知道的节点，剩余少量节点成为覆盖尾部。

在随机混合良好、消息有足够容量等假设下，许多 epidemic 协议的传播时间随节点数近似对数增长。这是带概率和模型条件的结论，不是任意网络都能在精确 log₂N 轮到达全部节点。

若两个机房之间断连，局部扩散再快也无法跨过分区。若更新产生速度超过可用传播带宽，积压也可能持续增长。Efficient Reconciliation and Flow Control 直接讨论了反熵在有限容量下的约束。

四个节点、两个知情者：下一轮也未必覆盖全部

假设同步轮次开始时只有 0、1 知道更新，每个知情节点从另外三个节点中等概率选一个目标 push，消息全部送达。新知情节点到下一轮才转发。两个发送者共有 3×3=9 种等可能选择，可以直接穷举：

from itertools import product
from fractions import Fraction

known = {0, 1}
outcomes = [known | {target0, target1}
            for target0, target1 in product((1, 2, 3), (0, 2, 3))]
assert len(outcomes) == 9
assert sum(len(result) == 4 for result in outcomes) == 2
assert sum(len(result) == 2 for result in outcomes) == 1
expected_new = Fraction(sum(len(result) - 2 for result in outcomes), 9)
assert expected_new == Fraction(10, 9)

# 对一个尚不知情的节点，每位发送者不选中它的概率是 2/3。
assert expected_new == 2 * (1 - Fraction(2, 3)**2)

其中只有 0→2,1→3 与 0→3,1→2 能覆盖四个节点，概率 2/9；0→1,1→0 完全没有新增覆盖，概率 1/9。其余选择都只增加一个知情节点。平均新增 10/9 个，不是机械翻倍所要求的两个。

推广到 N 个节点、k 个知情者，在上述独立均匀选择且无丢包的条件下，下一轮新增的期望是 (N−k)×[1−(1−1/(N−1))^k]。它是对一轮的期望，不是每条实际传播轨迹。网络分区、偏向局部的选点或消息容量不足，都会改变这个模型。

有限传播次数还会留下概率性遗漏。例如 A 把更新传给 B 后停止，B 唯一一次又选回 A，C、D 就再也收不到这条 rumor。周期反熵的意义是提供后续补齐机会；如果更新本身已被完全丢弃，后续接触再频繁也恢复不了内容。

两个知情节点，并不保证下一轮变成四个

期望式可以按一个未知节点拆开理解：一个发送者不选它的概率是 1−1/(N−1)，k 个独立发送者都没选它的概率是这个数的 k 次方。取补集得到它本轮获知的概率，再对 N−k 个未知节点求和。不同未知节点是否获知并不需要相互独立，期望的可加性已经足够。

$$E[\Delta ]=(N-k)\left[1-{\left(1-\frac{1}{N-1}\right)}^k\right]$$

去重、版本与合并决定最终状态

同一更新可能经不同路径多次到达。接收端需要稳定标识或版本规则，避免重复执行副作用。若传播的是完整状态，则需要定义如何合并两个状态；若传播的是操作，则要考虑丢失、重复和顺序。

例如每个节点维护自己的单调计数分量，收到另一副本的状态后对每个分量取最大值，再求和，就能避免重复消息把计数重复累加。直接广播“总数加一”并在每次收到时执行，则不能容忍重复。

新旧判断也不能只看本地接收时间。延迟消息可能比新消息更晚到；成员重启后若计数归零，需要 incarnation 等代际信息。更一般的合并条件见 冲突解决。

G-Counter：交换各写者的累计状态，不能把快照再加一次

三个写者各自只增加自己的分量。A 已产生两次增加，B 产生三次，C 产生一次。副本交换状态时，对同一写者取较大分量，再求总数。重复快照不会变成新操作。

from itertools import permutations

def join(a, b):
    return {writer: max(a.get(writer, 0), b.get(writer, 0))
            for writer in a.keys() | b.keys()}

updates = [{"A": 2}, {"B": 3}, {"C": 1}]
for order in permutations(updates):
    state = {}
    for update in (*order, order[0], order[1]):  # 故意重复、改变顺序
        state = join(state, update)
    assert state == {"A": 2, "B": 3, "C": 1}
    assert sum(state.values()) == 6
assert join({"A": 2}, {"A": 1}) == {"A": 2}  # 迟到的旧状态不倒退

# 重启后复用身份却把本地累计值清零，会让新的增加被旧分量吞掉。
assert join({"A": 2}, {"A": 1}) != {"A": 3}
# 新 incarnation 可使用新身份；旧分量仍保留。
assert sum(join({"A#1": 2}, {"A#2": 1}).values()) == 3

逐分量 max 满足交换律、结合律和幂等性，因此完整状态在重复、乱序到达时仍可收敛。前提是所有增加最终传播，并且每个写者独占自己的单调分量；两个进程误用同一身份各自从 0 加到 1，合并只会得到 1，无法表达两次独立增加。

重启时可恢复持久分量，也可使用新 incarnation，但新身份不是无成本的修复：旧分量不能随意删除，否则总数会下降，需要另行设计身份回收或压缩协议。这里的 G-Counter 也只支持增加，不支持任意扣减。状态型 CRDT 的合并条件及 GCounter 实例见 Akka Distributed Data。

成员传播与数据反熵

SWIM 的探测层取得存活证据，传播层扩散加入、离开、怀疑与存活更新。只写成传播 dead 事件是不完整的：反驳怀疑和新成员加入同样需要扩散。协议细节见 SWIM。

对于大规模业务数据，逐条传播完整状态可能太昂贵，可以先交换摘要，再定位需要同步的范围。Merkle tree 是其中一种工具，它帮助减少传输，不会自动决定版本冲突。详见 反熵与数据修复。

Fanout、周期与载荷预算

若每节点每秒联系 3 个对端、每次发送约 2 KB，一个节点单向发送量约 6 KB/s；一千节点约 6 MB/s，尚未包含回复和协议开销。这里展示的是估算方法，不是任何实现的默认配置。

提高 fanout 或缩短周期可能加快传播，也可能造成拥塞与处理排队，使实际收敛反而更慢。还要限制单条更新的重传次数、消息大小、队列积压，并为反熵预留补齐机会。

故障相关更新通常比低优先级统计信息更紧急，但优先级不能让某些类别永久得不到发送。混合使用周期摘要与事件快速传播，可以兼顾及时性与最终覆盖。

Gossip 不能替代什么

两个节点暂时持有不同成员列表，是 Gossip 允许的状态。它们若各自凭本地列表授予独占写权限，就可能同时认为自己是唯一所有者。需要独占决策时，应把弱一致视图接入具有明确安全规则的协调协议。

同样，Raft AppendEntries 是复制状态机协议的一部分，不能拿它当成所有可靠广播的定义。判断系统时，应分别写出传播、排序、持久化与交付保证，避免只凭“有没有 leader”比较正确性。

参考

• Efficient Reconciliation and Flow Control for Anti-Entropy Protocols
• SWIM 论文
• 故障检测

关键词：gossip、push、pull、push-pull、rumor mongering、anti-entropy、fanout、概率覆盖、状态合并