Categories
程式開發

分佈式系統全景分析:從故障容錯到拜占庭容錯


注意:

下面提到的節點根據上下文有不同的含義,說到zookeeper時主要是指註冊在zookeeper的不同類型的znode,說到集群時是指集群的不同實例。

談到分佈式系統就避免不了CAP理論,分區容錯對於分佈式系統並不是一個可選性,多節點因為網絡或自身故障引起通信延遲或丟包,從而導致系統分區時,只能在一致性和可用性之間選一個,想要保持完全一致,對外服務就只能等待,有可能會服務超時。

對於單機系統來說就不存在上述多節點通信的問題,所以排除P,比如關係型數據庫就是取了CA,高可用和強一致性,並且由事務支持延伸出ACID理論。

而分佈式系統基於大量實踐衍生出了BASE理論,從高可用到基本可用Basically Available,從強一致到最終一致性Eventual Consistency,加上軟狀態Soft State, 基本在追求一種平衡,對於一個系統來說如果一直都無法保持一致,基本也是不堪用的了,所以一致性還是基本上都是要追求的,只不過根據強弱程度可以進一步細分。

思維比較縝密的讀者對於eventual consistency可能會有疑問,是在什麼時間範圍內達到一致,這裡不得不提另一個理論FLP,跟CAP類似,但是從另外一個角度解讀,包含safety, liveness, fault tolerance, liveness用來指示分佈式系統內的各個節點必須在合理的時間內in bounded time達成一致。

1.關於一致性

對於一個單機系統,一致性一般是強調在並發請求的情況下,該系統事務級別和會話級別下根據系統的設置表現出來的讀寫的一致或衝突,比如兩個並發事務的讀寫衝突, 比如前面說的關係型數據庫,不考慮主從數據庫單機部署時,一致性的表現是會根據數據庫的隔離水平設置isolation level有所不同,有興趣可以自己查閱。

對於分佈式系統,一致性一般是強調集群內部各個節點上面的相關數據保持同步。

本質上其實都是大同小異,只是說一個是宏觀從集群角度看,一個是從微觀的單機看,分佈式系統當成一個整體看對外部系統來說就是一個大的“單機”系統。

根據角度的不同有很多分類方式,比如根據強弱簡單分為:

  • 強一致性 strong consistency
  • 最終一致性 eventual consistency
  • 弱一致性 weak consistency

還有其他角度更細分的單調讀一致性,單調寫一致性,會話一致性,讀後寫一致性,寫後讀一致性,順序一致性等, 我還看到有人根據協議進行劃分:

  • 留言/多播協議 gossip/multicast protocols,包括redis在內的很多集群都是採用gossip
  • 共識協議 consensus protocols

為了澄清更多的概念,我引用這個分類方式文ref中的一段話:

The former includes things like epidemic broadcast trees, bimodal multicast, SWIM, HyParView, and NeEM. These tend to be eventually consistent and/or stochastic. The latter, which I’ve described in more detail here, includes 2PC/3PC, Paxos, Raft, Zab, and chain replication. These tend to favor strong consistency over availability.

作者也很謹慎的用了tend to,需要說明的是,前者基本上是最終一致沒有什麼問題, 而後者就要分清上下文了,在傳統的分佈式系統上這個說法問題不大,因為傳統的分佈式共識算法是基於故障容錯crash fault tolerance,前提是假設系統中只會存在故障節點(消息會丟失,重複), 而在區塊鏈的世界中,共識算法是基於拜占庭容錯Byzantine fault tolerance,前提是假設系統中存在惡意節點(會發送假消息),基本都是最終一致,而不是強一致;

通過前面關係型數據庫的例子可以看到一個系統的一致性不是固定死的,很多情況下一致性會根據系統的設置或系統的架構不同發生變化,在同一個系統中不同類型的數據也可能有著不同的表現; 單機系統都如此,分佈式系統更是複雜,而對於區塊鏈來說,一致性更加有著豐富的表現,比如比特幣的6個確認,是中本聰基於泊松分佈做的一種類似聯合泊松分佈的概率計算, 以全網千分之一的算力來做惡意節點得出6個確認之後可以忽略不計,當然隨著單節點算力越高,需要的確認也隨之增長。

2.基於故障容錯CFT(Crash fault tolerance或非拜占庭容錯)的分佈式系統

中心化系統有單點故障的風險,所以引入多個節點, 故障容錯的假設是多節點中可能會存在故障節點,消息會丟失或重複,但是不會有發送假消息的惡意節點,因為都是部署在內網的可控節點。

在這種假設前提下,多個節點協同工作方式有兩種思路。

2.1 主備方案和一致性狀態機

2.1.1 主備方案

最直接的想法是指定一個leader,只由leader單節點負責管理競爭資源,然後其他節點作為follower保存副本:

  • 一致性,客戶端寫入數據請求都是交由或轉發給leader處理,所以單節點維護保持了數據寫的一致,所有節點都會接受客戶端的讀請求;
  • 排除單點故障,當某個follower發生故障,leader就將follower從自己的通訊錄中剔除或拉黑,如果該follower再次重新恢復上線,leader會將其再加回通訊錄。

現在出現兩個問題:

1) follower轉發寫數據請求給leader,如果他們轉發的請求互相有衝突呢,比如對同一個數據同時修改;

2) 如何動態選出的leader並且當leader節點發送故障如何從follower中選出leader呢。

這兩個問題都要依賴共識算法解決,比如zookeeper的ZAP協議就是解決這個問題的。

第一個問題解決方法是2PC即兩階段提交協議:

