vlambda博客
学习文章列表

1.Paxos算法

    Google Chubby的作者Mike Burrows说过：这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

    在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

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

    Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

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

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

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

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

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

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

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

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

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

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

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

    但Paxos算法存在活锁问题且一次只能对一个值达成共识，Multi-Paxos基于Basic Paxos做了两点改进：:

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

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

2.ceph的Paxos算法实现

Phase1

    leader当选后调用Paxos::collect()函数，此函数首先检查数据库中是否存在未提交的数据，如果有的话把上次未提交的提案号pending_pn、pending_v、对应的value记录下来；然后生成新的proposal number，附带first_committed、last_committed封装成op_collect请求发送给其他peon节点；

    peon收到op_collect请求之后，如果leader的first_commited大于peon的last_committed+1，则peon触发monitor进入probing状态返回，即先完成数据同步；否则判断leader的accepted_pn与peon的accepted_pn的关系，如果leader的accepted_pn较大，则将leader的accepted_pn持久化；否则忽略。然后用如下信息填充op_last请求：

    1).peon的first_commited、last_commited、最新的accepted_pn;

    2).如果leader的last_committed小于peon的last_commited，说明peon节点的数据更新，将增量数据也放到op_last请求中，

    3).如果peon存在未提交的pending数据，说明上次选举中此peon节点可能为leader，因为某种原因故障；此种情况下需要把未提交的数据和accepted_pn填到op_last请求中；

    leader收到op_last请求后，先进行数据差异的比较：

    1).如果peon的first_committed大于leader的last_committed，说明peon的数据更新，leader需要进入probe状态；

    2).leader检查请求中是否有增量数据，有的话将数据包装成事务持久化；

    3).如果leader的first_commited大于任何一个peon的last_committed，则leader也会进入probe状态；

    4).如果leader的数据较新，leader会把差异数据封装成op_commit请求发送给相应的peon;

    5).如果数据没有差异了，则判断peon的accepted_pn是否有效；

        a.如果peon的accepted_pn大于leader的accepted_pn，则leader会递增自己的accepted_pn，重新发送op_collect请求；

        b.如果peon的accepted_pn等于leader的accepted_pn，说明peon已经接受了leader，统计个数，如果收到全部的请求，则会判断peon是否有未提交的数据，如有未提交的数据，则进入updating_previous状态，先更新未提交的数据，此过程是paxos的第二阶段；如果没有未提交的数据，则通过发送请求延长lease；

        c.如果peon的accepted_pn小于leader的accepted_pn，说明这是一个旧消息，忽略掉；

    至此，paxos算法的Phase 1已经完成，即所有peon节点都对leader节点的accepted_pn达成一致，在该leader的任期内不会再改变。

Phase2

 leader调用Paxos::begin()，在本地持久化pending_v(last_committed+1)、pending_pn、和提案的值（注意此时last_committed并没有递增，也没有持久化）。然后把自己的accepted_pn和last_committed放入op_begin请求中发送给peon；

    peon在handle_begin中处理收到的op_begin消息：在本地持久化pending_v、pending_pn、和提案的值（注意此last_committed并没有递增，也没有持久化）。然后把自己的accepted_pn和last_committed放入op_accept请求中发送给leader；

    leader收到op_accepted消息后，统计已经接受的数量，如果都接受了，将last_committed+1持久化（但此时last_committed内存的值并没有递增）；然后把该事务放到异步队列中去处理，主程序继续做其他事情。当last_commited持久化的事务完成后，内存中last_committed才会加1，并向其它peon发送op_commit消息。

    peon收到op_commit消息后，将last_committed持久化(并未看到内存中last_committed加1，想来也没必要，peon当选leader的话会重新选举，会从db中重新读取)。