图解Gossip:可能是最有趣的一致性协议
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个目标节点传播消息:
如下图所示,红色的节点表示其已经“受到感染”,即接下来要传播信息的源头,连线表示这个初始化感染的节点能正常连接的节点(其不能连接的节点只能靠接下来感染的节点向其传播消息)。并且N等于4,我们假设4根较粗的线路,就是它第一次传播消息的线路:
第一次消息完成传播后,新增了4个节点会被“感染”,即这4个节点也收到了消息。这时候,总计有5个节点变成红色:
那么在下一次传播周期时,总计有5个节点,且这5个节点每个节点都会向4个节点传播消息。最后,经过3次循环,20个节点全部被感染(都变成红色节点),即说明需要传播的消息已经传播给了所有节点:
需要说明的是,20个节点且设置fanout=4,公式结果是2.16,这只是个近似值。真实传递时,可能需要3次甚至4次循环才能让所有节点收到消息。这是因为每个节点在传播消息的时候,是随机选择N个节点的,这样的话,就有可能某个节点会被选中2次甚至更多次。
发送消息
由前面对Gossip协议图解分析可知,节点传播消息是周期性的,并且 每个节点有它自己的周期 。另外,节点发送消息时的 目标节点数 由参数fanout决定。至于往哪些目标节点发送,则是 随机 的。
一旦消息被发送到目标节点,那么目标节点也会被感染。一旦某个节点被感染,那么它也会向其他节点传播消息,试图感染更多的节点。最终,每一个节点都会被感染,即消息被同步给了所有节点:
可扩展性
Gossip协议是可扩展的,因为它只需要O(logN) 个周期就能把消息传播给所有节点。某个节点在往固定数量节点传播消息过程中,并不需要等待确认(ack),并且,即使某条消息传播过程中丢失,它也不需要做任何补偿措施。大哥比方,某个节点本来需要将消息传播给4个节点,但是由于网络或者其他原因,只有3个消息接收到消息,即使这样,这对最终所有节点接收到消息是没有任何影响的。
如下表格所示,假定fanout=4,那么在节点数分别是20、40、80、160时,消息传播到所有节点需要的循环次数对比,在节点成倍扩大的情况下,循环次数并没有增加很多。所以,Gossip协议具备可扩展性:
失败容错
Gossip也具备失败容错的能力,即使网络故障等一些问题,Gossip协议依然能很好的运行。因为一个节点会 多次 分享某个需要传播的信息,即使不能连通某个节点,其他被感染的节点也会尝试向这个节点传播信息。
健壮性
Gossip协议下,没有任何扮演特殊角色的节点(比如leader等)。任何一个节点无论什么时候下线或者加入,并不会破坏整个系统的服务质量。
然而,Gossip协议也有不完美的地方,例如, 拜占庭 问题(Byzantine)。即,如果有一个恶意传播消息的节点,Gossip协议的分布式系统就会出问题。
*** 图解Raft:应该是最容易理解的分布式一致性算法 ***