leader直接或間接通過follower收到轉發的寫操作請求,都會按照FIFO順序發送proposal給所有follower,如果收到半數以上的follower的ack響應,leader就會發送commit指令給所有follower(注意leader也是自己的follower)。

第二個問題解決方法是:

每個節點啟動後默認都是looking模式,當leader選出後,其他節點就立即變成follower模式,如果leader崩潰了,則跟followers的心跳連接失敗,follower又會變回looking模式,然後leader崩潰後選舉新leader原則是採用“Use a best-effort leader election algorithm that will elect a leader with the latest history from a quorum of servers.”,具體後面算法講解的leader恢復機制; 每次選舉出新的leader都會有自己的標誌,有的叫term有的叫epoch,主要是為了防止腦裂,比如掛掉的leader或者分區後的leader突然恢復連接,通過這個標誌老leader可以知道自己已經過時了,然後轉換成follower聽從新的leader。

2.1.2 一致性狀態機

一致性狀態機也是基於共識算法的,不過原則上不需要選舉leader節點,實際的算法實現很多還是引入了leader來降低一些問題的實現難度, 總的來說跟主備的側重不同:一個是構建高可用的分佈式主備系統,一個是為了構建分佈式一致性狀態機。

我們首先要從經典的“paxos島兼職議會問題”說起。

希臘島嶼Paxos上通過議會的方式來表決通過法律,議員們通過服務員傳遞紙條的方式交流信息,每個議員都將通過的法律記錄在自己的本子上,需要保證大家記下的法律條款都一致; 問題在於議員和服務員都是兼職的,他們隨時會因為各種事情離開議會大廳,傳遞的消息也可能會重複或丟失,並隨時可能有新的議員進入議會大廳進行法律表決,使用何種方式能夠使得這個表決過程正常進行,且通過的法律不發生矛盾。注意我們假設議員和服務員都是道德高尚的人,不會惡意發送假消息。

解決這個問題的經典故障容錯算法就簡稱paxos,很多其他的基於故障容錯的共識算法都是基於paxos改進演變的,paxos本身也有很多變種, 甚至有這種說法:“there is only one consensus protocol, and that’s Paxos — all other approaches are just broken versions of Paxos” . 所以我們只需要理解一下最基礎的Basic Paxos這個算法的基本原理。

引用斯坦福的教學內容Basic Paxos的基本流程圖。

分佈式系統全景分析:從故障容錯到拜占庭容錯 1

basic paxos是基於2PC兩階段提交協議的,這里首先引入提議者proposer和接受者acceptor作為兩階段的具體實施者,我們用一個機票預訂的例子來講解:

為了簡化描述,假設我們只有5個節點Node1|Node2|Node3|Node4|Node5 ,其中Node1和Node2是proposer角色,然後Node3|Node4|Node5都是acceptor角色, 實際上一個節點可以是多種角色,上面引用的圖中是說broadcast to all servers,實際上對於一個2F+1的節點配置來說,只需要得到F+1個節點響應即可,我們例子中忽略這些細節,集中分析主要的邏輯, 然後算法主要分兩步或兩階段,提議propose和決議commit,第一階段主要是為了將已經落實的最新決議狀態(數據)同步給其他節點(所有proposer),第二階段主要是擋住舊的決議(並落實新決議)
Node1收到客戶端請求Alice要預訂廣州到新加坡的scoot100,座位號選擇A1,
Node1提議者proposer發起一個寫數據的提議proposal:Prepare(【Node1-P-1】),其中P是Proposal,1是編號
(加上標誌Node1是因為每個節點都維護自己的編號,如果Node1同步到其他節點Node2的最新編號是100的話,就會重置自己維護的編碼並加1變成101)
現在Node3|Node4|Node5這三個acceptor都收到了提議proposal,假設當前三個acceptor上面的minProposal=0,acceptedProposal=null,acceptedValue=null,因為minProposal<1此時三個節點都會更新為
minProposal=1,acceptedProposal=null,acceptedValue=null,並返回【P-OK,acceptedProposal=null,acceptedValue=null】,P-OK代表同意這個Proposal
Node1收到了全部是P-OK,而且收到的acceptedProposal=null,acceptedValue=null跟自己的數據沒有衝突,所以開始提出決議commit:Accept(【Node1-C-1,“Alice航班scoot100,座位號A1 ”】)
現在Node3|Node4|Node5這三個acceptor都收到了決議commit,而且1>=minProposal=1,所以三個節點都會更新acceptedProposal=minProposal=1,acceptedValue=“Alice航班scoot100,座位號A1”,並且都返回【C-OK,minProposal=1】;
Node1收到了result=1 判斷result>n 1>1是false,所以沒有問題(注意假設任何一個Acceptor返回的是result>1就證明該Acceptor已經接受了另外一個proposer的更新的一個決議,那麼Node1要立即放棄決議,重新回到第一步)
假設接著Node2收到客戶端請求Bob要預訂同一班次廣州到新加坡的scoot100,座位號也是選擇A1,
假設Node2上面的計數器沒有同步最新的,所以發起一個寫數據的提議proposal:Prepare(【Node2-P-1】)
Node3|Node4|Node5這三個acceptor都收到了提議proposal,因為需要n>minProposal=1但是1>1是false,所以會返回【P-FAIL,acceptedProposal=1,acceptedValue=“Alice航班scoot100,座位號A1”】
Node2收到任何一個P-FAIL後都會同步最新決議,而且acceptedProposal=1,acceptedValue=“Alice航班scoot100,座位號A1”,所以跟自己的數據”Bob航班scoot100,座位號A1″有衝突,所以也是要同步最新決議,
注意,在simple paxos算法中,不管P-FAIL還算P-OK,只要任何一個返回中的acceptedValue有值都要立即同步,因為是代表通過的最新的決議,
所以Node2會同步更新本地的value=“Alice航班scoot100,座位號A1”,並且繼續廣播決議commit:Accept【Node2-C-1,“Alice航班scoot100,座位號A1”】看到這裡可以感覺是無用功,實際上PAXOS算法卻是複雜,而且有很多變種,我們只是講解基本的邏輯,
實際中可以做各種優化,不過這一步可能還真有用,比如可以同步之前掉線的Acceptor節點,要看具體實現中的考慮;
Node3|Node4|Node5這三個acceptor都收到了決議,更新並返回【C-OK,minProposal=1】;
Node2收到了result=1 判斷result>n 1>1是false,所以沒有問題。

