本文更接近復(fù)習(xí)筆記，側(cè)重Basic Paxos的整體把握和實(shí)現(xiàn)（Go語言）。系統(tǒng)學(xué)習(xí)建議繼續(xù)閱讀相關(guān)論文^[1]和wiki^[2]。

解決的問題

假設(shè)server group中有N個(gè)server，每個(gè)都可以處理client發(fā)來的請(qǐng)求，但要求這個(gè)group對(duì)外表現(xiàn)一致——即在所有client看來都像是只有一個(gè)server。因此，任何一個(gè)server只有在確定知曉自己的狀態(tài)與其他（大部分）server相同時(shí)才會(huì)處理client的請(qǐng)求。一致性算法（consensus algorithm）是server用來在互相之間針對(duì)某個(gè)問題達(dá)成一致所用的方法，Paxos就是其中的一種。

總體認(rèn)識(shí)

Paxos算法可以理解成一群server來針對(duì)某個(gè)議題（比如變量x的取值）開會(huì)討論，至少有一個(gè)server帶來了自己的提案，最多也可以每個(gè)server都帶來了自己的提案。servers會(huì)按一定的規(guī)則進(jìn)行投票。會(huì)議在大多數(shù)的server對(duì)議題成一致之后結(jié)束。

一些概念

提案（proposal）：server對(duì)“議題”的“想法”（比如“x=2”），每個(gè)提案還會(huì)包含一個(gè)唯一的proposal number；
proposer：提出提案的server；
acceptor：接收提案并選擇是否接受的server
quorum：acceptors的一個(gè)子集，簡言之就是其中的大多數(shù)；

• proposer和acceptor是Paxos算法中為了結(jié)構(gòu)清晰而抽象出來的概念，一般來說代碼實(shí)現(xiàn)的時(shí)候一個(gè)server會(huì)同時(shí)扮演proposer和acceptor的角色

原則

重要的是讓server中的大多數(shù)盡快達(dá)成一致，最終選誰的提案不重要。

過程

算法的介紹和詳細(xì)分析已經(jīng)有很多^[3]，本文直接從偽代碼開始進(jìn)行分析。

-- Paxos Proposer --
# v為該proposer準(zhǔn)備提出的值
proposer(v):
    # 選擇一個(gè)大于當(dāng)前所有n_p的proposal number
    choose n > n_p
    # 將proposal發(fā)送給所有server（包括自己）
    broadcast prepare(n) to all servers
    # 若收到了大多數(shù)的prepare_ok回復(fù)
    if prepare_ok(n, n_a, v_a) from majority:
        # 選擇其中最大的n_a對(duì)應(yīng)的v_a來更新v的值，如果還沒有這樣的值則選擇自己之前準(zhǔn)備的v
        # 注意這里處理的目的是：如果存在已被accept（但還未decide）的值，則選擇其中最新的作為自己的提案值，從而便于盡快達(dá)成一致
        v' = v_a with highest n_a; choose own v otherwise
        # 向所有server發(fā)送accept請(qǐng)求
        send accept(n, v') to all
        # 如果收到了大多數(shù)的accept_ok回復(fù)
        if accept_ok(n) from majority:
            # 對(duì)所有server發(fā)送decided請(qǐng)求
            send decided(v') to all

-- Paxos Acceptor --
每個(gè)acceptor需要維護(hù)的狀態(tài)（需持久存儲(chǔ)以應(yīng)對(duì)機(jī)器故障）:
    n_p: 最小proposal number，小于該數(shù)的proposal直接reject；同時(shí)也是當(dāng)前見過的最高的prepare(n)中的n
    n_a: 已接受的proposal的對(duì)應(yīng)number
    v_a: 已接受的v值

acceptor's prepare(n) handler:
    if n > n_p:
        n_p = n
        reply prepare_ok(n, n_a, v_a)
    else:
        reply prepare_reject

acceptor's accept(n, v) handler:
    if n >= n_p:
        n_p = n
        n_a = n
        v_a = v
        reply accept_ok(n)
    else:
        reply accept_reject

• 實(shí)現(xiàn)代碼中使用RPC進(jìn)行不同server間的通訊，比如prepare請(qǐng)求的發(fā)送實(shí)際上是server1中的prepare()進(jìn)行對(duì)server2中的prepareHandler()的遠(yuǎn)程調(diào)用

func (px *Paxos) prepare(peerIndex int, seq int, proposeNum int) (PrepareReply, error) {
    var reply PrepareReply
    // 準(zhǔn)備參數(shù)
    ...
    // RPC
    ok := call(px.peers[peerIndex], "Paxos.PrepareHandler", args, &reply)
    // 根據(jù)RPC結(jié)果進(jìn)行處理
    if !ok {
        return reply, fmt.Errorf("prepare RPC failed: index: %d, number: %d, seq: %d", peerIndex, proposeNum, seq)
    }
    return reply, nil
}

func (px *Paxos) PrepareHandler(args *PrepareArgs, reply *PrepareReply) error {
    // 根據(jù)args（傳來的參數(shù)）進(jìn)行處理
    ...
    // 根據(jù)處理結(jié)果生成結(jié)果值并存入reply
    ...
    return nil
}

• 幾種情況的流程圖（圖片來源網(wǎng)絡(luò)）
  以下圖為例，其中左側(cè)的X和Y分別為server S1和S5準(zhǔn)備提出的提案中的值（即偽碼中的v）；方框中的表示相應(yīng)Handler操作，比如S2時(shí)間線上的P3.1即表示S2的prepareHandler()被遠(yuǎn)程調(diào)用，傳入的proposal number是3.1，圖中proposal number的構(gòu)成是number + '.' + 'serverId'的形式，即P3.1是由S1的prepare()調(diào)用的；同理，A3.1X表示acceptHandler()被遠(yuǎn)程調(diào)用，同時(shí)傳入的參數(shù)是proposal number 3.1和proposal value X。
  
  例1：S5發(fā)起提案時(shí)大多數(shù)server已接受了同樣的值，S5得知后便將自己提案的值改成同樣的值

例2：S5發(fā)起提案時(shí)大多數(shù)還未達(dá)成一致，但S5看到S3已接受了一個(gè)值，也會(huì)將自己的提案值改成相同的值以便盡快達(dá)成一致

例3：S3在處理P4.5的時(shí)候還沒有accept S1提出的X，之后再處理A3.1X的時(shí)候因?yàn)橐呀?jīng)見過S5 prepare的更大的proposal number (3.1 < 4.5)，所以會(huì)拒絕S1的A3.1X而接受S5的A4.5Y

代碼實(shí)現(xiàn)

上學(xué)期Distributed System課上的一個(gè)lab，類似MIT-6.824的這個(gè)lab。

源碼地址：Github




03/09/18

1. Paxos Made Simple - Leslie Lamport ?

2. Paxos - Wiki ?

3. 如何淺顯易懂地解說 Paxos 的算法？ - GRAYLAMB的回答 - 知乎 ?