跳到主要内容

The Part-Time Parliament & Consensus on Transaction Commit

TL;DR​

  • 2PC是Paxos允許0 failure的情境
  • Paxos保證consistency和progress
  • Paxos的所有node都可以當leader
  • Paxos只要majority還work，就可以運作
  • Transaction commit在unpredictable communication delay的假設下，比consensus更難，但實務上我們不會做此假設，所以可以用consensus來處理Transaction commit

Paxos​

Paxos 如何保證 Consistency​

藉由證明，可以得出滿足以下三個properties，就可以保證consistency:

  • B1: 每個ballot都有unique ballot number(global unique id)
  • B2: 任兩個ballot的quorum都有重疊的投票者(majority)
  • B3: 對每個ballot B，只要B的quorum在之前的ballot有投過票，則B的結果就是quorum最近一個ballot的投票結果

Paxos 如何保證 Progress​

要保證progress，必須要有一個node當leader，並且只有leader可以init ballot。leader會發送訊息給non-leader node，non-leader node如果在時間內沒收到leader的訊息，就會發起leader election。

當一個新leader上來以後，它會broadcast這個訊息，被且詢問其他node最後的ballot，確保自己有最新的資訊。

Paxos Protocol (Basic Paxos）​

Phase 1​

Phase 1a

leader挑選挑選它認為所有sent 1a最大的ballot number給所有acceptor

Phase 1b

當acceptor接收到ballot b，如果它有任何低於b number的ballot還沒處理，它就回傳:

  • 收到的最大的1a ballot的number
  • sent的最大的2b ballot number

如果它已經在更大的ballot number perform過action，就無視1a訊息。

Phase 2​

Phase 2a

Free: majority of acceptors都回報沒有sent 2b訊息，leader可以挑選任何value。

Forced: 某些 majority acceptors回報sent 2b訊息，leader需要挑選此2b訊息的value和ballot number。

Phase 2b

當acceptor收到2a訊息，如果它沒收到比此2a訊息ballot number還大的1a訊息或2a訊息，它就accept此訊息，並send 2b訊息給leader。

Phase 3​

如果leader從majority收到2b訊息，它知道這個value被accept，它就broadcast給所有有興趣的processes。

2PC​

Protocol​

2PC state machine

當有client要commit，leader會要求其他節點進入prepared狀態，如果有任何一個node無法進入prepared，就會全體進入aborted。當leader收到所有節點都進入prepared狀態，接著就會要求進入committed狀態，然後等待所有node回報committed。

Paxos vs 2PC​

Paxos Commit​

Paxos是consensus演算法，要拿來transaction commit，需要做兩次的consensus (一次for prepared，另一次for commited)，這種做法的performance不好。

因此Paxos commit稍微做了一點修改，每個RM(resource manager)都配置了一個paxos instance，步驟如下:

  1. RM send BeginCommit message給 leader說要進入prepare
  2. Leader決定要prepare的話，send phase 2a message with value prepared、ballot number 0到 Paxos instance，否則送aborted
  3. 其他instance send either prepared或aborted phase 2b給leader
  4. leader 只要收到majority(F+1)個訊息，就送phase 3訊息給所有instance

Note: 如果consensus是prepared就commit，否則就abort

Performance​

performance comparison

References​