Gossip 协议

前言

通过对 Raft 等算法的了解,我们知道它们都需要大多数节点正常运行才能稳定运行。如果我们需要系统在极端的情况下也要保证正常运行,比如集群中只有一个节点,那么就必须另辟蹊径了。其实,要求系统在极端的情况下也能稳定运行,根据 BASE 理论,这需要实现最终一致性,而 Gossip 协议就能实现这种系统。

概述

Gossip 协议,顾名思义就像流言蜚语一样,利用一种随机、带有传染性的方式,将信息传播到整个网络中,并在一定时间内,使得系统内的所有节点数据一致。

思考

集群中一个节点上有数据被改动,如果想让这个改动迅速传遍整个集群中的节点,进而达到一致性的状态。一般常见的做法是发生改动的节点将最新的数据发送到其它节点,或者其它节点去定期拉取数据。但是上述的解决方案在分布式的情况下会存在以下问题:

  • 发生改动的节点还没有将最新数据给到其它节点宕机了
  • 由于网络原因,可能存在某个或某些节点不能连接上发生改动的节点,那么也不能获取到数据,即使其它节点已经同步到了最新的数据。
    以上两个问题虽然在像 Raft 等算法中能解决,但是存在效率问题。而我们今天的主角 Gossip 协议就能很好的解决以上问题,以一传十,十传百的方式最后迅速传遍整个集群。

过程

Gossip 过程是由种子节点发起,它会周期性的随机选择周围几个节点散播消息,收到消息的节点也会重复该过程,直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间,由于不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,因此它是一个最终一致性协议。需要注意的是,Gossip 过程是异步的,也就是说发消息的节点不会关注对方是否收到,即不等待响应;

类型

Gossip 有两种类型:

  • 反熵:传播所有的数据
  • 谣言传播:仅传播新到达的数据

反熵

反熵指的是集群中的节点,每隔段时间就随机选择其它节点,然后通过相互交换自己的所有数据来消除两者之间的差异,实现数据的最终一致性。

需要注意的是,反熵需要节点两两交换和对比自己所有的数据,执行反熵时通讯成本会很高。其次,反熵虽然实用,但是执行反熵时相关的节点都是已知的,而且节点数量不能太多,如果是一个动态变化或节点比较多的分布式环境,这时反熵就不适用了。

谣言传播

谣言传播,指的是当一个节点有了新数据后,这个节点变成活跃状态,并周期性地联系其它节点向其发送数据,直到所有的节点都存储了该新数据。谣言传播非常具有传染性,它适合动态变化的分布式系统。

通信模式

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

特点

优势

扩展性:允许节点的任意增加和减少,新增节点的状态最终会与其他节点一致。
容错性:任意节点的宕机和重启都不会影响 Gossip 消息的传播,一方面一个节点会多次传播信息,另一方面即使不能连通某个节点,其他被“感染”的节点也会尝试向这个节点传播信息。具有天然的分布式系统容错性。
健壮性:无需中心节点,所有节点都是对等的,只要网络连通,任意节点可把消息散播到全网。

缺点

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

需要说明的是,Gossip 协议适用于 AP 场景的数据一致性。

小结

Gossip 协议基本思想是,一个节点想要分享一些信息给网络中的其他节点,会周期性的随机选择一些节点,并把信息传递给这些节点。这些收到信息的节点接下来会做同样的事情,即把这些信息传递给其他一些随机选择的节点。基于 Gossip 协议的一些系统,如 Apache Cassandra,Redis(Cluster模式),Consul等。