Gossip协议理解

概述

Gossip协议,又称epidemic协议,基于流行病传播方式的节点或进程之间信息交换的协议,在分布式系统中被广泛使用。

在1987年8月由施乐-帕洛阿尔托研究中心发表ACM上的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出。原本用于分布式数据库中节点同步数据使用,后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。

六度分隔理论(Six Degrees of Separation):一个人通过6个中间人可以认识世界任何人。数学公式: n = l o g ( N ) l o g ( W ) n=\frac{log(N)}{log(W)} n=log(W)log(N)n表示复杂度,N表示人的总数,W表示每个人的联系宽度。依据邓巴数,即一个人认识150人,其六度就是 15 0 6 150^6 1506=11,390,625,000,000(约11.4万亿)。

基于六度分隔理论,任何信息的传播其实非常迅速,且网络交互次数不会很多。

过程

Gossip协议利用一种随机的方式将信息传播到整个网络中,并在一定时间内使得系统内的所有节点数据一致。一种去中心化思路的分布式协议,解决状态在集群中的传播和状态一致性的保证两个问题。

Gossip协议执行过程:

  • 种子节点周期性的散播消息【假定把周期限定为1秒】
  • 被感染节点随机选择N个邻接节点散播消息【假定fan-out(扇出)设置为6,每次最多往6个节点散播】
  • 节点只接收消息不反馈结果
  • 每次散播消息都选择尚未发送过的节点进行散播
  • 收到消息的节点不再往发送节点散播:A->B,则B进行散播时,不再发给A。

Goosip协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间,由于不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,因此它是一个最终一致性协议。

Gossip协议是一个多主协议,所有写操作可以由不同节点发起,并且同步给其他副本。Gossip内组成的网络节点都是对等节点,是非结构化网络。

应用场景

Gossip协议可以支持以下需求:

  • Database Replication
  • 消息传播
  • Cluster Membership
  • Failure 检测
  • Overlay Networks
  • Aggregations(如计算平均值、最大值以及总和)

使用Gossip协议的技术组件或框架:

  • Riak:使用Gossip协议来共享和传递集群的环状态(ring state)和存储桶属性(bucket properties)
  • Cassandra:节点间的信息交换使用Gossip协议,所有节点都可以快速了解集群中的所有其他节点
  • Dynamo:基于Gossip协议的分布式故障检测和成员协议,这样集群中添加或移除节点,其他节点可以快速检测到
  • Consul:使用称为SERF的Gossip协议,主要有两个目的:1、发现新节点或故障节点;2、为一些重要的事件(如Leader选举)传播提供可靠快速的传播
  • Amazon S3:使用Gossip协议将服务的状态传递给系统
  • Redis Cluster:
  • Zeppelin:

类型

消息传播方式有两种:

  • Anti-Entropy(反熵):以固定的概率传播所有的数据
  • Rumor-Mongering(谣言传播):仅传播新到达的数据

一般来说,为了在通信代价和可靠性之间取得折中,需要将这两种方法结合使用。

Anti-Entropy

反熵传播是以固定的概率传播所有的数据。所有参与节点只有两种状态:Suspective(病原)、Infective(感染)。这种模型叫做simple epidemics,SI model。处于infective状态的节点代表其有数据更新,并且会将这个数据分享给其他节点;处于susceptible状态的节点代表其并没有收到来自其他节点的更新。

种子节点会把所有的数据都跟其他节点共享,以便消除节点之间数据的任何不一致,它可以保证最终、完全的一致。缺点是消息数量非常庞大,且无限制;通常只用于新加入节点的数据初始化。

每个节点周期性地随机选择其他节点,然后通过互相交换自己的所有数据来消除两者之间的差异。这种方法非常可靠,但是每次节点两两交换自己的所有数据会带来非常大的通信负担,因此不会频繁使用。

Rumor-Mongering

谣言传播是以固定的概率仅传播新到达的数据。所有参与节点有三种状态:Suspective(病原)、Infective(感染)、Removed(愈除)。这种模型叫做complex epidemics,SIR model。相比Anti-Entropy多一种状态:removed,处于removed状态的节点说明其已经接收到来自其他节点的更新,但是其并不会将这个更新分享给其他节点。

Rumor消息会在某个时间标记为removed,然后不会发送给其他节点,所以Rumor-Mongering类型的Gossip协议有极小概率使得更新不会达到所有节点。

