算法-共识算法

一、Paxos

       基础的Paxos算法包括如下三种：Basic Paxos、Multi Paxos、Fast Paxos 

       Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner)：

       【Proposer】：提出提案（Proposal）。Proposal信息包括提案编号（Proposal ID）和提议的值 （Value）。

       【Acceptor】：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。

       【Learner】：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。      

 二、Base  Paxos    

       Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

      1、第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。

      2、第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

      3、第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。 

    Paxos算法流程中的每条消息描述如下：

    【Prepare】：Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。

    【Promise】：Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。

      两个承诺：

                     1、不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。

                     2、不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。

     一个应答：

                    不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。   

                    a、Propose：Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。

                    b、Accept：Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。

                    c、Learn：Proposer收到多数Acceptors的Accept后，决议形成，将形成的决议发送给所有Learners。

      【正常流程】：     

      【Acceptor出现异常时流程】：

                   虽然Accetor3 出现异常，没有向Proposer反馈，但是Proposer此时收到的接受提案的反馈有2个Acceptor，仍然满足多数派的情况，此时仍然能够将提案内容继续写入的，所以后续的Accept的发送只需要发送给剩下的两个Acceptor即可。

       【Proposer出现异常时流程】：

                     Proposer失败的话表示收到Acceptor的Propose请求之后无法继续发送Accept请求，这个时候集群会重新选出另一个新的能够工作的Proposer，再从prepare阶段开始处理，同时Prepare的提案版本号会增加一个，但是提案的内容还是之前的内容。

            【活锁问题】：

                      简化了如下处理流程，当然其中的 Proposers和Acceptors 不只一个，是由多个组成的。

基本情况就是集群中有多个Propser，当proposer1发送prepare版本为1并收到propose的时候节点发生了异常，集群切换到了新的proposer，并重新prepare 版本2，准备好和版本1相同的内容的提案。（因为acceptor处理的过程中发现更高版本的提案，会丢弃当前的版本，转向更高版本去处理）。

                     当proposer2等待acceptor的propose返回时，proposer1有上线了，发现自己prepare(1)提案被打断，此时又准备了一个更高版本的prepare(3)提案，打断了proposer2的2版本提案；当proposer2发现自己的2号版本被打断，又准备了更高的4号版本，从而打断了propose1的3号提案版本；依此下去，整个集群将会阻塞在相同的提案的不断提交之中，这种情况就是集群出现了活锁。

                     当然也有较好的解决措施，比如：proposer1的上线之后 重新提交法案使用随机时间机制，即随机生成一个时间戳，在这段时间内不向Acceptor发送消息；这样proposer2的提案能够被处理完成，这个时候proposer1再次提交新的提案。

     小结：Acceptor不再应答Proposal ID小于等于当前请求的Prepare请求。意味着需要应答Proposal ID大于当前请求的Prepare请求。

三、Multi-Paxos

       原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。

       实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了两点改进：

       1、针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。

       2、在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。       

Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。

 Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。

四、Raft

        基于log replicated的共识算法。raft是更为简化的Multi paxos其实也就是上一个图中的paxos）算法，相比于paxos的复杂实现来说角色更少，问题更加精简。

      可以拆分为3个子问题：

                     1、Leader Election ：如何选择出leader

                     2、Log Replication ：如何将log复制到其他的节点

                     3、Safety ： 保证复制之后集群的数据时一致的

     重新定义了新的角色：

                     1、Leader ： 一个集群只有一个leader

                     2、Follower ：一个服从leader决定的角色

                     3、Cadidate：Follower发现集群没有leader，会重新选举leader，参与选举的节点会变成candidate

          参考：Raft (thesecretlivesofdata.com)

五、ZAB     

    基本和raft相同，只是在一些名词的叫法上有一些区别
    比如ZAB 将某一个leader的周期称为epoch,而raft称为 term。

    实现上的话 raft为了保证日志连续性，心跳方向是从leader到follower，ZAB则是相反的。