`
m635674608
  • 浏览: 5021799 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

Gossip算法学习

 
阅读更多
1. 概述 
gossip,顾名思义,类似于流言传播的概念,是一种可以按照自己的期望,自行选择与之交换信息的节点的通信方式 
gossip, or anto-entropy,  is an attractive way of replicating state that does not have strong consistency requirements 

2. 算法描述

假设有 {p, q, ...} 为协议参与者。 每个参与者都有关于一个自己信息的表。 
用编程语言可以描述为: 
记 InfoMap = Map<Key, (Value, Version)>, 那么每个参与者要维护一个 InfoMap 类型的变量 localInfo。 同时每一个参与者要知道所有其他参与者的信息, 即要维护一个全局的表,即 Map<participant, InfoMap> 类型的变量 globalMap。 每个参与者更新自己的 localInfo, 而由 Gossip 协议负责将更新的信息同步到整个网络上。 
每个节点和系统中的某些节点成为 peer (如果系统的规模比较小,和系统中所有的其他节点成为 peer)。 有三种不同的同步信息的方法: 
1)push-gossip: 最简单的情况下, 一个节点 p 向 q 发送整个 GlobalMap 
2)pull-gossip: p 向 q 发送 digest, q 根据 digest 向 p 发送 p 过期的 (key, (value, version)) 列表 
3)push-pull-gossip:与pull-gossip类似,只是多了一步,A再将本地比B新的数据推送给B,B更新本地 

3. 特点
gossip不要求节点知道所有其他节点,因此具有去中心化的特点,节点之间完全对等,不需要任何的中心节点。
gossip算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致,这充分说明了Gossip的特点:
在一个有界网络中,每个节点都随机地与其他节点通信,经过一番杂乱无章的通信,最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点,也可能仅知道几个邻节点,只要这些节可以通过网络连通,最终他们的状态都是一致的
gossip算法是一个最终一致性算法,其无法保证在某个时刻所有节点状态一致,但可以保证在”最终“所有节点一致,”最终“是一个现实中存在,但理论上无法证明的时间点

4. 协调机制
协调机制是讨论在每次2个节点通信时,如何交换数据能达到最快的一致性,也即消除两个节点的不一致性。
协调所面临的最大问题是,因为受限于网络负载,不可能每次都把一个节点上的数据发送给另外一个节点,也即每个Gossip的消息大小都有上限。在有限的空间上有效率地交换所有的消息是协调要解决的主要问题。
“Efficient Reconciliation and Flow Control for Anti-Entropy Protocols”中描述了两种同步机制
1)precise reconciliation
precise reconciliation希望在每次通信周期内都非常准确地消除双方的不一致性,具体表现为相互发送对方需要更新的数据,因为每个节点都在并发与多个节点通信,理论上很难做到。precise reconciliation需要给每个数据项独立地维护自己的version,在每次交互是把所有的(key,value,version)发送到目标进行比对,从而找出双方不同之处从而更新。但因为Gossip消息存在大小限制,因此每次选择发送哪些数据就成了问题。当然可以随机选择一部分数据,也可确定性的选择数据。对确定性的选择而言,可以有最老优先(根据版本)和最新优先两种,最老优先会优先更新版本最新的数据,而最新更新正好相反,这样会造成老数据始终得不到机会更新,也即饥饿。
2)Scuttlebutt Reconciliation
Scuttlebutt Reconciliation 与precise reconciliation不同之处是,Scuttlebutt Reconciliation不是为每个数据都维护单独的版本号,而是为每个节点上的宿主数据维护统一的version。比如节点P会为(p1,p2,...)维护一个一致的全局version,相当于把所有的宿主数据看作一个整体,当与其他节点进行比较时,只需比较这些宿主数据的最高version,如果最高version相同说明这部分数据全部一致,否则再进行precise reconciliation。

5. Merkle tree
信息同步无疑是gossip的核心,Merkle tree(MT)是一个非常适合同步的数据结构。
简单来说 Merkle tree就是一颗hash树,在这棵树中,叶子节点的值是一些hash值、非叶节点的值均是由其子节点值计算hash得来的,这样,一旦某个文件被修改,修改时间的信息就会迅速传播到根目录。需要同步的系统只需要不断查询跟节点的hash,一旦有变化,顺着树状结构就能够在logN级 别的时间找到发生变化的内容,马上同步。
在Dynamo中,每个节点保存一个范围内的key值,不同节点间存在有相互交迭的key值范围。在去熵操作中,考虑的仅仅是某两个节点间共有的key值范围。MT的叶子节点即是这个共有的key值范围内每个key的hash,通过叶子节点的hash自底向上便可以构建出一颗MT。Dynamo首先比对MT根处的hash,如果一致则表示两者完全一致,否则将其子节点交换并继续比较的过程。

6.总结
Gossip常见于大规模、无中心的网络系统,可以用于众多能接受“最终一致性”的领域:失败检测、路由同步、Pub/Sub、动态负载均衡。

7.参考文献
paper: Efficient Reconciliation and Flow Control for Anti-Entropy Protocols
http://tianya23.blog.51cto.com/1081650/530743
http://ultimatearchitecture.net/index.php/2010/09/12/merkle-tree/

分享到:
评论

相关推荐

    Algorithm-Gossip.rar_gossip_gossip.rar_gossip算法

    通过阅读和学习这个压缩包中的内容,开发者可以了解如何在C语言环境中设计和实现gossip算法,从而在自己的项目中利用这种强大的分布式算法。无论是初学者还是经验丰富的程序员,都能从中受益,提升对分布式计算的...

    AlgorithmGossip 常用算法C/java实现

    总之,AlgorithmGossip是一个宝贵的资源,它将理论与实践相结合,帮助我们深入学习和掌握各种算法。无论你是准备参加编程竞赛,还是希望在工作中提升技能,这个压缩包都是一个不可多得的学习工具。

    电子政务-基于Gossip通信算法的微网电压不平衡补偿方法.zip

    Gossip算法在这种情境下起到了关键作用,因为它允许微网内的各个节点通过高效、可靠且去中心化的方式交换信息。 在Gossip通信算法中,每个节点随机与网络中的其他节点进行通信,分享和更新状态信息。这种通信模式...

    算法学习

    "算法学习"这个主题涵盖了广泛的理论和技术,旨在帮助我们理解和实现各种算法。在这个压缩包文件“AlgorithmGossip”中,我们可以期待找到与算法相关的深入讨论和实践案例。 源码部分通常包含了算法的具体实现,这...

    AlgorithmGossip数据结构精妙解法

    总结来说,《AlgorithmGossip数据结构精妙解法》是一个全面且实用的学习资源,它不仅介绍了数据结构的基本概念和操作,还通过实际的C和Java代码让学习者亲身体验算法的实现过程,这对于提升编程能力和解决实际问题的...

    Gossip-Learning-Framework:这个开源的基准测试框架允许您构建自己的P2P学习算法,并在模拟但现实的环境中对其进行评估-在此环境中,您可以建模消息延迟,丢弃或搅动-网络环境。 此外,它包含一些著名的机器学习算法(例如SVM和Logistic回归)的原型实现。

    这个开源的基准测试框架允许您构建自己的P2P学习算法,并在模拟但现实的环境中对其进行评估-在此环境中,您可以建模消息延迟,丢弃或搅动-网络环境。 此外,它包含一些著名的机器学习算法(例如SVM和Logistic回归)...

    CSC-582-3-W15-GOSSIP:分布式八卦算法

    - **Gossip算法类(GossipAlgorithm)**:实现了Gossip协议的具体逻辑,包括选择通信伙伴、更新本地状态等。 - **事件驱动(Event-driven)**:通常使用异步事件处理模型来处理节点间的通信,以提高性能。 在"CSC-...

    算法集合——拓展思路、随时查看的好资料

    这个"AlgorithmGossip"集合,无疑是算法学习者的宝典。通过深入研究这些经典算法,我们可以提升编程技巧,增强问题解决能力,同时也能激发创新思维,设计出更高效、更智能的解决方案。无论你是初学者还是经验丰富的...

    java中的经典算法经典算法

    在"AlgorithmGossip"这个压缩包中,可能包含了这些算法的Java实现代码、示例和解释,对于学习和提升Java算法能力非常有价值。深入理解和掌握这些算法,不仅可以提升编程技巧,还能帮助解决实际问题,提升工作效率。...

    良葛格Gossip_struts_spring_hibernate

    9. **AlgorithmGossip**:算法是编程的基础,这个文件名可能包含了算法的讨论或者教程,对于提升编程能力和解决问题的效率非常重要。 这些资源对于想要深入学习Java EE技术栈,特别是Spring框架的开发者来说是非常...

    算法大全(中文版)

    综上所述,《算法大全(中文版)》这本书涵盖了广泛的算法知识,从简单的排序算法到高级的图论算法,以及概率算法、动态规划等,为读者提供了一个全面而深入的学习资源。无论是初学者还是专业人士,都能从中找到适合...

    AlgorithmGossip

    "AlgorithmGossip"这一资源集合,聚焦于常用算法的分析及其C和Java语言的实现,为学习和理解算法提供了宝贵的材料。 1. **排序算法**: - **冒泡排序**:通过重复遍历待排序的序列,依次比较并交换相邻元素,使得...

    大学算法课程设计相关算法C,Java版解答

    以上只是部分可能包含在"AlgorithmGossip"文件中的内容,实际的解答可能会涉及更多具体算法的实现细节和优化技巧。学习和理解这些算法,不仅能提升编程能力,还能培养解决复杂问题的逻辑思维。对于IT专业的学生和...

    各种常用的算法,wiki

    "AlgorithmGossip"可能包含这些算法的详细解释、伪代码和实例,帮助学习者理解和掌握这些基本概念。通过深入学习和实践,这些算法能够提升编程能力,解决复杂问题,并在软件开发中发挥重要作用。

    算法设计与分析中国科大研究生ppt

    这部分可能会讲解如何在分布式环境下设计和实现算法,比如Paxos协议、Gossip协议或者MapReduce模型,这些都是现代大数据处理和云计算中的关键算法。 第三部分,"分布式算ch4.ppt",可能详细阐述了分布式计算的一些...

    分布式操作系统算法Demo

    这不仅有助于学习者深入理解分布式操作系统的内在机制,也为开发者提供了实际应用这些算法的平台,从而在实际项目中更好地解决分布式环境中的问题。无论是对于学术研究还是工业实践,这样的Demo都是非常有价值的资源...

    改变未来的9大算法

    最后,分布式计算算法,如MapReduce和Gossip协议,是处理大规模数据和构建容错系统的关键,它们在云计算和大数据处理中发挥着重要作用。 以上九类算法共同构成了信息技术的基石,不断推动着科技的发展,改变了我们...

Global site tag (gtag.js) - Google Analytics