数据同步gossip协议原理与应用场景介绍

作者：京东物流 冯鸿儒

1 简介

Gossip是一种p2p的分布式协议。它的核心是在去中心化结构下，通过将信息部分传递，达到全集群的状态信息传播，传播的时间收敛在O（Log（N））以内，其中N是节点的数量。基于gossip协议，可以构建出状态一致的各种解决方案。
一些常见的分布式协议如二阶段提交协议和 Raft 算法，你发现它们都需要全部节点或者大多数节点正常运行，才能稳定运行。而Gossip即使只有一个节点可用也能提供服务。

1.1 适用场景

适用于AP 场景的数据一致性处理：分布式数据库中节点同步数据使用（如Apache Cassandra、Redis Cluster）；
其他场景如信息扩散、集群成员身份确认、故障探测等（如Consul）。

1.2 优势

• 学习成本：实现简单
• 扩展性：允许节点的任意增加和减少，新增节点的状态 最终会与其他节点一致。
• 容错：任意节点的宕机和重启都不会影响 Gossip 消息的传播，具有天然的分布式系统容错特性。可以在一定程度上避免网络分割带来的问题。
• 去中心化：无需中心节点，所有节点都是对等的，任意节点无需知道整个网络状况，只要网络连通，任意节点可把消息散播到全网。
• 性能：指数级一致性收敛。消息会以“一传十的指数级速度”在网络中传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
  Gossip协议的最大的好处是，即使集群节点的数量增加，每个节点的负载也不会增加很多，几乎是恒定的。如Consul管理的集群规模能横向扩展到数千个节点。

1.3 劣势

• 消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网；不可避免的造成消息延迟。
• 消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤；不可避免的引起同一节点消息多次接收，增加消息处理压力。

2 细节介绍

2.1 传播方式

Gossip 协议的消息传播方式主要有两种：Anti-Entropy(反熵传播)和 Rumor-Mongering(谣言传播)。

2.1.1 反熵传播

• 定义：反熵（指消除不同节点中数据的差异，提升节点间数据的相似度，降低熵值）。反熵传播：以固定的概率传播所有的数据，可用来避免因为UDP数据包丢失或者新节点的加入而导致的集群元数据不一致问题。
• 过程：集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。
• 适用场景：执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境（比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态），这时反熵就不适用了。
• 缺点：消息数量非常庞大，且无限制；通常只用于新加入节点的数据初始化。可以通过引入校验和（Checksum）等机制，降低需要对比的数据量和通讯消息等。

2.1.2 谣言传播

• 定义：当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。
• 过程：消息只包含最新 update，谣言消息在某个时间点之后会被标记为 removed，并且不再被传播。
• 当一个新节点A连接到Gossip集群内的某个节点B时，A节点会将自己的信息发送给B节点，然后B节点会在集群中随机选取几个未被传染的节点，向他们广播A节点的信息（首次传染），集群中的其他节点收到A节点的信息后，又会像B节点那样广播A节点的信息给其他未被传染的节点（二次传染）。直至多次传染后，集群所有节点都收到了A节点的信息，同步完成。
• 适用场景：适合动态变化的分布式系统。
• 缺点：系统有一定的概率会不一致，通常用于节点间数据增量同步。

2.2 通信方式

Gossip 协议最终目的是将数据分发到网络中的每一个节点。根据不同的具体应用场景，网络中两个节点之间存在三种通信方式：推送模式、拉取模式、Push/Pull。

• 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 的收敛速度也是最快的。

2.3 执行示例

2.3.1 状态的传播

以Gossip协议同步状态的思路类似于流言的传播,如下图所示。

A节点率先知道了某个流言（msg），它首先将此信息传播到集群中的部分节点（比如相邻的两个节点）B和C，后者再将其传递到它们所选择的“部分”节点，例如B选择了D和E，C选择了将流言传播到B和F。以此类推，最终来自于A的这条流言在3轮交互后被传播到了集群中的所有节点。
在分布式系统的实践中，这个“流言”可能是：某个节点所感知到的关于其它节点是否宕机的认识；也可能是数据水平拆分的缓存集群中，关于哪些hash桶分布在哪些节点上的信息。每个节点起初只掌握部分状态信息，不断地从其它节点收到gossip信息，每个节点逐渐地掌握到了整个集群的状态信息。因此解决了状态同步的第一个问题：全集状态的获取。
对于集群中出现的部分网络分割，消息也能通过别的路径传播到整个集群。如下图所示：

2.3.2 状态的一致

状态同步的第二个问题：对于同一条状态信息，不同的节点可能掌握的值不同，也能通过基于gossip通信思路构建的协议包版本得到解决。例如水平拆分的redis缓存集群，初始状态下hash桶在各个节点的分布如下图所示：

此时各个节点预先通过某种协议（比如Gossip）得知了集群的状态全集，此时新加入了节点D，如下图所示：

D分担了C的某个hash桶，此时C/D和集群中其它节点就C所拥有哪些hash这件事发生了分歧：A/B认为C目前有6/7/8个hash桶。此时通过为gossip消息体引入版本号，使得关于C的最新状态信息（只有6/7两个桶了）在全集群达到一致。例如B收到来自A和C的gossip消息时会将版本号更新的消息（来自C的v2）更新到自己的本地副本中。
各个节点的本地副本保存的集群全量状态也可能用来表示各个节点的存活状态。对于部分网络分割的情况如下图所示：

例如A和C的网络断开，但A和C本身都正常运行，此时A和C互相无法通信，C会将A标记为不可用状态。对于中心化思路的协议，如果C恰好是中心节点，那么A不可用的信息将会同步到集群的所有节点上，使得这些节点将其实可用的A也标记为宕机。而基于gossip这类去中心化的协议进行接收到消息后的实现逻辑扩展（例如只有当接收到大多数的节点关于A已经宕机的消息时，才更新A的状态），最终保证A不被误判为宕机。

3 开源软件中的应用

3.1 Fabric

Fabric gossip使用push（从成员视图随机选出活跃邻居，给他们转发消息），pull（定期探测，请求遗失的消息）的方式扩散区块。

3.2 Cassandra

Cassandra使用的是pull-push，这种方式是均等的，会有3次发送，但是发送完以后双方都可以更新彼此的信息。利用pull-push方式，如果A要与B节点同步，需要进行如下图的三个通信阶段。

3.3 RedisCluster

Redis Cluster 在运行时，每个实例上都会保存 Slot 和实例的对应关系（也就是 Slot 映射表），以及自身的状态信息。新节点加入、节点故障、Slot 变更等事件发生时，实例间也可以通过 gossip协议进行PING、PONG 消息的传递，完成集群状态在每个实例上的同步。
redisCluster默认组建集群的方式：

• 通过cluster meet命令将一个节点跟集群中其中一个节点建立连接（此时只能被集群中这一个节点认识）
• 通过Gossip消息转播给其他节点，其他节点收到消息后，再通过类似meet的命令来跟对新节点建立集群连接（需要一定时间的扩散）

使用gossip算法利用PFAIL和FAIL flags的转换和传播来判定故障

3.4 Consul

一致性协议采用 Raft 算法,用来保证服务的高可用.
成员管理和消息广播 采用GOSSIP协议，支持ACL访问控制。
consul是建立在serf之上的，它提供了一个完整的gossip协议，用在很多地方。Serf提供了成员，故障检测和事件广播。Gossip的节点到节点之间的通信使用了UDP协议。
Consul的每个Agent会利用Gossip协议互相检查在线状态，本质上是节点之间互Ping，分担了服务器节点的心跳压力。如果有节点掉线，不用服务器节点检查，其他普通节点会发现，然后用Gossip广播给整个集群。

4 总结

gossip协议是很多开源中间件和区块链实现的一种底层通信机制，掌握它的原理和细节能更好的理解中间件和区块链的一些行为和分布式特性。