分布式共识算法之Gossip协议
Gossip背景
谈到分布式共识算法,大家一定会记得Paxos、Raft、Zab算法,这些算法按照BASE理论实现的强一致性算法。强一致性算法,在实际应用场景中,实现起来复杂度是比较高的。那么有没有一种算法,既能满足数据最终一致性,实现也比较简单?
Gossip协议(Gossip Protocol
)也叫流行病协议(Epidemic Protocol
)或者流言算法、疫情传播算法(Epidemic Algorithms
)等。该协议最早是在1987年8月温哥华举行的第六届ACM分布式计算原理的学术会议上发布。相关论文《Epidemic Algorithms for Replicated Database Maintenance》。
Gossip协议是基于六度分隔理论(Six Degrees of Separation)哲学的体现,简单的来说,一个人通过6个中间人可以认识世界任何人,数学公式如下:
c = fw
c即复杂度,f为每个人的朋友圈数量,w为人际宽度。
1506 =11,390,625,000,000(约11.4万亿)
意思为每个人朋友圈数量为150人,当人际宽度为6时,大约可以容纳11.4万亿人的体量。
基于六度分隔理论得知,任何信息的传播其实非常迅速,而且网络交互次数不会很多。比如Facebook在2016年2月4号做了一个实验:研究了当时已注册的15.9亿使用者资料,发现这个神奇数字的“网络直径”是4.57,翻成白话文意味着每个人与其他人间隔为4.57人。
Gossip协议就是按照六度分隔理论实现的一致性随机算法。就像流言蜚语一样,利用一种随机的、带有传染性的方式,将信息传播到整个网络中,并在一定时间内,使系统内所有节点数据达到一致性。
该算法非常简单,它可以看作以下两个步骤的简单循环:
- 如果有某一项信息需要在整个网络中所有节点中传播,那从信息源开始,选择一个固定的传播周期(譬如 1 秒),随机选择它相连接的 k 个节点(称为 Fan-Out)来传播消息。
- 每一个节点收到消息后,如果这个消息是它之前没有收到过的,将在下一个周期内,选择除了发送消息给它的那个节点外的其他相邻 k 个节点发送相同的消息,直到最终网络中所有节点都收到了消息,尽管这个过程需要一定时间,但是理论上最终网络的所有节点都会拥有相同的消息。
接下来内容,让我们具体看下Gossip是如何实现数据一致性的。
消息传递三种机制
在提到Gossip特点前,先让我们回顾下一致性协议最基础、最核心、最终的动作是什么?当然是数据更新了,为了保证各个节点的数据一致性,必然就涉及到数据的更新操作。
那么Gossip是通过什么方法来实现数据的更新操作?
Gossip协议主要是通过直接邮寄(direct mail)、反熵传播(anti-entropy)、谣言传播(rumor mongering)
三种机制来实现数据更新。
直接邮寄(direct mail
)
对于直接邮寄这种方式,主要是当节点有数据更新便开始遍历给其他所有节点发送消息来通知自身节点数据,实现算法比简单、粗暴。这种方式在分布式环境下是不可靠的,因为遍历通知是一次性的,在遇到网络故障、节点宕机之后是没有容错和补偿的,会出现数据丢失。所以它是无法保证分布式环境下各节点数据一致性的。
那么如何实现最终一致性呢?答案就是反墒。
反墒(anti-entropy
)
熵(Entropy)是生活中少见但科学中很常用的概念,它代表着事物的混乱程度,反熵的意思就是反混乱。
在Gossip中,反墒是指集群中每个节点都周期性随机选择节点池中的一些节点,通过互相交换所有数据来消除两者之间的差异,实现数据的最终一致性。也就是说反墒指消除不同节点中数据差异,提升节点间数据的相似度,降低墒值。
反熵传播(anti-entropy)
中的节点只有两种状态,病原(Suspective)
和感染(Infective)
,因此称作SI模型,一般叫做简易流行病(simple epidemics) 。
- 消息生产节点即为
Suspective(病原)
状态 - 消息接收节点即为
Infective(感染)
状态,会进行消息传播
对于反熵(anti-entropy) 这种方式,和直接邮寄(direct mail)相比的最大特点就是解决了消息丢失无法补偿容错导致的数据无法保持一致的致命问题。
这里需要注意的是,反墒传播每次节点两两交换自己的所有数据会带来非常大的通信负担,因此不会频繁使用,通常只用于新加入节点的数据初始化。
谣言传播(rumor mongering
)
我们先来看了谣言传播流程:
- 所有的节点在最开始没有产生数据变更时都假设是未知状态,它是不知道任何谣言信息的
- 当一个节点有了新的消息,这个节点就变成了活跃状态,并周期性地联系其他节点向其发送消息
- 当节点收到其他节点更新数据通知时,相当于听到了一条谣言,并将其视为热门开始传播给周边节点
- 当某个节点谣言盛行时,它会定期随机选择其他节点,并确保另一个节点知道
- 当某个节点发现周边节点都知道这个谣言时,该节点将停止将该谣言视为热点,并保留更新,而不会进一步传播
谣言传播(rumor mongering)
中的节点状态有Suspective(病原)、Infective(感染)、Removed(愈除)
,因此称作SIR模型,一般叫做复杂流行病(complex epidemics)
- 消息生产节点即为
Suspective(病原)
状态 - 消息接收节点即为
Infective(感染)
状态,会进行消息传播 - 节点接收消息后即为
Removed(愈除)
状态,不再进行传播
消息只包含最新更新数据,消息在某个时间点之后会被标记为Removed(愈除)
状态,并且不再被传播,通常用于节点间数据增量同步。
消息传递机制对比
机制 | 工作原理 | 工作机制 |
---|---|---|
直接邮寄(direct mail) | 某一节点有数据更新时遍历所有其他节点同步更新数据 | 简单、粗暴、不可靠,会存在数据丢失 |
反墒(anti-entropy) | 以固定周期传播所数据 | 新加入节点初始化 |
谣言传播(rumor mogering) | 仅传播新到达数据 | 节点增量数据 |
消息通信三种模式
Gossip中,消息间通讯主要是通过推、拉和推拉三种方式。我们以下图,2个数据副本不一致为例:
推模式(Push)
推模式,就是将自己的副本数据,推给对方,修复对方副本中的熵
反墒机制下:
-
节点A将所有数据(key、value、version)及对应版本号推送给节点D
-
节点D更新节点A中比自己新的数据
谣言传播机制下:
-
节点A将新的数据(key、value、version)及对应版本号推送给节点D
-
节点D更新节点A中比自己新的数据
拉模式(Pull)
拉模式,就是拉取对方的副本数据,修复自己副本中的熵
反墒机制下:
-
节点A请求拉取节点D所有数据
-
节点D将所有数据推送给节点A
-
节点A更新节点D回传所有数据,根据版本号覆盖相同Key更新的数据
谣言传播机制下:
- 节点A将数据(key)及对应版本号推送给节点D
- 节点D将本地比A新的数据(Key, value, version)推送给节点A
- 节点A更新回传数据
推拉模式(Push&Pull)
推拉模式,就是同时修复自己副本和对方副本中的墒。
消息通信模式对比
通信模式 | 次数 |
---|---|
推模式(Push) | 1 |
拉模式(Pull) | 2 |
推拉模式(Push&Pull) | 3 |
Gossip优缺点
优点
-
可扩展性
允许节点的任意增加和减少,新增节点的状态最终会与其他节点一致 -
分布式容错
任意节点的宕机和重启都不会影响 Gossip 消息的传播,具有天然的分布式系统容错特性 -
去中心化
无需中心节点,所有节点都是对等的,任意节点无需知道整个网络状况,只要网络连通,任意节点可把消息散播到全网 -
最终一致性
消息会以一传十、十传百的指数级速度在网络中传播,因此系统状态的不一致可以在很快的时间内收敛到一致,消息传播速度达到了logN -
通俗易懂
算法简单,容易理解,实现成本低
缺点
-
消息延迟
节点随机向少数几个节点发送消息,消息最终是通过多个轮次的散播而到达全网,不可避免的造成消息延迟
-
消息冗余
节点定期随机选择周围节点发送消息,而收到消息的节点也会重复该步骤;不可避免的引起同一节点消息多次接收,增加消息处理压力,一般通过文件校验和、缓存节点列表等方式来进行优化减少数据对比带来的性能损耗
基于以上优缺点分析,Gossip协议
满足CAP分布式理论中基于AP场景的数据最终一致性处理
常见使用Gossip协议应用场景
-
Redis Cluster
-
Consul
-
Apache Cassandra
-
Apache Gossip
-
InfluxDB
内容小结
Gossip是一个去中心化的、多主的分布式协议。它通过直接邮寄、反墒、谣言传播机制实现数据同步,同时通过推、拉、推拉通信模式实现数据副本最终一致性。
在实际应用场景中,一般直接邮寄方式是一定要实现了,因为足够简单、性能足够高,但可能会存在数据丢失,所以补充通过谣言传播同步更新数据,在集群新增节点时,一般通过反墒方式使新节点初始化完整数据。