Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢?
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。
理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。
学习Paxos算法有两部分:a) 算法的原理/证明;b) 算法的理解/运作。
理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得多。
网上我觉得讲Paxos讲的好的属于这篇:paxos图解及Paxos算法详解,我这里就结合wiki上的实例进一步阐述。一些paxos基础通过这里提到的两篇文章,以及wiki上的内容基本可以理解。
算法内容
Paxos在原作者的《Paxos Made Simple》中内容是比较精简的:
Phase 1
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.
Phase 2
(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
借用paxos图解文中的流程图可概括为:
实例及详解
Paxos中有三类角色Proposer
、Acceptor
及Learner
,主要交互过程在Proposer
和Acceptor
之间。
Proposer
与Acceptor
之间的交互主要有4类消息通信,如下图:
这4类消息对应于paxos算法的两个阶段4个过程:
- phase 1
- a) proposer向网络内超过半数的acceptor发送prepare消息
- b) acceptor正常情况下回复promise消息
- phase 2
- a) 在有足够多acceptor回复promise消息时,proposer发送accept消息
- b) 正常情况下acceptor回复accepted消息
因为在整个过程中可能有其他proposer针对同一件事情发出以上请求,所以在每个过程中都会有些特殊情况处理,这也是为了达成一致性所做的事情。如果在整个过程中没有其他proposer来竞争,那么这个操作的结果就是确定无异议的。但是如果有其他proposer的话,情况就不一样了。
以paxos中文wiki上的例子为例。简单来说该例子以若干个*提议税收,确定最终通过的法案税收比例。
以下图中基本只画出proposer与一个acceptor的交互。时间标志T2总是在T1后面。propose number简称N。
情况之一如下图:
A3在T1发出accepted给A1,然后在T2收到A5的prepare,在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况:
- A5发来的N5小于A1发出去的N1,那么A3直接拒绝(reject)A5
- A5发来的N5大于A1发出去的N1,那么A3回复promise,但带上A1的(N1, 10%)
这里可以与paxos流程图对应起来,更好理解。acceptor会记录(MaxN, AcceptN, AcceptV)。
A5在收到promise后,后续的流程可以顺利进行。但是发出accept时,因为收到了(AcceptN, AcceptV),所以会取最大的AcceptN对应的AcceptV,例子中也就是A1的10%作为AcceptV。如果在收到promise时没有发现有其他已记录的AcceptV,则其值可以由自己决定。
针对以上A1和A5冲突的情况,最终A1和A5都会广播接受的值为10%。
其实4个过程中对于acceptor而言,在回复promise和accepted时由于都可能因为其他proposer的介入而导致特殊处理。所以基本上看在这两个时间点收到其他proposer的请求时就可以了解整个算法了。例如在回复promise时则可能因为proposer发来的N不够大而reject:
如果在发accepted消息时,对其他更大N的proposer发出过promise,那么也会reject该proposer发出的accept,如图:
这个对应于Phase 2 b):
it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
总结
Leslie Lamport没有用数学描述Paxos,但是他用英文阐述得很清晰。将Paxos的两个Phase的内容理解清楚,整个算法过程还是不复杂的。
至于Paxos中一直提到的一个全局唯一且递增的proposer number,其如何实现,引用如下:
如何产生唯一的编号呢?在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择,例如系统有5个Proposer,则可为每一个Proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)
参考文档
- paxos图解, http://coderxy.com/archives/121
- Paxos算法详解, http://coderxy.com/archives/136
- Paxos算法 wiki, http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95#.E5.AE.9E.E4.BE.8B
图解分布式一致性协议Paxos的更多相关文章
-
[转帖]图解分布式一致性协议Paxos
图解分布式一致性协议Paxos https://www.cnblogs.com/hugb/p/8955505.html Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分 ...
-
[转]图解分布式一致性协议Paxos
Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者MikeBurrows说过这个世界上只有一种一致性算法,那就是 ...
-
分布式一致性协议 --- Paxos
问题 Paxos 到底解决什么样的问题,动机是什么 Paxos 流程是怎么样的? Paxos 算法的缺陷是什么 概述 Paxos 是分布式一致性算法,根据少数服从多数的原则多个节点确定某个数值.通过学 ...
-
[从Paxos到ZooKeeper][分布式一致性原理与实践]<;二>;一致性协议[Paxos算法]
Overview 在<一>有介绍到,一个分布式系统的架构设计,往往会在系统的可用性和数据一致性之间进行反复的权衡,于是产生了一系列的一致性协议. 为解决分布式一致性问题,在长期的探索过程中 ...
-
搞懂分布式技术2:分布式一致性协议与Paxos,Raft算法
搞懂分布式技术2:分布式一致性协议与Paxos,Raft算法 2PC 由于BASE理论需要在一致性和可用性方面做出权衡,因此涌现了很多关于一致性的算法和协议.其中比较著名的有二阶提交协议(2 Phas ...
-
[转帖]分布式一致性协议介绍(Paxos、Raft)
分布式一致性协议介绍(Paxos.Raft) https://www.cnblogs.com/hugb/p/8955505.html 两阶段提交 Two-phase Commit(2PC):保证一个 ...
-
使用GO实现Paxos分布式一致性协议
什么是Paxos分布式一致性协议 最初的服务往往都是通过单体架构对外提供的,即单Server-单Database模式.随着业务的不断扩展,用户和请求数都在不断上升,如何应对大量的请求就成了每个服务都需 ...
-
分布式一致性协议Raft原理与实例
分布式一致性协议Raft原理与实例 1.Raft协议 1.1 Raft简介 Raft是由Stanford提出的一种更易理解的一致性算法,意在取代目前广为使用的Paxos算法.目前,在各种主流语言中都有 ...
-
Zookeeper——分布式一致性协议及Zookeeper Leader选举原理
文章目录 一.引言 二.从ACID到CAP/BASE 三.分布式一致性协议 1. 2PC和3PC 2PC 发起事务请求 事务提交/回滚 3PC canCommit preCommit doCommit ...
随机推荐
-
excel 作图中次横坐标及次纵坐标的调试,以及excel自定义轴标签的步骤方法
在工作中除了要做一些常用的图表之外,不时还会有一切奇怪图表的制作需求. 今天的内容主要记录的是如何对excle图表的次横坐标及次纵坐标进行调试,以及如何自定义调整轴标签 首先看下如何做次纵坐标,工作中 ...
-
java学习第10天 (增加关于eclipse添项目)
自己遇到一个问题..觉得有必要说下,就是如何将别人发给你的文件也就是项目如何导入到你的eclipse中,不是直接add那么简单,首先右键找到import,找到general,展开找到existing ...
-
使用go的ssh包快速打造一个本地命令行ssh客户端
热身运动
-
JAVA对象是如何占用内存的
本文使用的是32位的JVM ,jdk1.6.本文基本是翻译的,加上了一些自己的理解,原文见文章底下链接. 在本文中,我们讨论如何计算或者估计一个JAVA对象占多少内存空间.(注意,使用 C ...
-
PHP signal 信号
最早写php时,发现在终端执行一个php文件,会一直等待程序执行完成以后,终端才能继续下面的操作,若不小心按了下Ctrl+C会导致php程序退出,闭避免这种情况发生,将会使用php的系统编程,即sig ...
-
python使用环境的设置
virtualenv usage mkidr ~/pyenv cd ~/pyenv virtualenv pycaffe #it will setup a new python environtmen ...
-
javascript语法之for-in语句
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
webpack4.0各个击破(9)—— karma篇
webpack作为前端最火的构建工具,是前端自动化工具链最重要的部分,使用门槛较高.本系列是笔者自己的学习记录,比较基础,希望通过问题 + 解决方式的模式,以前端构建中遇到的具体需求为出发点,学习we ...
-
page0902未完成
/** * @author:(LiberHome) * @date:Created in 2019/3/1 23:14 * @description: * @version:$ */ import j ...
-
爬虫万金油,一鹅在手,抓遍全球:goose 简介!
GOOSE 现已弃用 经过多年的服务,GOOSE接口和支持它的MySQL数据现已弃用 . 在我们进行替换的同时,我们建议寻找一般查询功能的用户在http://rdf.geneontology.org上 ...