消息只包含最新update,谣言消息在某个时间点之后会被标记为removed,并且不再被传播。缺点是系统有一定的概率会不一致,通常用于节点间数据增量同步。

当一个节点有新的信息后,这个节点变成活跃状态,并周期性地联系其他节点向其发送新信息。直到所有的节点都知道该新信息。因为节点之间只是交换新信息,所以大大减少通信的负担。

通讯方式

Anti-Entropy和Rumor-Mongering都涉及到节点间的数据交互方式,节点间的交互方式主要有三种:Push、Pull及Push&Pull。

  • Push:发起信息交换的节点A随机选择联系节点B,并向其发送自己的信息,节点B在收到信息后更新比自己新的数据,一般拥有新信息的节点才会作为发起节点。
  • Pull:发起信息交换的节点A随机选择联系节点B,并从对方获取信息。一般无新信息的节点才会作为发起节点。
  • Push&Pull:发起信息交换的节点A向选择的节点B发送信息,同时从对方获取数据,用于更新自己的本地数据。

如果把两个节点数据同步一次定义为一个周期,则在一个周期内,Push需通信1次,Pull需2次,Push/Pull则需3次。消息数增加,但从效果上来讲,Push/Pull最好,理论上一个周期内可以使两个节点完全一致。直观上,Push/Pull的收敛速度也是最快的。

优缺点

优点

  • 可扩展性(Scalable)
    Gossip协议是可扩展的,一般需要O(logN)轮就可以将信息传播到所有的节点,其中N代表节点的个数。每个节点仅发送固定数量的消息,并且与网络中节点数目无法。在数据传送的时候,节点并不会等待消息的ack,所以消息传送失败也没有关系,因为可以通过其他节点将消息传递给之前传送失败的节点。系统可以轻松扩展到数百万个进程。
  • 容错(Fault-tolerance)
    网络中任何节点的重启或宕机都不会影响Gossip协议的运行。
  • 去中心化(Decentralized)
    无中心节点,所有节点都是对等的,任意节点无需知道整个网络状况,只要网络连通,任意节点可把消息散播到全网;任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开,而不会影响系统的整体服务质量(QoS)
  • 最终一致性(Convergent Consistency)
    可实现信息指数级的快速传播,在有新信息需要传播时,消息可快速发送到全局节点,在有限时间内做到所有节点都拥有最新数据。

缺点

  • 消息延迟:节点随机向少数几个节点发送消息,消息最终是通过多个轮次的散播而到达全网;不可避免的造成消息延迟。
  • 消息冗余:节点定期随机选择周围节点发送消息,而收到消息的节点也会重复该步骤;不可避免的引起同一节点消息多次接收,增加消息处理压力。

由于以上优缺点,适合于AP场景的数据一致性处理,常见应用有:P2P网络通信、Apache Cassandra、Redis Cluster、Consul。

实现

Consul

Consul使用两种不同的Gossip池:

  • LAN池
    Consul中的每个数据中心有一个LAN池,包含这个数据中心的所有成员,包括clients和servers。LAN池有以下几个目的:
    • 成员关系信息允许client自动发现server,减少所需要的配置量
    • 分布式失败检测机制使得由整个集群来做失败检测这件事,而不是集中到几台机器上
    • 使得类似领导人选举这样的事件变得可靠且迅速
  • WAN池
    WAN池是全局唯一的,无论位于哪个数据中心的server都应该加入到WAN池中。由WAN池提供的成员关系信息允许server做一些跨数据中心的请求。一体化的失败检测机制允许Consul优雅地去处理:整个数据中心失去连接,或仅仅是别的数据中心的某一台失去连接。

Consul在gossip上的实现实际上是使用的memberlist库,其实现集群内节点发现、节点失效探测、节点故障转移、节点状态同步等。

节点状态有3种

  1. alive:存活的
  2. suspect:可疑的,对于PingMsg没有应答或应答超时
  3. dead:已死亡

Redis Cluster

Redis3.0版本加入Redis Cluster,主从架构的Redis Cluster架构图:
在这里插入图片描述
其中虚线表示各个节点之间的Gossip通信。

Gossip协议是个松散的协议,没有对数据交换的格式做特别的约束,各框架可自由设定实现机制。Redis Cluster有以下9种消息类型的定义,详情可见注释。

