你可能用过Redis、Cassandra、AmazonS3、BitTorrent等著名软件，但你可能不知道它们在底层通信协议中都使用了一个Gossip（八卦）。一直想写这篇八卦，却找不到合适的方式。今天看到这个八卦模拟器（点击阅读原文查看），就知道不用写了。我只是为每个人携带它。在开始之前，还是要先说说问题。只有出了问题，你才会知道这个技术要解决什么问题。假设你有一个集群，这个集群里有几千台服务器，现在客户端对服务器A上的一个数据做了一个改动，你想让这个改动快速的传播到整个集群里的服务器上，也就是说，让这些servers如果所有的数据都达到了一致的状态，你会怎么做？最简单的办法就是把客户的数据改了，保存在一个稳定的服务器X上，然后其他服务器A、B、C、D……都定期从服务器X上拉取数据不就可以了吗？但是在分布式的情况下，至少有两个问题：1.服务器X虽然很稳定，但是还是有可能挂掉。一旦挂了，整个系统就完事了。还可以给X服务器做备份，让数据同步到X1、X2、X3……服务器，这样就不怕X服务器挂了，但是问题又来了，如何让数据在X1、X2、X3...这些服务器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个节点呢？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协议传播速度快，但需要经过好几轮传播才能到达全网所有节点，不适合对于实时性要求高的场景。也就是说，Gossip协议只能做到最终一致性。消息是多余的。从动画中可以明显看出消息的发送是多余的，尤其是接下来的几轮。大多数节点已经收到消息，但它们仍在选择要发送的节点。留言的数量可以说是蔚为壮观。【本文为专栏作家“刘欣”原创稿件，转载请通过作者微信获取授权公众号coderising】点此查看该作者更多好文