目前都是假設節點正常運作,paxos算法的意義就是可以在某些節點崩潰及通信延遲的情況下仍然可以達到最終一致的效果,所以你可以自行想一下如果proposer節點或者acceptor節點掉線會不會影響系統穩定,比較顯然不再贅述, 這裡需要多提一個概念叫做活鎖livelock。

Node1發起一個寫數據的提議proposal:Prepare(【Node1-P-1】),假設Node1已經完成了Prepre,意思是Node3|4|5都返回了,現在開始提交決議【Node1-C-1,Value 】
此時Node2發起一個寫數據的提議proposal:Prepare(【Node2-P-2】),根據前面的分析,Node3|4|5收到後會更新minimalProposal=2,從而會拒絕Node1的決議【Node1- C-1,Value】,
再根據前面的分析,Node1會從頭開始重新提議【Node1-P-3】,
然後剛剛Node2完成了提議,開始提交決議【Node2-C-2,Value】,但是Node3|4|5已經收到了Node1的新提議【Node1-P-3】,所以minimalProposal=3,所以會拒絕Node2的決議【Node2-C-2,Value】,
所以Node2也只好放棄重頭開始重新提議【Node2-P-4】…如此循環,誰也無法成功實現決議。

解決上面的活鎖問題有兩種方法,一個是在每次重頭開始提新提議的時候加一個隨機的delay延遲,這樣會可以給機會讓其中一個proposer成功完成提議和決議; 另一種比較更多采用的做法就是從proposer中選一個leader出來,由leader統一提議決議,避免衝突。

說到這裡,還有一個問題,上面說了對於2F+1個節點,只需要F+1個節點達成一致就可以move forward,即對外部提供服務了,所以paxos為了滿足FLP理論的liveness要求,引入了一個learner的概念。

Acceptor接受決議後會通知給每一個learner節點,learner在判斷已經有F+1個節點達成共識後就可以返回給客戶端以及同步給其他Acceptor節點, 當然paxos算法本身並不保證liveness,只是引入learner可以改善liveness。

PAXOS很經典但是也是比較臭名昭著的複雜,RAFT是其實現的簡化版本,RAFT主要包含選舉leader election和日誌拷貝log replication。

其leader election也是利用心跳和過半數選舉的機制,並且leader也是有第幾代leader的term標誌,ZAP用的是epoch,simple paxos沒有leader概念; 然後log replication跟simple paxos的2PC些許類似,首先所有客戶端的寫請求都會轉發給leader來處理,然後leader寫入日誌,狀態是uncommitted,通過心跳發給所有followers, follower收到後也寫入自己的日誌,狀態是uncommitted,leader等得到過半數的followers的ack響應後將狀態改為committed,然後再通知所有follower,follower收到後也更新數據更改狀態為committed, 注意寫日誌的時候,leader是將請求變成entry,然後每個entry都有一個index值用來保持操作的有序性,類似於ZAP協議中的leader廣播message賦值的單調遞增monotonically increasing unique id的zxid,paxos中則類似每個proposer使用的Ballot Number; 除了系統上線第一次leader election ,後續各種原因觸發的重新選舉都需要一個recovery protocol,term+index,epoch+zxid是為了在leader選舉的時候選擇有著最完美日誌的節點作為leader進行恢復。

下面拿RAFT協議來舉例完善一下前面沒詳細說的分區容錯partition tolerance:

分佈式系統全景分析:從故障容錯到拜占庭容錯 2

可以看到網絡分為兩個分區,兩個leader,他們的時代是不同的一個是term=1一個是term=2,互相不知道彼此,但是由於term=1在更改數據的時候無法得到超過半數的響應, 所以所有數據更改都會處於uncommit未提交狀態;而反之在另一邊term=2這裡,是可以達成共識的; 最後一旦網絡恢復正常,term=1的分區就會發現自己全部過時了,就會放棄自己的uncommit日誌,同步term=2的提交日誌; 由此可見在網絡分區的情況下分佈式狀態機一樣可以實現一致性。

實際上前面“主備方案”中提到的zookeeper本質也是一個狀態機模型,只不過是利用狀態機的狀態實現了主備方案, 從大的角度講zookeeper的ZAP協議分為3個階段,Discovery ,Sync,Boradcast,跟前面這些協議都是大同小異,只需要說下不同點。

和raft的有序性不同,ZAP協議有序性(znode節點操作)不僅體現在採用的FIFO先進先出隊列,還有重新選舉恢復的時候需要Sync。

比如leader在崩潰之前廣播出去的數據(proposal和commit)不會丟失,由leader產生但沒有廣播出去的proposal和commit則跳過,但是如果該leader之後重新被再次選舉為新leader,其上沒有提交的事務需要根據判斷其epoch是否小於當前的epoch,是則丟棄,如果相同則還會被提交。