Dynamo

memberlist

memberlist是hashicorp开源的go语言实现版本,参考GitHub。

GitHub给出的README文档:

list, err := memberlist.Create(memberlist.DefaultLocalConfig())
if err != nil {panic("Failed to create memberlist: " + err.Error())
}
// Join an existing cluster by specifying at least one known member.
n, err := list.Join([]string{"1.2.3.4"})
if err != nil {panic("Failed to join cluster: " + err.Error())
}
// Ask for members of the cluster
for _, member := range list.Members() {fmt.Printf("Member: %s %s\n", member.Name, member.Addr)
}

与memberlist交互入口就是Config配置struct类,源码见链接。

这个类里面定义各种配置,如BindAddr、BindPort、AdvertiseAddr、AdvertisePort。同时基于Config,有3种实现类方便初始化一个Gossip集群:

  • DefaultLANConfig:局域网,基础类
  • DefaultWANConfig:广域网,基于DefaultLANConfig,调整一些参数
  • DefaultLocalConfig:本地网,基于DefaultLANConfig,调整一些参数

memberlist提供的功能主要分为两块:维护成员状态(gossip)及数据同步(boardcast、SendReliable)。

参考

  • 漫谈gossip协议与其在rediscluster中的实现

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/204759.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OpenStack云计算平台

目录 一、OpenStack 1、简介 2、硬件需求 3、网络 二、环境搭建 1、安全 2、主机网络 3、网络时间协议(NTP) 4、OpenStack包 5、SQL数据库 6、消息队列 7、Memcached 一、OpenStack 1、简介 官网:https://docs.openstack.org/2023.2/ OpenStack系统由…

RPA机器人如何解决非银企直联网银账户的数据自动采集?

数字时代来临,随着全球信息化水平的不断提升,企业们纷纷向自动化办公、数字化转型靠拢。财务部门作为一个企业的重要部门,承担着管理和监控公司所有项目的重要职责,因而一直被视为企业数字化转型的重要突破口。 由于企业经营理念和…

第二十章多线程

线程简介 java语言提供了并发机制,程序员可以在程序中执行多个线程,每一个线程完成一个功能,并与其他线程并发运行。 一个进程是一个包含有自身地址的程序,每个独立执行的程序都称为进程。也就是说每个正在执行的程序都是一个进程…

C语言错误处理之“非局部跳转<setjmp.h>头文件”

目录 前言 setjmp宏 longjmp函数 使用方法: 实例:测试setjmp与longjmp的使用 前言 通常情况下,函数会返回到它被调用的位置,我们无法使用goto语句改变它的返回的方向,因为goto语句只能跳转到同一函数内的某个标号…

python与机器学习1,机器学习的一些基础知识概述(完善ing)

目录 1 AI ,ML,DL,NN 等等概念分类 1.1 人工智能、机器学习、深度学习、神经网络之间的关系: 1.2 人工智能的发展 2 ML机器学习的分类:SL, USL,RL 2.1 机器学习的分类 2.2 具体的应用举例 2.3 数据分类 3 关于阈值θ和偏移量b的由来 4 不同的激…

中小型工厂如何进行数字化转型

随着科技的快速发展和市场竞争的日益激烈,中小型工厂面临着诸多挑战。为了提高生产效率、降低成本、优化资源配置,数字化转型已成为中小型工厂发展的必经之路。中小型工厂如何进行数字化转型呢? 一、明确数字化转型目标 在进行数字化转型之前…

【Linux下基本指令——(1)】

Linux下基本指令——(1) 一. ls 指令1.1.语法:1.2.功能:1.3.常用选项:1.4.举例:1.5.Xshell7展示 二. pwd 命令2.1.语法: 2.2.功能:2.3.常用选项:2.4.Xshell7展示 三. cd 指令3.1.语法…

0004Java程序设计-ssm基于微信小程序的校园第二课堂

文章目录 摘 要目录系统设计开发环境 编程技术交流、源码分享、模板分享、网课分享 企鹅🐧裙:776871563 摘 要 随着信息技术和网络技术的飞速发展,人类已进入全新信息化时代,传统管理技术已无法高效,便捷地管理信息。…

3D模型纹理集合并【Python|C#】

