MONGER 分布式原理：一文了解 Gossip 协议

什么是八卦

流言协议，又称流行病协议，是基于流行病传播模式的节点或进程之间交换信息的协议，广泛应用于分布式系统中。例如，我们可以使用流言协议来确保网络中所有节点的数据。

八卦可以从八卦这个词看出来，八卦在汉语里是八卦和八卦的意思。我们可以想象八卦的传播(或者流行病的传播)；八卦协议是这样运作的。八卦以随机的方式向整个网络传播信息，使系统中所有节点的数据在一定时间内保持一致。流言其实是一个分散的分布式协议，解决了两个问题:状态在集群中的传播和状态一致性的保证。

八卦优势

可扩展性(可扩展性)

八卦协议是可扩展的，通常需要O(logN)轮将信息传播到所有节点，其中n代表节点数。每个节点只发送固定数量的消息，网络中的节点数量不够。在数据传输过程中，节点不会等待消息的ack，所以消息传输失败也没关系，因为消息可以通过其他节点传输到之前传输失败的节点。该系统可以轻松扩展到数百万个进程。

容错；容错

网络中任何节点的重启或停机都不会影响gossip协议的运行。

健壮性(健壮性)

Gossip协议是一个分散的协议，所以集群中所有节点都是平等的，没有特殊的节点，所以任何一个有问题的节点都不会阻止其他节点发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量(QOS)

最终一致性(收敛一致性)

流言协议实现了信息的指数级快速传播，因此当需要传播新信息时，消息可以快速发送到全局节点，所有节点都可以在有限的时间内拥有最新的数据。

八卦协议的类型

据说节点会将信息传播到整个网络，那么节点在什么情况下发起信息交换呢？这涉及到八卦协议的类型。目前，主要有两种方法:

Anti-Entropy（反熵）：以固定的概率传播所有的数据Rumor-Mongering（谣言传播）：仅传播新到达的数据

反熵

反熵的主要工作模式是每个节点周期性地随机选择其他节点，然后通过交换各自所有的数据来消除它们之间的差异。这种反熵的方法非常可靠，但是每次节点成对交换自己所有的数据都会带来很大的通信负担，所以不会频繁使用。

反熵使用的是“简单流行病学”的方式，所以包含了易感性和感染性两种状态。这个模型也叫SI模型。感染状态的节点表示有数据更新，会和其他节点共享这个数据；处于易受影响状态的节点意味着它没有从其他节点接收到更新。

散布谣言

造谣的主要工作模式是，当一个节点有新的信息时，该节点变得活跃，并定期联系其他节点向其发送新的信息。直到所有节点都知道新的信息。由于节点之间只交换新信息，通信负担大大降低。

相比于反熵，造谣使用的是“复杂流行病学”的方法，多了一个状态:去除。这种模型也被称为安全气囊系统模型。处于已删除状态的节点表示它已从其他节点接收到更新，但它不会与其他节点共享此更新。

因为谣言消息会在某个时间被标记为删除，然后不会发送到其他节点，所以造谣八卦协议更新不会到达所有节点的概率非常小。

一般来说，为了在通信成本和可靠性之间达成妥协，有必要将这两种方法结合起来。

八卦协议的通信方式

反熵和造谣都涉及节点之间的数据交互，节点之间的交互方式主要有三种:推、拉和推&拉。

Push：发起信息交换的节点 A 随机选择联系节点 B，并向其发送自己的信息，节点 B 在收到信息后更新比自己新的数据，一般拥有新信息的节点才会作为发起节点。Pull：发起信息交换的节点 A 随机选择联系节点 B，并从对方获取信息。一般无新信息的节点才会作为发起节点。Push&Pull：发起信息交换的节点 A 向选择的节点 B 发送信息，同时从对方获取数据，用于更新自己的本地数据。

八卦算法实现

流言协议是按照流言传播或者疫情传播的思路来实现的，所以流言协议的实现算法也很简单。以下是反熵和造谣的伪代码。

八卦在工程中的应用

八卦协议可以支持以下要求:

Database replication消息传播Cluster membershipFailure 检测Overlay NetworksAggregations (比如计算平均值、最大值以及总和)

八卦协议用于以下项目。

Riak（https://github.com/basho/riak） 使用 gossip 协议来共享和传递集群的环状态（ring state）和存储桶属性（bucket properties）。Cassandra：节点间的信息交换使用了 gossip 协议，因此所有节点都可以快速了解集群中的所有其他节点。Dynamo：采用基于 gossip 协议的分布式故障检测和成员协议，这样集群中添加或移除节点，其他节点可以快速检测到。Consul：使用了称为 SERF 的gossip 协议，主要有两个目的：1、发现新的节点或者发现故障节点；2、为一些重要的事件（比如 Leader 选举）传播提供可靠、快速的传播Amazon s3：使用 gossip 协议将服务的状态传递给系统。