共識演算法特性

⑴ 詳解分布式共識（一致性）演算法Raft

所謂分布式共識（consensus），與 CAP理論 中的一致性（consistency）其實是異曲同工，就是在分布式系統中，所有節點對同一份數據的認知能夠達成一致。保證集群共識的演算法就叫共識演算法，它與一致性協議這個詞也經常互相通用。

當今最著名的共識演算法就是Paxos演算法。它由Leslie Lamport在1990年提出，很長時間以來都是一致性的事實標准。但是它有兩個不小的缺點：難以理解和證明，難以在實際工程中實現。Google Chubby的工程師就曾有以下的評論：

於是2014年，來自斯坦福的兩位大佬Diego Ongaro與John Ousterhout通過論文 《In Search of an Understandable Consensus Algorithm》 提出了一個新的共識演算法Raft。從題目就可以看出，Raft的特點就是容易理解，在此基礎上也容易實現，因此在real world中，它的應用也比Paxos要廣泛，比較有名的如etcd、Ku等。

Raft為了達到易懂易用的目標，主要做了兩件事：一是分解問題（decomposition），即將復雜的分布式共識問題拆分為 領導選舉 （leader election）、 日誌復制 （log replication）和 安全性 （safety）三個子問題，並分別解決；二是壓縮狀態空間（state space rection），相對於Paxos演算法而言施加了更合理的限制，減少因為系統狀態過多而產生的不確定性。

下面先簡要介紹共識演算法的基礎——復制狀態機，然後就來按順序研究Raft是如何解決三個子問題的。

在共識演算法中，所有伺服器節點都會包含一個有限狀態自動機，名為復制狀態機（replicated state machine）。每個節點都維護著一個復制日誌（replicated logs）的隊列，復制狀態機會按序輸入並執行該隊列中的請求，執行狀態轉換並輸出結果。可見，如果能保證各個節點中日誌的一致性，那麼所有節點狀態機的狀態轉換和輸出也就都一致。共識演算法就是為了保障這種一致性的，下圖示出簡單的復制狀態機及其相關架構。

根據分布式系統的 Quorum機制 與NRW演算法，集群中半數以上節點可用時，就能正確處理分布式事務，因此Raft集群幾乎都使用奇數節點，可以防止腦裂並避免浪費資源。採用ZAB協議的ZooKeeper集群也是如此。

在Raft集群中，任意節點同一時刻只能處於領導者（leader）、跟隨者（follower）、候選者（candidate）三種狀態之一。下圖示出節點狀態的轉移規則。

可見，集群建立時所有節點都是跟隨節點。如果在一定時間過後發現沒有領導節點，就會切換到候選狀態，發起選舉。得到多數票的候選者就會成為領導節點。如果候選節點或當前領導節點發現了更新的領導者，就會主動退回跟隨狀態。

領導節點全權負責管理復制日誌，也就是從客戶端接收請求，復制到跟隨節點，並告訴跟隨節點何時可以處理這些請求。如果領導節點故障或斷開連接，就會重新進行選舉。可見，領導節點的存在大大簡化了共識演算法的設計。

在上面的圖中出現了任期（term）這個詞。領導者並不是一直「在位」的，工作一段時間之後，就會選舉出新的領導者來接替它。

由上圖可見，藍色表示選舉時間段，綠色表示選舉出的領導者在位的時間段，這兩者合起來即稱作一個任期，其計數值是自增的。任期的值就可以在邏輯上充當時間戳，每個節點都會保存一份自己所見的最新任期值，稱為currentTerm。另外，如果因為票數相同，沒能選出領導，就會立即再發起新的選舉。

如果一個或多個跟隨節點在選舉超時（election timeout）內沒有收到領導節點的心跳（一個名為AppendEntries的RPC消息，本意是做日誌復制用途，但此時不攜帶日誌數據），就會發起選舉流程：

根據其他節點回復的消息，會出現如下三種結果：

獲得多數票的節點只要當選，就會立即給其他所有節點發送AppendEntries，避免再次選舉。另外，在同一任期內，每個節點只能投一票，並且先到先得（first-come-first-served），也就是會把票投給RequestVote消息第一個到達的那個節點。

至於上面的第三種情況，也就是所謂「split vote」現象，容易在很多跟隨者變成候選者時出現，因為沒有節點能得到多數票，選舉有可能無限繼續下去。所以，Raft設置的選舉超時並不是完全一樣的，而是有些許隨機性，來盡量使得投票能夠集中到那些較「快」的節點上。

領導節點選舉出來後，集群就可以開始處理客戶端請求了。前面已經說過，每個節點都維護著一個復制日誌的隊列，它們的格式如下圖所示。

可見，日誌由一個個按序排列的entry組成。每個entry內包含有請求的數據，還有該entry產生時的領導任期值。在論文中，每個節點上的日誌隊列用一個數組log[]表示。

當客戶端發來請求時，領導節點首先將其加入自己的日誌隊列，再並行地發送AppendEntries RPC消息給所有跟隨節點。領導節點收到來自多數跟隨者的回復之後，就認為該請求可以提交了（見圖中的commited entries）。然後，領導節點將請求應用（apply）到復制狀態機，並通知跟隨節點也這樣做。這兩步做完後，就不會再回滾。
這種從提交到應用的方式與最基礎的一致性協議——兩階段提交（2PC）有些相似，但Raft只需要多數節點的確認，並不需要全部節點都可用。

注意在上圖中，領導節點和4個跟隨節點的日誌並不完全相同，這可能是由於跟隨節點反應慢、網路狀況差等原因。領導節點會不斷地重試發送AppendEntries，直到所有節點上的日誌達到最終一致，而不實現強一致性。這就是CAP理論中在保證P的情況下，C與A無法兼得的體現。

日誌復制的過程仍然遺留了一個問題：如果領導或者跟隨節點發生異常情況而崩潰，如何保證日誌的最終一致性？它屬於下面的安全性問題中的一部分，稍後會解答它。

安全性是施加在領導選舉、日誌復制兩個解決方案上的約束，用於保證在異常情況下Raft演算法仍然有效，不能破壞一致性，也不能返回錯誤的結果。所有分布式演算法都應保障安全性，在其基礎上再保證活性（liveness）。

Raft協議的安全性保障有5種，分別是：選舉安全性（election safety）、領導者只追加（leader append-only）、日誌匹配（log matching）、領導者完全性（leader completeness）、狀態機安全性（state machine safety） 。下面分別來看。

選舉安全性是指每個任期內只允許選出最多一個領導。如果集群中有多於一個領導，就發生了腦裂（split brain）。根據「領導選舉」一節中的描述，Raft能夠保證選舉安全，因為：

在講解日誌復制時，我們可以明顯地看出，客戶端發出的請求都是插入領導者日誌隊列的尾部，沒有修改或刪除的操作。這樣可以使領導者的行為盡量簡單化，使之沒有任何不確定的行為，同時也作為下一節要說的日誌匹配的基礎。

日誌匹配的具體描述如下。
如果兩個節點的日誌隊列中，兩個entry具有相同的下標和任期值，那麼：

第一點自然由上一節的「領導者只追加」特性來保證，而第二點則由AppendEntries RPC消息的一個簡單機制來保證：每條AppendEntries都會包含最新entry之前那個entry的下標與任期值，如果跟隨節點在對應下標找不到對應任期的日誌，就會拒絕接受並告知領導節點。

有了日誌匹配特性，就可以解決日誌復制中那個遺留問題了。假設由於節點崩潰，跟隨節點的日誌出現了多種異常情況，如下圖。

注意圖中不是6個跟隨節點，而是6種可能的情況。比如a和b是丟失了entry，c和d是有多餘的未提交entry，e和f則是既有丟失又有冗餘。這時領導節點就會找到兩個日誌隊列中最近一條匹配的日誌點，將該點之後跟隨節點的所有日誌都刪除，然後將自己的這部分日誌復制給它。例如對於上圖中的情況e來說，最近一條匹配的日誌下標為5，那麼5之後的所有entry都會被刪除，被替換成領導者的日誌。

領導者完全性是指，如果有一條日誌在某個任期被提交了，那麼它一定會出現在所有任期更大的領導者日誌里。這也是由兩點來決定的：

根據這兩個描述，每次選舉出的領導節點一定包含有最新的日誌，因此只存在跟隨節點從領導節點更新日誌的情況，而不會反過來，這也使得一致性邏輯更加簡化，並且為下面的狀態機安全性提供保證。

狀態機安全性是說，如果一個節點已經向其復制狀態機應用了一條日誌中的請求，那麼對於其他節點的同一下標的日誌，不能應用不同的請求。這句話就很拗口了，因此我們來看一種意外的情況。

這里就有問題了，在時刻c的日誌與新領導者的日誌發生了沖突，此時狀態機是不安全的。
為了解決該問題，Raft不允許領導者在當選後提交「前任」的日誌，而是通過日誌匹配原則，在處理「現任」日誌時將之前的日誌一同提交。具體方法是：在領導者任期開始時，立刻提交一條空的日誌，所以上圖中時刻c的情況不會發生，而是像時刻e一樣先提交任期4的日誌，連帶提交任期2的日誌。就算此時S1再崩潰，S5也不會重新被選舉了。

如果想要更直觀地理解Raft，建議參考 這里 ，是一個用動畫來描述該演算法的網頁，形象生動。

