1. 概述
Paxos协议是一个解决分布式系统中,多个节点之间就某个值(提案)达成一致(决议)的通信协议。它能够处理在少数节点离线的情况下,剩余的多数节点仍然能够达成一致。
Paxos协议是一个两阶段协议,分为Prepare阶段和Accept阶段,涉及三个参与者角色:Proposers、Acceptors和Learners。Proposers提出提案,提案信息包括提案编号和提议的 value;Acceptors 收到提案后可以接受(accept)提案,若提案获得多数 acceptors 的接受,则称该提案被批准(chosen);Learners 只能“学习”被批准的提案。
2. Prepare阶段
- Prepare阶段1:Proposer发送Prepare请求
Proposer生成全局唯一且递增的提案ID,并向Paxos集群的所有机器发送请求,这里只需携带提案ID即可,无需携带提案内容(暂且把提案ID叫做Pn)。
- Prepare阶段2:Acceptor应答Prepare请求
Acceptor收到Prepare请求后,做出以下约定:
- 不再应答 <=Pn 的Prepare请求
- 对于 < Pn 的Accept请求也不处理
Acceptor对于Prepare请求,做以下处理:
- 应答前要在本地持久化当前提案ID(Pn)
- 如果现在请求的提案ID(Pn)大于此前存放的proposalID,则做以下逻辑:
if Pn > proposalID then proposalID = Pn
如果该Acceptor Accept过提案,则返回提案中proposalID最大的那个提案的内容,否则返回空值。
3. Accept阶段
- Accept阶段1:Proposer发送Accept请求
Proposer收集到多数派应答(多数派是指超过 n/2 + 1,n是集群数)Prepare阶段的返回值后,从中选择proposalID最大的提案内容,作为要发起Accept的提案,如果这个提案为空值,则可以自己随意决定提案内容。然后携带上当前proposalID,想Paxos集群的所有机器发送Accept请求。
- Accept阶段2:Acceptor应答Accept请求
Acceptor收到Accept请求后,检查不违背约定(上述约定①、②)的情况下,持久化当前proposalID和提案内容,最后Proposer收集到多数派应答的Accept回复后,形成决议。
4. 思考
Prepare阶段与Accept阶段是并行(即不同提案的Prepare和Accept请求并行执行)、持续的(在最终决议产生前,流程不会终止):
比方说ProposerA生成一个提案P0,发送Prepare请求到所有的Acceptor,Acceptor在本地持久化当前提案ID,并向ProposerA应答,此时Acceptor处理的提案为P0。(如果同时有多个提案发送到Acceptor且先接收到提案Pn,则后续接收到的小于Pn的提案会被忽略。若P0提案的Prepare请求应答没有达到多数派,则P0提案作废,流程继续)
ProposerA如果接收到多数派的对提案P0的Prepare请求应答,则向Acceptor发送Accept请求并带上PO对应的ID,如果多数派Acceptor应答了该Accept请求,则形成决议。(如果Acceptor在应答PO提案的Prepare请求后,在应答P0提案的Accept请求之前继续应答其他大于P0的提案,则忽略对P0提案的Accept请求的应答。若提案P0的Accept请求应答没达到多数派,则P0提案作废,流程继续)
相关推荐
voguedb是Paxos一致性算法的生产级高性能Java实现,支持多分组,可用于解决高并发、高可靠分布式系统中多副本数据一致性问题以及分布式共识问题。针对一些网络分区、机器宕机、进程异常(OOM、卡顿、强制关闭)等...
#资源达人分享计划#
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
磁盘阵列,CAP原则,数据的一致性,Paxos算法,Raft算法
《Paxos到Zookeeper:分布式一致性原理与实践》从分布式一致性的理论出发,向读者简要介绍几种典型的分布式一致性协议,以及解决分布式一致性问题的思路,其中重点讲解了Paxos和ZAB协议。同时,本书深入介绍了分布式...
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
对Paxos和Raft算法进行了综合介绍
WPaxosWPaxos是Paxos一致性算法的生产级高性能Java实现,参考了微信团队C++语言开发的类库,支持多分组,可用于解决高并发、高可靠分布式系统中多副本数据一致性问题以及分布式共识问题。针对一些网络分区、机器宕机...
paxos算法,zookeeper分布式一致性,理论实践结合,详细的解析。
铁路客票系统中基于Paxos算法的数据一致性模型研究.pdf
先讲PAXOS算法,然后逐步进入时间zookeeper,从分布式一致性原理到实践,全盘讲解,带书签。
Raft 是一种用来管理日志复制的一致性算法。它和 Paxos 的性能和功能是一样的,但是它和 Paxos 的结构不一样;这使得 Raft 更容易理解并且更易于建立实际的系统。为了提高理解性,Raft 将一致性算法分为了几个部分,...
Paxos算法是分布式技术大师Lamport提出的,主要目的是通过这个算法,让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说,就是在一个选举过程中,让不同的选民最终做出一致的决定。 Lamport为了...
分布式算法理论说明,分布式两阶段提交,paxos算法介绍
Raft是一种共识算法,旨在替代Paxos。 它通过逻辑分离比Paxos更容易理解,但它也被正式证明是安全的,并提供了一些额外的功能。[1] Raft提供了一种在计算系统集群中分布状态机的通用方法,确保集群中的每个节点都...
分布式一致性算法最著名的应该是 Paxos,1990年提出,google的Chubby Lock服务就是使用的Paxos 之后的一些一致性算法基本都是在Paxos思路上的调整,例如 ZooKeeper的 ZAB 但Paxos算法一直被认为比较繁杂,很不好理解...
从Paxos到ZooKeeper一书高清的PDF、带完整书签,质量很好!
Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一,其解决的问题就是在分布式系统中如何就某个值(决议)达成一致。...
Raft 是用来管理复制日志(replicated log)的一致性协议。它跟 multi-Paxos 作用相同,效率也相当,但是它的组织结构跟 Paxos 不同。这使得 Raft 比 Paxos 更容易理解并且更容易在工程实践中实现。为了使 Raft 协议...
Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可理解性,Raft 将一致性算法...