文档章节

[转]分布式基础通信协议:paxos,totem和gossip

强子1985
 强子1985
发布于 2016/10/06 20:03
字数 1635
阅读 78
收藏 2

背景

在分布式中,最难解决的一个问题就是多个节点间数据同步问题。为了解决这样的问题,涌现出了各种奇思妙想。只有在解决了如何进行信息同步的基础之上才衍生出形形色色的应用。这里开始介绍几种分布式通信协议。

简单即有效——totem协议:

totem协议也许你还比较陌生,但是corosync就是totem协议的一个开源实现。比较火的HA软件pacemaker就是基于corosync来提供各种服务的。说起totem协议,最简单的形象就是,他将多个节点组成一个令牌环。多个节点手拉手形成一个圈,大家依次的传递token。只有获取到token的节点才有发送消息的权利。简单有效的解决了在分布式系统中各个节点的同步问题,因为只有一个节点会在一个时刻发送消息,不会出现冲突。当然,如果有节点发生意外时,令牌环就会断掉,此时大家不能够通信,而是重新组建出一个新的令牌环。

进化的二段提交——paxos协议:

说起paxos,需要稍微提提二段提交。简单来说,二阶段提交就是1.一个节点询问其他节点,我是不是可以进行消息提交。2.如果收到所有人的同意,则告诉大家,开始提交吧。这个协议在实际中并不能很好的解决分布式中信息同步问题。例如只要有节点失效,就会发生得不到所有人同意的结果,在超时后,这一次提交失败,等一系列问题。但是paxos在对二段提交进行了优化后,得到了一个比较好的解决办法。 paxos协议引入了多数派,以及消息编号的概念。在1准备时,询问2/n+1的参与者,要求他们保证不会接受小于编号n的提交。 2.如果得到了2/n+1的回复,则可以开始告诉2/n+1的参与者进行消息的提交。 可以明显的看出,这就是对二段提交的一个优化版。就是这么一个比较巧妙的思想,解决了一些二阶段提交带来的问题。 顺便说一句,这个协议的作者Leslie Lamport。他刚刚获得2013年图灵奖。

 

奇思妙想——gossip协议:

gossip协议是一个神奇的协议。它常用于P2P的通信协议,这个协议就是模拟人类中传播谣言的行为而来。简单的描述下这个协议,首先要传播谣言就要有种子节点。种子节点每秒都会随机向其他节点发送自己所拥有的节点列表,以及需要传播的消息。任何新加入的节点,就在这种传播方式下很快地被全网所知道。这个协议的神奇就在于它从设计开始就没想到信息一定要传递给所有的节点,但是随着时间的增长,在最终的某一时刻,全网会得到相同的信息。当然这个时刻可能仅仅存在于理论,永远不可达。

基础协议的对比:

简单的介绍了这几种协议,下面我们来看看他们的对比:

基础协议 paxos totem gossip
数据同步 第一阶段: proposer 选择一个提案编号 n 并将 prepare 请求发送给acceptors 中的一个多数派;acceptor 收到 prepare 消息后,如果提案的编号大于它已经回复的所有 prepare 消息,则 acceptor 将自己上次的批准回复给 proposer并承诺不再批准小于 n 的提案。 第二阶段: 当一个 proposor 收到了多数 acceptors 对 prepare 的回复后,就进入批准阶段。它要向回复 prepare 请求的acceptors 发送 accept 请求,包括编号 n 和根据 P2c 决定的 value(如果根据 P2c 没有决定 value,那么它可以自由决定 value)。在不违背自己向其他 proposer 的承诺的前提下,acceptor 收到 accept 请求后即批准这个请求。 1.通信方式。 当集群有节点要发起通信时,需要等待token。当拿到token后,先广播这次需要发送的数据,然后传递token来确认所有人都接收到消息。 如果确认成功,释放token。2.节点的加入和退出。 当集群中有节点加入时,加入的节点广播一个加入信息,所有人都开始广播自己的信息,当所有人都获得同伴信息,开始由id最小的人提交一个token,交由所有节点确认。 如果都确认后,则节点正式加入,开始正常运行。 当集群有节点退出时,由于令牌环断链,触发token超时,则同样开始广播信息,然后由最小id提交token,经过确认后恢复正常。 gossip协议有多种实现,这里说一个例子当节点启动时,读配置文件,然后向一个seed发送信息,进行信息同步,然后开始没秒都随机选择一个seed节点来同步信息1、随机取一个当前活着的节点,并向它发送同步请求 2、向随机一台不可达的机器发送同步请求 3、如果第一步中所选择的节点不是seed,或者当前活着的节点数少于seed数,则向随意一台seed发送同步请求
数据一致性 强一致性 强一致性 最终一致性
相关应用 zookeeper corosync Cassandra
优点 可以很好的解决通信一致性问题,在集群规模上比corosync要略大一些 简单方便,按照协议实现后就可以直接使用 协议本身简单,组网规模几乎不受限制,通信性能好
缺点 理论性太强,如果要实际使用,还是需要进行优化 使用了广播包,对于跨域传送有影响,而且令牌环本身带来的问题使得组网规模不大 不能提供传统的数据一致性服务,在传输中占用较多的网络流量

原文链接: http://openstack.wiaapp.com/?p=106

© 著作权归作者所有

共有 人打赏支持
强子1985

强子1985

粉丝 866
博文 1002
码字总数 681491
作品 8
南京
架构师
加载中

评论(1)

靖先生
靖先生
Cassandra国内唯一一个社区。 innosql.cn
强一致、高可用、自动容灾能力背后,阿里X-Paxos的应用实践

axos(分布式一致性算法)作为分布式系统的基石,一直都是计算机系统工程领域的热门话题。Paxos 号称是最难理解的算法,其实当真这么困难么? X-Paxos 是阿里巴巴数据库团队面向高性能、全球部署...

雪夜凋零
2017/08/08
0
0
Java 版的 Gossip 协议实现--jgossip

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

采芹人
2017/08/01
334
0
consul(一)什么是consul

Consul是一个用来实现分布式系统的服务发现与配置的开源工具。他主要由多个组成部分: 服务发现:客户端通过Consul提供服务,类似于API,MySQL,或者其他客户端可以使用Consul发现服务的提供者...

漫然
06/22
0
0
Windows 下安装使用 Consul

介绍 Consul 是一个支持多数据中心分布式高可用的服务发现和配置共享的服务软件, 由 HashiCorp 公司用 Go 语言开发, 基于 Mozilla Public License 2.0 的协议进行开源。Consul 支持健康检查,...

Adairs
01/11
0
0
《BIG DATA大数据日知录 架构和算法》读书笔记

1.数据分片和路由 Hash Hash H(Key) = hash(key) mod K 虚拟桶(Virtual Buckets) 先hash到桶,在Hash,多加一层Hash便于扩展 一致性Hash 分布式Hash表(DHT),P2P对等网络,构成环,节点加...

selfless
2016/06/18
163
4

没有更多内容

加载失败,请刷新页面

加载更多

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
今天
51
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
45
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
50
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
48
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
50
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部