這也是zookeeper可以作為分佈式框架保證primary order基本順序的信心保證。

RAFT沒有ZAP的sync這個階段,而是靠AppendEntries RPC同步糾正,而paxos算法本身沒有保證有序性paxos run。

2.2 分佈式產品和zookeeper

前面講了很多理論,現在我們落實到市面上的各種分佈式產品,看看具體大家都是如何實現的:

  • 分佈式服務框架 zookeeper的ZAP協議;
  • 分佈式消息隊列集群Kafka;
  • 分佈式計算 spark, storm以及Hadoop mapreduce2.0;
  • 分佈式存儲系統:hbase基於zookeeper, 而ETCD採用RAFT協議;
  • 分佈式任務調度:Elastic-Job等。

挑幾個產品看看它們的架構圖就會發現一種現象,很多產品都是依賴zookeeper,為什麼呢?

簡單回答,不要重複造輪子!

Zookeeper適用的場景:ref

  • 統一命名服務(Name Service)
  • 配置管理(Configuration Management)
  • 集群管理(Group Membership)
  • 共享鎖(Locks):共享鎖在同一個進程中很容易實現,但是在跨進程或者在不同Server之間就不好實現了,依賴zookeeper這樣的分佈式框架實現大大降低難度

3.基於拜占庭容錯BFT(Byzantine fault tolerance)的分佈式賬本技術

分佈式系統全景分析:從故障容錯到拜占庭容錯 3

我們前面的分佈式產品都是部署在內網中,不管是私有云公有云還是自己的機房,都不會給外界暴露端口,一般更不會允許外面的節點隨便連進來,屬於關在籠子裡面的內部系統, 一切的根源都在於以上前提假設都是基於故障容錯的,都是假設不會有惡意節點,因為都是公司內網可控的內部節點。

而區塊鏈技術,又被稱作分佈式賬本技術Distributed Ledger Technology,簡稱DLT,尤其是比特幣作為區塊鏈的第一應用,才算是真正意義上的去中心化分佈式技術,不管是手機,普通電腦,還是礦機,都可以運行一個比特幣節點,隨時加入退出, 甚至你可以惡意篡改比特幣源碼的節點都沒關係,只要算力不超過51%,都不會影響比特幣的正常運行,那麼他的共識算法跟以上的共識算法有什麼區別呢?下面我開始給大家介紹下區塊鏈技術的入門知識。

3.1 區塊鏈分類簡介

單純從技術上來說區塊鏈分為permissioned 和permissionless blockchain,前者是私有鍊和聯盟鏈,後者是公鏈; 如果從去中心化角度來說只有公鏈技術才算區塊鏈,當然這個涉及到關於中心化的辯論,屬於哲學問題,不予討論。

私有鏈基本上沒有任何意義,唯一用武之處就是用來教學演示,對於正常的普通企業用傳統的辦法更高效,如果真的要搞行業級別的集成自然是選擇聯盟鏈, 我就以IBM的hyperledger fabric為代表來講解下聯盟鏈。

直接看核心流程圖,我只是簡略說主要內容,不會講解他的會員系統(節點的加入都是要經過審核後配置到系統中),也不會細分peer節點的類型。

分佈式系統全景分析:從故障容錯到拜占庭容錯 4

客戶端發一個transaction請求,實現了hyperledger sdk的客戶端程序接收請求,驗證後發給peers節點,peers節點驗證並進行endorse簽名然後返回結果給客戶端, 客戶端收到一定數量(一定數量決定於事前設定的policy,比如半數以上)的endorse之後就發起提交請求,將transaction及endorsement一起發給ordering service,又是一種2PC兩階段提交, ordering service排序打包交易到一個區塊再發給peers ,peers會驗證區塊中的每個交易,然後更新賬本。

不過等等,這裡的ordering service聽起來像是一個單節點,不像peers那樣有多個節點,難道是個中心化的排序服務嗎?然後我們看IBM文檔的說法如下:

分佈式系統全景分析:從故障容錯到拜占庭容錯 5

看到沒,關鍵的ordering service可以是一個單節點或者kafka集群,單節點不用說了,kafka集群仍然是基於故障容錯的分佈式產品; 不過共識這塊hyperledger是可以插拔自定義的,實際上V1.4版本引入了RAFT算法,當然也是基於故障容錯的。

近期hyperledger的另外一個產品Sawtooth開始推出PBFT,據說跟fabric不同,Sawtooth可以支持permissionless網絡,有興趣的讀者可以自行研究。

公鏈有兩大代表:區塊鏈第一應用比特幣及支持智能合約的超級計算機以太坊,當然還有EOS,BTS等等其他公鏈,他們的共識算法都是基於解決拜占庭將軍問題的算法, 注意這裡並非特指拜占庭容錯算法BFT或PBFT,而是泛指,區塊鏈的共識算法也經常被稱作trustless consensus,意思是無信任共識,換句話說跟前面那些故障容錯算法的假設不同,對於無信任共識來說節點之間是不可以相互信任的, 會有好節點和發送假消息的壞節點。

3.2 拜占庭將軍問題和實用拜占庭容錯算法PBFT

#拜占庭將軍問題

東羅馬帝國也就是拜占庭帝國國王準備攻打一座城堡, 拜占庭軍隊的多個軍區駐紮在城外,每個軍區都有一個將軍Generals, 由於這些將軍相距很遠只能通過信使messengers傳遞消息, 現在軍隊必須在撤退和進攻兩個命令中達成一致並且同時行動,否則就會被擊敗。

歸納為規則A和B:

