查看原文
其他

分布式系统的“流言蜚语”

码农翻身刘欣 码农翻身 2021-04-20


你也许用过Redis,Cassandra,Amazon S3, BitTorrent 等著名的软件,但是也许你不知道,它们在底层通信时都采用了一个叫做Gossip(流言蜚语)的协议。


我一直以来都想写一下这个Gossip, 但是苦于找不到合适的方式,今天看到这Gossip模拟器(点阅读原文查看),我就知道不用我写了,我给大家搬运一下就行了。


开始之前,我的习惯还是得先讲讲问题,有了问题,你才会知道这个技术到底想解决什么问题。


假设你有一个集群,这个集群中有上千台服务器,现在客户对服务器A上的一个数据做了改动,你想让这个改动迅速地传遍整个集群中的服务器,换句话说,让这些服务器的数据都达到一致性的状态, 你会怎么办呢?


最简单的办法


让客户的数据改动,保存到一个稳定的服务器X上,然后其他的服务器A,B,C,D.... 都从服务器X中去定期地拉取数据不就行了?


但是在分布式的情况下,至少会有两个问题:


1.  服务器X虽然很稳定,但还是可能会挂掉,一旦挂掉,整个系统就完了。


还可以给服务器X做备份嘛,让数据同步到服务器X1, X2,X3....中,这样就不怕服务器X挂掉了,但是问题又出现了,如何让数据在这些服务器X, X1,X2,X3之间达成一致呢?


2.  由于网络原因(这是非常常见的),如果某一台服务器H连不上服务器X, 它也无法拉取数据了,即使服务器H能连上其他服务器也不行。


这就是一个典型的分布式系统中的一致性的问题,科学家们已经研究出了很多中算法出来,比如Paxos, Raft,今天我们要介绍的就是其中之一:Gossip协议,也可以叫做流言蜚语协议,这个协议就类似于社交网络中小道消息的传播,一传十,十传百,最后迅速传遍整个网络。


图解Gossip


流言蜚语协议是怎么玩的呢? 我们来看看这个图:



图中有40个花花绿绿的圆圈,表示40个节点,就认为是服务器吧。

接下来,我选择了一个节点,假设数据改动发生在它这里:


接下里我可以显示这个节点所知道的那些“相邻节点”,  如图中的绿线所示。


其中有4根线比较粗,那就意味着这个节点从相邻节点中随机地选择了4个来发送消息。


数目4 被称为Fanout



接下里就可以发送消息了,注意,消息发送完以后,这4个节点也变红了,这就意味着他们已经收到了数据的更新。


用病毒传播的术语来说,有4个节点被感染了。


接下来,所有的红色节点(拥有数据更新的、被“感染”的节点)遵循第一个节点的策略,从自己知道的节点中随机选择4个,传播这次的数据改动。


于是,更多的节点被“感染”了,变红了。


如此循环下去,被感染的节点持续随机传播“病毒”(数据改动),最后所有的节点都被传染了,达到了一致性的状态。



来一张动图,看一看整体的过程,感兴趣的同学可以直接点击阅读原文去网站玩一下,非常有意思。




这里展示的是40个节点的情况,可以看到,经过3轮次以后,所有的节点都被感染了,数据保持一致了。


优点


1. 可伸缩性


刚才展示的是40个节点, 如果是80个节点呢? 经过多少轮传播才能达成一致?


大家可以自己玩一下,实际上仅仅需要4轮就可以了,


从理论上讲, Gossip协议的的复杂度是O(logN) , 如果每次随机选取4个节点作为Fanout 的话:

40个节点:  2.66 轮

80个节点:  3.16 轮

120个节点: 3.45 轮

....

可见流言蜚语协议对付节点的增长是非常有效的。


2. 容错性


假设节点A和节点B之间是有连接的,A可以向B发送消息, A-> B


突然有一天由于网络原因,A无法连接上B,消息发不过去,怎么办?


不用担心,总会有另外一个节点从另外一个路径发送给它,例如C->B


从下面的动图中能看得更加清楚, 我把两个消息传输的路径给删除了,但是对应的节点还是从其他途径收到了消息。



3. 收敛的一致性


Gossip 协议能以一传十,十传百这种指数级快速传播信息,当一个消息到达以后,能够快速传遍整个网络,系统状态的不一致可以在很快的时间内收敛,消息传播速度是log(N)


4. 极端去中心化


Gossip 协议不要求任何中心的关键节点,所有节点都可以是对等的,任何一个节点无需知道整个网络状况,只要网络是连通的,任意一个节点就可以把消息散播到全网。


其他通信模式


这个模拟器展示的只是一种通信模式: Push , 也就是说一个节点把数据推送给其他节点。


还有拉的方式(Pull): 节点A 将本地数据的版本告诉其他节点,其他节点将比A新的数据发给节点A,  A再来更新数据。


当然还可以有推拉结合(Push-Pull)结合的方式。


缺点


世界上没有免费的午餐,流言蜚语协议也有弱点:


消息是有延迟的


Gossip协议虽然传播得很快,但是还需要经过几个轮次的传播才能到达全网的所有节点, 这就不适合对实时性要求很高的场景了。 或者说,Gossip协议只能达到最终一致性。


消息是有冗余的


从动图中可以清楚地看出,消息的发送是有冗余的,尤其是到了后面几轮,大多数节点已经收到了消息,但是还在持续选择节点发送,消息数可以说是蔚为壮观啊。


你可能会喜欢

关于老刘和码农翻身

我是一个线程

我是一个Java Class

面向对象圣经

TCP/IP之大明邮差

CPU阿甘

负载均衡的原理

一个故事讲完HTTPs

编程语言的巅峰

Java:一个帝国的诞生

JavaScript:一个屌丝的逆袭

C语言:春节回家,我发现只有我没有对象

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存