Gossip protocol

概述

流言协议是一种计算机对计算机的沟通协议(该协议的灵感来源于社会网络中的“八卦”)。在现代的分布式系统中,通常使用流言协议来解决其它方式难以解决的问题,比如:底层的网络结构非常复杂,或者流言协议是最有效的解决方案等。
流行病协议有时被当做流言协议的同义词,因为流言协议传播信息的方式与生物群落中病毒的传播方式相似。


流言协议

流言协议的概念可以类比为办公室工作人员散播传闻。假设每小时办公室工作人员都在饮水机周围聚集,每个雇员都随机地和另外一个人结成一对,然后分享最新的传闻。最开始的时候,Alice开始传播一个新的传闻,她告诉Bob:Charlie染胡子了。在下次会议的时候,Bob把这个传闻告诉了Dave,而Alice又把这个传闻告诉了eva。在每次饮水机会议之后,听说传闻的人数都大致会翻倍。计算机系统通常以随机的“节点选择”的形式,实现gossip协议:在一个指定的频率下,每台机器都随机的选取另外一台机器,并与之分享信息。
流言的力量在于强大的信息传播能力。即使Dave误解了Bob,他可能很快就与其他人交流信息。
流言协议满足下面的条件:

  • 协议的核心涉及到周期性,配对,进程间交互
  • 交互期间,交换的消息的大小是有限的
  • 客户端之间的通讯可以不可靠
  • 与典型的消息延迟相比,客户端之间的交互的频率很低,以便协议的消耗是可以忽略不计的
  • 在节点选择的过程中,有某种形式的随机性。节点可能从全部的节点中选择,也可能从相邻的节点中选择
  • 因为信息的复制,信息应该被冗余投递

流言协议的类型

流言协议是一种复制没有强一致性需求的状态的方式,即使在通讯失败或消息丢失的情形下,更新也可以在期望的时间内传播。
有两种类型的gossip:anti-entropyrumor-mongering
每个节点维护一组状态,状态可以用一个key/value对表示,还会附带一个版本号,版本号大的为更新的状态。
消息的处理有3种方式:

Push-gossip A节点将状态集合发送到B,B通过和本地的状态集合比较,返回 S(A)和S(B)的笛卡尔积
Pull-gossip A发送一个摘要(digest,只包含key和version)给 B,B通过比较,仅仅返回A上需要更新的状态
Push-pull-gossip 这种方式和pull-gossip一样,在B发送给A其需要更新的 状态的同时,会向A请求本地过期的状态

gossip的例子

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: