iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 9
0

前言

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

  1. Termination: 保證所有參與決策且無故障的節點最終會做一個決定,執行的演算法不會無法終止,也稱為Liveness
  2. Agreement: 當演算法完成時,所有節點都會做相同的決定,不會再變動,也稱為Safety
  3. 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 可以重啟且會記得原本的值。

系統裡的角色

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

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

系統裡的訊息類型

先介紹兩個:

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

演算法流程

Paxos分為兩個 Phase

  1. 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。

  1. 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判斷)。

示例:

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

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

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")
  1. 如果有人沒收到訊息還是可以達成共識嗎,只要過半數就可以!

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了。

小結

今天先將Paxos的情境、系統假設、角色與流程介紹一遍,搭配幾個例子讓大家對他的運作有點感覺。
明天我們會更正式的討論他如何滿足TerminationAgreementValidity

大家可以先想想,根據FLP定理,完美的共識演算法應該不存在,但是感覺Paxos考量了各種情況,似乎完美無缺,真的可以讓分散式系統針對一個結果達成共識。
但是真的是這樣嗎?最後Q2的討論就是一個小提示xD

Reference:
All the pictures are from "System EngineerI&II" Lectures from TU Dresden.
如果非常有興趣可以看看Lamport自己寫的paper
Paxos Made Simple


上一篇
Day 8 - 共識演算法(前言)
下一篇
Day 10 - 共識演算法之虛構的希臘城邦 - Paxos(下)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言