Gossip协议

Gossip

Trying to squash a rumor is like trying to unring a bell.

—— Shana Alexander,American Journalist

Paxos、Raft、ZAB这些分布式算法经常会被称作是“强一致性”的分布式共识协议,这样的描述扣细节概念的话是很别扭的,有语病嫌疑,但我们都明白它的意思其实是在说“尽管系统内部节点可以存在不一致的状态,内部是最终一致的,但从系统外部看来,不一致的情况并不会被观察到,所以整体上看系统是强一致性的”。与它们相对的,还有一类被冠以“最终一致性”的分布式共识协议,这表明系统中不一致的状态有可能能够在一定时间内被外部观察到。一种典型而又极为常见的最终一致的分布式系统就是DNS系统,在各节点缓存的TTL到期之前,都有可能与真实的域名翻译结果存在不一致,在本节中,我们将介绍在比特币网络和许多重要分布式框架中都有应用的另一种具有代表性的“最终一致性”的分布式共识协议:Gossip协议。

Gossip最早由施乐公司(Xerox,现在可能很多人不了解施乐了,或只把施乐当一家复印产品公司看待,这家公司是计算机许多关键技术的鼻祖,图形界面的发明者、以太网的发明者、激光打印机的发明者、MVC架构的提出者、RPC的提出者、BMP格式的提出者……) Palo Alto研究中心在论文《Epidemic Algorithms for Replicated Database Maintenance》中提出的一种用于分布式数据库在多节点间复制同步数据的算法。从论文题目中可以看出,最初它是被称作“流行病算法”(Epidemic Algorithm)的,而今天Gossip这个名字使用得更为普遍。除此以外,它还有“流言算法”、“八卦算法”、“瘟疫算法”等别名,这些名字都是很形象化的描述,反应了Gossip的特点:要同步的信息如同流言一般传播、病毒一般扩散。

尽管笔者按照习惯也把Gossip也称作是“共识协议”,但首先必须强调它所解决的问题并不是直接与Paxos、Raft这些共识协议等价的,只是基于Gossip之上可以通过某些方法去实现与Paxos、Raft一致的目标。一个最典型的例子是比特币网络中使用到了Gossip协议,用它来在各个分布式节点中互相同步区块头和区块体的信息,这是整个网络能够正常交换信息的基础,但并不能称作共识;比特币使用工作量证明(Proof of Work,PoW)来对“这个区块由谁来记账”这一件事情在全网达成共识,这个目标才可以认为与Paxos、Raft的目标是一致的。

下面,我们来了解Gossip的具体算法过程。相比起Paxos、Raft,Gossip的算法过程可算是十分简单了,它可以看作是以下两个步骤的简单循环:

  • 如果有某一项信息需要在整个网络中所有节点中传播,那从信息源开始,选择一个固定的传播周期(譬如1秒),随机选择它相连接的k个节点(称为Fan-Out)来传播消息。

  • 每一个节点收到消息后,如果这个消息是它之前没有收到过的,将在下一个周期内,选择除了发送消息给它的那个节点外的其他相邻k个节点发送相同的消息,直到最终网络中所有节点都收到了消息,尽管这个过程需要一定时间,但是理论上最终网络的所有节点都会拥有相同的消息。

Gossip传播示意图(图片来源

上图是Gossip传播过程的示意图,根据示意图和Gossip的过程描述,我们很容易发现Gossip对网络节点的连通性和稳定性几乎没有任何要求,它将网络某些节点只能与一部分节点部分连通(Partially Connected Network)而不是以全连通网络(Fully Connected Network)作为前提;能够容忍网络上节点的随意地增加或者减少,随意地宕机或者重启,新增加或者重启的节点的状态最终会与其他节点同步达成一致。Gossip把网络上所有节点都视为平等的、普通的,没有任何中心化节点或者主节点的概念,这些特点使得Gossip具有很强的鲁棒性,而且极为适合在公众互联网中应用。

同时我们也很容易找到Gossip的缺点,消息最终是通过多个轮次的散播而到达全网的,因此它必然会存在全网各节点状态不一致的情况,而且由于是随机选取发送消息的节点,所以尽管可以在整体上测算出传播速率,但对于个体消息来说,无法准确地预计到需要多长时间才能达成全网一致。另外一个缺点是消息的冗余,同样是由于随机选取发送消息的节点,也就不可避免的存在消息重复发送给同一节点的情况,增加了网络的传输的压力,也给消息节点带来额外的处理负载。

Gossip传播消息时,有两种可能的传播方式:反熵(Anti-Entropy)和传谣(Rumor-Mongering),这两个名字都挺文艺的。熵(Entropy)是生活中少见但科学中很常用的概念,它代表着事物的混乱程度。反熵的意思就是反混乱,以提升网络各个节点之间的相似度为目标,所以在反熵模式下,会同步节点的全部数据,以消除各节点之间的差异,目标是整个网络各节点完全的一致。但是,在节点本身就会发生变动的前提下,这个目标将使得整个网络中消息的数量会非常庞大,给网络带来巨大的传输开销。而传谣模式是以传播消息为目标,仅仅发送新到达节点的数据,即只对外发送变更信息,这样消息数据量将显著缩减,网络开销也较小。

Kudos to Star
总字数: 1,840 字  最后更新: 8/11/2020, 8:22:53 PM