⑵ 簡評三個基於VRF的共識演算法

上交所技術公司  朱立

Algorand、Dfinity和Ouroboros Praos三個共識演算法（Dfinity雖然是項目名，這里用來稱呼其共識演算法也應無不妥）近期較受關注，而且都是基於VRF(Verifiable Random Function) 設計，可以對照學習。Algorand的版本很多，以下單指  1607.01341v9 ，暫稱其為Algorand'（筆者手中另有Algorand的 最新版本 ，其中已對下文提及的幾處問題完成了修正，可與本文參看）。

一、VRF的共性

VRF的意義很好理解——用以完成出塊人（群）的隨機選擇。為此，VRF的返回值應盡力難以預測。先看Algorand'和Dfinity的套路是怎麼做的：大體上是先將前一個隨機數（最初的隨機數卻是協議給定的）和某種代表高度、輪次的變數進行組合，用某種私鑰對之進行簽名（或者是先簽名再組合），最後哈希一下得出最新的隨機數。這樣產生的隨機數旁人很容易驗證其合乎演算法，"V"就這樣得到了；而哈希返回值又是隨機分布的，「R」也因此得到保證。在此過程中，為降低操縱結果的可能性，有兩個注意事項： A) 簽名演算法應當具有唯一性，也就是用同一把私鑰對同樣的信息進行簽名，只有一個合法簽名可以通過驗證——普通的非對稱加解密演算法一般不具備這個屬性，如SM2。如果用的簽名演算法沒有這種uniqueness屬性，那在生成新隨機數的時候就存在通過反復多次嘗試簽名以挑出最有利者的餘地，會降低安全性。 B) 避免在生成新隨機數時將當前塊的數據作為隨機性來源之一，比如引用本塊交易列表的merkle root值等等，因為這樣做會給出塊人嘗試變更打包交易順序、嘗試打包不同交易以產生最有利的新隨機數的餘地。在設計和檢視新的共識演算法時，以上兩個注意事項是要特別留意的。

考察一下VRF的返回結果應該如何運用。目前所見用法中，VRF的返回結果可以用來公開完成節點或節點群體的選擇，也可以私密地完成選擇。以Dfinity為例，它是利用mod操作來唯一、公開地確定一個Group。Algorand'、Ouroboros Praos是私密選擇的範例，大致套路是對VRF的最新返回值，配上輪次等變數後用私鑰進行簽名並哈希，如果哈希值小於某個閾值，節點就可以私密地知道自己被選中。這種方法很可能在網路節點數較多時的表現會更穩定，否則幸運兒個數上下波動會較大，進而影響協議表現，包括空塊和分叉。

二、簡評強同步假設版本的Algorand'

私密選擇提供了較強的抗擊定點攻擊的能力，但由於幸運兒的總數對於任何一個幸運兒都是不能預知的，也因此給後續共識演算法的設計和區塊鏈的優化帶來了困難。Algorand『採用了很強的同步網路假設（同步網路假設下的共識演算法當然容易做一些），要求預先知道網路消息傳播時間的上限：在固定時間內完成對固定比例的用戶的網路傳播。比如要知道，1KB消息，在1秒鍾內完成全網95%的傳播，而1MB消息需要1.5分鍾完成全網95%的傳播。但這個傳輸上限應該如何選擇？ 通過一段時間的統計結果再乘以一個系數這種經驗統計？只能說「感覺上可以」，但如果要嚴謹和安全，Algorand『演算法應該補充證明即使在遭遇DDOS或互聯網擁堵的情況下消息傳播嚴重超限後演算法仍然能夠保證安全——然而這個證明是缺失的。作為對照，Ouroboros Praos公開承認之前在同步網路假設下設計的Ouroboros協議在非同步網路條件下會出錯，所以才又做了Ouroboros Praos；新版本的Algorand承認在弱同步網路時會在不同的塊上達成共識（後續網路恢復強同步時分叉可以得到解決）雲雲，這些都可資參考。

即使我們暫且認可Algorand'演算法可以通過設定一個很大的傳播時間上限來回應上述問題，但隨之而來的是此時可以看出此演算法缺乏一個非常好的特性：Responsiveness。這個特性指的是：若一個協議被設計為在一個較大的傳播時間上限DELTA下工作，但若實際傳播時間是較小的delta，則協議的實際推進步調將只和delta有關，這種協議被稱為Responsive的。具有Responsive特性的共識演算法再配以同步網路假設會非常理想——出於安全，上限可以設置很大，然而協議執行速度只和當時網路條件有關。Algorand'並不具有這種特性。平均而言，Algorand'完成共識所需的消息傳送次數是11輪，每輪如果要確保安全，完成共識的時間就會很長，單個分區的吞吐量就不會太高。當然，架構設計涉及很多取捨，最終評價一個演算法好還是不好還是要回到初心——准備拿來實現的目標是什麼。上述分析只是嘗試客觀地指出Algorand'演算法的幾個少為人知的固有特徵，供讀者自行評估。

三、簡評Dfinity的可擴展性問題

私密選擇並且立即上任的做法，也給系統分片帶來了極大挑戰。Dfinity是明確要做分片(Sharding)的，所以必須直面挑戰。可擴展性問題非常復雜，完整解決這個問題需要通盤考慮網路、存儲、計算三方面的可擴展性——時下大多數區塊鏈3.0項目只注意到計算的分片和可擴展性，忽略了其餘二者，從而不可能真正實現理想的擴展。由於公鏈節點網路帶寬的制約，計算合約所需的數據通常很難迅速地從一個節點拷貝到另一節點，所以就算用VRF實現了飄忽來去的出塊節點選擇，存儲節點是沒法同樣飄逸如風的。明顯的選擇有那麼幾個：全部節點存儲全部數據，不同節點靜態地分配用來存儲不同分區。前者的可擴展性很差，對於後者而言，如果出塊節點漂浮不定且出塊節點還需要完成合約運算，就意味著基於P2P網路來回遠程訪問存儲，性能多半急劇下降；動態決定的出塊節點只完成排序共識，計算能力和存儲捆綁，通過靜態分區提供可擴展性，可能是合理的應對。然而，最可恨的就是「然而」二字——即使如此，系統還存在一處對存儲和網路構成壓力的所在：最終用戶提交的待打包交易。普通公鏈（先不考慮EOS那種）的帶寬有限，如果用戶提交的待打包交易必須粗放型地全網泛濫傳播，那現有網路帶寬可以提供多少TPS？如果出塊節點是靜態分區或者至少提前一段時間公開知曉，事情尚有迴旋餘地；如果出塊節點是如此飄忽不定，而且直到最後一刻也只有這些節點自己知道，那無論是用戶還是出塊節點候選人看起來最直接的應對之道就是全網泛濫傳播全部待打包交易、保存全部待打包交易，這樣帶寬和存儲仍然成為系統瓶頸。

所以這里碰到的，本質上還是安全、可擴展性、去中心化的不可能三角。

四、簡評Ouroboros Praos

BM懟 Ouroboros的文字已經流傳廣泛。BM的話當然有些明顯是不對的，比如Ouroboros的DPOS是指"Dynamic [stake distribution] POS"而不是BM的Delegate POS，但其關於Pareto分布的評論則值得玩味。如果我們仔細瀏覽後出的Ouroboros Praos，可以發現協議的安全假設和安全證明完全沒有考慮經濟博弈因素，因此洋洋灑灑的證明很可能會不得要領而錯過真正需要防護的方向——畢竟一直以來POS/DPOS這些協議的血管裡面流淌的就是基於經濟博弈和人性進行設計的血液。最明顯的例子是在forward secure signature的實現方法上，協議目前的設計是要求每個好的節點自覺主動地安全刪除用過的私鑰，而完全沒有考慮近乎零的私鑰保存成本如何面對bribe attack的誘惑，然而這卻是值得考慮的。除了形式化證明之外，Ouroboros Praos本身並沒有太多值得關注的協議特徵，總體上就是用VRF抽簽結合POS演算法並針對某些安全假設進行了形式化證明，其做事的態度是非常值得贊賞的。

五、總結

這幾個演算法本身頗有創意，也很值得學習。與此同時，在看過以太坊CASPER目前披露的分區技術後，筆者的體會是：區塊鏈3.0的競爭才剛剛開始，從以太坊團隊的技術路線看，他們的技術考量和選擇要比很多宣稱要超越以太坊的團隊來得深刻和全面。如果當真要超越以太坊，還是應該先從理解以太坊開始。

順便感謝趣鏈邱煒偉博士對本文的貢獻！

⑶ 共識演算法（分布式下的一致性演算法)

共識演算法（分布式下的一致性演算法)

業務場景：

達到的效果：可以保證在過半節點正常的情況下，所有的寫入操作不會丟失。

Zab協議並不保證強一致性，也不是弱一致性，而是在一定限度內的強一致性慎轎山。

缺點：

缺點：

區塊鏈1.0時代：比特幣，作用就是去中心化的貨幣，無國界的貨幣，並且可以匿名性的洗錢
區塊鏈2.0時代：代表以太坊，引入了智能合約的概念，發揮其 去中心化和不可篡改的特性，可以實現類似於 追溯、拍賣、投票等業務場景。

區塊鏈技術的實用價值：
無國界虛擬貨幣：比如比特幣

模擬一個拍賣（盲拍）的業務場景（發布一個智能合約）：
https://solidity.readthedocs.io/en/latest/solidity-by-example.html#simple-open-auction

普通拍賣可能存在的問題：

商家A對一件商品公開自己要拍賣，智能合約在規定的時間會開始接收競拍（參與競拍的人需要支付保證金（以太幣）），在競拍結束之後，價格最高的人會完成支付，帆空其它的買家的保證金會全額退回。
然後成功競拍者可以線下去找賣家，證明自己的身份，然後獲得競拍品

優點：

工作量證明（ PoW ）通過計算一個數值（ nonce ），使得拼揍上交易數據後內容的 Hash 值滿足規定的上限。在節點成功找到滿足的Hash值之後，會馬上對全網進行廣播打包區塊，網路的節點收到廣播打包區塊，會立刻對其進行驗證

舉個例子，給定的一個基本的字元串」Hello, world!」，我們給出的工作量要求是，可以在這個字元串後面添加一個叫做nonce的整數值，對變更後（添加nonce)的字元串進行SHA256哈希運算，
如果得到的哈希結果（以16進制的形式表示）是以」0000」開頭的，則驗證通過。為了達到這個工作量證明的目標。我們需要不停的遞增nonce值，對得到的新字元串進行SHA256哈希運算。
按照這個規則，我們需要經過4251次計算才能找到恰好前4位為0的哈希散列。計算完之後，然後廣播到臨近的節點，臨近的節點會先驗算交易是否合法（金額是否異常），再驗證hash值是否滿足要求，都滿足的話，就會把這個數據塊添加到自己的賬本中。

優點：

缺點：

計算難度值會因為 股東持有的 幣齡而降低，為挖礦無形之中提升了壁壘，股東更容易算出結果值（難度更低），從而避免過度的算力競爭，節省電力，提升系統的穩定性。
因為從人性的角度，股東更不願意讓不安全的現象發生（比如攻擊主鏈)，因為會造成信用降低，從而自己的礦幣貶值。讓股東擁有更多的記賬權，讓主鏈更安全寬中。

擴展可以參考我之前寫過的zab專欄博客
https://www.jianshu.com/nb/32551354

⑷ 區塊鏈 --- 共識演算法

PoW演算法是一種防止分布式服務資源被濫用、拒絕服務攻擊的機制。它要求節點進行適量消耗時間和資源的復雜運算，並且其運算結果能被其他節點快速驗算，以耗用時間、能源做擔保，以確保服務與資源被真正的需求所使用。

PoW演算法中最基本的技術原理是使用哈希演算法。假設求哈希值Hash(r)，若原始數據為r（raw），則運算結果為R（Result）。

R = Hash(r)

哈希函數Hash()的特性是，對於任意輸入值r，得出結果R，並且無法從R反推回r。當輸入的原始數據r變動1比特時，其結果R值完全改變。在比特幣的PoW演算法中，引入演算法難度d和隨機值n，得到以下公式：

Rd = Hash(r+n)

該公式要求在填入隨機值n的情況下，計算結果Rd的前d位元組必須為0。由於哈希函數結果的未知性，每個礦工都要做大量運算之後，才能得出正確結果，而算出結果廣播給全網之後，其他節點只需要進行一次哈希運算即可校驗。PoW演算法就是採用這種方式讓計算消耗資源，而校驗僅需一次。

 

PoS演算法要求節點驗證者必須質押一定的資金才有挖礦打包資格，並且區域鏈系統在選定打包節點時使用隨機的方式，當節點質押的資金越多時，其被選定打包區塊的概率越大。

POS模式下，每個幣每天產生1幣齡，比如你持有100個幣，總共持有了30天，那麼，此時你的幣齡就為3000。這個時候，如果你驗證了一個POS區塊，你的幣齡就會被清空為0，同時從區塊中獲得相對應的數字貨幣利息。

節點通過PoS演算法出塊的過程如下：普通的節點要成為出塊節點，首先要進行資產的質押，當輪到自己出塊時，打包區塊，然後向全網廣播，其他驗證節點將會校驗區塊的合法性。

 

DPoS演算法和PoS演算法相似，也採用股份和權益質押。

但不同的是，DPoS演算法採用委託質押的方式，類似於用全民選舉代表的方式選出N個超級節點記賬出塊。

選民把自己的選票投給某個節點，如果某個節點當選記賬節點，那麼該記賬節點往往在獲取出塊獎勵後，可以採用任意方式來回報自己的選民。

這N個記賬節點將輪流出塊，並且節點之間相互監督，如果其作惡，那麼會被扣除質押金。

通過信任少量的誠信節點，可以去除區塊簽名過程中不必要的步驟，提高了交易的速度。
 

拜占庭問題：