A. All loyal generals decide upon the same plan of action. 叛徒可以任意而為,但是忠誠的將軍必須達成一致的計劃agreement(進攻或撤退),所有節點不僅要達成共識而且是要合理的共識agreement;

B. A small number of traitors cannot cause the loyal generals to adopt a bad plan. 我們無須考慮什麼是bad plan,只需要確認忠誠的將軍節點如何做出決定decision。

假設v(i)代表第i個將軍發送的信息,那麼n個將軍的信息就是v(1),…v(n) 所以滿足A很簡單,只需要所有節點按照同一個方法將收到的v (1),…v(n)轉成行動,輸入一樣則輸出一樣。

而對於B,假設最終的決定只有進攻和撤退兩種,那麼第i個將軍的決定可以基於最多的投票, 如果叛徒節點多到剛好讓誠實的節點平均分成攻擊和撤退兩個陣營則第i個將軍無法做出決定。

A的前提可以歸納為條件1:

condition1:每個節點都收到同樣的v(1),…v(n), 但是有可能所有的誠實節點都是發送進攻的消息,但是一部分叛徒會導致誠實節點發送retreat。

為了滿足B歸納出條件2:

condition2:如果第i個節點是忠誠的,那麼發送的v(i)必須被每個忠誠的節點使用。

結合condition2,我們可以重寫condition1變成condition1’:任意兩個忠誠的節點都使用相同的v(i)。

至此,condition1’和condition2都是基於第i個將軍發送的信息v(i),所以到這裡我們可以把問題轉化成:一個將軍節點如何發送信息給其他節點;我們重新組織語言,將問題轉化歸納為:

將軍節點如何發送命令給他的lieutenants副官們,具體來說是一個將軍節點如何發送命令給他的n-1個副官節點,並且滿足以下兩個條件。

IC1. 所有的忠誠副官節點都遵守同一個命令。

IC2. 如果將軍是誠實的,每一個誠實副官都應該遵守將軍發送的命令。

IC1和IC2統稱為interactive consistency conditions交互型一致條件。

分佈式系統全景分析:從故障容錯到拜占庭容錯 6

fig2違背了IC1,所以3個節點中有一個叛徒是無解的,我們由此就證明了對付m個叛徒至少要3m+1個節點,黑人問號,什麼時候證明的?

The proof is by contradiction,很簡單,上面3個節點1個叛徒無解,設m=1,3m=3個節點無解,所以反正法結束!

定義口頭信息算法Oral Message algorithms OM(m), ∀m∈N, m>0,將軍向n-1個副官發送命令,定義函數 majority(v1 ,…,vn-1)的值兩種取法:

假設數值是二元的則取少數服從多數,比如多數是進攻則進攻,否則默認值為撤退;

假設數值是一個可排序序列則選擇中位數;

執行方法是:OM(m)調用n-1次OM(m-1)算法,每一個算法OM(m-1)再分別調用n-2次的OM(m-2),如此直至m=0 。

下面假設m=1,3m+1=4:

分佈式系統全景分析:從故障容錯到拜占庭容錯 7

fig3,OM(m=1)將軍首先發送v給所有節點,然後OM(m=0)副官1發送v給副官2,副官3發送x給副官2,副官2有v1=v2=v,v3= x,v=majority(v,v,x),其他副官同理; 同時還可以判斷出副官3是叛徒。

fig4,OM(m=1)將軍首先分別發送x,y,z給副官1,2,3,OM(m=0),副官1發送x給副官2,副官3發送z給副官2,副官2收到(x,y,z),同理所以每個副官都收到(x,y,z), 可以判斷將軍是叛徒。

#實用拜占庭容錯算法PBFT

分佈式系統全景分析:從故障容錯到拜占庭容錯 8

主節點 p = v mod |R|。 v:視圖編號(類似前面提到的term),|R|節點個數,p:主節點編號 現在R=4,v=0,p=0。

1>.client c客戶端發送請求給主節點0:

REQUEST包含消息內容m,以及消息摘要d(m),客戶端對請求進行簽名; o: 請求的具體操作,t: 請求時客戶端追加的時間戳,c:客戶端標識。

2>.主節點0預準備pre-prepare:

主節點校驗消息簽名並拒絕非法請求; 校驗通過則分配編號n,用於對客戶端請求的排序; 然後多播消息<, m>給其他副本節點: d為客戶端消息摘要,m為消息內容,n是要在範圍區間內的[h, H],用於垃圾回收; 對簽名。

3>.副本節點發送PREPARE:

副本節點1、2、3收到主節點0的PRE-PREPARE消息,校驗並拒絕非法請求: 主節點PRE-PREPARE消息簽名; 當前副本節點是否已經收到了一條在同一v=0下並且編號也是n,但是簽名不同的PRE-PREPARE信息; d與m的摘要是否一致; n是否在區間[h, H]內。

然後副本節點都向其他節點發送prepare消息,i是當前副本節點編號; 節點i對進行簽名; PRE-PREPARE和PREPARE消息寫入log,用於View Change時恢復未完成的操作。

4>.全部節點COMMIT:

所有節點收到PREPARE消息,校驗並拒絕非法請求: 節點PREPARE消息簽名是否正確; 當前節點是否已經收到了同一視圖v下的n; n是否在區間[h, H]內; d是否和當前已收到PRE-PPREPARE中的​​d相同。

節點i等待2f+1個驗證通過的PREPARE消息(對於副本節點來說包括自己)則進入prepared狀態並向其他節點發送commit消息, 節點i對簽名; COMMIT消息寫入日誌,用於View Change時恢復未完成的操作。

5>.全部節點REPLY:

