Basic-Paxos

https://zhuanlan.zhihu.com/p/31780743
https://www.cnblogs.com/linbingdong/p/6253479.html

---

所有的server都兼具proposer，acceptor，learner的角色，不考虑拜占庭式的篡改数据。

Basic Paxos

• 最简单的方案（单Acceptor）

只有一个ACer，只要Acceptor接受它收到的第一个提案，则该提案被选定，该提案里的value就是被选定的value。这样就保证只有一个value会被选定。

但是，如果这个唯一的Acceptor宕机了，那么整个系统就无法工作了。

• 多个Acceptor方案

如果我们希望即使只有一个Proposer提出了一个value，该value也最终被选定。

那么，就得到下面的约束：

P1：一个Acceptor必须接受它收到的第一个提案。

但是，这又会引出另一个问题：如果每个Proposer分别提出不同的value，发给不同的Acceptor。根据P1，Acceptor分别接受自己收到的value，就导致不同的value被选定。出现了不一致。如下图（2，2，1没有1个value得到大于等于3个ACer同意）：（这也是只有accept没有prepare产生的问题）

所以如果节点可以喜新厌旧（存在prepare竞争），就可以避免陷入这种尴尬的境界。但是如果允许覆盖原有的值，可能会出现安全问题（中途不知道被哪个广播给改了），所以需要在更改的时候查询是否已有别的value已经AC，这样就直接选择已经AC的value即可避免冲突。（下图 two-phase protocol）

?是提出但是没正式AC

但是还有新的问题出现，如果s1和s5先后提出了value但是都没被AC，结果还是相互覆盖了。解决方法就是拒绝旧的提议，保留最新的那个提议。（见下图）

• proposal number=时间戳+server_id

下图分为两个阶段：（proposal和value的双同步）

1. prepare

（1）生成新proposal number N=时间戳+server_id
（2）广播N给其他server（每个server都是Acceptor） （3）因为对于未提交/已经提交的minproposal，你都不能比它小（时间戳早，原因见上reject old），当然也不能等于它（有可能本地时钟更新了时间，或者两次获取时间戳到时间过短）。对于N>minProposal的情况返回已经AC的值（acceptProposal，acceptValue）《acceptProposal没啥意思，Value才是重点》，否则可以reject。
（4）wait，然后凑够majority数量（差不多过半数）的return后再用最大的acceptProposal对应的acceptValue替换value，当然，如果没有value的话就用自己的随机value代替

2. accept

（5）广播Accept（N，value）给所有的server。 （6）如果N大于等于minProposal，则acceptProposal=minProposal=N，acceptValue=value，本地持久化后返回minProposal
（7）提议者接收超过半数请求后，如果发现有返回值大于N，表示有更新的提议，跳转到第一步重新开始（再次开始的时候会参考返回的minProposal），否则value达成一致。

---

• 实例1：（已被半数以上AC，接受现实）

图中P代表Prepare阶段，A代表Accept阶段。3.1代表Proposal ID为3.1，其中3为时间戳，1为Server ID。X和Y代表提议Value。

实例1

实例1中P 3.1达成多数派，其Value(X)被Accept，然后P 4.5学习到Value(X)，并Accept。

• 实例2：(未被半数以上AC无视value直接最新覆盖)

实例2中P 3.1没有被多数派Accept（只有S3 Accept），但是被P 4.5学习到，P 4.5将自己的Value由Y替换为X，Accept（X）

image.png

• 实例3：（未探测到AC）

实例3中P 3.1没有被多数派Accept（只有S1 Accept），同时也没有被P 4.5学习到。由于P 4.5 Propose的所有应答，均未返回Value，则P 4.5可以Accept自己的Value (Y)。后续P 3.1的Accept (X) 会失败，已经Accept的S1，会被覆盖。

image.png

• 活锁实例：（只要有一个acceptor失败就重来）

当同一时段有两个及以上的proposer在广播且都没有AC的时候，他们会相互覆盖，最后谁也抢不过谁锁死。（高并发的时候表现得尤其严重）

回顾两个承诺之一，Acceptor不再应答Proposal ID小于等于当前请求的Prepare请求。意味着需要应答Proposal ID大于当前请求的Prepare请求。

两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。

image.png

解决方案：（1）设置AC失败后重新开启下一轮的时间间隔为1个随机数（2）使用Multi-Paxos（leader-selection确保只有一个proposer在线）

• 其他注意要点：当value被选中的时候，只有参与其中的那一台机器的proposer知道被选中的value。其他机器想知道这个value必须由自己的proposer亲自执行Paxos才能得到value