文档章节

图解 Paxos 一致性协议

openthings
 openthings
发布于 02/02 10:32
字数 1026
阅读 44
收藏 1

参考:

前言

Paxos 一致性协议可以说是一致性协议研究的起点,也以难以理解闻名。其实协议本身并没有多难理解,它的难理解性主要体现在:为何如此设计协议以及如何证明其正确性。本文尝试通过流程图来说明协议的内容以及基本应用过程,不涉及如何证明其正确性。

基本概念

Paxos 可以分为两种:

  • Single-Decree Paxos:决策单个 Value
  • Multi-Paxos:连续决策多个 Value,并且保证每个节点上的顺序完全一致,多 Paxos 往往是同事运行多个单 Paxos 协议共同执行的结果。

本文只关注单 Paxos 的原理,理解了单 Paxos,多 Paxos 也就不难理解了。

Paxos 协议中的三种角色

  • 倡议者(Proposer):倡议者可以提出提议(数值或者操作命令)以供投票表决
  • 接受者(Acceptor):接受者可以对倡议者提出的提议进行投票表决,提议有超半数的接受者投票即被选中
  • 学习者(Learner):学习者无投票权,只是从接受者那里获知哪个提议被选中

在协议中,每个节点可以同时扮演以上多个角色。

Paxos 的特点

  • 一个或多个节点可以提出提议
  • 系统必须针对所有提案中的某个提案达成一致(超过半数的接受者选中)
  • 最多只能对一个确定的提议达成一致
  • 只要超半数的节点存活且可互相通信,整个系统一定能达成一致状态,即选择一个确定的提议

协议图示

PaxosPaxos
通过上面的流程,如果有多个节点同时提出各自的提议,Paxos 就可以保证从中选出一个唯一确定的值,保证分布式系统的一致性。

实例

下面我们通过例子来理解 Paxos 的实际应用过程。

假设现在有五个节点的分布式系统,此时 A 节点打算提议 X 值,E 节点打算提议 Y 值,其他节点没有提议。
Paxos-1Paxos-1

假设现在 A 节点广播它的提议(也会发送给自己),由于网络延迟的原因,只有 A,B,C 节点收到了。注意即使 A,E 节点的提议同时到达某个节点,它也必然有个先后处理的顺序,这里的“同时”不是真正意义上的“同时”。
Paxos-2Paxos-2

A,B,C接收提议之后,由于这是第一个它们接收到的提议,acceptedProposal 和 acceptedValue 都为空。
Paxos-3Paxos-3

由于 A 节点已经收到超半数的节点响应,且返回的 acceptedValue 都为空,也就是说它可以用 X 作为提议的值来发生 Accept 请求,A,B,C接收到请求之后,将 acceptedValue 更新为 X。
Paxos-4Paxos-4

A,B,C 会发生 minProposal 给 A,A 检查发现没有大于 1 的 minProposal 出现,此时 X 已经被选中。等等,我们是不是忘了D,E节点?它们的 acceptedValue 并不是 X,系统还处于不一致状态。至此,Paxos 过程还没有结束,我们继续看。
Paxos-5Paxos-5

此时 E 节点选择 Proposal ID 为 2 发送 Prepare 请求,结果就和上面不一样了,因为 C 节点已经接受了 A 节点的提议,它不会三心二意,所以就告诉 E 节点它的选择,E 节点也很绅士,既然 C 选择了 A 的提议,那我也选它吧。于是,E 发起 Accept 请求,使用 X 作为提议值,至此,整个分布式系统达成了一致,大家都选择了 X。
Paxos-6Paxos-6

上面是 Paxos 的一个简单应用过程,其他复杂的场景也可以根据流程图慢慢推导,这里只是抛砖引玉。

本文转载自:http://blog.xiaohansong.com/2016/09/30/Paxos/

共有 人打赏支持
openthings
粉丝 271
博文 1004
码字总数 540756
作品 1
东城
架构师
私信 提问
图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残...

wangdy
2016/06/22
15
0
从分布式一致性到共识机制(一)Paxos算法

从分布式系统的CAP理论出发,关注分布式一致性,以及区块链的共识问题及解决。 区块链首先是一个大规模分布式系统,共识问题本质就是分布式系统的一致性问题,但是又有很大的不同。 工程开发...

邴越
03/25
0
0
博客阅读整理一

(部分文章是系列文章,可在原文博客查找) Java ClassLoader, JavaAgent, Aspectj Weaving一站式扫盲帖:主要总结了ClassLoader、java代理、反射相关的知识点 jdbc实现篇-源码:介绍了jdbc的源...

oO脾气不坏Oo
2015/10/17
80
0
Paxos算法浅析

前言 在文章2PC/3PC到底是啥中介绍了2PC这种一致性协议,从文中了解到2PC更多的被用在了状态一致性上(分布式事务),在数据一致性中很少被使用;而Paxos正是在数据一致性中被广泛使用,在过去...

ksfzhaohui
2016/12/17
3.1K
1
ZAB协议和Paxos算法

前言 在上一篇文章Paxos算法浅析中主要介绍了Paxos一致性算法应用的场景,以及对协议本身的介绍;Google Chubby是一个分布式锁服务,其底层一致性实现就是以Paxos算法为基础的;但这篇文件并...

ksfzhaohui
2016/12/27
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL 索引 explain索引分析优化

EXPLAIN是MySQL提供的工具,可用于模拟优化器执行SQL查询语句,从而知道MySQL是如何处理SQL语句的,包括表的读取顺序、数据读取操作的操作类型、可能使用的索引、实际使用的索引、表之间的引...

PeakFang-BOK
3分钟前
0
0
17-《深度拆解JVM》之即时编译(上)

一、问题引入 在第一篇中,我们简单了解过即时编译。这是一项用来提升应用程序运行效率的技术。通常而言,代码会先被 Java 虚拟机解释执行,之后反复执行的热点代码则会被即时编译成为机器码...

飞鱼说编程
3分钟前
0
0
OSChina 周二乱弹 —— 请上车吧

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @2amor :分享王菲的单曲《闷》 《闷》- 王菲 手机党少年们想听歌,请使劲儿戳(这里) @開源中國周杰倫 :昨天睡觉肚子疼,妈蛋,半夜爬起来...

小小编辑
53分钟前
432
9
工作中如何做好技术积累

参考:https://tech.meituan.com/study_vs_work.html 看了这篇文章,觉得总结得非常好,因此摘抄了一些关键点,以便自己经常翻阅。 引言 在繁忙的工作中做好技术积累,构建个人核心竞争力. 在...

grace_233
今天
8
0
Mariadb二进制包安装,Apache安装

安装mariadb 下载二进制包并解压 [root@test-a src]# wget https://downloads.mariadb.com/MariaDB/mariadb-10.2.6/bintar-linux-glibc_214-x86_64/mariadb-10.2.6-linux-glibc_214-x86_64.t......

野雪球
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部