11 | Gossip协议：流言蜚语，原来也可以实现一致性

Mar 6, 2020

11 | Gossip协议：流言蜚语，原来也可以实现一致性-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

11 | Gossip协议：流言蜚语，原来也可以实现一致性

2020-03-06 韩健来自北京

《分布式协议与算法实战》

课程介绍



讲述：于航

时长10:08大小9.28M



你好，我是韩健。
有一部分同学的业务在可用性上比较敏感，比如监控主机和业务运行的告警系统。这个时候，相信你希望自己的系统能在极端情况下（比如集群中只有一个节点在运行）也能运行。回忆了二阶段提交协议和 Raft 算法之后，你发现它们都需要全部节点或者大多数节点正常运行，才能稳定运行，那么它们就不适合了。而根据 Base 理论，你需要实现最终一致性，怎么样才能实现最终一致性呢？
在我看来，你可以通过 Gossip 协议实现这个目标。
Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。对你来说，掌握这个协议不仅能很好地理解这种最常用的，实现最终一致性的算法，也能在后续工作中得心应手地实现数据的最终一致性。
为了帮你彻底吃透 Gossip 协议，掌握实现最终一致性的实战能力，我会先带你了解 Gossip 三板斧，因为这是 Gossip 协议的核心内容，也是实现最终一致性的常用三种方法。然后以实际系统为例，带你了解在实际系统中是如何实现反熵的。接下来，就让我们开始今天的内容吧。
Gossip 的三板斧Gossip 的三板斧分别是：直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣言传播（Rumor mongering）。
直接邮寄：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。从图中你可以看到，节点 A 直接将更新数据发送给了节点 B、D。
图1
在这里我想补充一点，直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。也就是说，只采用直接邮寄是无法实现最终一致性的，这一点我希望你能注意到。
那如何实现最终一致性呢？答案就是反熵。本质上，反熵是一种通过异步修复实现最终一致性的方法（关于异步修复，你可以回顾一下04 讲）。常见的最终一致性系统（比如 Cassandra），都实现了反熵功能。
反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性：
图2
从图 2 中你可以看到，节点 A 通过反熵的方式，修复了节点 D 中缺失的数据。那具体怎么实现的呢？
其实，在实现反熵的时候，主要有推、拉和推拉三种方式。我将以修复下图中，2 个数据副本的不一致为例，具体带你了解一下。
图3
推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵：
图4
拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵：
图5
理解了推和拉之后，推拉这个方式就很好理解了，这个方式就是同时修复自己副本和对方副本中的熵：
图6
也许有很多同学，会觉得反熵是一个很奇怪的名词。其实，你可以这么来理解，反熵中的熵是指混乱程度，反熵就是指消除不同节点中数据的差异，提升节点间数据的相似度，降低熵值。
另外需要你注意的是，因为反熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高，所以我不建议你在实际场景中频繁执行反熵，并且可以通过引入校验和（Checksum）等机制，降低需要对比的数据量和通讯消息等。
虽然反熵很实用，但是执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境（比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态），这时反熵就不适用了。那么当你面临这个情况要怎样实现最终一致性呢？答案就是谣言传播。
谣言传播，广泛地散播谣言，它指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据：
图7
从图中你可以看到，节点 A 向节点 B、D 发送新数据，节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。其实，谣言传播非常具有传染性，它适合动态变化的分布式系统。
如何使用 Anti-entropy 实现最终一致在分布式存储系统中，实现数据副本最终一致性，最常用的方法就是反熵了。为了帮你彻底理解和掌握在实际环境中实现反熵的方法，我想以自研 InfluxDB 的反熵实现为例，具体带你了解一下。
在自研 InfluxDB 中，一份数据副本是由多个分片组成的，也就是实现了数据分片，三节点三副本的集群，就像下图的样子：
图8
反熵的目标是确保每个 DATA 节点拥有元信息指定的分片，而且不同节点上，同一分片组中的分片都没有差异。比如说，节点 A 要拥有分片 Shard1 和 Shard2，而且，节点 A 的 Shard1 和 Shard2，与节点 B、C 中的 Shard1 和 Shard2，是一样的。
那么，在 DATA 节点上，存在哪些数据缺失的情况呢？也就说，我们需要解决哪些问题呢？
我们将数据缺失，分为这样 2 种情况。
缺失分片：也就是说，在某个节点上整个分片都丢失了。
节点之间的分片不一致：也就是说，节点上分片都存在，但里面的数据不一样，有数据丢失的情况发生。
第一种情况修复起来不复杂，我们只需要将分片数据，通过 RPC 通讯，从其他节点上拷贝过来就可以了：
图9
你需要注意的是第二种情况，因为第二种情况修复起来要复杂一些。我们需要设计一个闭环的流程，按照一个顺序修复，执行完流程后，也就是实现了一致性了。具体是怎么设计的呢？
它是按照一定顺序来修复节点的数据差异，先随机选择一个节点，然后循环修复，每个节点生成自己节点有、下一个节点没有的差异数据，发送给下一个节点，进行修复（为了方便演示，假设 Shard1、Shard2 在各节点上是不一致的）：
图10
从图中你可以看到，数据修复的起始节点为节点 A，数据修复是按照顺时针顺序，循环修复的。需要你注意的是，最后节点 A 又对节点 B 的数据执行了一次数据修复操作，因为只有这样，节点 C 有、节点 B 缺失的差异数据，才会同步到节点 B 上。
学到这里你可以看到，在实现反熵时，实现细节和最初算法的约定有些不同。比如，不是一个节点不断随机选择另一个节点，来修复副本上的熵，而是设计了一个闭环的流程，一次修复所有节点的副本数据不一致。
为什么这么设计呢？因为我们希望能在一个确定的时间范围内实现数据副本的最终一致性，而不是基于随机性的概率，在一个不确定的时间范围内实现数据副本的最终一致性。
这样做能减少数据不一致对监控视图影响的时长。而我希望你能注意到，技术是要活学活用的，要能根据场景特点权衡妥协，设计出最适合这个场景的系统功能。最后需要你注意的是，因为反熵需要做一致性对比，很消耗系统性能，所以建议你将是否启用反熵功能、执行一致性检测的时间间隔等，做成可配置的，能在不同场景中按需使用。
内容小结以上就是本节课的全部内容了，本节课我主要带你了解了 Gossip 协议、如何在实际系统中实现反熵等。我希望你明确这样几个重点：
作为一种异步修复、实现最终一致性的协议，反熵在存储组件中应用广泛，比如 Dynamo、InfluxDB、Cassandra，我希望你能彻底掌握反熵的实现方法，在后续工作中，需要实现最终一致性时，优先考虑反熵。
因为谣言传播具有传染性，一个节点传给了另一个节点，另一个节点又将充当传播者，传染给其他节点，所以非常适合动态变化的分布式系统，比如 Cassandra 采用这种方式动态管理集群节点状态。
在实际场景中，实现数据副本的最终一致性时，一般而言，直接邮寄的方式是一定要实现的，因为不需要做一致性对比，只是通过发送更新数据或缓存重传，来修复数据的不一致，性能损耗低。在存储组件中，节点都是已知的，一般采用反熵修复数据副本的一致性。当集群节点是变化的，或者集群节点数比较多时，这时要采用谣言传播的方式，同步更新数据，实现最终一致。
课堂思考既然使用反熵实现最终一致性时，需要通过一致性检测发现数据副本的差异，如果每次做一致性检测时都做数据对比的话，肯定是比较消耗性能的，那有什么办法降低一致性检测时的性能消耗呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的朋友。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 12