使用 Substance Painter 时,将模型的各个部分分成不同的纹理集非常有用。 这可以帮助遮罩,或者只是保持层栈干净。 不幸的是,Painter 无法将多个纹理集中的所有贴图导出为单个图集,即使在创建单独对象的 UV 时考虑到了这一点。 显…

SpringCloud实用-OpenFeign整合okHttp

文章目录 前言正文一、OkHttpFeignConfiguration 的启用1.1 分析配置类1.2 得出结论,需要增加配置1.3 调试 二、OkHttpFeignLoadBalancerConfiguration 的启用2.1 分析配置类2.2 得出结论2.3 测试 附录附1:本系列文章链接附2:OkHttpClient 增…

Spring Security 6.x 系列(6)—— 显式设置和修改登录态信息

一、前言 此篇是对上篇 Spring Security 6.x 系列(5)—— Servlet 认证体系结构介绍 中4.9章节显式调用SecurityContextRepository#saveContext进行详解分析。 二、设置和修改登录态 2.1 登录态存储形式 使用Spring Security框架,认证成功…

六、Lua运算符

文章目录 一、Lua 运算符(一)算术运算符(二)关系运算符(三)逻辑运算符(四)其他运算符 二、运算符优先级 一、Lua 运算符 运算符是一个特殊的符号,用于告诉解释器执行特定…

MSB3541 Files 的值“<<<<<<< HEAD”无效。路径中具有非法字符。

MSB3541 Files 的值“<<<<<<< HEAD”无效。路径中具有非法字符。 一般来说出现这个问题是因为使用git版本控制工具合并代码出现了问题&#xff0c;想要解决也很简单。 如图点击错误后定位到文件&#xff0c;发现也没有什么问题。 根据错误后边的提示&a…

P9242 [蓝桥杯 2023 省 B] 接龙数列(dp+最长接龙序列+分类)

1. 计算0~9为结尾的最长子串长度 2. 对于每个数字&#xff0c;比较其开头可连接子串长度1 与 原来以其末位为末尾的子串长度 3. 更新以其末位为末尾的子串长度 #include<iostream> #include<string.h>using namespace std;// 相当于记录…

如何运行C/C++程序

一、在线运行C/C 码曰 - 让代码在云端多飞一会&#xff1a;这是一个支持C/C&#xff0c;Java&#xff0c;Python等多种语言的在线编程&#xff0c;编译运行&#xff0c;粘贴分享的平台。你可以在这里输入你的代码&#xff0c;点击运行按钮&#xff0c;就可以看到输出结果。你也…

leetcode 283. 移动零

代码&#xff1a; class Solution {public void swap(int[] nums,int m,int n){int tmpnums[m];nums[m]nums[n];nums[n]tmp;}public void moveZeroes(int[] nums) {int cur0;int dest-1;int nnums.length;for(;cur<n;cur){if(nums[cur]!0){dest;swap(nums,cur,dest);}}} } …

一些好用的12款前端小插件

1. cropper.js Cropper.js 2.0 是一系列用于图像裁剪的 Web 组件。 官网地址&#xff1a;https://fengyuanchen.github.io/cropperjs/v2/zh/ 2. Vditor Vditor是一款浏览器端的 Markdown 编辑器&#xff0c;支持所见即所得、即时渲染&#xff08;类似 Typora&#xff09;和分…

【Python深度学习第二版】学习笔记之——什么是深度学习

机器学习是将输入&#xff08;比如图像&#xff09;映射到目标&#xff08;比如标签“猫”&#xff09;的过程。 这一过程是通过观察许多输入和目标的示例来完成的。 深度神经网络通过一系列简单的数据变换&#xff08;层&#xff09;来实现这种输入到目标的映射&#xff0c;这…

C++ day42背包理论基础01 + 滚动数组

背包问题的重中之重是01背包 01背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 每一件物品其实只有两个状态&#xff0c;取或者不…

抖音视频如何无水印下载,怎么批量保存主页所有视频没水印?

现在最火的短视频平台莫过于抖音&#xff0c;当我们刷到一个视频想下载下来怎么办&#xff1f;我们知道可以通过保存到相册的方式下载&#xff0c;但用这种方法下载的视频带有水印&#xff0c;而且有些视频不能保存到相册&#xff08;这是视频作者设置了禁止下载&#xff09;。…