Distributed Systems-Paxos

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。 https://blog.csdn.net/feilengcui008/article/details/50347281

本文主要提煉了《Paxos Make Simple》中的一些主要觀點，然後加上自己的了解，使用通俗的語言嘗試做一些解釋。

• 關于Paxos算法背景和一緻性相關問題可以參見原論文
• 算法涉及的主要對象
  • action 對一條記錄(某個變量)的一次操作(這一點隻是本人便于後面了解加上的)
    • 這裡選用操作這個詞，而不是值，因為一個在對某個變量達成某個值的共識前可能已經經過多個更新操作，是以為了差別，使用操作作為每次proposal的對象，而操作的值代表具體的修改動作，而且這也算是狀态機複制(SMR)的一個基本組成單元，個人感覺更易于了解。比如action(log_id, log_content)，log_id全局辨別了此action的唯一性，log_content通常是針對某條記錄的修改，可看做action的值。
  • proposer
    • 發起proposal的機器，注意在Paxos算法中允許多台機器同時發起proposal，并且有可能由于并發擷取”需要達成一緻的下一操作(action)”，進而使得不同的proposal針對同一個”需要達成一緻的下一操作”達成共識，但是算法保證了其達成共識的action的值相同。
  • acceptor
    • 接受來自proposer的proposal，并根據對于proposer的prepare和accept消息做出響應。
  • learner
    • 從錯誤中恢複的機器，需要重新學習出錯之前最後一次accpet的proposal id之後的所有proposal
• Paxos instance
  • 針對某個”需要達成一緻的操作(action)”運作一次Paxos算法的完整過程。
• 算法推導邏輯
  • P0. To ensure data integrity under fault tolerence, a proposal is succeeded only when more than half machines accepted the proposal.
  • notice: P1[a] stands for requirement and algorithm for acceptors; P2[abc] stands for requirement and algorithm for proposer.

  • P1. An acceptor must accept the first proposal that it receives

    => problem : maybe two proposal are proposed at the same time and two less-than-half machine quorums receive separately these two different proposals, then these two proposals can not be succeeded.

    => so we must allow each acceptor to receive multiple proposals for the same value

    => so we must give each proposal a global unique and increasing id

  • P1a. An acceptor can accept a proposal numbered n iff it has not responed to a prepare request having a number greater than n

    => P1a -> P1 because this can ensure acceptor do not receive the before proposals which arrive later

    => so we ignore these proposal whose id is <= accepted and prepared id of acceptors

  • P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v

    => this is because we must ensure there is only a specific value chosen for a specific paxos instance which may contains multiple proposals

  • P2a. if a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v

    => notice: P2a -> P2

  • P2b. if a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v

    => notice: P2b -> P2a -> P2

  • P2c. for any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either
    • (a) no acceptor in S has accepted any proposal numbered less than n

    • (b) v is set to the value of the highest-numbered proposal among all proposals numbered less than n and accepted by the acceptors in S

      => notice: P2c -> P2b -> P2a -> P2

      => this is the specific algorithm for proposer in prepare phase

  • 總結
    • 根據上面的推導，核心的就兩點，P1a和P2c，P1a規定了acceptor的行為，P2c規定了proposer的行為，由于P2c的需求，決定了需要有prepare階段，這階段主要是為了accept階段為目前proposal設定正确的值。

