Day 9 - 共識演算法之虛構的希臘城邦 - Paxos(上)

11th鐵人賽分散式系統一致性 paxos 共識演算法

Jack Lin

2019-09-24 17:00:37

5959 瀏覽

分享至

前言

前面我們提到了共識演算法是達成Strong Consistency的一種做法。
而共識演算法必須滿足以下三個條件:

Termination: 保證所有參與決策且無故障的節點最終會做一個決定，執行的演算法不會無法終止，也稱為Liveness。
Agreement: 當演算法完成時，所有節點都會做相同的決定，不會再變動，也稱為Safety。
Validity: 最終的決議一定是來自某一個參與的節點。

接著FLP Impossibility告訴我們

在Asynchronous網路環境且允許一個節點失效的情況下，任何Consensus protocol無法確保共識在有限時間內完成。

接著我們來看看前面提過的Lamport如何設計出一個雖然沒辦法完全滿足三個條件，但是從工程的角度仍然合乎使用的共識演算法 - Paxos

Paxos

情境

我們先描述最初的一致性情境，我們有一個資料假設為變數v，為了保證Availability，我們準備了一堆replica servers，且Client可以對每一個replica servers去讀寫v的值。而Consistency希望所有replica servers可以保存一樣的結果。

而Paxos演算法是一個共識演算法，追求滿足上面三個條件，讓每個replica servers在執行完Paxos後可以對v值達成共識，決定一個統一的值。並保證如下的一致性，「不存在某個時刻v已經被決定為a，而另一個時刻又被決定為b」，也就是Agreement。

Note: 沒錯，這的確暫時讓Paxos無法解決讓Client多次複寫v值的情境。要讓Client多次覆寫v值，還能達到一致性要搭配replicated state machine，這會在接下來的Raft提到。

System Model

註: Paxos原文將分散式系統的每個節點(參與者)稱為process，這邊沿用。

Processes之間的溝通: 使用訊息溝通。
Network Model: Asynchronous Network Model，訊息的傳遞會延遲，且延遲無上限，但是可以保證最終一定會傳到且無Byzantine failures。
Processes 可以重啟且會記得原本的值。

系統裡的角色

Proposers: 向系統其他processes提出一個v=C，希望大家達成共識v=C
Acceptors: 其餘沒有要發起proposal的processes，負責接收Proposers的提議。

註: 一個process可以同時身兼角色，不影響正確性。

系統裡的訊息類型

先介紹兩個:

Prepare(n): n 為 proposal number (後面解釋)
Accept(n,v): v 為希望達成的共識值

演算法流程

Paxos分為兩個 Phase

Phase1 - Preparation
在這一輪中，Proposers為了接下來的提案可以讓大家接受達成共識，需要先得到過半數人的回應 (先願意聆聽才會接受嘛～)，所以我們必須先盡量地讓過半數的processes願意聆聽某一個Proposers。
- Proposers: 向所有人發送 prepare(n)
  n包含一些metadata，例如: time()、process ID
  n可以比較，比方規定比較process ID大小。
- Acceptors: 收到某個ProposerA prepare(n)訊息，與這一輪從其他Proposers收到的最大那個 proposal N 比較
  - 如果n > N:
    =>
    a. 表示這一個Proposer更好，我願意聽他的，回覆ack(n,(nx,vx))
    b. 令目前最大的N=n
  - 否則:
    => 我當然不聆聽你的proposal，直接無視。

Note:
這裡Acceptor有一個 ack(n,(nx,vx)) 與 vx 值。
ack(n,(nx,vx)): 可以視為向該Proposer保證我收到你的邀請，且接下來我保證不會聆聽比n小的Proposer的話，(nx,vx)是在你之前收到的最大proposal N=nx。
vx: 有些Proposer可能已經收到「過半數」的ack而開始進入phase2，發送v值給Acceptor，此vx即為剛剛收到的最大的proposal N=nx後收到的vx值，如果之前沒有別的proposser，此為null。

