知識拓展：區塊鏈技術之共識演算法

望文生義，所謂共識，就是共同的認識，也就是達成一致。

開會表決出的結果是共識，領導的權威是共識，鑽石的價值是共識。更簡單直接一點，如果我們都認為貓咪很可愛，那麼在這件事情上，我們就達成共識。

可以說，人類的發展，就是在互相認可、達成共識中進行的。

從單機到叢集

從單機到叢集，通常有兩種原因：

1.效能不足。 單機處理的能力達到了上限，此時就需要多臺機器一起提供服務，這種情況下，每臺機器就相當於一個分片，各司其職，處理好自己的那部分。

2.可靠性不足。 單機存在風險和隱患，所以需要擴展出多個副本，一起協作，完成使命。這種情況下，多個節點之間，怎麼交流，資料怎麼保持一致，就是值得考慮的。

由於效能不足這部分更像分工合作，基本不涉及共識。所以 我們主要聚焦於可靠性，看看 如何通過共識，解決分片一致性問題 。

多副本共識

從一個分片到多個分片，就會涉及到資料的共識。我們設想一下，如果在現實中，兩個人的資訊要達成一致，有哪些手段呢？

最簡單的一種，就是信任，即我的資訊完全從你那裡得知，你說啥，我認可啥。平常我們的資料庫容災，就是這樣的。

再者就是協商，慣例是少數服從多數，可以用投票決定。

聽起來是不是很簡單，但實際做起來卻不容易。我們的生產環境中，可能會遇到一些很棘手的挑戰。

接下來，我們就來談談從 私有環境、聯盟環境 ，最後到 公有環境 ， 由淺至深 ，會面臨哪些挑戰，應對的方法又是怎麼樣的。

挑戰一：系統異常

做後臺開發的都知道，異常是不可避免的，我們總會遇到系統出現網路、磁碟故障、伺服器宕機這類問題，這些都屬於Crash Fault，而我們需要做到的，就是Crash Fault Tolerance，即在故障情況下也能正常工作。

05

解決方案：Crash Fault Tolerance

經典的CFT演算法包括Paxos、Raft等，這類演算法效能較好、處理速度較快、可以容忍不超過一半的故障節點。

Paxos演算法 是Leslie Lamport於1990年提出的一種基於訊息傳遞且具有高度容錯特性的共識演算法。

它描述的是這樣一個場景：在一座叫Paxos的小島，議會決議島上的所有事務。 議會成員的數量是確定的，每個提案都需要超過 半數的議員同意才能生效 。

議員們通過 信使傳遞訊息來對 議案 進行表決。 但議員可能離開，信使可能走丟，甚至同一封信投遞好幾次 。

在這樣的條件下，我們要怎麼達成共識呢？

Paxos演算法將議員的角色分為 Proposers 、 Acceptors 和 Learners 。由proposers提出提案，通過一系列複雜的互動，最終得到共識。

這裡先不做贅述，大家只需要知道Paxos特點是晦澀複雜，難理解。

Raft演算法 則起源於2013年斯坦福Diego Ongaro和John Ousterhout的一篇論文。

他們覺得Paxos太難理解了，都不知道怎麼向學生講解，於是設計出了Raft這個既便於學生學習又容易上手實現的一致性演算法。

Raft的資料一致性等價於Multi Paxos ，可以用於取代Paxos，並且證明可 以提供與Paxos相同的容錯性以及效能 。

Raft演算法是基於日誌複製的，它將節點分為 Leader 、 Follower 、 Cadidate 三種，由Leader將請求寫入日誌，再通知到其它節點進行復制，以達到狀態的 最終一致， Cadidate 則是Follower進取成為Leader的中間狀態。

Raft協議設計的首要目標是易於理解，所以採用了分解法：Raft流程可分解為 選主、日誌複製、安全性和儲存回收 ，能為在計算機叢集之間部署有限狀態機提供一種通用方法，並確保叢集內的任意節點在某種狀態轉換上保持一致。

關於RAFT，我們目前只需要記住幾點：

1.它將複雜問題轉變為幾個簡單的問題；

2.採用日誌複製演算法；

3.簡單清晰。

挑戰二：害群之馬

解決了CFT問題，在相對安全的網路環境是可以高枕無憂了。注意，我們說的是 相對安全 ，比如平常在公司的內網環境中。

什麼時候不安全呢？

叢集由幾個組織下的不同機房管理，我們把這個環境稱為 聯盟環境 ，這時候就可能會有作惡節點出現。

這些作惡節點輕則會搗亂，不讓大家達成共識，重則釋出惡意的虛假資訊造成危害。

也就是說，如果群眾裡面有壞人，單純的CFT演算法就cover不住了。

這種需要考慮惡意節點的場景，就叫做 拜占庭問題 。