• 算法基本流程

  論文上主要有prepare和accept兩個階段，省略了選action(值)和選proposal id的階段

  • 0.資料結構
    • 每台機器需要記錄最大accpeted的proposal id(latest_accepted_id)和對應的accepted的操作(latest_accepted_action)以及最大promised的proposal id(latest_promised_id)，這些資料需要刷盤。
  • 1.選擇需要達成一緻的操作
    • 來自用戶端的請求，比如 Action{write A 12} => 通常這作為需要達成的某個操作的值，還需要一個全局唯一的id辨別這個操作，比如對于某個log記錄達成一緻，需要尋找下一次需要記錄的log id，這就需要向其他節點詢問其記錄的最近log id，并取最大值+1作為下一次需要達成一緻的”記錄日志這個操作(action)”的action(log) id。而這個過程可能會産生并發問題，即不同的機器可能針對同一個log id發起proposal，這一點後面階段保證了一旦達成了proposal，則後續所有proposal都以相同的操作(值)達成。
  • 2.選擇proposal id
    • proposal id需要保證全局唯一遞增(這個後面補充)。
  • 3.prepare
    • 假設2中選擇的proposal id為n，proposer發送prepare(n)給大多數機器
      • 對于acceptor，如果(n > latest_promised_id) /\ (n > latest_promised_id)
        • 如果acceptor已經有latest_accepted_id(說明之前對于同一個操作已經達到proposal了)，則傳回對應于latest_accepted_id的操作的值，為了accept階段保證目前的proposal和以前已經達成的proposal最終操作值一樣。
        • 如果acceptor沒有latest_accepted_id(說明之前還未達成proposal)，則不用傳回值(accept階段可以使用任意proposed的值)　
        • 令latest_accepted_id = latest_promised_id = n，并保證不再接受proposal id小于latest_promised_id的proposal
      • 否則acceptor傳回拒絕，重新開始算法。
  • 4.accept
    • proposer收到大多數的機器對prepare的回複
      • 如果傳回消息中latest_accepted_action集合不為空，則将目前proposal的action設定為對應于最大latest_accepted_id的latest_accepted_action，發送accept(n, action)消息
      • 如果傳回消息中latest_accepted_action集合為空，則直接使用目前proposal的action(也就是論文中所說的any value)，發送accept(n, action)消息　
    • 如果acceptor收到accept(n, action)消息時
      • latest_promised_id > n(說明有更新的)，則放棄目前proposal，重新進入算法。
      • 否則接受proposal，完成此次proposal
    • 如果proposer收到大多數acceptor的成功消息，則成功傳回給用戶端，否則重新進入算法，由于liveness requirement，一個proposed的value必須eventually chosen，是以要麼用戶端傳回成功，要麼用戶端請求逾時，對于逾時，用戶端需要重新發起讀的請求，此時可能已經成功了，否則繼續重新發逾時請求。
• 幾點輔助了解的說明
  • 多數是為了保證至少會有一台機器記錄了上次達成的proposal的值，這樣保證在不多于n/2台機器挂掉的條件下，在每次proposal的過程中，至少有一台機器有前面所有的proposal值的記錄，進而保證所有的資料的完整。
  • 一輪paxos instance 是針對某個變量的一次操作的，而不是同一個變量。比如針對同一變量的一次操作打一次log，而這個log id應當是唯一的，而且針對這條log可能會有多次proposal，但是隻要有一次proposal已經達成，那麼針對這條log的proposal隻能使用相同的log值更新(這也是為什麼在prepare傳回階段，如果有一個acceptor已經達成過proposal，則傳回其值替換目前proposal值)。
  • 對某個唯一的記錄比如log或者變量的某次操作達成一緻，那麼proposer在發起proposal之前必定要到某個地方取下次需要達成一緻的值，比如下一條日志記錄的id，某個變量的下一個版本(某個變量的下一次操作)。而由于proposer可能有多個，那麼在并發發起proposal時，不同的proposal可能會針對相同的某次操作，這時對于後達成的proposal來說，隻能将其propose的值換為已經達成的proposal的值，而這個過程是通過prepare階段accptor傳回的結果集是否空來判斷的。如果結果集不為空，說明針對此次操作，之前已經達成了一緻，則後續proposal隻能使用相同值；如果為空，那麼可以使用此次proposal的值(也就是論文中所說的any value)。另外，在accept階段，如果有accptor的最小promise　id大于目前proposal id，那麼說明已經有更更大proposal id的proposal先到達了(此時不管之前是否已經達成一緻)，此時需要放棄目前次的proposal

下面給一個一輪Paxos算法的僞代碼：

# 一輪Paxos協定的流程
# 此處為了清晰将proposer和acceptor的邏輯分開寫了，實際上原論文中一個server既可以做proposer也可以做acceptor

# 對每一個值(比如logid唯一的一條日志)可能會同時發起寫請求(比如兩個用戶端并發通路qorumn裡面的兩個server)
# 是以此時這兩個server都是proposer，針對同一條logid發起不同ballot number的決議請求。此時，如果是ballot number 
# 小的那個決議請求先達到多數派，那麼應該保證後到的ballot number的請求使用相同的值。是以Acceptor需要做的事情如下：
# prepare phase:
# 1.如果請求的req_ballot_id比目前server已經應答過的last_ballot_id小，此時直接忽略，因為有更新的投票決議。
# 2.如果請求的req_ballot_id大于等于目前server已經應答過的last_ballot_id，此時使用req_ballot_id更新last_ballot_id，并傳回last_voted_value，注意這個可以是空，說明要麼是目前這個server以前未參與此值的多數派投票，要麼是此值還未達成過多數派投票。
# commit phase:
# 1.如果commit消息資料中的ballot_id與last_ballot_id不同，則放棄
# 2.否則更新相應的值，并寫日志
class Acceptor(object):
    last_ballot_id = None #我正在等着
    last_voted_value = None
    last_voted_ballot_id = None 
    servers = []
    def handleProposalRequest(self, reqData):
        req_ballot_id = reqData.ballot_id
        if req_ballot_id < self.last_ballot_id:
            pass # return nothing 
        else:
            self.last_ballot_id = req_ballot_id 
            return (self.last_ballot_id, self.last_voted_value, self.last_voted_ballot_id)

    def handleCommitRequest(self, reqData):
        commit_ballot_id = reqData.last_sent_ballot_id
        client_value = reqData.client_req_value 
        if commit_ballot_id != self.last_ballot_id:
            pass 
        self.last_ballot_id = self.last_voted_ballot_id = reqData.last_sent_ballot_id
        self.last_voted_value = client_value 
        writelog((self.last_ballot_id, self.last_voted_ballot_id, self.last_voted_value))

    def writelog(self, data):
        pass 

# 1.如果有acceptor接收到其他proposal發出的更大ballot_id的決議請求，那麼放棄此次決議　
# 2.如果為達到多數派，放棄此次決議
# 3.如果acceptor中傳回的last_voted_value不為空，則将目前proposal的值設定為相同值，進入commit階段，否則直接用client_req_value作為值進入commit
class Proposer(object):
    last_sent_ballot_id = None 
    client_req_value = None 
    res_data = []
    servers = []
    quorumn_number = 5

    def sendRequest(self, data):
        pass 
    def sendProposal(self):
        self.last_sent_ballot_id += 1
        reqData.ballot_id = self.last_sent_ballot_id
        for i in self.servers:
            sendRequest(i, reqData)

    def readData(server):
        pass
    def handleEachProposalResponse(self, server):
        resData = self.readData(server)
        self.res_data.append((resData.last_ballot_id, resData.last_voted_value, resData.last_voted_ballot_id))
    def handleProposalResponse(self):
        for i in servers:
            handleEachProposalResponse(servers[i])
        res_ballot_id = max([i[0] for i in self.res_data])
        if res_ballot_id > self.last_sent_ballot_id:
            pass # maybe another proposer has finished a proposal for the value, what should we give back to client? 
        elif len(res_data) < (self.quorumn_number / 2 + 1):
            pass # failed, maybe timeout due to network or server crash?
        else:
            voted_data = [(i[1], i[2]) for i in self.res_data]
            voted_data.sort()
            if voted_data[0][1] is not None:
                self.client_req_value = voted_data[0][1] 
            self.commit((self.last_sent_ballot_id, self.client_req_value))

    def commit(self, reqData):
        pass 
           

• ref:
  • Paxos Made Simple