Paxos、Raft、ZAB 等分布式算法经常会被称作是“强一致性”的分布式共识协议，其实这样的描述抠细节概念的话是很别扭的，会有语病嫌疑，但我们都明白它的意思其实是在说“尽管系统内部节点可以存在不一致的状态，但从系统外部看来，不一致的情况并不会被观察到，所以整体上看系统是强一致性的”。与它们相对的，还有另一类被冠以“最终一致性”的分布式共识协议，这表明系统中不一致的状态有可能会在一定时间内被外部直接观察到。一种典型且极为常见的最终一致的分布式系统就是DNS 系统，在各节点缓存的 TTL 到期之前，都有可能与真实的域名翻译结果存在不一致。在本节中，笔者将介绍在比特币网络和许多重要分布式框架中都有应用的另一种具有代表性的“最终一致性”的分布式共识协议：Gossip 协议。
Gossip 协议也叫 Epidemic Protocol（流行病协议），主要用于消息传播，是一种一致性算法。协议也非常好理解，正如协议的名称，如流行病一样靠“感染”节点进行持续传播。使用 Gossip 协议的有：Redis Cluster、Consul、Apache Cassandra等。
也把 Gossip 称作是“共识协议”，但首先必须强调它所解决的问题并不是直接与 Paxos、Raft 这些共识算法等价的，只是基于 Gossip 之上可以通过某些方法去实现与 Paxos、Raft 相类似的目标而已。一个最典型的例子是比特币网络中使用到了 Gossip 协议，用它来在各个分布式节点中互相同步区块头和区块体的信息，这是整个网络能够正常交换信息的基础，但并不能称作共识；比特币使用工作量证明（Proof of Work，PoW）来对“这个区块由谁来记账”这一件事情在全网达成共识，这个目标才可以认为与 Paxos、Raft 的目标是一致的。
六度分隔理论
要说 Gossip 就不得不提“六度分隔理论”，简单的说：你和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人你就能够认识任何一个陌生人。由时任哈佛大学的心理学教授 Stanley Milgram 在1967年提出。
Facebook 研究了已注册的15.9亿使用者资料，在2016年公布标题为 “Three and a half degrees of separation” 的研究结果。发现世界比人们想象的更紧密，世界上的每个人（至少在 Facebook 活跃的15.9亿人）平均通过3.57个人就可以与任意另外一个人产生联系。
基于六度分隔理论，信息的传播会非常迅速，而且网络交互次数不会很多。Gossip 协议是基于六度分隔理论的很好实现。
协议原理
Gossip协议基本思想就是：一个节点想要分享一些信息给网络中的其他的节点，于是随机选择一些节点进行信息传递。这些收到信息的节点接下来把这些信息传递给其他一些随机选择的节点。整体过程描述如下。
- Gossip 是周期性的散播消息
- 被感染节点随机选择 k 个邻接节点（fan-out）散播消息，假设把 fan-out 设置为2，每次最多往2个节点散播
- 每次散播消息都选择尚未发送过的节点进行散播
-
收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A
Gossip-Node-Spread
上图是 Gossip 传播过程的示意图，根据示意图和 Gossip 的过程描述，我们很容易发现 Gossip 对网络节点的连通性和稳定性几乎没有任何要求，它一开始就将网络某些节点只能与一部分节点部分连通（Partially Connected Network）而不是以全连通网络（Fully Connected Network）作为前提；能够容忍网络上节点的随意地增加或者减少，随意地宕机或者重启，新增加或者重启的节点的状态最终会与其他节点同步达成一致。Gossip 把网络上所有节点都视为平等而普通的一员，没有任何中心化节点或者主节点的概念，这些特点使得 Gossip 具有极强的鲁棒性，而且非常适合在公众互联网中应用。
Gossip协议的类型
前面说了节点会将信息传播到整个网络中，那么节点在什么情况下发起信息交换？这就涉及到 gossip 协议的类型。目前主要有两种方法：
- Anti-Entropy（反熵）：以固定的概率传播所有的数据
- Rumor-Mongering（谣言传播）：仅传播新到达的数据
Anti-Entropy
Anti-Entropy 的主要工作方式是：每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。Anti-Entropy 这种方法非常可靠，但是每次节点两两交换自己的所有数据会带来非常大的通信负担，以此不会频繁使用。
Anti-Entropy 使用“simple epidemics”的方式，所以其包含两种状态：susceptible 和 infective，这种模型也称为 SI model。处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点；处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。
Rumor-Mongering
Rumor-Mongering 的主要工作方式是：当一个节点有了新的信息后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新信息。直到所有的节点都知道该新信息。因为节点之间只是交换新信息，所有大大减少了通信的负担。
Rumor-Mongering 使用“complex epidemics”方法，相比 Anti-Entropy 多了一种状态：removed，这种模型也称为 SIR model。处于 removed 状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。
因为 Rumor 消息会在某个时间标记为 removed，然后不会发送给其他节点，所以 Rumor-Mongering 类型的 gossip 协议有极小概率使得更新不会达到所有节点。
一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。
Gossip协议的通讯方式
不管是 Anti-Entropy 还是 Rumor-Mongering 都涉及到节点间的数据交互方式，节点间的交互方式主要有三种：Push、Pull 以及 Push&Pull。
- Push：发起信息交换的节点 A 随机选择联系节点 B，并向其发送自己的信息，节点 B 在收到信息后更新比自己新的数据，一般拥有新信息的节点才会作为发起节点。
- Pull：发起信息交换的节点 A 随机选择联系节点 B，并从对方获取信息。一般无新信息的节点才会作为发起节点。
- Push&Pull：发起信息交换的节点 A 向选择的节点 B 发送信息，同时从对方获取数据，用于更新自己的本地数据。
Gossip算法实现
Gossip 协议是按照流言传播或流行病传播的思想实现的，所以，Gossip 协议的实现算法也是很简单的，下面分别是 Anti-Entropy 和 Rumor-Mongering 的实现伪代码。
Gossip-Algorithm-SI.jpg
Gossip-Algorithm-SIR.jpg
协议优缺点
优点
扩展性
Gossip 协议的可扩展性极好，一般只需要 O(LogN) 轮就可以将信息传播到所有的节点，其中 N 代表节点的个数。即使集群节点的数量增加，每个节点的负载也不会增加很多，几乎是恒定的。这就允许集群管理的节点规模能横向扩展到几千几万个，集群内的消息通信成本却不会增加很多。
容错
网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。
健壮性
Gossip 协议是去中心化的协议，所以集群中的所有节点都是对等的，任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量。
最终一致性
消息传播是指数级的快速传播，因此当有新信息传播时，消息可以快速地发送到全局节点。系统状态的不一致可以在很快的时间内收敛到一致。
缺点
消息延迟
节点随机向少数几个节点发送消息，消息最终是通过多个轮次的传播而到达全网，不可避免的造成消息延迟。不适合于对实时性要求较高的场景。
消息冗余
节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。
拜占庭问题
如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出问题。
Gossip在工程上的使用
gossip 协议可以支持以下需求：
- Database replication
- 消息传播
- Cluster membership
- Failure 检测
- Overlay Networks
- Aggregations (比如计算平均值、最大值以及总和)
在下面的工程上使用到了 Gossip 协议。
- Riak（https://github.com/basho/riak） 使用 gossip 协议来共享和传递集群的环状态（ring state）和存储桶属性（bucket properties）。
- Cassandra：节点间的信息交换使用了 gossip 协议，因此所有节点都可以快速了解集群中的所有其他节点。
- Dynamo：采用基于 gossip 协议的分布式故障检测和成员协议，这样集群中添加或移除节点，其他节点可以快速检测到。
- Consul：使用了称为 SERF 的gossip 协议，主要有两个目的：1、发现新的节点或者发现故障节点；2、为一些重要的事件（比如 Leader 选举）传播提供可靠、快速的传播
- Amazon s3：使用 gossip 协议将服务的状态传递给系统。
- Redis Cluster：集群中的 Nodes 之间使用 gossip 协议向其他 nodes 传播集群信息，以达到自动发现的特性。
- 比特币：著名的比特币网络在发送消息（比如发起一笔比特币转账）的时候会使用 gossip 协议，比确保所有的结点都会收到。
- Akka Cluster：Akka 基于 gossip 协议提供了一种故障检测机制，能够自动发现出现故障而离开集群的成员节点，通过事件驱动的方式，将状态传播到整个集群的其它成员节点。
参考：
网友评论