起源
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协议执行过程:
种子节点周期性的散播消息 【假定把周期限定为 1 秒】。
被感染节点随机选择N个邻接节点散播消息【假定fan-out(扇出)设置为6,每次最多往6个节点散播】。
节点只接收消息不反馈结果。
每次散播消息都选择尚未发送过的节点进行散播。
收到消息的节点不再往发送节点散播:A -> B,那么B进行散播的时候,不再发给 A。
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: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点,B 节点更新 A 中比自己新的数据
Pull:A 仅将数据 key, version 推送给 B,B 将本地比 A 新的数据(Key, value, version)推送给 A,A 更新本地
Push/Pull:与 Pull 类似,只是多了一步,A 再将本地比 B 新的数据推送给 B,B 则更新本地
如果把两个节点数据同步一次定义为一个周期,则在一个周期内,Push 需通信 1 次,Pull 需 2 次,Push/Pull 则需 3 次。虽然消息数增加了,但从效果上来讲,Push/Pull 较好,理论上一个周期内可以使两个节点完全一致。直观上,Push/Pull 的收敛速度也是最快的。
总结
综上所述,我们可以得出Gossip是一种去中心化的分布式协议,数据通过节点像病毒一样逐个传播。因为是指数级传播,整体传播速度非常快,很像现在美国失控的2019-nCoV(新冠)一样。它具备以下优势:
扩展性:允许节点的任意增加和减少,新增节点的状态 最终会与其他节点一致。
容错:任意节点的宕机和重启都不会影响 Gossip 消息的传播,具有天然的分布式系统容错特性。
去中心化:无需中心节点,所有节点都是对等的,任意节点无需知道整个网络状况,只要网络连通,任意节点可把消息散播到全网。
一致性收敛:消息会以“一传十的指数级速度”在网络中传播,因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
简单
同样也存在以下缺点:
消息延迟:节点随机向少数几个节点发送消息,消息最终是通过多个轮次的散播而到达全网;不可避免的造成消息延迟。
消息冗余:节点定期随机选择周围节点发送消息,而收到消息的节点也会重复该步骤;不可避免的引起同一节点消息多次接收,增加消息处理压力。
Gossip协议由于以上的优缺点,所以适合于AP场景的数据一致性处理,常见应用有:P2P网络通信、Apache Cassandra、Redis Cluster、Consul。
from : http://distributedsystem.dataguru.cn/article-15753-1.html
相关推荐
难度五 多线程
#资源达人分享计划#
详细介绍了一种经典的基于Gossip协议的p2p成员管理协议,发表于IEEE transactions of Computers,已被引用多次,想了解P2P成员管理协议或应用层组播的同学可以读一下
vegamcache是一个使用gossip协议构建的分布式内存中golang缓存库
基于结构化Gossip协议的网格服务发现.pdf 论文
此为很有人气的Gossip的学习笔记,里面深入浅出的讲解了关于spring框架的知识与学习心得,是理解spring的不可多得的好资料。 此资料为html形式,每个知识点单独列为一张html页面,阅读很方便,不需要pdf格式下的阅读...
一个 Java 版的 Gossip 协议实现。 Gossip 算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致,这充分说明了 Gossip 的特点:在一个有界网络中,每个节点...
Gossip协议的Go实现。 概述 该软件包提供了最终一致的内存中数据存储的实现。 数据存储值使用推挽式八卦协议进行交换。 // Create a gossiper g := NewGossiper("<ip>:<port>", "<unique>", "<peer>") // Add ...
该机制基于gossip模式,节点和随机选择的对等体交换信息,并按照特定的P2P应用需求来重新安排拓扑,本协议非常的高效和鲁棒,能够处理节点持续的加入和离开系统的流,且即使现存的所有SP移除也能修复。
网络游戏-分布式网络中基于gossip算法的多目标DOA估计系统及估计方法.zip
网络游戏-分布式网络中基于gossip算法的单目标DOA估计系统及估计方法.zip
一、redis cluster 介绍 自动将数据进行分片,每个 master 上放一部分数据 提供内置的高可用支持,部分 master 不可用时,还是...cluster bus 用的是一种叫gossip 协议的二进制协议,用于节点间高效的数据交换,占
「来道题」服务端面试真题全解析 互联网大厂的资深工程师,带您开启技术成长之路~ 多年大规模在线服务实战经验,近百场校招、社招面试经历,告诉您最...Redis的Gossip协议:随机通信,最终一致;PING、PONG;配置纪元
文章目录一、Gossip协议的功能二、Leader PeerLeader Election三、Anchor Peer四、Gossip 消息传播原理 一、Gossip协议的功能 Fabric中需要在3个不同类型的节点间进行交易流 转,需要非常安全的、可靠的以及可扩展的...
在分析P2P(peer-to-peer)流媒体系统的典型模型的基础上,设计一种基于Gossip协议的P2P网络流媒体直播系统.该系统可以为每个节点独立地选择良好的伙伴节点,节点的自组织能力能够有效地减轻服务器的压力.实验表明,...
2.Algorithm Gossip: 费式数列 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 5.Algorithm Gossip: 老鼠走迷官 6.Algorithm Gossip: 老鼠走迷官(二) 7.Algorithm Gossip: 骑士走棋盘 8.Algorithm Gossip: 八皇 9....
基于MATLAB的平面路由协议Flooding仿真源码
针对在分布式一致性系统中常用的gossip算法负载均衡效率较低的问题,本文在概率gossip算法(probabilistic gossip algorithm)的基础上,设计了一种寄存器gossip算法(register gossip algorithm,下文简称R-gossip...
电信设备-基于Gossip通信协议和Raft选举算法的优化方法.zip