分布式系统的“流言蜚语”
你也许用过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协议，也可以叫做流言蜚语协议，这个协议就类似于社交网络中小道消息的传播，一传十，十传百，最后迅速传遍整个网络。
流言蜚语协议是怎么玩的呢？ 我们来看看这个图：
图中有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协议只能达到最终一致性。
消息是有冗余的
从动图中可以清楚地看出，消息的发送是有冗余的，尤其是到了后面几轮，大多数节点已经收到了消息，但是还在持续选择节点发送，消息数可以说是蔚为壮观啊。