提建议

10 | 一致哈希算法：如何分群，突破集群的“领导者”限制？

12 | Quorum NWR算法：想要灵活地自定义一致性，没问题！

 写留言

精选留言(50)

Jialin
2020-03-06
课堂笔记（综合第四讲和第十一讲内容） 1.Gossip 协议存在的原因？为了实现 BASE 理论中的“最终一致性原则”。两阶段提交协议和 Raft 算法需要满足“大多数服务节点正常运行”原则，如果希望系统在少数服务节点正常运行的情况下，仍能对外提供稳定服务，这时就需要实现最终一致性。最终一致性是指系统中所有的数据副本在经过一段时间的同步后，最终能够达到一个一致的状态。 2.最终一致性原则中的一致性标准（实际工程实践） • 以最新写入的数据为准，比如 AP 模型的 KV 存储采用的就是这种方式 • 以第一次写入的数据为准，如果不希望存储的数据被更改，可以以它为准 3.实现最终一致性的具体方式 • 读时修复：在读取数据时，检测数据的不一致，进行修复。比如 Cassandra 的 Read Repair 实现，具体来说，在向 Cassandra 系统查询数据的时候，如果检测到不同节点的副本数据不一致，系统就自动修复数据 • 写时修复：在写入数据，检测数据的不一致时，进行修复。比如 Cassandra 的 Hinted Handoff 实现。具体来说，Cassandra 集群的节点之间远程写数据的时候，如果写失败就将数据缓存下来，然后定时重传，修复数据的不一致性 • 异步修复：这个是最常用的方式，通过定时对账检测副本数据的一致性，并修复 4.Gossip 协议实现最终一致性 • 直接邮寄，即写时修复，直接发送更新数据，当数据发送失败时，将数据缓存在失败重试队列，然后重传。这种方式虽然存在丢数据问题，但是实现简单、数据同步及时，不需要校验数据一致性对比，性能消耗低 • 反熵，即异步修复，集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。主要有推、拉、推拉三种实现方式。适合集群节点数已知、少量、稳定的场景，主要由于反熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高，性能消耗高。需要注意的是实现反熵时一般设计一个闭环的流程，一次修复所有节点的副本数据不一致，因为我们希望能在一个确定的时间范围内实现数据副本的最终一致性，而不是基于随机性的概率，在一个不确定的时间范围内实现数据副本的最终一致性 • 谣言传播，指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。由于谣言传播非常具有传染性，它适合动态变化的分布式系统 5.思考题：既然使用反熵实现最终一致性时，需要通过一致性检测发现数据副本的差异，如果每次做一致性检测时都做数据对比的话，肯定是比较消耗性能的，那有什么办法降低一致性检测时的性能消耗呢？除了老师在文章中提到的通过校验和进行数据一致性检测，可以借鉴通信原理中数据校验方法，如奇偶校验、CRC校验和格雷码校验等方式，但是这些方式只能检测出错误，但是无法纠错，可以通过重传的方式进行纠错。
展开
作者回复: 加一颗星:)
共 7 条评论
45
小晏子
2020-03-06
一致性检测是对比两个节点上的数据是否一致，如果每次都是全量比对，那么肯定性能不是很高，那为了提升性能，那么最好是不比对或增量数据比对，这里抛个砖， 1. 假设从某一时刻开始，所有节点数据都是一致的，每个节点都记录从这个时刻开始的数据变化， 2. 当反墒放生时，先看相关的两个节点上数据变化是否为空，如果为空就证明两个节点此时数据一致，不需要数据同步。 3. 如果相关的两个节点上数据有变化，则只比较变化的数据，然后只同步变化的差集，同时也要更新数据变化状态记录， 4. 在某个时间段内数据的变化只增不减，某个时刻所有节点做全量比对，然后重置数据变化记录。 5. 为了快速比较，可以同时计算数据变化记录的hash值用于比较，hash值一样就说明数据变化是相同的，两节点数据一致，否则就需要一致性查询并同步。
展开
作者回复: 加一颗星:)
22
忆水寒
2020-03-06
老师，有个疑惑。文章中说直接邮寄肯定要实现的，在固定节点的系统中可以实现反墒修复一致性。那么两者如何兼容呢？是不是每次有新数据写入，先执行直接邮寄。然后周期性的执行反墒修复数据一致性呢？
作者回复: 加一颗星:)，是的。
共 4 条评论
19
myrfy
2020-03-06
老师，gossip中，遇到数据冲突，以谁为准呢？
作者回复: 加一颗星:)，取决于场景，比如KV数据，以新数据为准。
共 4 条评论
13
老辉
2020-03-17
老师，如果反熵过程中，组成的环上的一个节点挂了，怎么同步数据一致。
作者回复: 加一颗星:)，绝大部分时候，系统是稳定运行的，如果出现了节点故障这种异常情况，一般而言，咱们需要先处理节点故障，然后再执行反熵，实现副本数据的最终一致。
11
Scott
2020-03-08
merkle tree可以用来减少比较差异负担的开销吗
作者回复: 加一颗星:)，是个办法:)
9
leitiannet
2020-10-18
Redis Cluster中用来维护节点集群状态信息的Gossip协议和本文的Gossip协议是一样的吗？ Redis Cluster使用反熵方法？
共 1 条评论
7
kylexy_0817
2020-04-26
韩老师好，我觉得其实就目的而言，Gossip的三板斧都是为了反熵，即都是为了降低系统因为数据不一致引起的混乱程度，只是实现方法不一样，第一种用到消息队列，就是消息订阅发布模式；第二种不经消息队列，直接推拉消息到随机节点；第三种就是散播谣言，这里方法是推，还应该会涉及一个散播算法，避免消息重复下发，避免消息风暴。不知我的理解到不到位？
作者回复: 加一颗星:)，可以这么类比理解:)
8
翠羽香凝
2020-03-11
老师，感觉谣言传播有很多细节值得讨论，比如：谣言何时停止？什么时候算是网络里都达到了一致性？而不是无止境的传下去？又比如：谣言传播可能会有很多消息被反复重传，会不会造成网络性能的下降？
作者回复: 加一颗星:)，问题1：这个问题比较共性，我后面做个补充吧。问题2：会的，尽管谣言传播能以去中心化的方式，在动态变化的集群中，实现数据副本的最终一致性，但通讯成本较高。
共 3 条评论
6
崔伟协
2020-03-09
直接邮寄，反熵，谣言传播三者的区别是什么
作者回复: 加一颗星:)，功能和适用场景不同，直接邮寄：直接发送更新数据，若失败，缓存、重传；反熵：修复数据副本差异，实现最终一致；谣言传播：去中心化的、节点相互传播新数据，适用动态变化的分布式场景。
6
test
2020-06-03
这三种方式，是不是主要的区别就是在过程中充当发起者的是单一个节点、轮询节点、多个节点？
作者回复: 加一颗星:)，这是其中一个区别，但三个协议最最主要的区别，是功能和适用场景不同，直接邮寄：直接发送更新数据，若失败，缓存、重传；反熵：修复数据副本差异，实现最终一致；谣言传播：去中心化的、节点相互传播新数据，适用动态变化的分布式场景。
3
每天晒白牙
2020-03-06
今日得到出于可用性考虑(即使一个节点也照常运行)，而二阶段提交和 raft 协议都是需要保证大多数几点正常运行才能保证稳定运行。根据 base 理论要实现最终一致性，所以 gossip 协议就出来了。 gossip 协议是一种利用随机，带有传染性的方式，将数据传播到整个网络中，在一定时间内，使网络内的所有节点达到最终一致性 gossip 协议有三种方法 1.直接邮寄【必须要实现的】直接发送更新数据给其他节点，如果失败缓存起来，然后后续进行重传。这种方式相对比较简单，但有个缺点是如果缓存满了会存在丢数据的风险 2.反熵反熵是指消除节点之间的数据差异，它是一种异步修复数据从而达到最终一致性的方案主要是指集群中的节点每隔断时间就随机选择集群中其他节点进行数据交换，达到数据同步的目的，这里有推、拉、推拉三种模式。因为反熵需要对比数据，所以挺耗性能的，老师提到可以通过校验和的方式解决，这块我下去需要在查查相关资料反熵有个局限性就是要求几点已经，且节点数量不能太多 3.谣言传播当一个节点有了新数据后，这个节点变成活跃状态，并周期性的向其他节点发送数据，直到所有节点都存储了这个新数据这种方式适合动态变化的分布式系统思考题反熵在做数据差异检查时是通过对比数据来进行的，比较耗性能，有啥好方式解决？老师在专栏中提到了使用校验和的方式，但还不太懂这种方式，老师可以简单介绍下吗？
展开
作者回复: 加一颗星:)，可以这么理解，先比较checksum，当checksum不一致时，再交换数据做数据差异性检查。
共 2 条评论
3
oops
2021-03-08
反熵数据不一的案例，节点按一定顺序消除差异性，怎么确定不一致的数据副本在哪个节点是对的。感觉例子是保障最后一致即可，并没有确定哪个节点的副本对的。
共 1 条评论
2
88591
2020-04-02
直接对比内容签名
作者回复: 加一颗星:)
2
Daiver
2020-03-07
Fabric目前1.4.1版本以上实现了raft共识，不过用的是etcd的组件；Hyperledger Fabric 中组织内部的peer节点之间为了同步账本数据使用了gossip协议。
作者回复: 加一颗星:)
2
Daiver
2021-11-19
如何设计反熵闭环呢
1
ppyh
2020-06-20
shard的各个节点有主副之分吗，读取的时候是不是允许读到的数据不是最新的？
作者回复: 加一颗星:)，如果实现的是最终一致性的系统，那么，这个集群是没有主备之分的，也允许读到旧数据。
1
evil
2020-06-15
3节点循环修复能兼顾到每个 ,更多节点的时候循环修复就存在问题而且感觉最后a和b 再同步是否有必要性如果我们通过时钟的方式去比较的话就是等于在我做数据同步的时候系统等于做了一次快照
1
忆水寒
2020-04-23
2020年4月23日，这是第二遍阅读。感觉基本上能理解了，比之前的理解要深一些。加油！
作者回复: 加一颗星:)，加油，多交流:)
1
colin
2020-04-12
反熵有点像路由算法啊
作者回复: 实现和解决的问题是不同的:)
1

