title: 分布式算法 Gossip
date: 2021-07-13 09:18:41
categories:
- 分布式
- 分布式理论
tags:
- 分布式
- 理论
- 算法
- 共识性
- Gossip
permalink: /pages/71539a/
Gossip 也叫 Epidemic Protocol (流行病协议),这个协议基于最终一致性以及去中心化设计思想。主要用于分布式节点之间进行信息交换和数据同步,这种场景的一个最大特点就是组成的网络的节点都是对等节点,是非结构化网络(去中心化)。
Gossip 协议最早是在 1987 年发表在 ACM 上的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出,其理论基础来源于流行病学的数学模型,这种场景的一个最大特点就是组成的网络的节点都是去中心化的对等节点,在信息同步过程中不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,实现最终一致性协议。
Gossip 协议是集群中节点相互通信的内部通信技术。 Gossip 是一种高效、轻量级、可靠的节点间广播协议,用于传播数据。它是去中心化的、“流行病”的、容错的和点对点通信协议。
在 CASSANDRA 中,节点间使用 Gossip 协议交换信息,因此所有节点都可以快速了解集群中的所有其他节点。
Consul 使用名为 SERF 的 Gossip 协议有两个作用:
Gossip 协议在概念上非常简单,代码也非常简单。它们背后的基本思想是:一个节点想要与网络中的其他节点共享一些信息。然后周期性地从节点集中随机选择一个节点并交换信息。接收信息的节点做同样的事情。信息定期发送到 N 个目标,N 称为扇出(Fanout
)。
Gossip 协议的执行过程:
Gossip 过程是由种子节点发起,当一个种子节点有状态需要更新到网络中的其他节点时,它会随机的选择周围几个节点散播消息,收到消息的节点也会重复该过程,直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间,由于不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,因此它是一个最终一致性协议。
为了表述清楚,我们先做一些前提设定
注意:Gossip 过程是异步的,也就是说发消息的节点不会关注对方是否收到,即不等待响应;不管对方有没有收到,它都会每隔 1 秒向周围节点发消息。异步是它的优点,而消息冗余则是它的缺点。
Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间,由于不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,因此它是一个最终一致性协议。
Gossip 有两种类型:
熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致。本质上,反熵是一种通过异步修复实现最终一致性的方法。反熵指的是集群中的节点,每隔段时间就随机选择某个其他节点,然后通过互相交换自己的所有数据来消除两者之间的差异,实现数据的最终一致性。由于消息会不断反复的交换,因此消息数量是非常庞大的,无限制的(unbounded),这对一个系统来说是一个巨大的开销。所以,反熵不适合动态变化或节点数比较多的分布式环境。
谣言传播模型指的是当一个节点有了新数据后,这个节点变成活跃状态,并周期性地联系其他节点向其发送新数据,直到所有的节点都存储了该新数据。在谣言传播模型下,消息可以发送得更频繁,因为消息只包含最新 update,体积更小。而且,一个谣言消息在某个时间点之后会被标记为 removed,并且不再被传播,因此,谣言传播模型下,系统有一定的概率会不一致。而由于,谣言传播模型下某个时间点之后消息不再传播,因此消息是有限的,系统开销小。
一般来说,为了在通信代价和可靠性之间取得折中,需要将这两种方法结合使用。
Gossip 中的通信模式
在 Gossip 协议下,网络中两个节点之间有三种通信方式:
如果把两个节点数据同步一次定义为一个周期,则在一个周期内,Push 需通信 1 次,Pull 需 2 次,Push/Pull 则需 3 次。虽然消息数增加了,但从效果上来讲,Push/Pull 最好,理论上一个周期内可以使两个节点完全一致。直观上,Push/Pull 的收敛速度也是最快的。
分布式网络中,没有一种完美的解决方案,Gossip 协议跟其他协议一样,也有一些不可避免的缺陷,主要是两个:
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。