分布式一致性算法06:Gossip

Gossip是一个最终一致性协议,适用于大规模的、弱一致性的、去中心化的场景。

为了达到最终一致性,Gossip实际上提供了三种同步方式:Direct Mail(直接邮寄)、Rumor Mongering(谣言传播)及 Anti-Entropy(反熵)。看起来都是新技术名词,但分开来看,却都十分简单。

1、Direct Mail(直接邮寄,增量)
通俗解释就是,当一个节点收到客户端的新信息后,就把这个新信息传递给系统内的每个节点。
Direct Mail功能实现简单、效率也很高。

但在一个开放性的大规模非中心化网络中,经常会出现节点的变化(增加、掉线、宕机),这种场景下,仅靠Direct Mail,是不可能实现最终一致性的。
比如,节点X宕机了1一小时,然后启动。这一小时中的数据就丢失了。虽然在技术上,我们可以将信息做一些缓存,但在一个开放网络里,管理每个节点是否接收并处理好自己发送的全部消息,这本身就是个技术难题,而且效率将会及其低下。

2、Anti-Entropy(反熵,全量)
通俗解释就是,一个节点,定期会选择一些节点,对比数据的差异,并相互修复缺失的数据。
同步方式,可以是推送、拉取、连推带拉。
Anti-Entropy会比较整个数据库的异同,是达成最终一致性的最后手段。

Anti-Entropy消息以固定的概率传播全量的数据。
所有节点只有两种状态:Suspective(病原)、Infective(感染),也被称作simple epidemics(SI model)。
S节点会把所有的数据都跟I节点共享,以便消除节点之间数据的任何不一致,它可以保证最终、完全的一致。

但是,在一个开放性的大规模非中心化网络中,定期同步全量数据,将会带来巨大的资源消耗。
所以这个操作的频率,必须足够低,否则整个网络就不用做其他事情了。
注:在实际工程落地中,为了加快数据同步效率,并不一定会“随机”选择同步节点,而是会想办法,用一定的顺序,尽快让全部节点完成同步。

聪明的你一定会发现,通过Direct Mail和Anti-Entropy,已经可以实现最终一致性的效果了。
但Direct Mail无法保证成功,Anti-Entropy无法保证频率,我们需要寻找额外的同步方案,在消耗尽量少资源的前提下,让整个网络的的可用性大幅提升。

3、Rumor Mongering(谣言传播,增量)
通俗解释就是,当一个节点收到新消息后,随机挑选N个节点,把新消息推送给这些节点。这N的节点在收到消息后,又会分别随机选择N个节点,推送新消息。
同步方式,同样可以是推送、拉取、连推带拉。

Rumor Mongering消息以固定的概率传播增量数据。
所有节点有三种状态:Suspective(病原)、Infective(感染)、Removed(愈除)。也被称作complex epidemics(SIR model)。
S节点只会把追加消息发送给随机选择的I节点。而这个消息在某个时间点之后会被标记为Removed,并且不再被传播。
根据六度分隔理论,经过几轮随机推送,可以基本确保每个节点都收到了新消息。但部分特殊节点仍有可能并未收到所有的追加消息。
所以,通过Direct Mail和Rumor Mongering并无法保证达到最终一致性。

聪明的你一定会发现,这一个信息,会被多次重复推送,一个节点也会重复接收。这其实是一个实现复杂度和性能之间的一个均衡。
和协议的名字相似,风言风语,口口相传,很快全村就都知道了。

4、新节点加入怎么处理
当一个节点加入网络后,会先使用Anti-Entropy的拉取方式,获取一个相对比较新的数据库。
然后就可以通过Direct Mail、Rumor Mongering获取新数据啦。
最后,还有Anti-Entropy,定期全量对比更新数据,这样新节点加入后,网络很快就能达到一致性了。

可见,Gossip协议,原理很简单,实现也并不复杂。虽然有一定程度的通讯浪费,但对于开放性的大规模非中心化网络中,Gossip协议很好的平衡了可用性、性能、工程复杂度之间的关系,实际中也获得了不少项目的青睐。

Leave a Reply

Your email address will not be published. Required fields are marked *

*