从Paxos入门分布式共识算法,先了解Paxos算法的总体结构和流程。
本文Paoxs指代的是Basic Paxos。
Paxos是强一致的算法,数据写入后立即可读取,不存在延迟。
分布式共识算法不同于分布式一致性算法。
共识只是某一个部分形成共识,比如某个变量。一致性则是整体一致,是由很多共识组成的。
Paxos是分布式共识算法,Paxos实例的目标是达成一个共识。一旦达成共识,共识内容就无法改变。
对应到Golang的SyncMap中,一个Paxos实例的语义:LoadOrStore。
如果值存在,则存入。否则,读出已存的值。
提案信息包括提案编号(ProposalID)和提议的内容(value),比如确定一个变量v的值。
提案编号隐含了提案的时序,编号越大提案越新,提案编号不允许重复。
决议是被批准的提案。
决议不代表最终的共识,因为决议可能还没有形成多数派,会被推翻。
形成多数派的决议,不可能被推翻,也可以认为是最终的决议,它是Paxos执行最终的结果。
一个Paxos系统需要这些角色来运作,每个角色都承担单独的作用。它们之间通过网络消息通信。
整个paxos服务中,有Proposer,Acceptor,和 Learner 3个角色。
发起提案的角色,提出提案,并运行Paxos的流程。
这是无状态的角色,可以集成到client中。多个Proposer可同时发起提案,也就是常说多点写。
接受提案的角色,也是系统中唯一一个必须持久化数据的角色(Learner和Proposal都可以不持久化数据)。最终决议(达成的共识)是存储在Acceptors中的。
Accptor之间并不通信,如果想让其它未存储最终决议的Accptors获取最终决议,需要重新提案。
读取最终提案的角色,类似异步备份,可以不在paxos的同步链路中。
整个流程分两个阶段,Prepare和Accept。
注意:PrepareID,是用在Prepare阶段的ProposalID。
Proposor生成一个提案编号PreposalID,并将这个ID作为PrepareID发送给Acceptors中的一个多数派。
注意
: Preapre时只需要发给多数派,并没有要求发给所有节点。
这是Accptor的动作,Accptor存储了3个信息,后两个合称为提案。
maxPrepareID
: 最大的请求ID。proposalID
: 最后批准的决议的ID。proposalValue
:最后批准的决议的内容。
Acceptor收到prepare消息后,会判断新的Prepare编号PrepareID
是否大于本地记录的maxPrepareID
。
如果是会更新maxPrepareID
。
并返回之前本地记录的决议信息proposalID
和proposalValue
(ProposalValue
可能是NULL)信息。如果本地的提案编号更大,则忽略这个消息,不接受整个提案。
这是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阶段
这是Proposor的动作。
进入Accept阶段后,正式发送提案内容,之前只是发送编号(占坑)。
将上一步确定的ProposalValue
广播给其中一个多数派。
这是Acceptor的动作。
和Prepare时一样,Acceptor会判断ProposalID
是否大于或等于当前的maxPrepareID
。如果是,则更新proposalID
和proposalValue
,意味着批准了提案,返回确认信息。
否则忽略该消息。
这是Proposor的动作。
如果前面一切顺利,Proposor得到Acceptor多数派应答后,就意味着达成共识。可以返回最终决议给Client了。
注意:决议返回的信息,不一定是Client想要写入的信息。
Paxos读也必须执行一次Paxos实例。
可以略微优化一下,在收到Promise后,如果都是空的,可以直接退出,不然就要赋值了。
以下是我认为paxos算法中的几个关键点。
ProposalID
体现了时序,算法中允许新提案号覆盖旧提案号。相当于可以撬锁。