拜占庭是古代東羅馬帝國的首都，為了防禦在每塊封地都駐扎一支由單個將軍帶領的軍隊，將軍之間只能靠信差傳遞消息。在戰爭時，所有將軍必須達成共識，決定是否共同開戰。

但是，在軍隊內可能有叛徒，這些人將影響將軍們達成共識。拜占庭將軍問題是指在已知有將軍是叛徒的情況下，剩餘的將軍如何達成一致決策的問題。

BFT：

BFT即拜占庭容錯，拜占庭容錯技術是一類分布式計算領域的容錯技術。拜占庭假設是對現實世界的模型化，由於硬體錯誤、網路擁塞或中斷以及遭到惡意攻擊等原因，計算機和網路可能出現不可預料的行為。拜占庭容錯技術被設計用來處理這些異常行為，並滿足所要解決的問題的規范要求。

拜占庭容錯系統 ：

發生故障的節點被稱為 拜占庭節點 ，而正常的節點即為 非拜占庭節點 。

假設分布式系統擁有n台節點，並假設整個系統拜占庭節點不超過m台（n ≥ 3m + 1），拜占庭容錯系統需要滿足如下兩個條件：

另外，拜占庭容錯系統需要達成如下兩個指標：

PBFT即實用拜占庭容錯演算法，解決了原始拜占庭容錯演算法效率不高的問題，演算法的時間復雜度是O(n^2)，使得在實際系統應用中可以解決拜占庭容錯問題
 

PBFT是一種狀態機副本復制演算法，所有的副本在一個視圖（view）輪換的過程中操作，主節點通過視圖編號以及節點數集合來確定，即：主節點 p = v mod |R|。v：視圖編號，|R|節點個數，p：主節點編號。

PBFT演算法的共識過程如下：客戶端（Client）發起消息請求（request），並廣播轉發至每一個副本節點（Replica），由其中一個主節點（Leader）發起提案消息pre-prepare，並廣播。其他節點獲取原始消息，在校驗完成後發送prepare消息。每個節點收到2f+1個prepare消息，即認為已經准備完畢，並發送commit消息。當節點收到2f+1個commit消息，客戶端收到f+1個相同的reply消息時，說明客戶端發起的請求已經達成全網共識。

具體流程如下 ：

客戶端c向主節點p發送<REQUEST, o, t, c>請求。o: 請求的具體操作，t: 請求時客戶端追加的時間戳，c：客戶端標識。REQUEST: 包含消息內容m，以及消息摘要d(m)。客戶端對請求進行簽名。

主節點收到客戶端的請求，需要進行以下交驗：

a. 客戶端請求消息簽名是否正確。

非法請求丟棄。正確請求，分配一個編號n，編號n主要用於對客戶端的請求進行排序。然後廣播一條<<PRE-PREPARE, v, n, d>, m>消息給其他副本節點。v：視圖編號，d客戶端消息摘要，m消息內容。<PRE-PREPARE, v, n, d>進行主節點簽名。n是要在某一個范圍區間內的[h, H]，具體原因參見 垃圾回收 章節。

副本節點i收到主節點的PRE-PREPARE消息，需要進行以下交驗：

a. 主節點PRE-PREPARE消息簽名是否正確。

b. 當前副本節點是否已經收到了一條在同一v下並且編號也是n，但是簽名不同的PRE-PREPARE信息。

c. d與m的摘要是否一致。

d. n是否在區間[h, H]內。

非法請求丟棄。正確請求，副本節點i向其他節點包括主節點發送一條<PREPARE, v, n, d, i>消息, v, n, d, m與上述PRE-PREPARE消息內容相同，i是當前副本節點編號。<PREPARE, v, n, d, i>進行副本節點i的簽名。記錄PRE-PREPARE和PREPARE消息到log中，用於View Change過程中恢復未完成的請求操作。

主節點和副本節點收到PREPARE消息，需要進行以下交驗：

a. 副本節點PREPARE消息簽名是否正確。

b. 當前副本節點是否已經收到了同一視圖v下的n。

c. n是否在區間[h, H]內。

d. d是否和當前已收到PRE-PPREPARE中的d相同

非法請求丟棄。如果副本節點i收到了2f+1個驗證通過的PREPARE消息，則向其他節點包括主節點發送一條<COMMIT, v, n, d, i>消息，v, n, d, i與上述PREPARE消息內容相同。<COMMIT, v, n, d, i>進行副本節點i的簽名。記錄COMMIT消息到日誌中，用於View Change過程中恢復未完成的請求操作。記錄其他副本節點發送的PREPARE消息到log中。

主節點和副本節點收到COMMIT消息，需要進行以下交驗：

a. 副本節點COMMIT消息簽名是否正確。

