Gossip protocol 也叫 Epidemic Protocol (流行病协议)。Gossip protocol在1987年8月由施乐-帕洛阿尔托研究中心发表ACM上的论文
《Epidemic Algorithms for Replicated Database Maintenance》
中被提出。原本用于分布式数据库中节点同步数据使用,后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。
Gossip协议是基于六度分隔理论(Six Degrees of Separation)哲学的体现,简单的来说,一个人通过6个中间人可以认识世界任何人。数学公式是:
n表示复杂度,N表示人的总数,W表示每个人的联系宽度。依据邓巴数,即每个人认识150人,其六度就是1506 =11,390,625,000,000(约11.4万亿)。
基于六度分隔理论,任何信息的传播其实非常迅速,而且网络交互次数不会很多。比如Facebook在2016年2月4号做了一个实验:研究了当时已注册的15.9亿使用者资料,发现这个神奇数字的“网络直径”是4.57,翻成白话文意味着每个人与其他人间隔为4.57人。
- 原理 -
Gossip协议执行过程:
Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间,由于不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,因此它是一个最终一致性协议。
Gossip协议是一个多主协议,所有写操作可以由不同节点发起,并且同步给其他副本。Gossip内组成的网络节点都是对等节点,是非结构化网络。
- 消息类型 -
Gossip 协议的消息传播方式有两种:Anti-Entropy(反熵传播)和Rumor-Mongering(谣言传播)。
反熵传播是以固定的概率传播所有的数据。所有参与节点只有两种状态:Suspective(病原)、Infective(感染)。这种节点状态又叫做simple epidemics(SI model)。过程是种子节点会把所有的数据都跟其他节点共享,以便消除节点之间数据的任何不一致,它可以保证最终、完全的一致。缺点是消息数量非常庞大,且无限制;通常只用于新加入节点的数据初始化。
谣言传播是以固定的概率仅传播新到达的数据。所有参与节点有三种状态:Suspective(病原)、Infective(感染)、Removed(愈除)。这种节点状态又叫做complex epidemics(SIR model)。过程是消息只包含最新 update,谣言消息在某个时间点之后会被标记为 removed,并且不再被传播。缺点是系统有一定的概率会不一致,通常用于节点间数据增量同步。
- 通信方式 -
Gossip 协议最终目的是将数据分发到网络中的每一个节点。根据不同的具体应用场景,网络中两个节点之间存在三种通信方式:推送模式、拉取模式、Push/Pull。
如果把两个节点数据同步一次定义为一个周期,则在一个周期内,Push 需通信 1 次,Pull 需 2 次,Push/Pull 则需 3 次。虽然消息数增加了,但从效果上来讲,Push/Pull 最好,理论上一个周期内可以使两个节点完全一致。直观上,Push/Pull 的收敛速度也是最快的。
- 总结 -
综上所述,我们可以得出Gossip是一种去中心化的分布式协议,数据通过节点像病毒一样逐个传播。因为是指数级传播,整体传播速度非常快,很像现在美国失控的2019-nCoV(新冠)一样。它具备以下优势:
同样也存在以下缺点:
Gossip协议由于以上的优缺点,所以适合于AP场景的数据一致性处理,常见应用有:P2P网络通信、Apache Cassandra、Redis Cluster、Consul。
本文来源于:奈学开发者社区
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。