Paxos算法学习笔记

  • A+
所属分类:分布式系统

从Paxos入门分布式共识算法,先了解Paxos算法的总体结构和流程。

前言

本文Paoxs指代的是Basic Paxos。
Paxos是强一致的算法,数据写入后立即可读取,不存在延迟。

Paxos是分布式共识算法

分布式共识算法不同于分布式一致性算法
共识只是某一个部分形成共识,比如某个变量。一致性则是整体一致,是由很多共识组成的。
Paxos是分布式共识算法,Paxos实例的目标是达成一个共识。一旦达成共识,共识内容就无法改变。

Paxos实例(Instance)的语义

对应到Golang的SyncMap中,一个Paxos实例的语义:LoadOrStore
如果值存在,则存入。否则,读出已存的值

术语说明

提案(Proposal)

提案信息包括提案编号(ProposalID)和提议的内容(value),比如确定一个变量v的值。
提案编号隐含了提案的时序,编号越大提案越新,提案编号不允许重复。

决议

决议是被批准的提案。
决议不代表最终的共识,因为决议可能还没有形成多数派,会被推翻。

共识(Consensus)

形成多数派的决议,不可能被推翻,也可以认为是最终的决议,它是Paxos执行最终的结果。

系统结构

图示

Paxos算法学习笔记
一个Paxos系统需要这些角色来运作,每个角色都承担单独的作用。它们之间通过网络消息通信。

角色

整个paxos服务中,有Proposer,Acceptor,和 Learner 3个角色。

Proposer

发起提案的角色,提出提案,并运行Paxos的流程
这是无状态的角色,可以集成到client中。多个Proposer可同时发起提案,也就是常说多点写。

Acceptor

接受提案的角色,也是系统中唯一一个必须持久化数据的角色(Learner和Proposal都可以不持久化数据)。最终决议(达成的共识)是存储在Acceptors中的
Accptor之间并不通信,如果想让其它未存储最终决议的Accptors获取最终决议,需要重新提案。

Learner

读取最终提案的角色,类似异步备份,可以不在paxos的同步链路中。

执行流程

图示

整个流程分两个阶段,Prepare和Accept。
注意:PrepareID,是用在Prepare阶段的ProposalID
1. 第一个阶段Prepare,是抢锁的动作。根据PrepareID大小,更大的PrepareID可以撬锁。
2. 第二个阶段Accept,检查锁是不是还在或可以撬开,并写入Value。

步骤说明

  1. 注意步骤中的箭头,它表示消息是从Proposor发送给Accptor还是Accptor返回给Proposor的。
  2. Accptor中处理请求的操作是并发安全的。

Prepare

Proposor生成一个提案编号PreposalID,并将这个ID作为PrepareID发送给Acceptors中的一个多数派
注意: Preapre时只需要发给多数派,并没有要求发给所有节点。

Promise(承诺)

这是Accptor的动作,Accptor存储了3个信息,后两个合称为提案。
1. maxPrepareID: 最大的请求ID。
2. proposalID: 最后批准的决议的ID。
3. proposalValue:最后批准的决议的内容。
Acceptor收到prepare消息后,会判断新的Prepare编号PrepareID是否大于本地记录的maxPrepareID
如果是会更新maxPrepareID
并返回之前本地记录的决议信息proposalIDproposalValue(ProposalValue可能是NULL)信息。

如果本地的提案编号更大,则忽略这个消息,不接受整个提案。

准备进入Accept阶段

这是Proposor的动作。
当一个Proposer收到了多数Acceptors的Promise,意味着Parepare阶段达成多数派。流程继续,否则流程终止。
假设收到的应答

{"ProposalID":6,"ProposalValue":"GTX1070"}
{"ProposalID":8,"ProposalValue":null}
{"ProposalID":7,"ProposalValue":"GTX1070Ti"}

在收到的Promise中,如果有proposalValue不是NULL的,意味着已经有决议形成。此时Proposer需要找出ProposealID最大,且ProposalValue非NULL的应答。比如上面的3个应答,就要选择{"ProposalID":7,"ProposalValue":"GTX1070Ti"}
如果都是NULL,则可以自由决定ProposalValue


下面进入Accept阶段


Propose(提议)

这是Proposor的动作。
进入Accept阶段后,正式发送提案内容,之前只是发送编号(占坑)。
将上一步确定的ProposalValue广播给其中一个多数派。

Accept(批准)

这是Acceptor的动作。
和Prepare时一样,Acceptor会判断ProposalID是否大于或等于当前的maxPrepareID。如果是,则更新proposalIDproposalValue,意味着批准了提案,返回确认信息。
否则忽略该消息。

Response(结束)

这是Proposor的动作。
如果前面一切顺利,Proposor得到Acceptor多数派应答后,就意味着达成共识。可以返回最终决议给Client了。
注意决议返回的信息,不一定是Client想要写入的信息

Paxos的读

Paxos读也必须执行一次Paxos实例
可以略微优化一下,在收到Promise后,如果都是空的,可以直接退出,不然就要赋值了。

总结

以下是我认为paxos算法中的几个关键点。
1. ProposalID体现了时序,算法中允许新提案号覆盖旧提案号。相当于可以撬锁。
2. Prepare时,只需要发给Acceptor的其中一个多数派(可以发给想要的多数派,比如proposalValue都为空的),用于占坑。Acceptor时,也只需广播给Acceptor的其中一个多数派
3. Paxos流程的语义是LoadOrStore,是一个带读写的原子操作,所以即便Paxos流程顺利走完,达成的共识也并不一定是调用者希望的值
4. Paxos流程,也是读取共识的唯一方法

相关笔记

Paxos算法的数学归纳法证明
Paxos算法学习疑问记录

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: