經典的Paxos算法

1.1 問題與需求：

我們讨論的對象是分布式系統中的一個變量。一緻性問題是：要求分布在不同機器上的多個程序，對于這個變量，無論有多少提案，最多隻能從衆多提案中選出一個值。也就是說，無論有多少故障，例如當機、消息延遲、亂序、重複甚至丢失(但消息不能被篡改)，絕對不能有兩個或者兩個以上的值被選擇；比如在ceph中，對于同一個epoch，絕對不能出現兩個不同的osdmap，否則monitor.a認為這部分OSD挂了，而monitor.b認為那部分OSD挂了，不同用戶端可能拿到不同的osdmap。另外，還要求隻要有足夠多的程序無故障，最終總會有一個值被選中。換言之，算法不能無限運作下去而選不出一個值。

總結來說，分布式一緻性問題有兩個需求：

a: 安全需求(safety requirement)，它又包括兩個方面：

• 非平凡性（Nontriviality）：隻有提案的值才能被學習；
• 一緻性（Consistency）：   最多隻有一個值能被學習；學習的意思相當于：學習者(learner)"接受"被選中的值，被學習相當于這個被選中的值在系統中生效。後文會介紹學習者(leaner)角色。

b: 前進需求（progress requirement）：隻要有足夠多的提案者(acceptor)，一個提案者(proposer)和一個學習者(leaner)無故障，最終總能選出一個值，不會無限運作而選不出值。後文會介紹決策者(acceptor)、提案者(proposer)角色；

1.2 角色：

• 提案者(proposer): 發出提案。我們讨論的對象是一個變量，提案者提議對這個變量設定某個它認為合理的值。
• 協調者(coordinator): 是提案者的代理；在下文中，很少有提案者的事，因為提案者被協調者代理。協調者和決策者直接互動，比如發出參與請求、提案等。
• 決策者(acceptor)：負責選出一個值。決策者需要決定參不參與某一輪提案，若參與了接不接受這一輪提案。後文會較長的描述它是如何工作的。
• 學習者(leaner): 若決策者決定接受一個值，會向學習者發送這個決定；在給定的一輪中，若學習者接受到了來自"大多數決策者"的接受決定，那麼這個值就被學習了(當然也被選擇了)。

         需要注意的是，一個agent可以承擔多個角色。論文不介紹如何實作，不過典型的場景是，一個angent充當所有角色，而隻有一個活動的coordinator。

1.3 前提條件：非拜占庭模型(non-Byzantine model)

• agent以任意速度運作，可以故障、停止、重新開機；但是不可以做不正确的動作；
• agent之間的消息可以任意慢、可以重複、亂序、丢失；但不可以被破壞；

1.4 保證safty requirement --> 基本的Paxos算法

基本的Poxos算法中，隻保證safty requirment，1.5中會擴充它來進一步保證progress requirment。另外，基本的Paxos分多輪進行，暫時不考慮它的終結，而假定它可以一直運作下去，但是無論運作多少輪，最終還是最多一個值被選擇學習。每輪有一個唯一的編号，多輪不必按順序進行；某一輪可以中斷或者跳過；多輪可以并發。

下面直接先看算法，然後解釋(證明)它是如何滿足safty requirement的。

1.4.1 算法描述：

acceptor a存儲的持久資訊：

• rnd[a]: acceptor a 參與的最大的round編号；0表示還未參與任何一輪。
• vrnd[a]: acceptor a 接受的最大的提案round編号；0表示還未接受過任何提案。
• vval[a]: acceptor a 接受的最大的提案值；若還未接受過任何提案，則無意義;

接受round r中的提案，一定參與了round r，是以 vrnd[a] <= rnd[a]；反過來參與了round r，不一定接受了round r中的提案。也就是說，若參與了round r并接受了其提案，vrnd[a]=rnd[a]；若參與了rund r但還未接受其提案，vrnd[a] < rnd[a]；

coordinator c存儲的持久資訊：

• crnd[c]: coordinator c 參與的最大的round編号；
• cval[c]: 在round crnd[c]中，coordinator c預選的值；這個值将會發給acceptor，請求acceptor接受。若還沒有預選值，則為none。

記号：

• {i,x}：表示一個提案，round編号為i，值為x;
• 1a消息：在步驟1a中，coordinator向acceptor發的參與請求消息；
• 1b消息：在步驟1b中，acceptor向acceptor發的回複消息；
• 2a消息：在步驟2a中，coordinator向acceptor發的參與請求消息；
• 大多數集：任意一個acceptor集合，隻要滿足集合size大于acceptor總數的一半；

Round i 開始：proposer向coordinator c發出一個提案，{i,x}；

1a: [coordinator c接收到proposer發來的提案]

    if crnd[c] < i then

        crnd[c] = i;              //更新自己參與的最大的round編号；

        cval[c] = none;           //coordinator c在round i中還沒有預選值。注意，不是把x設為預選值；         

        向所有acceptor發送參與請求ParticipateRequest(内容是:i)，請求他們參與；

    else

        丢棄提案{i,x};

1b: [acceptor a接受到c發出的1a消息(内容是:i)]

    if rnd[a] < i then

        rnd[a] = i;                                       //更新自己參與的最大的round編号；是以，以後不再參與

                                                          //編号小于等于i的提案；

        向coordinator c回複消息(内容是:i, vrnd[a], vval[a]) //告訴c：我保證不再參與編号小于等于i的提案；我曾經接

                                                          //受的編号最大的提案為{vrnd[a], vval[a]}；

    else

        丢棄；                                             //不參與編号小于等于rnd[a]的提案；

2a: [coordinator c接收到1b消息(内容是: i, vrnd[a], vval[a])]

    if crnd[c]==i   AND                                    //此消息是對c發出的1a消息的回複，而c還沒有開始更高輪

                                                           //的提案(也就是說，c正在等1a消息的回複)

       cval[c]==none AND                                   //c在round i還沒有預選值(就是說，這是本輪第一次經曆2a)

       c 已經接受到大多數acceptor發來的1b消息                  //可以預選值了

    then

        預選一個值v        //如何選？見下文

        cval[c] = v;      //設定預選值。

        向這些acceptor發送接受請求AcceptRequest(内容是：i,v)，請求他們在round i接受預選值v；

2b: [acceptor a接受到2a消息(内容是:i,v)]

    if i >= rnd[a] AND  //沒有開始更高輪的提案

       vrnd[a] != i     //在round i，還沒有接受一個值(換言之，還沒有為round i投票)     

    then                     

        vrnd[a] = i;    //接受提案{i,v}

        vval[a] = v;

        向所有learner發送消息，宣布它在round i中決定接受v; 若leaner接受到大多數acceptor發來的接受決定，他就學習到了v。

    else                //i<rnd[a] OR vrnd[a]==i, 已經開始了更高的round OR 在round i已經接受了一個值

        丢棄請求

為了加深了解，我們看看那些能滿足這個2b中的if條件的情況：

• i>rnd[a]>vrnd[a]：在rnd[a]沒有接受值(因為rnd[a]!=vrnd[a])，i是開始的更高輪。i!=rnd[a]說明沒有接收到1a消息而直接接收到了2a消息。這種情況不可能發生，因為在步驟2a中，c隻向回複了1a消息的acceptor發送2a消息；
• i>rnd[a]=vrnd[a]：在rnd[a]接受了一個值(因為rnd[a]==vrnd[a])，i是開始的更高輪。由于i!=rnd[a]，此情況也不可能，理由同上。
• i=rnd[a]>vrnd[a]：在rnd[a]沒有接受值(因為rnd[a]!=vrnd[a])，i是正在進行的一輪。也就是說，已經接收到過1a消息，并向c發出了回複，這是c發出的2a消息。

再看看被選擇和被學習的關系：

1. 當大多數acceptor接受了v時，v在round i就被選擇了。它們發給learner的消息可以丢失，但這隻影響學習過程，而不影響v在round i被選擇這一事實，因為vrnd[a]=i， vval[a]=v被持久化了；
2. 隻有被選擇(大多數acceptor接受v并向learner發送接受決定)，才能被學習(learner接受到大多數acceptor發的接受決定);

1.4.2 如何保證safty requirement？

• 定義：一個值被選擇，當且僅當它在某一輪中被選擇；
• 定義：一個值在某一輪中被選擇，當且僅當大多數acceptor接受（accept）了這個值；

