Gossip协议理解

Gossip protocol 也叫 Epidemic Protocol （流行病协议），实际上它还有很多别名，比如：“流言算法”、“疫情传播算法”等。

Gossip协议是基于六度分隔理论（Six Degrees of Separation）哲学的体现，简单的来说，一个人通过6个中间人可以认识世界任何人。

Gossip protocol 最早是在 1987 年发表在 ACM 上的论文 。主要用在分布式数据库系统中各个副本节点同步数据之用，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络，这区别与之前介绍的用于结构化网络中的 DHT 算法 Kadmelia。

很多知名的 P2P 网络或区块链项目，比如 IPFS，Ethereum 等，都使用了 Kadmelia 算法，而Bitcoin 、Fabric则是使用了 Gossip 协议来传播交易和区块信息。

这里先简单介绍一下 Gossip 协议的执行过程：

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

具体的传播流程

Gossip协议在计算机系统通常以随机的“对等选择”形式实现：以给定的频率，每台计算机随机选择另一台计算机，并共享任何消息。定义十分简单，所以实现方式非常多，可能有几百种Gossip协议变种。因为每个使用场景都可能根据组织的特定需求进行定制。

因为Gossip只是类似一直思想，其实现多种多样。如下介绍一下其基本思想。

  • 种子节点周期性的散播消息 【假定把周期限定为 1 秒】。
  • 被感染节点随机选择N个邻接节点散播消息【假定fan-out(扇出)设置为6，每次最多往6个节点散播】。
  • 节点只接收消息不反馈结果。
  • 每次散播消息都选择尚未发送过的节点进行散播。
  • 收到消息的节点不回传散播：A -> B，那么B进行散播的时候，不再发给 A。

这里一共有 16 个节点，节点 1 为初始被感染节点，通过 Gossip 过程，最终所有节点都被感染：

传世经典！

如果要实现该协议，有几个需要注意的点：

  • 初始种子节点的定义

  • 更新种子节点状态，通常需要使用UDP协议广播心跳

  • 数据不回传散播，需要每个节点记录之前接收的数据

  • Gossip有两种传播的方式：

    • Anti-Entropy（反熵）：以固定的概率传播所有的数据
    • Rumor-Mongering（谣言传播）：仅传播新到达的数据

    反熵模式使用“simple epidemics(SI model)”的方式：以固定的概率传播所有的数据。所有参与节点只有两种状态：

    1
    2
    Suspective(病原)：处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。
    Infective(感染)：处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点。

    反熵传播过程是每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。

    反熵传播方法每次节点两两交换自己的所有数据会带来非常大的通信负担，因此不会频繁使用，通常只用于新加入节点的数据初始化。

    谣言传播模式使用“complex epidemics”(SIR model)的方式:以固定的概率仅传播新到达的数据。所有参与节点有三种状态：Suspective(病原)、Infective(感染)、Removed(愈除)。

    1
    Removed(愈除):其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

    谣言传播过程是消息只包含最新 update，谣言消息在某个时间点之后会被标记为removed，并且不再被传播。缺点是系统有一定的概率会不一致，通常用于节点间数据增量同步。

    总结： 一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。

  • Gossip协议网络中两个节点之间有三种通讯方式：

    • Push: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
    • Pull：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
    • Push/Pull：与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地

    如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push&Pull 则需 3 次。虽然消息数增加了，但从效果上来讲，Push&Pull 最好，理论上一个周期内可以使两个节点完全一致。直观上，Push&Pull 的收敛速度也是最快的。

下面分别是 Anti-Entropy 和 Rumor-Mongering 的实现伪代码：

Gossip的优点

Gossip是一种去中心化的分布式协议，数据通过节点像病毒一样逐个传播。因为是指数级传播，整体传播速度非常快，很像现在美国失控的2019-nCoV(新冠)一样。它具备以下优势

  • 可扩展性（Scalable）：允许节点的任意增加和减少，新增节点的状态最终会与其他节点一致。
  • 容错（Fault-tolerance）：网络中任何节点的重启或者宕机都不会影响 gossip 协议的运行，具有天然的分布式系统容错特性。
  • 健壮性（Robust）：gossip 协议是去中心化的协议，所以集群中的所有节点都是对等的，没有特殊的节点，所以任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量。
  • 最终一致性（Convergent consistency）：谣言传播可以是指数级的快速传播，因此新信息传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。 O(LogN)
  • 简单

Gossip的缺点

  • 消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网，不可避免的造成消息延迟。
  • 消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此不可避免地引起同一节点多次接收同一消息，增加消息处理的压力。一次通信会对网路带宽、CUP资源造成很大的负载，而这些负载又受限于 通信频率，该频率又影响着算法收敛的速度。
  • 拜占庭问题：如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出问题。

总结

上述优缺点的本质是因为Gossip是一个带冗余的容错算法，是一个最终一致性算法，虽然无法保证在某个时刻所有节点状态一致，但可以保证在“最终所有节点一致”，“最终”的时间是一个理论无法明确的时间点。所以适合于AP场景的数据一致性处理，常见应用有：P2P网络通信、Apache Cassandra、Redis Cluster、Consul。

参考：

https://ask.qcloudimg.com/draft/6986415/rdrwmo0c0c.pdf

https://cloud.tencent.com/developer/article/1662426

https://www.cnblogs.com/jockming/p/12627868.html#autoid-1-0-0

代码实现：

https://github.com/edwardcapriolo/gossip

https://github.com/libopenstorage/gossip