`

Paxos一致性算法

 
阅读更多

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请求后,做出以下约定:

  1. 不再应答 <=Pn 的Prepare请求
  2. 对于 < Pn 的Accept请求也不处理

Acceptor对于Prepare请求,做以下处理:

  1. 应答前要在本地持久化当前提案ID(Pn)
  2. 如果现在请求的提案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实现.zip

    voguedb是Paxos一致性算法的生产级高性能Java实现,支持多分组,可用于解决高并发、高可靠分布式系统中多副本数据一致性问题以及分布式共识问题。针对一些网络分区、机器宕机、进程异常(OOM、卡顿、强制关闭)等...

    The Part-Time Parliament+ Paxos Made Simple+ paxos made live-paper

    《The Part-Time Parliament》、《Paxos Made Simple》以及《Paxos Made Live-paper2-1》是分布式系统领域中的三篇经典论文,主要关注的是Paxos一致性算法。Paxos是一种解决分布式系统中如何达成共识问题的算法,其...

    综合介绍了Paxos和Raft算法

    Paxos算法是一种经典的分布式一致性算法,可以解决分布式系统中的数据一致性问题。Paxos算法的核心思想是使用投票机制来实现分布式系统中的数据一致性。 Raft算法 Raft算法是一种广泛使用的分布式一致性算法,可以...

    分布式一致性原理与实践.pdf(完整书签)

    ZooKeeper是一个开源的分布式协调服务,它基于Paxos等一致性算法实现了一套高可用的分布式数据管理和服务框架。ZooKeeper提供了命名服务、配置管理、组服务、分布式锁和领导者选举等基础功能。 **ZooKeeper的主要...

    Paxos算法中文翻译

    如Raft算法,它是Paxos算法的另一种形式,旨在提供更容易理解和实施的一致性协议。 在《The Part-Time Parliament》的翻译中,译者对Paxos算法的历史、原理以及与现代分布式计算系统的关系进行了详细的介绍和分析。...

    从Paxos到Zookeeper分布式一致性原理与实践PDF

    Zookeeper则将Paxos等一致性算法进行了封装和简化,提供了一套易于使用的API,使得开发者可以快速构建分布式协调服务。Zookeeper的主要功能包括命名服务、配置管理、集群同步、分布式锁等。它采用了ZAB(Zookeeper ...

    从PAXOS到ZOOKEEPER分布式一致性原理与实践

    本书《从PAXOS到ZOOKEEPER:分布式一致性原理与实践》深入浅出地介绍了PAXOS算法的原理和ZOOKEEPER的实现,同时结合实际案例分析了分布式一致性在各种应用场景下的解决方案。通过阅读这本书,读者不仅可以理解分布式...

    云计算:C++实现的可直接运行paxos算法

    Paxos算法是一种在分布式系统中解决一致性问题的经典协议,由Leslie Lamport提出。它的主要目标是在存在网络延迟、消息丢失或重复、节点故障等不可靠因素的情况下,确保一组分布式节点能够就一个值达成一致。在...

    一致性算法 .zip

    一致性算法是分布式计算领域中的重要概念,用于保证网络中各个节点的数据一致性,即使在面临网络延迟、节点故障或并发更新等复杂情况时也能确保数据的正确性和同步性。这一算法在分布式数据库、分布式文件系统、...

    基于Paxos的分布式一致性算法的实现与优化.pdf

    #资源达人分享计划#

    一致性算法

    一致性算法在分布式计算领域扮演着至关重要的角色,它旨在确保网络中的多个节点或智能体能够达成一致的状态,即使面临各种故障或通信延迟。这个压缩包包含的“一致性算法”源程序,很可能是为了帮助研究者理解和模拟...

    consensus_based_auction_algothm_auction算法_任务分配_一致性算法_CBAA_竞拍算法_源

    一致性算法在这里的作用是确保所有智能体最终达成一致的决策,即使在存在网络延迟或消息丢失的情况下。通过设计适当的一致性协议,如Gossip协议或Paxos协议,智能体能够逐渐收敛到相同的出价,从而避免死锁或无解的...

    从Paxos到Zookeeper分布式一致性原理与实践包括源码

    Zookeeper基于Paxos和其他一致性算法的实现,为分布式应用程序提供了命名服务、配置管理、分布式锁、群组服务等功能。Zookeeper通过ZNode(类似于文件系统的节点)来存储和操作数据,并采用观察者模式来实时监控数据...

    cpp-PaxosStore腾讯开源的分布式数据库

    **PaxosStore**是腾讯开源的一款分布式数据库系统,它基于经典的Paxos一致性算法设计,旨在提供高可用性、高性能和高可扩展性的数据存储服务。在两年前,PaxosStore已被应用于微信的核心业务场景,能有效处理数十亿...

    《Paxos到Zookeeper——分布式一致性原理与实践》高清完整版

    Zookeeper是Apache的一个开源项目,它基于Paxos和其他一致性算法,为分布式应用提供了一个高可用、高性能的协调服务。Zookeeper的主要功能包括命名服务、配置管理、集群同步、领导者选举等。它的设计目标是简化...

    从Paxos到Zookeeper 分布式一致性原理与实践 PDF电子书下载 带目录书签 完整版.pdf

    本书《从Paxos到Zookeeper:分布式一致性原理与实践》深入浅出地讲解了分布式一致性算法及其应用,并以Zookeeper为例进行了详细剖析。 #### 二、Paxos算法概述 Paxos算法是一种解决分布式系统中一致性的经典算法。...

    分布式一致性算法的研究及应用.pdf

    综上所述,分布式一致性算法是分布式系统设计中不可或缺的一部分,而Paxos算法则在其中扮演了重要角色。尽管Paxos算法有着复杂的逻辑和操作过程,但它的稳定性和可靠性使其成为解决分布式系统数据一致性问题的首选...

    分布式事务与一致性算法 Paxos & raft & zab.pdf

    分布式事务与一致性算法Paxos、Raft和ZAB是解决分布式系统中数据一致性的代表性算法,它们能够确保在网络分区、节点故障等异常情况下,系统依然能达成共识并保持数据的一致性。 首先,CAP原理是分布式计算中的基础...

Global site tag (gtag.js) - Google Analytics