Phase2
- Proposers: 等待「過半數」的Acceptors回覆，這時針對從Acceptors收到的 ack(n,(nx,vx)) 我們要做些判斷
  - 如果有恰好一個的vx值不為空:
    表示該Acceptor已經接受了另一個Proposer的v值，為了盡快達成一致，我主動放棄想提議的v
    => 復述vx，傳送 accept(n,vx) 給所有的Acceptors
  - 如果有多個的vx值不為空:
    => 復述有著最大的nx的vx，傳送 accept(n,vx) 給所有的Acceptors
  - 否則:
    => 傳送 accept(n,my-v) 給所有的Acceptors
- Acceptors: 收到 accept(n,v)，但是你想想，此時有可能又有別的Proposer發出邀請或是提議，因此還要判斷
  - 他可能收到prepare(n') n'>n 或是 accept(n',vy) n'>n:
    => 直接忽略
  - 否則:
    => 接受該Proposer的提議v，令此時的N=n且nx=n, vx=v，此時整個系統也達成共識也就是v(下面圖示說明為什麼只要有Acceptor接受了提議，就會達成共識)

圖解演算法:

Phase1 - Preparation
對於Acceptors來說，每一次收到 prepare(n) 都只接收n比目前自己最大的N還大的訊息。

Phase2
到了第二階段，如果Acceptors收到ProposerA發送的accept(n,v) 發現該n比自己的N還小，就直接忽略:

這種情況的發生正是因為

在ProposerA在收到Acceptors ack，準備發送accept(n,v) 時，Acceptors被其他的Proposers發送的 accept(n',v) 或是prepare(n') 複寫掉 (前面Phase2的Acceptor判斷)。

示例:

我們再看更多的例子讓大家熟悉運作模式，並去感覺他的正確性。

我們首先看最簡單最簡單的情境

a. ProposerP 發送 prepare(3)給其他的Acceptors
b. AcceptorsR,S,T 回覆ack(3, -)給 ProposerP
c. ProposerQ 發送 prepare(2)給其他的Acceptors
d. 因為n=2比N=3小，所以都被忽略
e. ProposerP 收到過半數的回覆，因此發送accept(3,v="joy")

如果有人沒收到訊息還是可以達成共識嗎，只要過半數就可以！

a. ProposerQ 發送 prepare(4)給其他的Acceptors，只有AcceptorsR,S收到
b. 但是因為已經過半數 ProposerQ 可以可以發送 accept(4, v="joy")的值
c. 而且因為AcceptorsR,S過半數的Acceptors已經決定v的值，此時phase2結束，共識已經達成是v="joy"
d. 就算ProposerP有一個更大的n=5，而Acceptors也必須更新自己的N=5
e. 但是因為前面規定如果Acceptors的回覆已經有了(nx,vx)，為了達成共識ProposerP必須放棄自己的主張，復述vx="joy"回去，因此共識並不會被破壞。

重點: 也就是說，當有「過半數」的Acceptors回覆了Proposer，且Proposer發送的accept(v="joy")的訊息Acceptors接受了。此時共識已經達成，不會再被破壞，v不會再被改動。

小討論

也許有人會想討論
Q1: 若是ProposerQ發送的accept因為訊息延遲只有AcceptorR收到，而AcceptorS來不及收到，此時會發生什麼事呢?
A1: 回到剛剛phase2的Proposser，只要有一個Acceptor回覆的ack夾帶(nx,vx)，ProposerP仍然必須復述vx，因此仍然會達成共識。

Q2: 若是ProposerQ發送的accept(4,v="joy")被延遲呢？
A2: AcceptorR,S因為先收到ProposerP的prepare(5)，則AcceptorR,S的N被覆寫為5，導致ProposerQ的accept(4,v="joy")會被忽略，此時就看ProposerP的accept了。