所有節點收到COMMIT消息,校驗並拒絕非法請求: 節點COMMIT消息簽名是否正確; 當前節點是否已經收到了同一視圖v下的n; d與m的摘要是否一致; n是否在區間[h, H]內。

節點i等待2f+1個驗證通過的COMMIT消息(包括自己),進入commit狀態,說明當前網絡中的大部分節點已經達成共識,運行客戶端的請求操作o,並返回給客戶端, r是請求操作結果。

6>.客戶端client c等待f+1個reply 如果收到f+1個相同的REPLY消息,說明請求已經達成全網共識,否則客戶端需要判斷是否重新發送請求給主節點; 記錄節點發送的COMMIT消息到log中。

算法其他細節:垃圾回收,視圖更改請自行查閱,不是討論重點。

幾個問題:

  • i.為什麼需要一個primary節點 ?

    PBFT的理論之一primary-backup [Alsberg and Day 1976] 跟paxos和raft類似的思想,用leader節點可以避免多個proposer的衝突,以及排序client端的請求,降低算法實現難度,比如恢復,在PBFT的概念裡epoch或term變成了view,然後leader叫做primary ,其他的follower叫做backups, 主節點負責將來自Client的請求給排好序,然後按序發送給備份節點; 如果主節點可能會是惡意節點,比如給不同的請求編上相同的編號或者不分配編號或者編號跳躍不連續,備份節點會動檢查這些序號的合法性,如果有發現問題,備份節點就會觸發view change協議來選舉出新的主節點,當然備份節點也會通過timeout心跳檢查主節點是不是掛掉。

  • ii.主節點如果是惡意節點,是否可以通過篡改消息來作惡呢,如果是的話又會怎樣 ?

    首先,肯定是可以的,但是要分兩方面來說,如果是篡改客戶端發來的消息,這個是行不通的,會被備份節點通過檢查簽名發現問題,注意一般單純用pbft的都是封閉系統,客戶端也是要經過註冊的, 當然主節點可以完全用自己的私鑰來簽名發起一個惡意的消息,客戶端通過公鑰驗證是肯定通過的,這種情況從算法角度看是無法解決的。

  • iii.為什麼prepare和commit是等待2f+1不是f+1個消息, 對於paxo或raft等基於CFT算法f+1個消息就能少數服從多數過半數確定下一步,但是為什麼PBFT需要2f+1才能確定下一步呢?

    PBFT的理論之一quorum replication [Gifford 1979] 假設節點總數為|R|的共識系統中選擇|Q|個節點作為一個仲裁機制,需要保證這任意兩個Q必須至少得有一個節點交集,不然可能會導致不一樣的共識結果,根據韋恩圖的計算法則: 2|Q| – |R| >= 1 => |Q| >= (|R| + 1) / 2, 對於CFT,|R| = 2 f + 1 => |Q| > = f + 1 這是針對CFT的情況,對於BFT交集還得容納f個惡意節點2|Q| – |R| >= 1 + f => |Q| >= (|R| + f + 1) / 2, |R| = 3 f + 1 => |Q| >= 2f + 1舉個例子,假設f=2,3*2+1=7個節點的情況下,i=0,1,2 ,3,4,5,6 其中5,6是壞節點,假設prepare階段,極端情況每個節點0 1 2 3 4都先收到了5和6的假消息及f個假消息,加上各自節點自己的1個消息, 是f+1個,可見,這種情況下就達成共識就是錯誤的結果或者達不成共識,取決於具體實現,比如至少不應該進入下一步; 對於CTF的f+1,是因為掛掉的節點無法發消息,所以f+1是為了假設半數發的是舊消息proposer,所以過半來做判斷確認半數認為這個消息是可以共識的。

  • iv.為什麼client是等待f+1個reply?

    前面說了根據qurom理論,任意兩個Q至少一個交集,並且允許容納f個惡意節點,所以f+1隱含的意思是即使有f個都是惡意節點,至少一個節點的reply是誠實的,有一個誠實節點隱含著客戶端的操作已經達成共識操作完成。

拜占庭容錯算法有著很多限制:

  • A.需要保證網絡上不超過1/3的節點作惡,1/3的來源是前面拜占庭將軍問題的反證法,另外根據前面的quorum理論也能證明, 對於一個permissioned network比如公司內網或者類似類似hyperledger這有的聯盟鏈來說比較容易監控, 但是對於一個開放式的網絡,每分鐘都可能有節點加入退出,根本無從監控和得知某個時間範圍內到底有多少惡意節點,簡單的數學模型是無法解決這個問題的。

  • B.節點數過多會影響PBFT節點達成共識的速度,我們簡單計算下互相發送的信息數量就大概知道隨著節點增多這種共識方式是不實際的。

    pre-prepare的消息數是接收者排除主節點自己1*(3f+1-1)=3f。

    prepare是【2f3f,3f3f】: 最少:發送者排除主節點和壞節點:3f+1-1-f=2f,接收者排除自己3f+1-1=3f 最多:發送者排除主節點:3f+ 1-1=3f,接收者排除自己3f+1-1=3f。

    commit是【(3f+1-f)(3f+1),(3f+1)3f】; 最少:發送者排除壞節點:3f+1-f=2f+1,接收者排除自己:3f+1 -1=3f 最多:發送者:3f+1,接收者排除自己3f+1-1=3f。

    repy是【2f+1,3f+1】。

  • C.拜占庭容錯算法本身是易於被Sybil attack, 因為默認情況下一個節點不需要花費任何代價就很容易偽造多個身份,由上面我們可以看到節點的區分只是序號i,,當然我們看到除了i之外還有簽名,簽名就涉及用公鑰驗證,如果我們可以保證這些節點是可以“中心化”去管理公私​​鑰配置的就可以防止sybil attack,不過代價是又變回了封閉式的系統,hyerledger, 對於一個closed system只要加上類似的身份控制就可以避免sybil attack,sybil attack只針對”decentralized and permissionless peer to peer network”。