b. 當前副本節點是否已經收到了同一視圖v下的n。

c. d與m的摘要是否一致。

d. n是否在區間[h, H]內。

非法請求丟棄。如果副本節點i收到了2f+1個驗證通過的COMMIT消息，說明當前網路中的大部分節點已經達成共識，運行客戶端的請求操作o，並返回<REPLY, v, t, c, i, r>給客戶端，r：是請求操作結果，客戶端如果收到f+1個相同的REPLY消息，說明客戶端發起的請求已經達成全網共識，否則客戶端需要判斷是否重新發送請求給主節點。記錄其他副本節點發送的COMMIT消息到log中。
 

如果主節點作惡，它可能會給不同的請求編上相同的序號，或者不去分配序號，或者讓相鄰的序號不連續。備份節點應當有職責來主動檢查這些序號的合法性。

如果主節點掉線或者作惡不廣播客戶端的請求，客戶端設置超時機制，超時的話，向所有副本節點廣播請求消息。副本節點檢測出主節點作惡或者下線，發起View Change協議。

View Change協議 ：

副本節點向其他節點廣播<VIEW-CHANGE, v+1, n, C , P , i>消息。n是最新的stable checkpoint的編號， C 是 2f+1驗證過的CheckPoint消息集合， P 是當前副本節點未完成的請求的PRE-PREPARE和PREPARE消息集合。

當主節點p = v + 1 mod |R|收到 2f 個有效的VIEW-CHANGE消息後，向其他節點廣播<NEW-VIEW, v+1, V , O >消息。 V 是有效的VIEW-CHANGE消息集合。 O 是主節點重新發起的未經完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的選取規則：

副本節點收到主節點的NEW-VIEW消息，驗證有效性，有效的話，進入v+1狀態，並且開始 O 中的PRE-PREPARE消息處理流程。
 

在上述演算法流程中，為了確保在View Change的過程中，能夠恢復先前的請求，每一個副本節點都記錄一些消息到本地的log中，當執行請求後副本節點需要把之前該請求的記錄消息清除掉。

最簡單的做法是在Reply消息後，再執行一次當前狀態的共識同步，這樣做的成本比較高，因此可以在執行完多條請求K（例如：100條）後執行一次狀態同步。這個狀態同步消息就是CheckPoint消息。

副本節點i發送<CheckPoint, n, d, i>給其他節點，n是當前節點所保留的最後一個視圖請求編號，d是對當前狀態的一個摘要，該CheckPoint消息記錄到log中。如果副本節點i收到了2f+1個驗證過的CheckPoint消息，則清除先前日誌中的消息，並以n作為當前一個stable checkpoint。

這是理想情況，實際上當副本節點i向其他節點發出CheckPoint消息後，其他節點還沒有完成K條請求，所以不會立即對i的請求作出響應，它還會按照自己的節奏，向前行進，但此時發出的CheckPoint並未形成stable。

為了防止i的處理請求過快，設置一個上文提到的 高低水位區間[h, H] 來解決這個問題。低水位h等於上一個stable checkpoint的編號，高水位H = h + L，其中L是我們指定的數值，等於checkpoint周期處理請求數K的整數倍，可以設置為L = 2K。當副本節點i處理請求超過高水位H時，此時就會停止腳步，等待stable checkpoint發生變化，再繼續前進。
 

在區塊鏈場景中，一般適合於對強一致性有要求的私有鏈和聯盟鏈場景。例如，在IBM主導的區塊鏈超級賬本項目中，PBFT是一個可選的共識協議。在Hyperledger的Fabric項目中，共識模塊被設計成可插拔的模塊，支持像PBFT、Raft等共識演算法。
 

 

Raft基於領導者驅動的共識模型，其中將選舉一位傑出的領導者(Leader)，而該Leader將完全負責管理集群，Leader負責管理Raft集群的所有節點之間的復制日誌。
 

下圖中，將在啟動過程中選擇集群的Leader（S1），並為來自客戶端的所有命令/請求提供服務。 Raft集群中的所有節點都維護一個分布式日誌（復制日誌）以存儲和提交由客戶端發出的命令（日誌條目）。 Leader接受來自客戶端的日誌條目，並在Raft集群中的所有關注者（S2，S3，S4，S5）之間復制它們。

在Raft集群中，需要滿足最少數量的節點才能提供預期的級別共識保證， 這也稱為法定人數。 在Raft集群中執行操作所需的最少投票數為 (N / 2 +1) ，其中N是組中成員總數，即 投票至少超過一半 ，這也就是為什麼集群節點通常為奇數的原因。 因此，在上面的示例中，我們至少需要3個節點才能具有共識保證。

如果法定仲裁節點由於任何原因不可用，也就是投票沒有超過半數，則此次協商沒有達成一致，並且無法提交新日誌。

 