回顧一下safty requirment，它包括兩個方面

• 非平凡性（Nontriviality）：隻有提案的值才能被學習；
• 一緻性（Consistency）：最多隻有一個值能被學習；

上面的算法中，隻有提案的值才可能被接受(見2b)，隻有接受的值才可能被選擇(見2b)，隻有被選擇的值才能被學習(見2b)，是以非平凡性已經被保證；

由于隻有被選擇的值才能被學習，是以一緻性的核心是：隻有一個值被選擇，即"大多數決策者"決定接受這個值。

下面分兩步，先證明在同一round隻可能有一個值被選擇(1.4.3)；然後給出一種方法，步驟2a中如何選擇v(1.4.4)，并證明這個方法能夠保證在多個round之間隻可能有一個值被選擇(1.4.5)。

1.4.3 證明同一round中最多隻可能一個值被選擇

• 在給定的一個round中(例如i)，隻有一個coordinator能夠成功接到大多數acceptor的參與回複。因為對于給定的i，一個acceptor在1b中隻能發出一個參與回複(後續的請求會被丢棄，因為rnd[a]=i，不滿足rnd[a]<i)。
• 一個coordinator在得到大多數acceptor的參與回複後，隻能預選一個值發送給acceptor；
• acceptor隻能接受coordinator發來的值；
• 是以，最多隻有一個值被接受；
• 隻有被大多數acceptor接受的才被選擇，是以最多隻有一個值被選擇。

1.4.4 如何保證多輪中也最多隻有一個值被選擇？

在算法的2a步驟中，coordinator c需要選擇一個值，而它選擇的這個值，應該能夠保證：在多個round之間，隻可能有一個值被選擇。

我們先提出一個假設需求

CP：對于任意round i和round j (j<i)，如果一個值v在round j中被選擇或者可能被選擇，那麼acceptor在round i中隻可能接受v。

由于一個值隻有被接受才能被選擇，是以CP蘊含：

 對于任意round i和round j (j<i)，如果一個值v在round j中被選擇或者可能被選擇，那麼在round i中，隻可能選擇v。

也就是說， CP可以保證在多個round之間，隻可能有一個值被選擇。已知同一round隻能有一個值被選擇。是以，隻要我們能夠滿足CP，就能夠滿足一緻性(Consistency)了。

CP的等價命題：

假如有acceptor在round i中接受了值v，那麼在任意round j (j<i)，被選擇或可能被選擇的隻能是v。

隻有2a中選出的值才能被acceptor接受，是以，我們隻需一個方法，滿足：

CP(i,v): 若這個方法在2a中選出了值v，那麼在任意round j(j<i)，被選擇或可能被選擇的隻能是v。(注意，在round j沒有選擇值也滿足條件)

總之： 隻要我們的方法能夠保證CP(i,v)，就能保證CP的等價命題，就能保證CP，進而保證一緻性。

在給出這個方法，并證明它能夠滿足CP(i,v)之前，我們通過觀察得出幾個結論：

結論1：假如在round j中，值v被選擇或者可能被選擇，那麼一定存在一個大多數集Q，滿足：Q裡的任意acceptor a，rnd[a]<=j,或者在round j中，a已經接受了v。

有三種情況：

• rnd[a]<j: a還沒參與round j；
• rnd[a]=j但在round j還沒有接受任何值: 已經參與了round j，但在round j還沒接受任何值。在j之前的round中，可能接受了值v，也可能接受了v以外的值；
• 在round j中已經接受了v

注意，後面隻是一個必要條件，而不是充分條件。換言之，在round j中v被選擇可以推出以上三種情況，但以上三種情況不能推出在round j中v被選擇。它的逆否命題更容易了解：

逆否命題：假如存在一個大多數集Q，滿足：Q裡的任意acceptor a， rnd[a]>j并且在round j中沒有接受v(可能接受了v以外的值，也可能沒有接受任何值)， 那麼v在round j中不可能被選擇。

證明：若a還沒有接受任何值，它也不可能接受任何值了(因為rnd[a]>j，見算法步驟2b)。是以，對于Q裡的任意acceptor a，要麼a接受了v以外的值，要麼不接受任何值。除Q外，即使所有acceptor在round j都接受了v，也不可能構成大多數。是以v在round j不可能被選擇。

