来自于流行病的Gossip协议

Gossip协议本身比较简单，其使用类似于流行病的传播方式，它把信息以一种随机的方式散布到整个网络中，你可以在这里看到Gossip协议的信息散布方式的在线模拟。Gossip协议传播数据的方式分为 Push-based 和 Pull-based 两种。

Push-based 方式的工作流程如下：

1. 网络中的某个节点随机选取其它n个节点作为传输对象
2. 该节点向其它n个节点传输相应的信息
3. 收到信息的节点重复 1 ~ 2 步的操作

Pull-based 方式则不一样，它的工作流程如下：

1. 某个节点s随机选取其它n个节点询问它们是否有最新的信息
2. 收到请求的节点回复节点s告知其最新的信息

Gossip协议收敛性是比较好的，也就是说随着节点的增加，一次数据更新所需要的完整时间的增长率会逐渐降低，最终所需要的时间会趋于平稳，这使得Gossip在海量节点的情况下也能有良好的同步效率。

著名的分布式搜索引擎Elasticsearch就是使用了类似于Gossip的算法来实现节点之间的发现的。所有的节点会根据此协议而相互通信，最终组合起来成为一个完整的整体。

Zen discovery uses a list of seed nodes in order to start off the discovery process. At startup, or when electing a new master, Elasticsearch tries to connect to each seed node in its list, and holds a gossip-like conversation with them to find other nodes and to build a complete picture of the cluster. By default there are two methods for configuring the list of seed nodes: unicast and file-based. It is recommended that the list of seed nodes comprises the list of master-eligible nodes in the cluster.

以上内容出自ES文档Seed nodes。

简单来说，ES节点启动时会根据组播或者文件配置的方式来发现一些种子节点，之后该节点与种子节点进行信息传输，而种子节点本身还可能会和一些其它的节点有着数据传输的操作。集群内部经过一段时间的节点间数据同步，集群中的任意一个节点都可以让其它所有的节点都知道自己，因此集群中的任意一个节点都可以得到集群中所有其它的节点的信息，所有的节点此时成为了一个完整的整体。

那么，什么是Gossip？
Gossip是分布式系统中被广泛使用的协议，其主要用于实现分布式节点或者进程之间的信息交换。Gossip协议同时满足应用层多播协议所要求的低负载，高可靠和可扩展性的要求。由于其简单而易于实现，当前很多系统（例如Amazon S3，Usenet NNTP等）选择基于Gossip协议以实现应用层多播的功能。

传播方式在上文中提到，这里不再赘述。

当然，为了提高Gossip协议的性能，还有基于Push-Pull的混合协议。同时需要注意的是Gossip协议并不对网络的质量做出任何要求，也不需要loss-free的网络协议。Gossip协议一般基于UDP实现，其自身即在应用层保证了协议的robustness。

Gossip协议的性能
Gossip协议的分析是基于流行病学（Epidemiology）研究的。因此在分析Gossip的性能之前，需要首先介绍一下流行病学中基本的模型。

Epidemiology
流行病传染最基本的模型仅作如下几个假设：

1. 个人均匀的分布在一起
2. 每一对人群之间的传染概率是，显然
3. 任意时刻，某个人要么处于infected的状态要么处于uninfected的状态
4. 一旦某个人从uninfected状态转变成为infected状态，其一直停留在infected状态

有了以上假设，我们可以进一步分析流行病的传染情况。我们记时刻处于infected状态的人数为，处于uninfected状态的人为
，那么初始状态 ，，并且在任何时候

考虑连续的时间。可知：

解得：

明显，当时，，，即经过足够的时间，所有的人都将被传染。

Gossip的性能
上述流行病传染模型为分析Gossip的性能提供了基础。在Gossip性能中，我们可以认为：（因为对每个节点而言，被其他节点选中的概率就是）。我们令，可以得到：

这表明，急需要个回合，gossip协议即可将信息传递到所有的节点。 根据分析可得，Gossip协议具有以下的特点：

1. 低延迟。仅仅需要个回合的传递时间
2. 非常可靠。仅有个节点不会收到消息
3. 轻量级，每个节点传送了

于此同时，Gossip协议的容错性比较高，例如，的丢包率等价于使用，代替进行分析；的节点错误等价于使用来代替，同时使用来代替进行分析，其分析结果不用带来数量级上的变化。