數據存儲：Tidb/TiKV

日誌：阿里巴巴的 DLedger

服務發現：Consul& etcd

集群調度：HashiCorp Nomad
 

只能容納故障節點(CFT)，不容納作惡節點

順序投票，只能串列apply，因此高並發場景下性能差
 

Raft通過解決圍繞Leader選舉的三個主要子問題，管理分布式日誌和演算法的安全性功能來解決分布式共識問題。

當我們啟動一個新的Raft集群或某個領導者不可用時，將通過集群中所有成員節點之間協商來選舉一個新的領導者。 因此，在給定的實例中，Raft集群的節點可以處於以下任何狀態: 追隨者(Follower)，候選人(Candidate)或領導者(Leader)。

系統剛開始啟動的時候，所有節點都是follower，在一段時間內如果它們沒有收到Leader的心跳信號，follower就會轉化為Candidate；

如果某個Candidate節點收到大多數節點的票，則這個Candidate就可以轉化為Leader，其餘的Candidate節點都會回到Follower狀態；

一旦一個Leader發現系統中存在一個Leader節點比自己擁有更高的任期(Term)，它就會轉換為Follower。

Raft使用基於心跳的RPC機制來檢測何時開始新的選舉。 在正常期間， Leader 會定期向所有可用的 Follower 發送心跳消息（實際中可能把日誌和心跳一起發過去）。 因此，其他節點以 Follower 狀態啟動，只要它從當前 Leader 那裡收到周期性的心跳，就一直保持在 Follower 狀態。

當 Follower 達到其超時時間時，它將通過以下方式啟動選舉程序：

根據 Candidate 從集群中其他節點收到的響應，可以得出選舉的三個結果。

共識演算法的實現一般是基於復制狀態機（Replicated state machines），何為 復制狀態機 ：

簡單來說： 相同的初識狀態 + 相同的輸入 = 相同的結束狀態 。不同節點要以相同且確定性的函數來處理輸入，而不要引入一下不確定的值，比如本地時間等。使用replicated log是一個很不錯的注意，log具有持久化、保序的特點，是大多數分布式系統的基石。

有了Leader之後，客戶端所有並發的請求可以在Leader這邊形成一個有序的日誌（狀態）序列，以此來表示這些請求的先後處理順序。Leader然後將自己的日誌序列發送Follower，保持整個系統的全局一致性。注意並不是強一致性，而是 最終一致性 。

日誌由有序編號（log index）的日誌條目組成。每個日誌條目包含它被創建時的任期號（term），和日誌中包含的數據組成，日誌包含的數據可以為任何類型，從簡單類型到區塊鏈的區塊。每個日誌條目可以用[ term, index, data]序列對表示，其中term表示任期， index表示索引號，data表示日誌數據。

Leader 嘗試在集群中的大多數節點上執行復制命令。 如果復製成功，則將命令提交給集群，並將響應發送回客戶端。類似兩階段提交(2PC)，不過與2PC的區別在於，leader只需要超過一半節點同意（處於工作狀態）即可。

leader 、 follower 都可能crash，那麼 follower 維護的日誌與 leader 相比可能出現以下情況

當出現了leader與follower不一致的情況，leader強制follower復制自己的log， Leader會從後往前試 ，每次AppendEntries失敗後嘗試前一個日誌條目（遞減nextIndex值）， 直到成功找到每個Follower的日誌一致位置點（基於上述的兩條保證），然後向後逐條覆蓋Followers在該位置之後的條目 。所以丟失的或者多出來的條目可能會持續多個任期。
 

要求候選人的日誌至少與其他節點一樣最新。如果不是，則跟隨者節點將不投票給候選者。

意味著每個提交的條目都必須存在於這些伺服器中的至少一個中。如果候選人的日誌至少與該多數日誌中的其他日誌一樣最新，則它將保存所有已提交的條目，避免了日誌回滾事件的發生。

即任一任期內最多一個leader被選出。這一點非常重要，在一個復制集中任何時刻只能有一個leader。系統中同時有多餘一個leader，被稱之為腦裂（brain split），這是非常嚴重的問題，會導致數據的覆蓋丟失。在raft中，兩點保證了這個屬性：

因此， 某一任期內一定只有一個leader 。
 

當集群中節點的狀態發生變化（集群配置發生變化）時，系統容易受到系統故障。 因此，為防止這種情況，Raft使用了一種稱為兩階段的方法來更改集群成員身份。 因此，在這種方法中，集群在實現新的成員身份配置之前首先更改為中間狀態（稱為聯合共識）。 聯合共識使系統即使在配置之間進行轉換時也可用於響應客戶端請求，它的主要目的是提升分布式系統的可用性。