在實際項目中pbft經常是跟其他算法一起使用,比如Zilliqa就是結合pbft和POW,另外PBFT看起來感覺跟paxos有幾分相似,確實,實際上paxos可以升級成BFT paxos,也有raft版本的BFT raft 。

從故障容錯到拜占庭容錯,我們算是跳躍了一步,允許有惡意節點,但是限制為不超過全網1/3的惡意節點, 我們接下來還要再跳躍更大的一步,因為我們要面向全網,不做任何限制:不限制節點數,無法得知惡意節點數,節點可以任意時刻加入退出,同時我們還要保證節點達成正確的共識結果, 下面我們看下比特幣是如何做到的。

3.3 比特幣共識算法

1.第一步 共識的門票:創造隨機事件

首先,比特幣的業務比較簡單(其實可以通過bitcoin script製造很多複雜的場景,具體可以學習Mastering Bitcoin), 基本場景就是Alice給bob轉一定數目的bitcoin。

現在問題是,這麼簡單的一項業務功能,Alice轉給bob 0.1個btc,驗證,打包,落庫(發佈到鏈上,即大部分節點同意把新區塊放到各自的本地最長的區塊鏈頭上),整過過程是誰發起的呢?

開始,Alice通過自己喜歡的比特幣錢包或者命令行(或者自己編寫的比特幣錢包)生成交易,錢包通過P2P協議把簽名好的交易廣播出去,接下來的問題是誰來驗證打包?

我們前面談了那麼多複雜的算法,基本都是要選一個leader出來做事情,而比特幣的目的是節點之間大家都是平等的,沒有leader worker之分,參與節點都有打包的權利,首先為什麼有人想要打包,這是因為有incentive激勵機制,打包成功可以獲取若干比特幣作為獎勵,還可以獲取區塊中每筆交易的費用,繼續打包權利遊戲, 比特幣為此創造了一個猜謎遊戲,我們稱作工作量證明POW,簡單來說,這個遊戲就是定一個目標:打包好的區塊的區塊頭取SHA256哈希值需要小於二進制01000000即64的數值即0到63之間的任何值, 而且找到後要立即全網廣播。

區塊頭包含版本號,上一個區塊的哈希值,默克爾樹根哈希,時間戳,難度目標,隨機值nonce,其中默克爾樹根的哈希簡單來說就是以交易作為葉子節點的哈希樹的樹根,哈希的哈希, 可見這裡面很多變量,所以最終獲取一個小於目標01000000的哈希值是很不容易的事情,找不到就需要調整Nonce值,再不行就需要調整區塊中的交易,總之是一個很激烈的隨機數尋找遊戲, 至於難度值,簡單理解,如果調高,比如目標變成00100000,前面0多了一個,可選的就剩下0到31,縮了一半,靶子越小越難打,如果全網算力提高,比特幣會動態調整難度,保持平均每10分鐘出一個區塊的速度。

一輪遊戲就是代表一個區塊的產生,遊戲又稱挖礦,參與競爭的節點也叫礦工節點。

比特幣創造的這個隨機遊戲,為後面泊松分佈的證明寫下了伏筆。

另外由於比特幣創造性的使用了腳本技術也保證了交易本身無法被篡改,比如最基礎的P2PKH (pay to public key hash):

保險箱scriptPubKey: OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG

解鎖scriptSig:

分佈式系統全景分析:從故障容錯到拜占庭容錯 9

虎符拼起來: OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG ,執行順序:

OP_DUP(PubKey)=PubKey
OP_HASH160(PubKey) = PubKeyHash
OP_EQUALVERIFY(PubKeyHash,PubKeyHash)==TRUE
OP_CHECKSIG(Sig)==TRUE

就是這麼簡潔優美!

當然還有其他的比如P2SH(pay to script hash),在以后區塊鏈的文章裡會再解析,這裡不贅述。

還有一個概念是utxo即未花費輸出unspent transaction output,在比特幣的世界中,比特幣是以utxo的形式存在的,每個比特幣,準確說是每個fraction of bitcoin, 或者每個satoshi(比特幣最小單位)都是以utxo的形式存在腳本保險箱中,只有私鑰的持有者才可以打開保險箱取出utxo使用; 因此解決了拜占庭將軍傳遞假消息的問題,除了私鑰擁有者,沒有人能夠偽造或者篡改交易,從而可以讓交易通過不安全的網絡傳輸,不管是公網還是藍牙設置衛星通信都可以。

好像講到這裡漏了點什麼,對的,我前面說了POW工作量證明的原理以及這個遊戲規則,那麼可能會有很多節點幾乎同時或者先後找到小於目標值的謎底並廣播出去, 那麼這一輪到底誰算獲勝者呢,第一個找到謎底的人?第一個找到並廣播出去的人?

這裡不得不說很多人將POW和POS誤解為共識算法,我在另外一篇文章是專門講了這個問題解密挖礦與共識的誤解

至於誰是某一輪遊戲的獲勝者,還要各位往下接著看。

2.第二步 長鏈勝出:泊松分佈的勝利

