- A+
从Paxos入门分布式共识算法，先了解Paxos算法的总体结构和流程。
前言
本文Paoxs指代的是Basic Paxos。
Paxos是强一致的算法，数据写入后立即可读取，不存在延迟。
Paxos是分布式共识算法
分布式共识算法不同于分布式一致性算法。
共识只是某一个部分形成共识，比如某个变量。一致性则是整体一致，是由很多共识组成的。
Paxos是分布式共识算法，Paxos实例的目标是达成一个共识。一旦达成共识，共识内容就无法改变。
Paxos实例(Instance)的语义
对应到Golang的SyncMap中，一个Paxos实例的语义:LoadOrStore。
如果值存在，则存入。否则，读出已存的值。
术语说明
提案(Proposal)
提案信息包括提案编号(ProposalID)和提议的内容(value)，比如确定一个变量v的值。
提案编号隐含了提案的时序，编号越大提案越新，提案编号不允许重复。
决议
决议是被批准的提案。
决议不代表最终的共识，因为决议可能还没有形成多数派，会被推翻。
共识(Consensus)
形成多数派的决议，不可能被推翻，也可以认为是最终的决议，它是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。
步骤说明
- 注意步骤中的箭头，它表示消息是从Proposor发送给Accptor还是Accptor返回给Proposor的。
- 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。
并返回之前本地记录的决议信息proposalID和proposalValue(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。如果是，则更新proposalID和proposalValue，意味着批准了提案，返回确认信息。
否则忽略该消息。
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流程，也是读取共识的唯一方法。
