炼数成金 门户 大数据 分布式系统 查看内容

图解Gossip-可能是最有趣的一致性协议

2019-8-26 09:33| 发布者: 炼数成金_小数| 查看: 14077| 评论: 0|原作者: 阿飞的博客|来自: 简书

摘要: Gossip协议是一个通信协议,一种传播消息的方式,灵感来自于:瘟疫、社交网络等。使用Gossip协议的有:Redis Cluster、Consul、Apache Cassandra等。说到社交网络,就不得不提著名的六度分隔理论。1967年,哈佛大学 ...

网络 Hadoop 集群 分布式 Redis

Gossip是什么
Gossip协议是一个通信协议,一种传播消息的方式,灵感来自于:瘟疫、社交网络等。使用Gossip协议的有:Redis Cluster、Consul、Apache Cassandra等。

六度分隔理论
说到社交网络,就不得不提著名的六度分隔理论。1967年,哈佛大学的心理学教授Stanley Milgram想要描绘一个连结人与社区的人际连系网。做过一次连锁信实验,结果发现了“六度分隔”现象。简单地说:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。

数学解释该理论:若每个人平均认识260人,其六度就是260↑6 =1,188,137,600,000。消除一些节点重复,那也几乎覆盖了整个地球人口若干多多倍,这也是Gossip协议的雏形。

原理
Gossip协议基本思想就是:一个节点想要分享一些信息给网络中的其他的一些节点。于是,它周期性的随机选择一些节点,并把信息传递给这些节点。这些收到信息的节点接下来会做同样的事情,即把这些信息传递给其他一些随机选择的节点。一般而言,信息会周期性的传递给N个目标节点,而不只是一个。这个N被称为fanout(这个单词的本意是扇出)。

用途
Gossip协议的主要用途就是信息传播和扩散:即把一些发生的事件传播到全世界。它们也被用于数据库复制,信息扩散,集群成员身份确认,故障探测等。
基于Gossip协议的一些有名的系统:Apache Cassandra,Redis(Cluster模式),Consul等。

图解
接下来通过多张图片剖析Gossip协议是如何运行的。如下图所示,Gossip协议是周期循环执行的。图中的公式表示Gossip协议把信息传播到每一个节点需要多少次循环动作,需要说明的是,公式中的20表示整个集群有20个节点,4表示某个节点会向4个目标节点传播消息:


Gossip Protocol

如下图所示,红色的节点表示其已经“受到感染”,即接下来要传播信息的源头,连线表示这个初始化感染的节点能正常连接的节点(其不能连接的节点只能靠接下来感染的节点向其传播消息)。并且N等于4,我们假设4根较粗的线路,就是它第一次传播消息的线路:

first infected node

第一次消息完成传播后,新增了4个节点会被“感染”,即这4个节点也收到了消息。这时候,总计有5个节点变成红色:


infected nodes

那么在下一次传播周期时,总计有5个节点,且这5个节点每个节点都会向4个节点传播消息。最后,经过3次循环,20个节点全部被感染(都变成红色节点),即说明需要传播的消息已经传播给了所有节点:


infected all nodes

需要说明的是,20个节点且设置fanout=4,公式结果是2.16,这只是个近似值。真实传递时,可能需要3次甚至4次循环才能让所有节点收到消息。这是因为每个节点在传播消息的时候,是随机选择N个节点的,这样的话,就有可能某个节点会被选中2次甚至更多次。

发送消息
由前面对Gossip协议图解分析可知,节点传播消息是周期性的,并且每个节点有它自己的周期。另外,节点发送消息时的目标节点数由参数fanout决定。至于往哪些目标节点发送,则是随机的。

一旦消息被发送到目标节点,那么目标节点也会被感染。一旦某个节点被感染,那么它也会向其他节点传播消息,试图感染更多的节点。最终,每一个节点都会被感染,即消息被同步给了所有节点:


infected

可扩展性
Gossip协议是可扩展的,因为它只需要O(logN) 个周期就能把消息传播给所有节点。某个节点在往固定数量节点传播消息过程中,并不需要等待确认(ack),并且,即使某条消息传播过程中丢失,它也不需要做任何补偿措施。大哥比方,某个节点本来需要将消息传播给4个节点,但是由于网络或者其他原因,只有3个消息接收到消息,即使这样,这对最终所有节点接收到消息是没有任何影响的。

如下表格所示,假定fanout=4,那么在节点数分别是20、40、80、160时,消息传播到所有节点需要的循环次数对比,在节点成倍扩大的情况下,循环次数并没有增加很多。所以,Gossip协议具备可扩展性:


可扩展性

失败容错
Gossip也具备失败容错的能力,即使网络故障等一些问题,Gossip协议依然能很好的运行。因为一个节点会多次分享某个需要传播的信息,即使不能连通某个节点,其他被感染的节点也会尝试向这个节点传播信息。

健壮性
Gossip协议下,没有任何扮演特殊角色的节点(比如leader等)。任何一个节点无论什么时候下线或者加入,并不会破坏整个系统的服务质量。
然而,Gossip协议也有不完美的地方,例如,拜占庭问题(Byzantine)。即,如果有一个恶意传播消息的节点,Gossip协议的分布式系统就会出问题。

声明:本文版权归原作者所有,文章收集于网络,为传播信息而发,如有侵权,请联系小编及时处理,谢谢!

欢迎加入本站公开兴趣群
软件开发技术群
兴趣范围包括:Java,C/C++,Python,PHP,Ruby,shell等各种语言开发经验交流,各种框架使用,外包项目机会,学习、培训、跳槽等交流
QQ群:26931708

Hadoop源代码研究群
兴趣范围包括:Hadoop源代码解读,改进,优化,分布式系统场景定制,与Hadoop有关的各种开源项目,总之就是玩转Hadoop
QQ群:288410967 

鲜花

握手

雷人

路过

鸡蛋

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2019-9-18 02:22 , Processed in 0.162719 second(s), 24 queries .

江苏快三开奖结果 河北快3开奖结果 上海快3开奖结果 内蒙古快三开奖结果 湖北快3开奖结果 江苏快3开奖结果 极速快3开奖结果 河北快三开奖结果 上海快3开奖结果 江苏快三开奖结果