最朴素的Paxos
最朴素的Paxos解决什么问题？这里举个例子：三个人分别只允许呆在不同的三个城市，他们手上有一张纸和一支笔，他们可以在纸上写下任何内容，但是，当他们停下他们的笔之后，我们希望三个人最后写下的内容都是一样的。
这个就是最朴素的Paxos尝试解决的问题，确定一个值。暂时千万别去想更多的东西，聚焦在确定一个值这么一个看似非常简单的事情身上，投票算法约束：
• 要求每轮投票的编号唯一。
• 要求任意两轮投票的Bqrm交集不为空，其实意思很明确，就是要求Bqrm超过半数的意思。
• 它强行约束了每轮投票的提议，使得这轮投票的提议不与之前的产生冲突。通俗一点讲就是，一旦我发现在我之前已经有人投过某个提议的票，那我就要用这个提议，并且是我之前最大编号的投票对应的提议，作为我这次的提议。（我可以理解为，一个提议未被所有的accetpor全部接受之前，不允许发起新的提案）
通过今天的学习有几个疑问需要解决：
-
Paxos的投票是否是定时触发，每个RS管控自己的投票序列？？怎么保证顺序，全局gts？？
解答：该问题在单副本多节点写的时候才需要考虑，单副本写只会在一个节点上发起，所以，不用考虑新任务补副本的场景，只是在多数派下某些缺少副本的节点上，需要顺序补齐部分日志即可，可以延续异步复制，也可以主动去rs上拉取日志
-
如果提议内容已经写过了，直接返回ok？？
解答：算法中会当做提议未写过再执行一次，理论上此处算法可以优化为直接prepare(ok)
-
副本数存储位置？？确认本次提议需要多少个accetpor满足，如果实现单副本运行是否就是修改副本个数就行，为啥这种方案被排除
Paxos，Multi-paxos，Raft
basic paxos是由client发起的同步过程，在两阶段返回前，client不能得到成功的返回。
第一阶段a（发送prepare），proposer向acceptor提出一个协议，这里的协议可以理解为client发送过来期望多节点一起保存的一致性内容，举例：一句日志，某个配置等 第一阶段b（计算协议vn），根据半数以上acceptor的返回，选择 max{va,vb,vc} = vn，这里的vx理解为这个acceptor已知的最大协议号，acceptor一旦返回了vx后，则表明： acceptor在接下来的prepare请求中，会返回的vx自增1 acceptor不会accept任何小于vx的协议请求，只会accept大于vx的协议请求 第二阶段a（发送决议好的vn），把vn发送给acceptor 第二阶段b，在半数acceptor返回了成功后，再返回client成功通过协议 引用wiki上的流程图：
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| |<---------X--X--X | | Promise(1,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(1,Vn)
| |<---------X--X--X------>|->| Accepted(1,Vn)
|<---------------------------------X--X Response
| | | | | | |
basic paxos的极端案例
Client Proposer Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| |<------------X--X--X | | Promise(1,{null,null,null})
| ! | | | | | !! LEADER FAILS
| | | | | | | !! NEW LEADER (knows last number was 1)
| X--------->|->|->| | | Prepare(2)
| |<---------X--X--X | | Promise(2,{null,null,null})
| | | | | | | | !! OLD LEADER recovers
| | | | | | | | !! OLD LEADER tries 2, denied
| X------------>|->|->| | | Prepare(2)
| |<------------X--X--X | | Nack(2)
| | | | | | | | !! OLD LEADER tries 3
| X------------>|->|->| | | Prepare(3)
| |<------------X--X--X | | Promise(3,{null,null,null})
| | | | | | | | !! NEW LEADER proposes, denied
| | X--------->|->|->| | | Accept!(2,Va)
| | |<---------X--X--X | | Nack(3)
| | | | | | | | !! NEW LEADER tries 4
| | X--------->|->|->| | | Prepare(4)
| | |<---------X--X--X | | Promise(4,{null,null,null})
| | | | | | | | !! OLD LEADER proposes, denied
| X------------>|->|->| | | Accept!(3,Vb)
| |<------------X--X--X | | Nack(4)
| | | | | | | | ... and so on ...
因为其他proposer的存在，大家交替propose的结果就是所有的prepare计算得到的vn，全部中途作废，accept的动作一个都没正常执行。显然，这样的决议过程是正确且低效的。 如何让basic paxos得以进行一阶段的递交，最最重点的地方聚焦在了一个点：假如只允许有一个proposer multi-paxos将集群状态分成了两种： • 选主状态，由集群中的任意节点拉票发起选主，拉票中带上自己的vx，通过收集集群中半数以上的vx，来更新自己的vx值，得到目前集群通过的最大vx = vn • 强leader状态，leader对vn的演变了如指掌，每次把vn的值直接在一阶段中发送给acceptor，和basic paxos的区别：basic paxos一阶段的时候，proposer对vn的值一无所知，要依赖一阶段的结果来算vn 一些有趣的细节：为何选主的时候，半数的vx就可以确定集群最大vn？ 因为在vn生成过程中，必须达成通知到半数节点的目的，vn才能成功生成，所以一定有半数以上的节点知道vn 选主的时候的限制恰好对应vn生成时的限制，这是一个环环相扣的证明，multi-paxos强leader状态的流程图：
Client Leader Acceptor Learner
| | | | | | | --- Following Requests ---
X-------->| | | | | | Request
| X--------->|->|->| | | Accept!(N,I+1,W)(prepare）
| |<---------X--X--X------>|->| Accepted(N,I+1,W)(prepared)
|<---------------------------------X--X Response
| | | | | | |
流程图中没有了basic paxos的两阶段，变成了一个一阶段的递交协议： 一阶段a：发起者（leader）直接告诉Acceptor，准备递交协议号为I+1的协议 一阶段b：收到了大部分acceptor的回复后（图中是全部），acceptor就直接回复client协议成功写入。wiki中写的Accept方法，我更愿意把它当做prepare，因为如果没有半数返回，该协议在超时后会返回失败，这种情况下，I+1这个协议号并没有通过，在下个请求是仍是使用I+1这个协议号
- raft vs multi-paxos 看到这里的，说明对分布式一致性的学习绝对是真爱。
在我的上一篇文章：raft 经典场景分析 - 知乎专栏 中，已经详细讨论了raft的 选主和日志复制，而在上一节中，我们惊喜的发现multi-paxos和raft，在选定了leader状态下的行为模式一模一样，在这一节中，主要将比较它们在选主和日志复制上的行为。
注意：raft的日志复制，等同我们在上文讨论的协议，为叙述方便，现在这一节，我们把multi-paxos的一阶段协议递交成为日志复制。
结论也同样隐藏在我上一篇文章中：
raft仅允许日志最多的节点当选为leader，而multi-paxos则相反，任意节点都可以当选leader raft不允许日志的空洞，这也是为了比较方便和拉平两个节点的日志方便，而multi-paxos则允许日志出现空洞 这两个不同的设定反应到日志中的区别可以看如下图：
如图，multi-paxos日志中间允许出现空洞，而multi-paxos的leader节点也会异步的查询其他节点来填补自身日志空洞
如图：raft的典型日志，可以看出这个raft集群中，8节点的日志仍未完成且返回，只有1，3，5这三个节点有机会被重新选为leader 深化一下刚才的理解，那就是：multi-paxos的leader只是知道最大的log index是多少，但是空洞部分，可以异步填充，而raft的leader，不但知道最大的log index是多少，也必须拥有从0到log index直接的之间日志，在被选择为leader后，raft的leader可以单向的向其他节点同步落后的日志。
多谢 @LoopJump 指出，raft这个协议方便的地方在于：”raft不允许日志的空洞，这也是为了比较方便和拉平两个节点的日志方便 “ Raft连续确认更大的一个优势是新主上任过程简单了。Multi Paxos在上任过程很复杂，不只是补全过程。我在raft经典场景这篇文章中也指出了这一点：
- 在一些一致性算法中，例如：Viewstamped Replication， 即使一开始没有包含全部已提交的条目也可以被选为领导人。 这些算法都有一些另外的机制来保证找到丢失的条目并将它们传输给新的领导人， 这个过程要么在选举过程中完成，要么在选举之后立即开始。 不幸的是，这种方式大大增加了复杂性。
- Raft 使用了一种更简单的方式来保证：也就是日志落后的候选人， 无法被选中为Leader，这其实大大减小了选举和日志复制的相关性， 简化了raft的算法理解难度。 其实这点也是raft把log replication 和 选主这两个过程的有机结合，大大简化了raft协议的理解难度，大家可以参考一下。