揭曉謎底,我們假設當前區塊高度是666666,區塊高度就是目前鏈上的區塊數,假設我們就一條幹乾淨淨的鏈,從第一塊算起,現在是第666666個區塊, 先假設一個極端情況只有M1 M2 M3這3個節點參與挖礦,M1率先打包了一個新的區塊並滿足條件,然後迅速廣播出去, 其他節點收到消息之後full validate block and activate best chain,即驗證區塊中每筆交易的合法性,如果有不合法的則區塊失效, 所以所有節點最開始在接收到交易的時候就應該做驗證,否則後面打包無效交易也是浪費自己的算力, 如果區塊合法,M2和M3就立即connect to the tip並激活best chain,就是將M1打包的區塊作為第666667個區塊加到鏈的頂端。

那麼尋找第666​​667個區塊的遊戲的勝出者就是M1嗎,M1可以立即拿到礦工獎勵嗎?答案是未必,因為現實世界是在M1出包的同時,還有可能上千個其他節點也出包了,甚至是別的節點出包落後,但是網絡比M1的快,更快的覆蓋全網最多的節點, 所以實際上在每個出包的時候,全網節點上的區塊鏈一般都是處於分叉狀態,有的同步到M1,有的同步到比如M100,所以第666667個區塊現在可能有兩個, 那麼就要看下一輪第666668個區塊是誰挖的,假設666668這個區塊是M2挖的,剛好M2又是支持M1的,即666668個區塊是基於M1挖到的666667個區塊之上挖的, 我們說666667這個區塊現在有了2個確認,全網其他節點假設他們上面還是停留在M100的666667個區塊高度,那麼隨著M2的666668的廣播,他們會迅速切換到最長鏈上, 此刻就是以M2為首的666668個區塊。

退一步說再假設區塊666668這個高度的時候,剛好M2挖到的時候又有M200挖到第666668個區塊並且M200是基於M100的第666667挖的,此刻全網仍然是兩條鏈不分伯仲,隨著遊戲的繼續進行,總會分出勝負, 在實際情況下,一般都是一兩個區塊的臨時分叉,不太會有更多的區塊分叉,除非是全球網絡剛好因為災害導致長時間物理隔離成了多個分區,那麼各自分區肯定是各自的長鏈, 隨著網絡恢復,肯定還會選出一個最長鏈,一個區塊是10分鐘,而且前面提到的獎勵確實是挖到新區塊就產生的,但是這個獎勵需要100個確認才能被使用,意思是100×10分鐘=16個多小時, 全球網絡斷開16多個小時除了世界大戰我是想不到還有什麼會造成這個狀況,所以小概率事件可以忽略。

說到這里基本原理都說完了,但是還是缺點東西,因為前面說的都是正常的節點競爭,我們現在談的是基於拜占庭將軍問題的共識,自然少不了惡意節點, 前面又說了因為密碼學保證了惡意節點無法篡改現有交易,但是惡意節點還可以乾另外一件事情。

通過前面分析,我們大概知道比特幣這條鏈因為競爭挖礦時刻處於一兩個區塊的分叉之中,不過一般我們說等待6個確認就可以認為交易成功了,為什麼是6個確認?我們先說惡意節點可以做的一件壞事就是嘗試雙花攻擊double spent,惡意節點首先做一筆交易從evil比特幣賬號賣給Alice 20個比特幣,完全合法的交易,並且Alice的比特幣錢包確實也收到了, 顯示目前是一個確認,然後又等了一會變成2個確認,Alice開心的通知第三方平台把押金釋放給evil的銀行帳號, 其實惡意節點在廣播給Alice20個比特幣之前就悄悄生成了另一筆交易,將那20個比特幣轉給自己的另外一個比特幣地址,並且已經悄悄打包好了一個甚至是多個區塊,Alice不是看到了2個確認嗎, 惡意節點準備了3個區塊,立馬廣播出去,變成最長鏈,Alice看到的兩個確認的區塊作廢,被全網拋棄,全部切換為更長的鏈,惡意節點一毛錢沒花,還掙了3個區塊的礦工獎勵,額外還有Alice的銀行資金。

上面這個理論是成立的,概率有多大呢,跟6個確認又有啥關係呢?

在《Bitcoin: A Peer-to-Peer Electronic Cash System》裡有著清晰的證明,泊松分佈提供了理論依據:

分佈式系統全景分析:從故障容錯到拜占庭容錯 10

泊松分佈比較簡單就不再介紹,當n趨向無窮,及把離散事件變成連續事件,可以推導出泊松分佈公式也不難,至於泊松密度,我的數學也是半桶水,所以就給了比較簡單的註釋:

k>z,每一次隨機事件中攻擊者都會得逞,所以是這裡的泊松密度是1, 而k<=z,攻擊者需要zk個區塊才能追上誠實節點,然後每一個區塊成功的可能是q/p,每次都是獨立的,所以是(q/p)^(zk);

由圖上面的計算可見只要單節點的算力不高,超過5個確認之後,惡意節點成功的概率都會很低。

實際上比特幣作為一個史無前例的社會實驗,是密碼學、軟件、經濟、哲學的混合產物:

“destroying the Bitcoin system will also undermine the effectiveness of his own wealth”

所以對於理性的節點來說,利益驅使下去正常挖礦獲得收益也比想辦法作弊惡意攻擊的收益大的多。

綜上所述,這些理論的總和就構成了nakamoto consensus中本聰共識算法的基礎, 至此我們相對完整的從故障容錯講到拜占庭容錯,從傳統的分佈式系統講到新興的區塊鏈技術,希望對大家有所幫助,話題有點大,難免有所疏漏,歡迎批評指正。

作者介紹

劉躍,現在就職於APEX – Asia Pacific Exchange 亞太交易所(新加坡),目前主要關注系統架構、區塊鏈、滲透測試