結論2(和結論1的逆否命題類似)：假如存在一個大多數集Q，滿足：Q裡的任意acceptor a，rnd[a]>j，并且在round j中沒有接受任何值，那麼沒有一個值可能在round j中被選擇。

證明：除Q之外，即使所有acceptor都接受了某個值w，也構不成大多數，故w不可能被選擇；

結論3：假如存在一個大多數集Q，滿足：Q裡的任意acceptor a，rnd[a]>j，并且，a在round j接受了v或者沒有接受任何值，在round j被選擇或可能被選擇的隻能是v。

證明：除Q之外，即使所有的acceptor都接受了v以外的某值w，也構不成大多數，故w不可能被選擇；

現在直接給出這個方法，後面再證明這個方法能夠滿足CP(i,v):

見算法步驟2a，這時coordinator c已經接收到來大多數的acceptor的1b消息(假設這個大多數集為Q，size為N)，這些消息是：

i, vrnd[a1], vval[a1]

i, vrnd[a2], vval[a2]

...

i, vrnd[aN], vval[aN]

假設vrnd[aX]是vrnd[a1],vrnd[a2],...,vrnd[aN]中最大的，對應的值為vval[aX](若有多個最大的，他們對應的值也是同一個，因為在同一round，隻有一個coordinator能夠得到大多數1b消息，而它又隻請求接受一個值)。設k=vrnd[aX]。那麼有兩種情況：

• k=0: 選擇proposer提案的x；
• k>0: 選擇vval[aX]；

1.4.5 證明這個選擇方法能夠滿足CP(i,v).

k=0時：對于Q裡的任意acceptor a，a在round i之前沒有接受過任何值。形式化的說，對于任意round j (j<j)，rnd[a]>j(因為rnd[a]>=i)，并且在round j沒有接受任何值。根據結論2，在任意round j(j<i)，沒有值在round j被選擇。這時，coordinator c可以任意選擇一個值v，都滿足CP(i,v)。是以，c選擇proposer提案的值x。

k>0時：因為acceptor在1b中，隻有i>rnd[a]時才回複，并且rnd[a]>=vrnd[a]。是以對于任意1b消息(i, vrnd[a], vval[a])，都有i>vrnd[a]。是以k<i。我們要證明CP(i,v): 既然2a中選出了值vval[aX](記為v)，那麼在任意round j(j<i)，被選擇或可能被選擇的隻能是v=vval[aX]。對j，有三種情況：

• k<j<i: 對于Q裡的任意acceptor a，a在回複1b消息時，肯定還沒有為round j接受一個值(因為若接受了，vrnd[a]=j，在coordinator c接收到的那些1b消息中，至少有vrnd[aR]=j，這和k是最大值沖突)。而這時rnd[a]>j(因為a在步驟1a中已經回複了1b消息，故rnd[a]>=i，故rnd[a]>j)。根據結論2，在round j中沒有選擇任何值。是以滿足C(i,v)。說白了，round j到現在還沒有選擇一個值，而大多數rnd[a]已經大于j，不可能再為round j接受一個值，是以，round j不可能選擇一個值了。
• j=k: 對于Q裡的任意acceptor a，rnd[a]>j(因為a在步驟1a中已經回複了1b消息，故rnd[a]>=i，i>k=j，故rnd[a]>j)，并且，a在round j中要麼接受了v=vval[aX](若vrnd[a]=k)，要麼沒有接受任何值(若rnd[a]<j)，根據結論3，在round j被選擇或可能被選擇的隻能是v=vval[aX]。
• j<k: 如果w(w!=v)在round j被選擇：那麼在round k中，步驟2a中一定會預選w，是以round k不可能選擇v，沖突；也可以通過歸納法證明：因為在round k中接受了值v，那麼在round j (j<j)中，被選擇或可能被選擇的隻能是v。 也就是說，在衆多小于k的1b消息中，有可能有多個值，但是沒有一個被選擇或可能被選擇。 

至此，我們已經完成了paxos算法safty requirement的證明，後續的文章中會介紹如何滿足progress requirement。