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

('分布式原理：一文了解Gossip协议gossip协议（gossipprotocol）又称epidemic协议（epidemicprotocol），是基于流行病传播方式的节点或者进程之间信息交换的协议，在分布式系统中被广泛使用，比如我们可以使用gossip协议来确保网络中所有节点的数据一样。从gossip单词就可以看到，其中文意思是八卦、流言等意思，我们可以想象下绯闻的传播（或者流行病的传播）；gossip协议的工作原理就类似于这个。gossip协议利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip其实是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。gossip优势可扩展性（Scalable）gossip协议是可扩展的，一般需要O（logN）轮就可以将信息传播到所有的节点，其中N代表节点的个数。每个节点仅发送固定数量的消息，并且与网络中节点数目无法。在数据传送的时候，节点并不会等待消息的ack，所以消息传送失败也没有关系，因为可以通过其他节点将消息传递给之前传送失败的节点。系统可以轻松扩展到数百万个进程。容错（Fault-tolerance）网络中任何节点的重启或者宕机都不会影响gossip协议的运行。健壮性（Robust）gossip协议是去中心化的协议，所以集群中的所有节点都是对等的，没有特殊的节点，所以任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量（QOS）最终一致性（Convergentconsistency）Gossip协议实现信息指数级的快速传播，因此在有新信息需要传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。gossip协议的类型前面说了节点会将信息传播到整个网络中，那么节点在什么情况下发起信息交换？这就涉及到gossip协议的类型。目前主要有两种方法：Anti-Entropy（反熵）：以固定的概率传播所有的数据Rumor-Mongering（谣言传播）：仅传播新到达的数据AnTI-EntropyAnTI-Entropy的主要工作方式是：每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。AnTI-Entropy这种方法非常可靠，但是每次节点两两交换自己的所有数据会带来非常大的通信负担，以此不会频繁使用。AnTI-Entropy使用“simpleepidemics”的方式，所以其包含两种状态：susceptible和infective，这种模型也称为SImodel。处于infective状态的节点代表其有数据更新，并且会将这个数据分享给其他节点；处于susceptible状态的节点代表其并没有收到来自其他节点的更新。Rumor-MongeringRumor-Mongering的主要工作方式是：当一个节点有了新的信息后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新信息。直到所有的节点都知道该新信息。因为节点之间只是交换新信息，所有大大减少了通信的负担。Rumor-Mongering使用“complexepidemics”方法，相比Anti-Entropy多了一种状态：removed，这种模型也称为SIRmodel。处于removed状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。因为Rumor消息会在某个时间标记为removed，然后不会发送给其他节点，所以Rumor-Mongering类型的gossip协议有极小概率使得更新不会达到所有节点。一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。gossip协议的通讯方式不管是Anti-Entropy还是Rumor-Mongering都涉及到节点间的数据交互方式，节点间的交互方式主要有三种：Push、Pull以及Push">Push：发起信息交换的节点A随机选择联系节点B，并向其发送自己的信息，节点B在收到信息后更新比自己新的数据，一般拥有新信息的节点才会作为发起节点。Pull：发起信息交换的节点A随机选择联系节点B，并从对方获取信息。一般无新信息的节点才会作为发起节点。Push">gossip算法实现Gossip协议是按照流言传播或流行病传播的思想实现的，所以，Gossip协议的实现算法也是很简单的，下面分别是Anti-Entropy和Rumor-Mongering的实现伪代码。gossip在工程上的使用gossip协议可以支持以下需求：Databasereplication消息传播ClustermembershipFailure检测OverlayNetworksAggregations（比如计算平均值、最大值以及总和）在下面的工程上使用到了gossip协议。',)