區塊鏈共識演算法 PBFT(拜占庭容錯)、PAXOS、RAFT簡述

區塊鏈共識演算法 PBFT(拜占庭容錯)、PAXOS、RAFT簡述

共識演算法

區塊鏈中最重要的便是共識演算法,比特幣使用的是POS(Proof of Work,工作量證明),以太幣使用的是POS(Proof of Stake,股權證明)使得算理便的不怎麼重要了,而今POS的變體DPOS(Delegated Proof of Stake,股份授權證明)進一步削減算力的浪費,同時也加強了區塊鏈的安全性。
不過,對於不需要貨幣體系的許可鏈或者私有鏈而言,絕對信任的節點,以及高效的需求上述共識演算法並不能夠提供,因此對於這樣的區塊鏈,傳統的一致性演算法成為首選,PBFT(拜占庭容錯)、PAXOS、RAFT。

PBFT(拜占庭容錯)

基於拜占庭將軍問題,一致性的確保主要分為這三個階段:預準備(pre-prepare)、準備(prepare)和確認(commit)。流程如下圖所示:
其中C為傳送請求端,0123為服務端,3為宕機的服務端,具體步驟如下:
1. Request:請求端C傳送請求到任意一節點,這裡是0
2. Pre-Prepare:服務端0收到C的請求後進行廣播,擴散至123
3. Prepare:123,收到後記錄並再次廣播,1->023,2->013,3因為宕機無法廣播
4. Commit:0123節點在Prepare階段,若收到超過一定數量的相同請求,則進入Commit階段,廣播Commit請求
5.Reply:0123節點在Commit階段,若收到超過一定數量的相同請求,則對C進行反饋
根據上述流程,在 N ≥ 3F 1 的情況下一致性是可能解決,N為總計算機數,F為有問題的計算機總數
N=4 F=0 時:
 得到資料最終資料
A1 1 1 11
B1 1 1 11
C1 1 1 11
D1 1 1 11

N=4 F=1 時:
 得到資料最終資料
A1 1 1 01
B1 1 0 11
C1 0 1 11
D0 1 1 11

N=4 F=2 時:
 得到資料最終資料
A1 1 0 0NA
B1 0 0 1NA
C0 0 1 1NA
D0 1 1 0NA

由此可以看出,拜占庭容錯能夠容納將近1/3的錯誤節點誤差,IBM建立的Hyperledger就是使用了該演算法作為共識演算法。

PAXOS

PAXOS是一種基於訊息傳遞且具有高度容錯特性的一致性演算法。
演算法本身用語言描述極其精簡:
phase 1
a) proposer向網路內超過半數的acceptor傳送prepare訊息
b) acceptor正常情況下回復promise訊息
phase 2
a) 在有足夠多acceptor回覆promise訊息時,proposer傳送accept訊息
b) 正常情況下acceptor回覆accepted訊息
PAXOS中有三類角色Proposer、Acceptor及Learner,主要互動過程在Proposer和Acceptor之間,做成圖便如下圖所示:
其中1,2,3,4代表順序。
以下圖描述多Proposer的情況,T代表時間軸,圖中僅畫全一個Proposer與Acceptor的關係:
A3在T1發出accepted給A1,然後在T2收到A5的prepare,在T3的時候A1才通知A5最終結果(稅率10%)。這裡會有兩種情況:
1. A5發來的N5小於A1發出去的N1,那麼A3直接拒絕(reject)A5
2. A5發來的N5大於A1發出去的N1,那麼A3回覆promise,但帶上A1的(N1, 10%)
最終A5也會接受10%
上圖描述,如果已經Promise一個更大的N,那麼會直接Reject更小的N
上述描述了,即使Promise了一個N,如果在未Accepted前,再收到一個更大的N,那麼依舊會Reject那個即使已經Promise的N
總流程圖氪概括如下:
PAXOS協議用於微信PaxosStore中,每分鐘呼叫Paxos協議過程數十億次量級。

RAFT

RAFT核心思想很容易理解,如果數個資料庫,初始狀態一致,只要之後的進行的操作一致,就能保證之後的資料一致。由此RAFT使用的是Log進行同步,並且將伺服器分為三中角色:Leader,Follower,Candidate,相互可以互相轉換。
RAFT從大的角度看,分為兩個過程:
1. 選舉Leader
2. Leader生成Log,並與Follower進行Headbeats同步

選舉Leader

Follower自增當前任期,轉換為Candidate,對自己投票,併發起RequestVote RPC,等待下面三種情形發生;

1. 獲得超過半數伺服器的投票,贏得選舉,成為Leader
2. 另一臺伺服器贏得選舉,並接收到對應的心跳,成為Follower
3. 選舉超時,沒有任何一臺伺服器贏得選舉,自增當前任期,重新發起選舉

同步日誌

Leader接受客戶端請求,Leader更新日誌,並向所有Follower傳送Heatbeats,同步日誌。所有Follwer都有ElectionTimeout,如果在ElectionTimeout時間之內,沒有收到Leader的Headbeats,則認為Leader失效,重新選舉Leader
流程圖示:

安全性保證

1. 日誌的流向只有Leader到Follower,並且Leader不能覆蓋日誌
2. 日誌不是最新者不能成為Candidate
動畫演示RAFT:http://thesecretlivesofdata.com/raft/

總結

以上三種一致性演算法僅僅只是核心思路而已,如果要具體實現當然還有很多方面需要進一步的完善。以上三種演算法都可以作為區塊鏈的共識演算法,並且部分公司已經開始使用,不過最出名的還應屬IBM的Hyperledger使用的PBFT共識演算法。
 得到資料最終資料
A1 1 1 11
B1 1 1 11
C1 1 1 11
D1 1 1 11