你好呀，我是歪歪。
除夕的时候我看到一个特地离谱的流言啊，具体是什么内容我就不说了，我怕脏了大家的眼睛。
然而，我看到一个群里传的那叫一个娓娓动听，大家探讨的风生水起的，好像大家就在现场似的。
这事吧原本我呵呵一笑也就过了。然而隔了一会我忽然大腿一拍：这是个素材啊。
我能够和大家聊一个共识算法呀。
说到共识算法，大家首先想到的应该都是 Raft、Paxos、Zab 算法这类了解起来比拟艰难的强一致性算法。
然而还有一个弱一致性的共识算法比拟好了解，Gossip 协定。
Gossip，先看这个单词，圈起来，要考的啊，这是一个六级词汇，也是考研单词，意思是“风言风语”。
接下来就带你简略的看看这个“风言风语”到底是怎么回事。
Gossip 协定
Gossip 协定最早提出的工夫得追溯到 1987 年公布的一篇论文：《Epidemic Algorithms for Replicated Database Maintenance》
http://bitsavers.trailing-edg…
我第一次看到这个论文的名字的时候，我都懵逼了：这也没有 Gossip 的关键词呢。
次要是 Epidemic Algorithms 这两个单词，我又恰好意识。
Algorithms，算法，没啥说的。
Epidemic 是啥？
紧扣当下时事：
所以 Epidemic Algorithms 翻译过去就是流行病算法。
因而 Gossip 的学名应该是又叫做“流行病算法”，只是大家更喜爱叫它 Gossip 而已。毕竟，虽不喜爱听点儿“小道消息”呢？
说论文之前，先简略定个基调。
你感觉一致性协定最根底、最外围、最重要的一个动作是什么？
是不是数据更新？
为了保障各个节点的数据的一致性，必然就波及到数据的更新操作。
所以，在论文的开篇介绍局部形容了三种办法来进行数据的更新：
- Direct mail（间接邮件）
- Anti-entropy（反熵）
- Rumor mongering（传谣）
Direct mail（间接邮寄）
废话先不说了，间接上个图：
下面这图啥意思呢？
就是一共八个小圆点，假如每个都代表一个服务器，它们之间都是平等的关系，不存在核心节点、主从什么的关系。
其中最下面的红色节点示意该节点有数据变更了，于是把变更的数据间接告诉给剩下的节点。
如果其余的节点上产生了数据变更也是同样的情理。
能够简略的了解为一个循环遍历，每产生一次数据变更，为了保持数据的一致性，就得进行一次循环遍历。
这个计划的长处很显著：简略、粗犷、间接。
然而毛病和长处一样显著，咱们看看论文外面怎么说：
次要看 but 的局部：
首先不齐全牢靠，因为这个要求每个站点都必须晓得所有站点的存在。然而理论状况是有的站点并不总是晓得所有其余站点。
而后，信息（mail）有时会失落，一旦失落，就连最终一致性也保障不了，整个凉凉。
其实 Direct mail（间接邮寄）并不是论文外面次要探讨的计划，把它写在第一个起一个抛砖引玉的作用。
次要聊聊 Anti-entropy（反熵）和 Rumor-Mongering（传谣）这两个计划。
先定个整体的基调：
- Anti-entropy（反熵），是流传节点上的所有的数据
- Rumor-Mongering（传谣），是流传节点上的新达到的、或者变更的数据
说白了，一个是全量，一个是增量。
Anti-entropy（反熵）
局部同学可能对“反熵”这个词感到莫名其妙哈，其实次要是不理解啥是“熵”。
其实说白了，“熵”的艰深了解就是“凌乱水平”。
比方你的房间，如果你不去整顿那么各自物品的摆放就会越来越凌乱，也就是越来越“熵”。而你整顿房间的这个操作就是“反熵”。
这个货色你能够简略的先这样了解，我一时半会也给你说不清楚，这货色要聊上来的话得回升到宇宙和哲学的高度。
我次要怕你听不懂。
在论文外面是这样的形容 Anti-entropy 模式的：
每个服务器有法则地随机抉择另一个服务器，这二者通过替换各自的内容来抹平它们之间的所有差别，这种计划是十分牢靠的。
（but 开始了）但须要查看各自服务器的全量内容，话中有话就是数据量略大，因而不能应用太频繁。
试验表明，反熵尽管牢靠，但流传更新的速度比间接邮件慢得多。
如果不同步，那么两者之间的数据差别越来越大，也就是越来越熵。
同步的目标是放大差别，达到最终一致性，这就是反熵。
定义就是这么个定义。
Rumor mongering（传谣）
比起反熵，传谣从字面上就很好了解了。
比方我是一个大学生，并不能齐全意识整个学校的人。然而学校外面的同学之间都有千头万绪的分割。
假如有一天，我刚好碰见校花一个人走在路上，我就下来和她探讨了一下计算机领域外面的共识算法等相干问题，对于这些问题咱们进行了深刻的探讨并且替换了彼此的了解和认识。
咱这边就是说，整个过程是越探讨越强烈，不晓得怎么走着走着就走到了情人坡。
应该每个大学都有一个叫做情人坡的中央吧。
而后被别的妹子看见了。她就给她闺蜜说：你晓得歪歪吗？对，就是大一新生，那个大帅比。我那会看到他和校花在情人坡那边溜达。
而后一传十、十传百。这个音讯全校师生都晓得了。
“歪歪和校花在情人坡那边溜达”这个音讯就通过 gossip 的传谣模式，达到了最终一致性。
“传谣”和“反熵”的差异在于只传递新信息或者产生了变更的信息，而不须要传递全量的信息。
比方下面的这个例子中，只须要同步“歪歪和校花在情人坡那边溜达”这个最新的音讯就行。
而不须要同步“歪歪是谁，校花是谁，情人坡在哪”等等这些之前大家早就达成一致性的信息。
在提到“传谣”和“反熵”的时候，论文中还有这么个定义：
simple epidemics：单纯性传染病
在这种模式下，蕴含两种状态：infective（传染性）和 susceptible（易感化）。
处于 infective 状态的节点代表其有数据更新，须要把数据分享（传染）给其余的节点。
处于 susceptible 状态的节点代表它还没承受到其余节点的数据更新（没有被感化）。
所以，前面我提到“感化”的时候，你应该要晓得我是从这里看到的，不是胡编的。
对于“传谣”和“反熵”，再借用周志明老师《凤凰架构》外面的正经一点的形容，是这样的：
http://icyfenix.cn/distributi…
达到一致性消耗的工夫与网络流传中音讯冗余量这两个毛病存在肯定对抗，如果要改善其中一个，就会好转另外一个。
由此，Gossip 设计了两种可能的音讯流传模式：反熵（Anti-Entropy）和传谣（Rumor-Mongering），这两个名字都挺文艺的。
熵（Entropy）是生存中少见但迷信中很罕用的概念，它代表着事物的凌乱水平。
反熵的意思就是反凌乱，以晋升网络各个节点之间的类似度为指标，所以在反熵模式下，会同步节点的全副数据，以打消各节点之间的差别，指标是整个网络各节点齐全的统一。
然而，在节点自身就会产生变动的前提下，这个指标将使得整个网络中音讯的数量十分宏大，给网络带来微小的传输开销。
而传谣模式是以流传音讯为指标，仅仅发送新达到节点的数据，即只对外发送变更信息，这样音讯数据量将显著缩减，网络开销也绝对较小。
一个网站
摊牌了，其实我是看到了这个网站，才决定写这篇文章的。
因为这个网站外面间接有十分仿真的动画模仿 gossip 协定的同步过程，一个动图胜过一言半语。
地址先放在这里，大家能够本人拜访玩儿一下：
https://flopezluis.github.io/…
先给你看一眼它的工作过程：
甭管看没看懂吧，这玩意至多看起来很厉害的样子。
接下来就给你介绍一下它是怎么玩的：
首先咱们看这里的 Nodes 和 Fanout。
Nodes 其实很好了解，就是节点数，这里的 40 就代表上面的小圆圈的个数，比方我往年 18 岁，那么我把它改成 18 它就是这样的：
次要是这个 Fanout 是个啥玩意呢？
在这个网页的头部的轮播图外面，第一张图是这样的：
答案就藏在这个 Learn more 外面。
https://managementfromscratch…
这段话外面就解释了，什么是 Fanout。同时也简略的介绍了 gossip 协定的根本工作原理。
它说 gossip 协定在概念上非常简单，编码也非常简单。它们背地的根本想法是这样的：
一个节点想与网络中的其余节点分享一些信息。而后，它定期从节点汇合中随机抉择一个节点并替换信息，收到信息的节点也做同样的事件。
该信息定期发送到 N 个指标，N 被称为扇出（Fanout）。
所以，后面的 Fanout=4，含意就是某个节点，每次会把本人想要分享的信息同步给集群中的另外 4 个节点。
在模拟器中体现进去应该是这样的：
下面这个图你能够看到有很多线，然而它们的终点都是一个红色的节点。
这个红色的节点就是你用鼠标随便点击小圆圈中的一个或者多个都能够，鼠标一点击就会变成红色，就是完犊子了，红码了，示意“被感化”了。
下面的线条是怎么搞进去的呢？
有了一个红色的小圆圈之后，点击下面的“Show Paths”就会呈现门路了：
然而不是说好 Fanout=4 吗，为什么怎么多的门路？
因为，尽管这个节点晓得这么多其余节点，然而它只会抉择其中的 4 个进行感化。
下面这个图还是有点简单，所以我把参数都调小一点，这样看起来就清新多了：
集群中有一个节点的信息更新了，这个节点晓得其余 5 个节点的存在，然而它只会把信息推送给其中的两个，点击 Send Message 按钮之后就会像是这样：
你能够发现下面这个图外面曾经有三个红色的节点了，有两条门路变粗了，含意是从这个门路流传过去的。
整个集群最终会全副实现“感化”，达成最终一致性：
同时，gossip 协定它也具备容错性：
依照页面上的提醒，咱们是能够通过“Delete”按钮删除一部分门路的，比方上面这样：
删除两个门路，代表这几个节点之间是不可达的，然而最终这个集群还是会全副被感化。
再来个动图演示一下，能够看到门路删除后，这个节点再也不会给对应的节点通信，然而整个集群还是达到了收敛：
你本人也能够关上网站去玩一下，还有一个小技巧是这样的：
点击 Play 按钮，是能够随时暂停的，这样就更容易察看到整个流传的过程。
最初，对于这个图外面，还有一个要害的货色没有说，就是外面的这个公式：
在 Learn More 外面也有提到这个公式，其实它就是 gossip 协定的复杂度，O(logN)：
比方，每次都设置为 Fanout=4，那么节点数和预估流传轮次之间的关系是这样的：
- 40 个节点，2.66 轮
- 80 个节点，3.16 轮
- 160 个节点，3.66 轮
- 320 个节点，4.16 轮
- 640 个节点，4.66 轮
- …
能够看到，随着节点数的翻倍减少，流传轮次并没有显著的减少。
这就是后面 Learn More 截图外面提到的这个词：Scalable
这是个四级词汇啊，会考的，记住了，是“可伸缩”的意思。
采纳 gossip 协定的集群，Scalable is very 的 nice。
其余留神点
在这个网站上，最重要的就是它的动图模仿性能了，然而也不要疏忽了它外面的其余局部的形容。
比方这一段话，我就感觉十分的重要。
这一段话外面提到了两个问题，我一个个的说。
首先它说在网站模仿的过程中，所有节点发送音讯仿佛都是同步的，就像有一个全局循环一样。
在模仿中这样做，是因为这样看起来更加的直观。
然而，在一个真正的 gossip 协定中，每个节点都有本人的周期，它们之间基本没有也不须要同步。
下面是说什么意思呢？
我再说的直白一点，每个节点往外同步音讯的时候，是依照本人的周期来解决的，比方每 10 秒一次。基本就不关怀其余节点什么时候触发同步音讯的操作，只须要管好本人就行了。
第二问题我认为就很重要了：
How do the nodes know about each other?
节点之间怎么晓得其余节点的存在的？
其中一个形式就是当节点退出集群时，必须晓得该集群中的一个节点的信息。通过后面的动图咱们晓得，如果一个节点被另外一个节点晓得，那么它最终也肯定会被感化。
那问题就来了：新节点退出时又是如何晓得集群中一个节点信息的呢？
很简略，我晓得的一个计划就是人工指定。
Redis 集群采纳的就是 gossip 协定来替换信息。当有新节点要退出到集群的时候，须要用到一个 meet 命令。
http://www.redis.cn/commands/…
这玩意就是人工指定。
还有一个能够留神一下的是这个：
这里提到了另外一个模仿的网站：
https://www.serf.io/docs/inte…
它能够通过管制这几个参数，来测算集群达成一致性的工夫。
下面这个图示意的就是在信息替换频率 (GOSSIP INTERVAL) 为 0.2s，Fanout 节点数为 3，总节点数为 30，丢包率和节点失败率为 0 的这个状况。
在这个状况下，对应的达到最终一致性的工夫图长这样：
基本上在一秒的工夫就搞定了。
你也能够本人去批改一下参数，看看对应的工夫图的变动。
比方，我只批改节点数，把它从 30 批改为 3000，工夫图变成了这样：
在 1.75s 左右实现了收敛。
节点扩充 100 倍，然而工夫减少不到 1s，的确是很优良。
这玩意好是好，然而给你看个刺激的，来感受一下这恐怖的流传规模：
从动图中能够看出，后面一两次流传还好，至多眼睛还能看出个大略，然而到了后几轮，大多数节点都被感化了，然而还在持续对外流传音讯。
这音讯数量，几乎是看的让人头皮发麻。
六度分隔实践
最初再说一个有意思的货色，叫做“六度分隔实践”：
1967 年，哈佛大学的心理学传授 Stanley Milgram 想要描述一个连结人与社区的人际连系网。做过一次连锁信试验，后果发现了“六度分隔”景象。简略地说：“你和任何一个陌生人之间所距离的人不会超过六个，也就是说，最多通过六个人你就可能意识任何一个陌生人。
六度宰割实践，也叫小世界实践。这其实和 Gossip 协定也有千头万绪的分割。
我在小破站上看到一个相干的视频，我感觉解释的还是挺分明的，你如果有趣味的话能够去看看：
https://www.bilibili.com/vide…
.png)
在视频外面，有这样的一个画面：
好家伙，这不是咱们后面的网站下面的翻版嘛，看起来可太亲切了。
这个实践刚刚提出来的时候还是“最多通过六个人你就可能意识任何一个陌生人”。
然而随着这几年社交网络的急速倒退，地球都被拉小到了一个“村”的概念了。
所以这个数字在逐步的缩小：
.png)
而且如果把这个范畴拉小一点，比方局限在程序员这个小范畴内，那就更小了。
有时候拉个业务对接群，进去一看好家伙还有前共事，你说这个圈子能有多大。
本文已收录到集体博客，欢送大家来玩。
https://www.whywhy.vip/