Gossip又被称为流行病算法,它与流行病毒在人群中传播的性质类似,由初始的几个节点向周围互相传播,到后期的大规模互相传播,最终达到一致性。Gossip协议被广泛应用于P2P网络,同时一些分布式的数据库,如Redis集群的消息同步使用的也是Gossip协议,另一个重大应用是被用于比特币的交易信息和区块信息的传播。

Gossip协议的整体流程非常简单,传输示意图见上图.初始由几个节点发起消息,这几个节点会将消息的更新内容告诉自己周围的节点,收到消息的节点再将这些信息告诉周围的节点。依照这种方式,获得消息的节点会越来越多,总体消息的传输规模会越来越大,消息的传偶速度也越来越快。虽然不是每个节点都能在相同的时间达成一致,但是最终集群中所有节点的信息必然是一致的。Gossip协议确保的是分布式集群的最终一致性。

预先设定好消息更新的周期时间T,以及每个节点每个周期能够传播的周围节点数,我们可以得到大致的消息更新流程如下:

  1. 节点A收到新消息并更新
  2. 节点A将收到的消息传递给与之直接相连的B,C
  3. B,C各自将新更新的消息传给与之直接相连的两个节点,这些节点不包含A
  4. 最终集群达成一致

在Gossip算法中,Gossip每次新感染的节点都会至少再感染一个节点,展开来看,这就是一个多叉树的结构,那么依据这个结构,最大的时间复杂度即使一个二叉树的形式,这时整体上达到一致性的速度是log(n)。可见Gossip传播性能还是相当惊人的,著名的Redis数据库便是使用Gossip传播协议保持一致性,Redis最多可支持百万级别的节点,gossip协议在其中起到了重要作用。

说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...