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

你也许用过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语言：春节回家，我发现只有我没有对象