大家好，我是伟伟。大年初一，看到一个特别离谱的谣言。具体是什么我就不说了，怕脏了大家的眼睛。但是，我在群里看到的，那才叫栩栩如生，讨论得热火朝天，每个人都仿佛身临其境。这件事，我会笑着过去的。可过了一会儿，我突然一拍大腿：这是个料子。我可以和你谈谈共识算法。说到共识算法，大家首先想到的就是Raft、Paxos、Zab算法等强共识算法比较难懂。但是还有一种比较容易理解的弱一致性共识算法，Gossip协议。八卦，先看这个词，圈起来，要考试，这是六级词汇，也是考研用词，意思是“八卦”。下面，小编就带大家简单看看这个“谣言”到底是怎么回事。GossipprotocolGossip协议最早是在1987年发表的一篇论文中提出来的：《Epidemic Algorithms for Replicated Database Maintenance》http://bitsavers.trailing-edg...刚看到这篇论文的名字的时候，一头雾水Forced:Gossip没有关键字.主要是我碰巧知道的EpidemicAlgorithms这两个词。算法，算法，没什么好说的。什么是流行病？与时事密切相关：所以EpidemicAlgorithms的翻译就是流行病算法。所以，Gossip的学名也应该叫“流行算法”，不过大家更喜欢叫它Gossip。毕竟，你不是喜欢听“八卦”吗？在谈论文之前，我们先简单定下基调。你认为共识协议最基本、最核心、最重要的动作是什么？是数据更新吗？为了保证各节点数据的一致性，必须涉及到数据的更新操作。因此，论文的介绍部分描述了三种更新数据的方法：直邮（directmail）反熵（anti-entropy）造谣（rumour）直邮（directmail）先不废话，Go直接上图：上图是什么意思？一共是八个小圆点，假设每个小圆点代表一个服务器，都是平等的关系，没有中心节点、主从关系。顶部的红色节点表示该节点有数据变化，所以变化的数据直接通知给剩余的节点。如果其他节点发生数据变化，也是如此。可以简单理解为循环遍历。每次发生数据变化时，为了保持数据的一致性，必须进行循环遍历。这个方案的优点很明显：简单、粗暴、直接。但是缺点和优点一样明显。看看论文里是怎么说的：主要看but部分：首先，它并不完全可靠，因为这需要每个站点都知道所有站点的存在。但现实情况是，某些站点并不总是了解所有其他站点。然后，信息（邮件）有时会丢失。一旦丢失，连最终的一致性都无法保证，整个就爽了。事实上，直邮（directmail）并不是论文中讨论的主要解决方案，把它写在第一位会起到催化剂的作用。主要说说Anti-entropy（反熵）和Rumor-Mongering（散布谣言）两种解决方案。首先定下整体基调：反熵（anti-entropy），就是把节点上的所有数据都扩散开来。Rumor-Mongering（谣言），就是在节点上传播新到的或变化的数据。说白了，一个是全额，一个是增量。反熵（anti-entropy）有些同学可能对“反熵”这个词一头雾水。其实主要是他们不明白什么是“熵”。其实，说白了，“熵”通俗的理解就是“混沌度”。比如你的房间，如果你不收拾，每件物品的排列就会越来越乱，也就是越来越“熵”。而收拾房间的操作就是“反熵”。这个东西你可以先这样简单的理解，我一时半会儿不给你解释了。要谈这个东西，就得上升到宇宙和哲学的高度。主要是怕你看不懂。在论文中，Anti-entropy模式是这样描述的：每个服务器定期随机选择另一个服务器，两个服务器通过交换各自的内容来消除它们之间的所有差异。这个方案很靠谱。（但开始了）但是你需要检查各个服务器的全部内容。言外之意就是数据量稍大，不能太频繁使用。实验表明，反熵虽然可靠，但传播更新的速度比直邮慢得多。如果不同步，两者的数据差异会越来越大，也就是熵越来越大。同步的目的是减少差异，达到最终一致性，也就是反熵。定义就是这样一个定义。Rumormongering（传播谣言）与反熵相比，谣言从字面意思就很好理解。比如我是一名大学生，我不可能完全了解全校的人。但学校里的同学却有着千丝万缕的联系。假设有一天，我正好遇到小花一个人走在路上，我就上去和她讨论计算机领域的共识算法等相关问题。我们就这些问题进行了深入讨论，交换了相互理解和看法。就这么说吧，整个过程随着讨论的越来越激烈，我也不知道怎么走，直到走到了情人坡。每个大学都应该有一个地方叫情人坡。然后我被另一个女孩看到了。她对她最好的朋友说：你认识WaiWai吗？没错，就是新生，帅哥。当时，我看到他和学妹在情人坡边散步。然后一过十，十过百。全校师生都知道了这个消息。“歪歪和小花漫步情人坡”的消息，通过八卦造谣的八卦模式达成了最终的一致。“造谣”与“反熵”的区别在于只传输新的信息或变化的信息，不需要传输全部信息。比如上面的例子，只需要同步最新消息“歪歪和小花漫步在情人坡”。无需同步“谁是歪歪，谁是小花，爱宝在哪里”之类的信息。在提到“传播谣言”和“反熵”时，论文中有这样的定义：simpleepidemics：在这种模式下，简单的传染病包括两种状态：infective（传染性）和susceptible（易感性infect）。处于感染状态的节点意味着它有数据更新，需要将数据共享（感染）给其他节点。处于易感状态的节点意味着它没有从其他节点（未被感染）接收到数据更新。所以，后面我提到“传染”的时候，大家应该知道，我是从这里看到的，不是瞎编的。关于“造谣”和“逆熵”，再借用《凤凰架构》周志明的认真描述，如下：http://icyfenix.cn/distributi...实现一致性和网络化所需要的时间通信介质消息冗余的两个缺点之间存在一定的对立。如果其中一个要改善，另一个就会恶化。因此，Gossip设计了两种可能的消息传播模式：反熵（Anti-Entropy）和造谣（Rumor-Mongering），这两种模式都颇具文学性。熵这个概念在生活中很少见，但在科学中却很常用。它代表事物的混乱程度。反熵意味着反混沌。目标是提高网络中节点之间的相似性。因此，在反熵模式下，所有节点的数据都会同步，以消除节点之间的差异。目标是确保整个网络中的所有节点完全一致。但是，在节点本身会发生变化的前提下，这种目标会使整个网络中的消息数量非常庞大，从而给网络带来巨大的传输开销。谣言模式以传播消息为目标，只发送新到达节点的数据，即只发送变化信息，这样消息数据量会明显减少，网络开销也相对较小。一个网站有一个摊牌。事实上，我看到这个网站并决定写这篇文章。因为本站有非常模拟的动画直接模拟八卦协议的同步过程，一个动画顶一千字。地址先放在这里，大家可以自行访问玩玩：https://flopezluis.github.io/...先给大家展示一下它的工作过程：不管你懂不懂，这个东西至少看起来很厉害的样子。下面给大家介绍一下它是如何工作的：首先，我们来看一下这里的Nodes和Fanout。nodes其实很好理解，就是节点的个数，这里40代表下面小圆圈的个数，比如我今年18岁，那我改成18就变成这样了：主要是什么这个扇出？在这个网页头部的轮播图中，第一张图是这样的：答案就藏在这个了解更多。https://managementfromscratch...这段话解释了什么是Fanout。同时也简要介绍了八卦协议的基本工作原理。它说八卦协议在概念上非常简单，编码也非常简单。它们背后的基本思想是：一个节点想要与网络中的其他节点共享一些信息。然后它周期性地从节点集合中随机选择一个节点并交换消息，接收到消息的节点也这样做。这些信息被周期性地发送给N个目标，N称为Fanout。所以，前面的Fanout=4，意思是某个节点每次都会把自己要分享的信息同步给集群中的其他4个节点。在模拟器中应该是这样反映的：可以看到上图中有很多条线，但是它们的起点是一个红色的节点。红色节点是可以用鼠标随意点击一个或多个小圆圈。一旦鼠标点击，就会变成红色，表示结束，红色代码表示“已感染”。上面的台词是怎么出来的？有一个小红圈后，点击上面的“ShowPaths”，会出现路径：但是你不是说Fanout=4吗，怎么那么多路径？因为，虽然这个节点知道这么多其他节点，但它只会选择其中的4个进行感染。上图还是有点复杂，稍微调整了一下参数，这样看起来就干净多了：集群中有一个节点的信息更新了，这个节点知道其他5个节点的存在，但是它只会更新信息Push给其中两个，点击SendMessage按钮后，会是这样的：可以发现上图中已经有3个红色节点，并且两条路径都变粗了，说明意义是从这条路径传播的。整个集群最终会完成“感染”，达到最终一致性：同时，gossip协议也是容错的：根据页面提示，我们可以通过“删除”按钮删除一些路径，对于示例如下：删除两个A路径意味着这些节点不可达，但最终集群还是会被完全感染。这里再放一个动图来演示一下，可以看到删除路径后，这个节点就不再和对应的节点通信了，但是整个集群已经达到收敛：也可以打开网站玩了，还有一点trick这种方式：点击播放按钮，可以随时暂停，这样更容易观察整个传播过程。最后这张图还有一个关键没说的，就是里面的公式：这个公式在LearnMore中也有提到，其实就是gossip协议的复杂度，O(logN)：例如，每time都设置为Fanout=4，则节点数与预估传播轮数的关系如下：40个节点，2.66轮80个节点，3.16轮160个节点，3.66轮320个节点，4.16轮640个节点rounds节点，4.66轮...可以看出，随着节点数翻倍，传播轮数并没有明显增加。这是LearnMore之前截图中提到的单词：Scalable是一个四级词汇。它将被测试。请记住，它的意思是“可扩展”。集群使用gossip协议，Scalable很好。其他注意点在这个网站上，最重要的是它的动画模拟功能，但是不要忽略里面其他部分的描述。比如这一段，我觉得很重要。这一段提到了两个问题，我会一一说明。首先，它说在模拟网站的过程中，所有发送消息的节点似乎都是同步的，好像有一个全局循环。在模拟中执行此操作，因为它看起来更直观。然而，在真正的八卦协议中，每个节点都有自己的周期，它们之间没有也不需要同步。以上是什么意思？让我说得更直白一点。每个节点在同步消息时，按照自己的周期处理，比如10秒一次。你不关心其他节点什么时候触发同步消息的操作，你只需要照顾好自己。第二个问题我觉得很重要：节点是怎么知道彼此的？节点如何知道其他节点的存在？其中一种方式是当一个节点加入集群时，它必须知道集群中一个节点的信息。我们从前面的动画中知道，如果一个节点被另一个节点知道，它最终会被感染。那么问题来了：一个新节点在加入时如何知道集群中某个节点的信息呢？很简单，我知道的一种解决方案是手动指定。Redis集群使用gossip协议交换信息。当一个新节点想要加入集群时，使用meet命令。http://www.redis.cn/commands/...这个东东是手动指定的。还有一点需要注意的是：这里提到另一个模拟网站：https://www.serf.io/docs/inte...可以通过控制这些参数时间来衡量集群的共识。上图为信息交换频率（GOSSIPINTERVAL）为0.2s，Fanout节点数为3，节点总数为30，丢包率和节点故障率为0的情况。本例，对应的达到最终一致性的时间图是这样的：基本上一秒钟就搞定了。也可以自己修改参数，在对应的时间图中看到变化。比如我只修改节点数，从30改为3000，时间图变成了这样：1.75s左右收敛完成。节点放大了100倍，时间却增加了不到1s，真的很优秀。这东西不错，不过给大家看个激动人心的感受一下这个恐怖传播的规模：从动图上看，前面一两次传播还可以，至少眼睛能看出大概的意思，但是当它到达后的几轮中，大部分节点都被感染了，却又继续传播消息。消息量之大，简直让人头皮发麻。六度分离理论最后，还有一个有趣的东西叫做“六度分离理论”：1967年，哈佛大学心理学教授斯坦利·米尔格拉姆想要描述一个连接人与社区的人际网络。我做了一个连锁信实验，发现了“六度分离”的现象。简单的说：“你和任何一个陌生人之间的间隔不会超过六个人，也就是说，你最多可以通过六个人认识任何一个陌生人。六度分离理论，也被称为小世界理论。这个其实和Gossip协议有着千丝万缕的联系，在小婆网站上看到了一个相关的视频，我觉得解释的还是比较清楚的，有兴趣的可以看看：https://www.bilibili.com/vide....png)视频中，有这么一张图：好家伙，这不是我们之前网站的翻版吗？看起来好亲切啊，这个理论刚提出来还是“你可以遇到任何人”最多有六个人的陌生人”。但是随着近年来社交网络的快速发展，地球已经沦为“村庄”的概念。所以这个数字正在逐渐减少:.png)并且如果范围缩小往下一点，比如限于程序员这个小范围，会更小。有时候你开一个业务对接群，进去看看好人和以前的同事，你说这个圈子能有多大.本文已收录在我的个人博客中，欢迎大家来玩。https://www.whywhy.vip/
