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

作者：刘欣 2019-03-18 16:29:01

开发

开发工具

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

[[259783]]

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

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

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

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

[[259785]]

最简单的办法

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

[[259785]]

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

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

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

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

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

图解Gossip

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

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

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

[[259785]]

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

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

数目4 被称为Fanout

[[259785]]

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

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

[[259785]]

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

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

[[259785]]

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

[[259785]]

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

这里展示的是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协议只能达到最终一致性。

消息是有冗余的

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

【本文为51CTO专栏作者“刘欣”的原创稿件，转载请通过作者微信公众号coderising获取授权】

戳这里，看该作者更多好文