`
gaojingsong
  • 浏览: 1182801 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

【Gossip协议】

阅读更多

1. Gossip背景

Gossip算法如其名,灵感来自办公室八卦,只要一个人八卦一下,在有限的时间内所有的人都会知道该八卦的信息,这种方式也与病毒传播类似,因此Gossip有众多的别名“闲话算法”、“疫情传播算法”、“病毒感染算法”、“谣言传播算法”。

但Gossip并不是一个新东西,之前的泛洪查找、路由算法都归属于这个范畴,不同的是Gossip给这类算法提供了明确的语义、具体实施方法及收敛性证明。

2. Gossip特点

Gossip算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致,这充分说明了Gossip的特点:在一个有界网络中,每个节点都随机地与其他节点通信,经过一番杂乱无章的通信,最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点,也可能仅知道几个邻居节点,只要这些节可以通过网络连通,最终他们的状态都是一致的,当然这也是疫情传播的特点。

要注意到的一点是,即使有的节点因宕机而重启,有新节点加入,但经过一段时间后,这些节点的状态也会与其他节点达成一致,也就是说,Gossip天然具有分布式容错的优点。

3. Gossip本质

Gossip是一个带冗余的容错算法,更进一步,Gossip是一个最终一致性算法。虽然无法保证在某个时刻所有节点状态一致,但可以保证在”最终“所有节点一致,”最终“是一个现实中存在,但理论上无法证明的时间点。

因为Gossip不要求节点知道所有其他节点,因此又具有去中心化的特点,节点之间完全对等,不需要任何的中心节点。实际上Gossip可以用于众多能接受“最终一致性”的领域:失败检测、路由同步、Pub/Sub、动态负载均衡。

但Gossip的缺点也很明显,冗余通信会对网路带宽、CUP资源造成很大的负载,而这些负载又受限于通信频率,该频率又影响着算法收敛的速度

 

 

Gossip是一种去中心化、容错而又最终一致性的绝妙算法,其收敛性不但得到证明还具有指数级的收敛速度。使用Gossip的系统可以很容易的把Server扩展到更多的节点,满足弹性扩展轻而易举。

唯一的缺点是收敛是最终一致性,不使用那些强一致性的场景,比如2pc。

 

 

Gossip是一个带冗余的容错算法,最终一致性算法。虽然无法保证在某个时刻所有节点状态一致,但可以保证在”最终“所有节点一致,”最终“是一个现实中存在,但理论上无法证明的时间点。因为Gossip不要求节点知道所有其他节点,因此又具有去中心化的特点,节点之间完全对等,不需要任何的中心节点。Gossip可以用于众多能接受“最终一致性”的领域:失败检测、路由同步、Pub/Sub、动态负载均衡。

 

Gossip的特点

     在一个有界网络中,每个节点都随机地与其他节点通信,经过一番杂乱无章的通信,最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点,也可能仅知道几个邻居节点,只要这些节可以通过网络连通,最终他们的状态都是一致的。

 

Gossip的缺点

       Gossip的缺点也很明显,冗余通信会对网路带宽、CPU资源造成很大的负载,而这些负载又受限于通信频率,该频率又影响着算法收敛的速度,后面我们会讲在各种场合下的优化方法。

 

 

Gossip通信方式:

      Gossip节点的通信方式及收敛性

两个节点(A、B)之间存在三种通信方式:

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的收敛速度是最快的。

(akka Cassandra都是采用的push/pull这种通信方式)

 

 

Gossip工作方式:

      Gossip的节点的工作方式又分两种:

Anti-Entropy(反熵):仅传播新到达的数据  

Rumor-Mongering(谣言传播):以固定的概率传播所有的数据

(注,网上些文章把上面两种的工作方式搞反了)

 

 

Anti-Entropy(反熵)又分为两种具体的工作(Reconciliation 和解/协调)方式:

     精确(Precise Reconciliation)

在每次通信周期内都非常准确地消除双方的不一致性,具体表现为相互发送对方需要更新的数据,因为每个节点都在并发与多个节点通信,理论上这很难做到。精确协调需要给每个数据项独立地维护自己的version,在每次交互是把所有的(key,value,version)发送到目标进行比对,从而找出双方不同之处从而更新。因为Gossip消息存在大小限制,因此每次选择发送哪些数据就成了问题。当然可以随机选择一部分数据,也可确定性的选择数据。对确定性的选择而言,可以有最老优先(根据版本)和最新优先两种,最老优先会优先更新版本最新的数据,而最新更新正好相反,这样会造成老数据始终得不到机会更新,也即饥饿。

当然,开发这也可根据业务场景构造自己的选择算法,但始终都无法避免消息量过多的问题。

     整体(Scuttlebutt Reconciliation)

不是为每个数据都维护单独的版本号,而是为每个节点上的宿主数据维护统一的version。比如节点P会为(p1,p2,...)维护一个一致的全局version,相当于把所有的宿主数据看作一个整体,当与其他节点进行比较时,只需必须这些宿主数据的最高version,如果最高version相同说明这部分数据全部一致,否则再进行精确协调。

整体协调对数据的选择也有两种方法:

广度优先:根据整体version大小排序,也称为公平选择

0
0
分享到:
评论

相关推荐

    基于Gossip协议的p2p成员管理协议.pdf

    ### 基于Gossip协议的P2P成员管理协议详解 #### 一、引言与背景 随着互联网分布式应用的迅速发展,可靠且可扩展的组通信机制变得尤为重要。传统上,网络级别的可靠组播协议(如SRM或RMTP)依赖于IP组播技术。然而...

    基于结构化Gossip协议的网格服务发现.pdf 论文

    ### 基于结构化Gossip协议的网格服务发现 #### 概述 在动态的网格环境中,资源和服务的快速准确发现是影响网格计算性能的关键因素。为了应对这一挑战,本文提出了一种基于消息扩散的网格服务发现机制,并进一步...

    一个 Java 版的 Gossip 协议实现.rar

    一个 Java 版的 Gossip 协议实现。 Gossip 算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致,这充分说明了 Gossip 的特点:在一个有界网络中,每个节点...

    Go-vegamcache是一个使用gossip协议构建的分布式内存中golang缓存库

    Go-vegamcache是一个专为Golang开发的分布式内存缓存库,其核心特性是采用了gossip协议来实现数据的同步和复制。这种协议在分布式系统中被广泛使用,因为它具有自我修复、高可用和扩展性强的特点。让我们深入探讨...

    gossip:Gossip协议的Go实现

    Gossip协议的Go实现。 概述 该软件包提供了最终一致的内存中数据存储的实现。 数据存储值使用推挽式八卦协议进行交换。 // Create a gossiper g := NewGossiper("<ip>:<port>", "<unique>", "<peer>") // Add ...

    SP.rar_gossip_gossip network_gossip协议

    该机制基于gossip模式,节点和随机选择的对等体交换信息,并按照特定的P2P应用需求来重新安排拓扑,本协议非常的高效和鲁棒,能够处理节点持续的加入和离开系统的流,且即使现存的所有SP移除也能修复。

    「来道题」Redis的Gossip协议:随机通信,最终一致;PING、PONG;配置纪元

    「来道题」服务端面试真题全解析 互联网大厂的资深工程师,带您开启技术成长之路~ 多年大规模在线服务实战经验,近百场校招、社招面试经历,告诉您最...Redis的Gossip协议:随机通信,最终一致;PING、PONG;配置纪元

    浅析redis cluster介绍与gossip协议

    `cluster bus`使用一种名为Gossip协议的二进制协议,该协议高效且节省资源,能够在节点间快速交换信息,减少网络带宽消耗和处理时间。 **Gossip协议** Gossip协议是一种分布式系统中常见的节点间通信机制,用于...

    基于Gossip协议的P2P流媒体系统 (2009年)

    在分析P2P(peer-to-peer)流媒体系统的典型模型的基础上,设计一种基于Gossip协议的P2P网络流媒体直播系统.该系统可以为每个节点独立地选择良好的伙伴节点,节点的自组织能力能够有效地减轻服务器的压力.实验表明,...

    Fabric v1.x Gossip协议的一些细节和传播原理

    文章目录一、Gossip协议的功能二、Leader PeerLeader Election三、Anchor Peer四、Gossip 消息传播原理 一、Gossip协议的功能 Fabric中需要在3个不同类型的节点间进行交易流 转,需要非常安全的、可靠的以及可扩展的...

    电信设备-基于Gossip通信协议和Raft选举算法的优化方法.zip

    1. **混合通信**:将Gossip协议用于日常状态传播和故障检测,而Raft用于关键决策和一致性维护,这样既能保证高效的信息传播,又能确保关键操作的一致性。 2. **动态选举**:利用Gossip协议快速发现节点状态变化,...

    2020分布式系统导论Gossip

    分布式系统导论中的Gossip协议是一种在大规模网络中传播信息的有效方法,尤其适用于容错性和扩展性要求高的环境。Gossip协议借鉴了社会学中消息传播的模式,通过节点之间的随机交互来传播和更新信息,使得整个网络...

    Gossip

    由于没有具体的文件内容可供参考,我将分别从Gossip协议和字体设计两个方面来详细阐述相关知识点。 首先,让我们来了解一下Gossip协议。这是一种在分布式系统中广泛使用的去中心化通信协议。它的设计理念源于社会学...

    基于分布式共识的Gossip 算法及时间同步研究.pdf

    他在文中引用了一些参考文献,并且给出了一些Gossip算法在分布式系统中的具体应用场景,例如P2P网络中使用Gossip协议进行数据同步等。由于文档中存在OCR扫描错误和遗漏,因此在理解时需要结合上下文以及专业知识进行...

    博士论文开题报告基于gossip的P2P网络拓扑优化技术研究.doc

    《基于gossip的P2P网络拓扑优化技术研究》这篇博士论文主要探讨了在当前互联网环境下,如何利用gossip协议优化对等网络(P2P网络)的拓扑结构,以提高网络性能和服务质量。P2P网络以其去中心化、高效能的特点,已经...

    PyPI 官网下载 | gossip-2.4.0.tar.gz

    - **消息传播**:gossip库采用 gossip 协议,以高效的方式在整个网络中传播信息,确保信息的快速传播和一致性。 - **多语言支持**:尽管名字中包含Python,但gossip实际上也支持其他编程语言,具有良好的跨平台...

    simu.zip_routing_routing wsn_wireless_路由 matlab

    本项目聚焦于WSN中的路由协议设计,特别是利用GOSSIP协议来实现这一目标。GOSSIP协议是一种分布式、自组织的路由算法,适用于资源受限的无线网络环境。 在WSN中,由于节点通常具有有限的能量、计算能力和存储空间,...

    GoccipAlgorithm(数据挖掘 大数据 课件)

    Goccip算法的名字可能与文档扫描过程中的OCR识别错误有关,但是根据上下文我们可以推测这里指的可能是Gossip协议,它在分布式系统中用于数据的一致性同步。Gossip协议是一种基于消息传播的算法,它模拟了人群中的...

    分布式系统作业-难度5.zip

    在本题中,学生们被分配了一项2021年东北大学的分布式系统作业,其核心是利用Gossip协议实现一个去中心化的平均数计算机制。这个任务的难度被评为5级,暗示了它可能涉及复杂的概念和技术。 首先,我们来理解Gossip...

Global site tag (gtag.js) - Google Analytics