P2P 网络核心技术（Gossip 协议）

• gossip 是什么

Gossip protocol 也叫 Epidemic Protocol （流行病协议），实际上它还有很多别名，比如：“流言算法”、“疫情传播算法”等。是基于流行病传播方式的节点或者进程之间信息交换的协议，主要用在分布式数据库系统中各个副本节点同步数据之用，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络，

gossip protocol 最初是由施乐公司帕洛阿尔托研究中心（Palo Alto Research Center）的研究员艾伦·德默斯（Alan Demers）于1987年创造的。从 gossip 单词就可以看到，其中文意思是八卦、流言等意思，我们可以想象下绯闻的传播（或者流行病的传播）；gossip 协议的工作原理就类似于这个。gossip 协议利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip 其实是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。

• Gossip 协议的执行过程：

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

如下：

1. Gossip 是周期性的散播消息，把周期限定为 1 秒
2. 被感染节点随机选择 k 个邻接节点（fan-out）散播消息，这里把 fan-out 设置为 3，每次最多往 3 个节点散播。
3. 每次散播消息都选择尚未发送过的节点进行散播
4. 收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A。

假设现在有 16 个节点，节点 1 为初始被感染节点，通过 Gossip 过程，最终所有节点都被感染：

gossip 优势

可扩展性（Scalable）

gossip 协议是可扩展的，一般需要 O(logN) 轮就可以将信息传播到所有的节点，其中 N 代表节点的个数。每个节点仅发送固定数量的消息，并且与网络中节点数目无法。在数据传送的时候，节点并不会等待消息的 ack，所以消息传送失败也没有关系，因为可以通过其他节点将消息传递给之前传送失败的节点。系统可以轻松扩展到数百万个进程。

容错（Fault-tolerance）

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

健壮性（Robust）

gossip 协议是去中心化的协议，所以集群中的所有节点都是对等的，没有特殊的节点，所以任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量（QOS）

最终一致性（Convergent consistency）

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 选举）传播提供可靠、快速的传播
• redis Cluster：集群中的 Nodes 之间使用 gossip 协议向其他 nodes 传播集群信息，以达到自动发现的特性。