之前提到的RAFT和PAXOS，都不能解決拜占庭問題。

07

解決方案：Byzantine Fault Tolerance

針對拜占庭問題，我們就需要專門的拜占庭演算法。

有小夥伴肯定會問，為什麼叫拜占庭呢？

如果我告訴你拜占庭演算法最早也是由 Leslie Lamport解決的 ，那你一定已經明白了，沒錯，這其實跟Paxos一樣，都是 L esl ie Lamport 藉由一個著名的城市編造一個故事，給我們描述一類問題。

拜占庭故事是這樣的：拜占庭帝國的軍隊都駐紮在敵城外，相隔很遠，每個師都由各自的將軍指揮。 將軍們只能通過信使相互溝通。

在戰爭時期，他們必須制定一個共同的行動計劃，如進攻(Attack)或者撤退(Retreat)，且只有當半數以上的將軍共同發起進攻時才能取得勝利。

然而, 其中一些將軍可能是叛徒，試圖阻止忠誠的將軍達成一致的行動計劃。更糟糕的是，負責訊息傳遞的信使也可能是叛徒，他們可能篡改或偽造訊息，也可能使訊息丟失。

這樣我們又怎麼樣才能達成一致，取得戰爭的勝利呢？

最知名也是最常見的解決方案是PBFT，即 實用拜占庭容錯演算法 ，這種演算法通過三階段的提交，以反覆進行階段確認的做法，可以保證在惡意節點不超過總數三分之一情況下，系統能良好正確的執行下去。

實用拜占庭演算法比起經典的拜占庭演算法，將效能從指數級降低到了多項式級，做了很大程度的優化，這才有了在生產中實踐的可能。

但是也有一些限制，比如需要節點認證，以及節點數量也不建議超過100。

這裡做個瞭解就好，也不過 多贅述了。

挑戰三：海量節點

實用拜占庭容錯演算法，節點通常是固定的，適用於聯盟場景 。但在公有場景下，節點需要能自由增加減少，比如比特幣。

同時出於效能考慮，BFT的節點通常建議不超過100個，而比特幣的節點遍佈全世界，多不勝數，顯然也是滿足不了的。

針對這種公鏈場景，又該如何達成共識呢？

09

解決方案：POW&POS

方法總比問題多，公鏈也有公鏈的共識演算法，最出名的就是POW和POS。

POW（工作量證明） 是比特幣系統採用的共識演算法。

比特幣的共識是通過10分鐘一輪的算力競賽實現的，競賽的勝利者，就獲得一次記賬的權力，並向其他節點同步新增賬本資訊。

當然，其它節點會做驗證，如果記賬節點有任何的作弊行為，都會導致網路的節點驗證不通過，直接丟棄其打包的區塊，這個區塊就無法記錄到總賬本中，作弊的節點耗費的成本就白費了。

由於有這樣巨大的挖礦成本，使得礦工自覺自願地遵守比特幣系統的共識協議，也就確保了整個系統的安全。

說白了，工作量證明是代價驅動。我都付出了這麼大的代價了，如果不能收穫獎勵，則損失巨大，所以我也就沒有了作弊的動機。比特幣最牛逼的地方，就是採取了經濟手段，實現共識。

POS（權益證明） 則走向了另一條路：記賬權取決於積分，積分由幣量和幣齡綜合決定。簡單來說，你擁有的幣越多，幣齡越長，就有越大的概率獲得記賬權。

POS的優點在於礦工不需要去拼算力，因而不會浪費太多算力，效能也高一些。

缺點在於擁有代幣的大戶可以坐享其成，而且所有參與者可以持幣拿利息。賣幣的人也會少了，大家想著存著幣拿利息，也不利於流動性。並且容易產生馬太效應，讓富人越富，窮人越窮，相對來說，POS沒有POW公平。

除了POW、POS，公鏈上還有DPOS、POA、POL等演算法，感興趣的小夥伴可以去了解一下。

總結

共識是分散式領域極具魅力的一個話題，也是區塊鏈的核心內容。

本次給大家介紹了私有環境的Raft、Paxos演算法，聯盟環境的PBFT演算法，以及公鏈情況下的POW、POS演算法。

後續牛牛也會選擇其中比較有代表性的演算法，單獨寫文章進行詳細分析。

點選下方連結檢視往期精彩文章

● 校招進騰訊，二本也可以？

● 騰訊面試題：兔子試毒

● Redis連擊，被打爆了

● 見識了MySQL基礎的天花板

● 用MySQL原理殺瘋了

END

你好，我是牛牛，普通二本畢業。

本科進騰訊，去過外企，肝過頭條。

目前回騰訊擔任高階工程師。

想來騰訊的朋友，可以找我 內推 哦！

點個“贊”和“在看”鼓勵一下嘛~