區塊鏈技術是近幾年逐漸變得非常熱門的技術，以比特幣為首的密碼貨幣其實已經被無數人所知曉，但是卻很少有人會去研究它們的底層技術，也就是作為一個分布式網絡比特幣等加密貨幣是如何工作的。

無論是 Bitcoin、Ethereum 還是 EOS，作為一個分布式網絡，首先需要解決分布式一致性的問題，也就是所有的節點如何對同一個提案或者值達成共識，這一問題在一個所有節點都是可以被信任的分布式集群中都是一個比較難以解決的問題，更不用說在復雜的區塊鏈網絡中了。

分布式一致性

在一個分布式系統中，如何保證集群中所有節點中的數據完全相同并且能夠對某個提案（Proposal）達成一致是分布式系統正常工作的核心問題，而共識算法就是用來保證分布式系統一致性的方法。

然而分布式系統由于引入了多個節點，所以系統中會出現各種非常復雜的情況；隨著節點數量的增加，節點失效、故障或者宕機就變成了一件非常常見的事情，解決分布式系統中的各種邊界條件和意外情況也增加了解決分布式一致性問題的難度。

在一個分布式系統中，除了節點的失效是會導致一致性不容易達成的主要原因之外，節點之間的網絡通信收到干擾甚至阻斷以及分布式系統的運行速度的差異都是解決分布式系統一致性所面臨的難題。

CAP

在 1998 年的秋天，加州伯克利大學的教授 Eric Brewer 第一次發布了 CAP 理論，在 1999 年論文?Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services?正式發布，其中總結了 Eric Brewer 提出的 CAP 理論。

這篇論文證明了兩個非常有意思的理論，首先是在異步的網絡模型中，所有的節點由于沒有時鐘僅僅能根據接收到的消息作出判斷，這時完全不能同時保證一致性、可用性和分區容錯性，每一個系統只能在這三種特性中選擇兩種。

不過這里討論的一致性其實都是強一致性，也就是所有節點接收到同樣的操作時會按照完全相同的順序執行，被一個節點提交的更新操作會立刻反映在其他通過異步或部分同步網絡連接的節點上，如果想要同時滿足一致性和分區容錯性，在異步的網絡中，我們只能中心化存儲所有數據，通過其他節點將請求路由給中心節點達到這兩個目的。

但是在現實世界中其實并不存在絕對異步的網絡環境，如果我們允許每一個節點擁有自己的時鐘，這些時鐘雖然有著完全不同的時間，但是它們的更新頻率是完全相同的，所以我們可以通過時鐘得知接收消息的間隔時間，在這種更寬松的前提下，我們能夠得到更強大的服務。

然而在部分同步的網絡環境中，我們仍然沒有辦法同時保證一致性、可用性和分區容錯性，證明的過程其實非常簡單，可以直接閱讀?論文?的 4.2 節，然而時鐘的出現能夠讓我們知道當前消息有多久沒有得到回應，通過超時時間就能在一定程度上解決信息丟失的問題。

由于網絡一定會存在延時，所以沒有辦法在分布式系統中做到強一致性的同時保證可用性，不過我們可以通過降低對一致性的要求，在一致性和可用性之間做出權衡，而這其實也是設計分布式系統首先需要考慮的問題，由于強一致性的系統會導致系統的可用性降低，僅僅將接受請求的工作交給其他節點對于高并發的服務并不能解決問題，所以在目前主流的分布式系統中都選擇最終一致性。

最終一致性允許多個節點的狀態出現沖突，但是所有能夠溝通的節點都能夠在有限的時間內解決沖突，從不一致的狀態恢復到一致，這里列出的兩個條件比較重要，一是節點直接可以正常通信，二是沖突需要在有限的時間內解決，只有在這兩個條件成立時才能達到最終一致性。

拜占庭將軍問題

拜占庭將軍問題是 Leslie Lamport 在?The Byzantine Generals Problem?論文中提出的分布式領域的容錯問題，它是分布式領域中最復雜、最嚴格的容錯模型。

在該模型下，系統不會對集群中的節點做任何的限制，它們可以向其他節點發送隨機數據、錯誤數據，也可以選擇不響應其他節點的請求，這些無法預測的行為使得容錯這一問題變得更加復雜。

拜占庭將軍問題描述了一個如下的場景，有一組將軍分別指揮一部分軍隊，每一個將軍都不知道其它將軍是否是可靠的，也不知道其他將軍傳遞的信息是否可靠，但是它們需要通過投票選擇是否要進攻或者撤退：

在這一節中，黃色代表狀態未知，綠色代表進攻，藍色代表撤退，最后紅色代表當前將軍的信息不可靠。

在這時，無論將軍是否可靠，只要所有的將軍達成了統一的方案，選擇進攻或者撤退其實就是沒有任何問題的：

上述的情況不會對當前的戰局有太多的影響，也不會造成損失，但是如果其中的一個將軍告訴其中一部分將軍選擇進攻、另一部分選擇撤退，就會出現非常嚴重的問題了。

由于將軍的隊伍中出了一個叛徒或者信息在傳遞的過程中被攔截，會導致一部分將軍會選擇進攻，剩下的一部分會選擇撤退，它們都認為自己的選擇是大多數人的選擇，這時就出現了嚴重的不一致問題。

拜占庭將軍問題是對分布式系統容錯的最高要求，然而這不是日常工作中使用的大多數分布式系統中會面對的問題，我們遇到更多的還是節點故障宕機或者不響應等情況，這就大大簡化了系統對容錯的要求；不過類似 Bitcoin、Ethereum 等分布式系統確實需要考慮拜占庭容錯的問題，我們會在下面介紹它們是如何解決的。

FLP

FLP 不可能定理是分布式系統領域最重要的定理之一，它給出了一個非常重要的結論：在網絡可靠并且存在節點失效的異步模型系統中，不存在一個可以解決一致性問題的確定性算法。

In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable it delivers all messages correctly and exactly once.

這個定理其實也就是告訴我們不要浪費時間去為異步分布式系統設計在任意場景上都能夠實現共識的算法，異步系統完全沒有辦法保證能在有限時間內達成一致，在這里作者并不會嘗試去證明 FLP 不可能定理，讀者可以閱讀相關論文?Impossibility of Distributed Consensuswith One Faulty Process?了解更多的內容。

共識算法

在上一節中，我們已經簡單了解了分布式系統中面對的問題與挑戰，在這里我們會介紹不同共識算法的實現原理，包括傳統分布式系統領域的 Paxos、Raft 以及密碼貨幣中使用的工作量證明（POW）、權益證明（POS）和委托權益證明（DPOS），通過對這些共識算法原理的介紹和分析，我相信各位讀者能對分布式一致性和共識算法有更深的理解。

Paxos 和 Raft

Paxos 和 Raft 是目前分布式系統領域中兩種非常著名的解決一致性問題的共識算法，兩者都能解決分布式系統中的一致性問題，但是前者的實現與證明非常難以理解，后者的實現比較簡潔并且遵循人的直覺，它的出現就是為了解決 Paxos 難以理解并和難以實現的問題。

我們先來簡單介紹一下?Paxos?究竟是什么，Paxos 其實是一類能夠解決分布式一致性問題的協議，它能夠讓分布式網絡中的節點在出現錯誤時仍然保持一致；Leslie Lamport 提出的 Paxos 可以在沒有惡意節點的前提下保證系統中節點的一致性，也是第一個被證明完備的共識算法，目前的完備的共識算法包括 Raft 本質上都是 Paxos 的變種。

作為一類協議，Paxos 中包含 Basic Paxos、Multi-Paxos、Cheap Paxos 和其他的變種，在這一小節我們會簡單介紹 Basic Paxos 和 Multi-Paxos 這兩種協議。

Basic Paxos

Basic Paxos 是 Paxos 中最為基礎的協議，每一個 Basic Paxos 的協議實例最終都會選擇唯一一個結果；使用 Paxos 作為共識算法的分布式系統中，節點都會有三種身份，分別是 Proposer、Acceptor 和 Learner：

我們在這里會忽略最后一種身份 Learner 簡化協議的運行過程，便于讀者理解；Paxos 的運行過程分為兩個階段，分別是準備階段（Prepare）和接受階段（Accept），當 Proposer 接收到來自客戶端的請求時，就會進入如下流程：

以上截圖取自?Paxos lecture (Raft user study)?的第 12 頁。

在整個共識算法運行的過程中，Proposer 負責提出提案并向 Acceptor 分別發出兩次 RPC 請求，Prepare 和 Accept；Acceptor 會根據其持有的信息?minProposal、acceptedProposal?和?acceptedValue?選擇接受或者拒絕當前的提案，當某一個提案被過半數的 Acceptor 接受之后，我們就認為當前提案被整個集群接受了。

我們簡單舉一個例子介紹 Paxos 是如何在多個提案下保證最終能夠達到一致性的，上述圖片中 S1 和 S5 分別收到了來自客戶端的請求 X 和 Y，S1 首先向 S2 和 S3 發出 Prepare RPC 和 Accept RPC，三個服務器都接受了 S1 的提案 X；在這之后，S5 向 S3 和 S4 服務器發出?Prepare(2.5)?的請求，S3 由于已經接受了 X，所以它會返回接受的提案和值?(1.1, X)，這時服務器使用接收到的提案代替自己的提案 Y，重新向其他服務器發送?Accept(2.5, X)?的 RPC，最終所有的服務器會達成一致并選擇相同的值。

想要了解更多與 Paxos 協議在運行過程中的其他情況可以看一下?Paxos lecture (Raft user study)?視頻。

Multi-Paxos

由于大多數的分布式集群都需要接受一系列的值，如果使用 Basic Paxos 來處理數據流，那么就會導致非常明顯的性能損失，而 Multi-Paxos 是前者的加強版，如果集群中的 Leader 是非常穩定的，那么我們往往不需要準備階段的工作，這樣就能夠將 RPC 的數量減少一半。

上述圖片中描述的就是穩定階段 Multi-Paxos 的處理過程，S1 是整個集群的 Leader，當其他的服務器接收到來自客戶端的請求時，都會將請求轉發給 Leader 進行處理。

當然，Leader 角色的出現自然會帶來另一個問題，也就是 Leader 究竟應該如何選舉，在?Paxos Made Simple?一文中并沒有給出 Multi-Paxos 的具體實現方法和細節，所以不同 Multi-Paxos 的實現上總有各種各樣細微的差別。

Raft

Raft 其實就是 Multi-Paxos 的一個變種，Raft 通過簡化 Multi-Paxos 的模型，實現了一種更容易讓人理解的共識算法，它們兩者都能夠對一系列連續的問題達成一致。

Raft 在 Multi-Paxos 的基礎之上做了兩個限制，首先是 Raft 中追加日志的操作必須是連續的，而 Multi-Paxos 中追加日志的操作是并發的，但是對于節點內部的狀態機來說兩者都是有序的，第二就是 Raft 對 Leader 選舉的條件做了限制，只有擁有最新、最全日志的節點才能夠當選 Leader，但是 Multi-Paxos 由于任意節點都可以寫日志，所以在選擇 Leader 上也沒有什么限制，只是在選擇 Leader 之后需要將 Leader 中的日志補全。

在 Raft 中，所有 Follower 的日志都是 Leader 的子集，而 Multi-Paxos 中的日志并不會做這個保證，由于 Raft 對日志追加的方式和選舉過程進行了限制，所以在實現上會更加容易和簡單。

從理論上來講，支持并發日志追加的 Paxos 會比 Raft 有更優秀的性能，不過其理解和實現上還是比較復雜的，很多人都會說 Paxos 是科學，而 Raft 是工程，當作者需要去實現一個共識算法，會選擇使用 Raft 和更簡潔的實現，避免因為一些邊界條件而帶來的復雜問題。

這篇文章并不會展開介紹 Raft 的實現過程和細節，如果對 Raft 有興趣的讀者可以在?The Raft Consensus Algorithm?找到非常多的資料。

POW(Proof-of-Work)

上一節介紹的共識算法，無論是 Paxos 還是 Raft 其實都只能解決非拜占庭將軍容錯的一致性問題，不能夠應對分布式網絡中出現的極端情況，但是這在傳統的分布式系統都不是什么問題，無論是分布式數據庫還是消息隊列集群，它們內部的節點并不會故意的發送錯誤信息，在類似系統中，最常見的問題就是節點失去響應或者失效，所以它們在這種前提下是有效可行的，也是充分的。

這一節介紹的?工作量證明（POW，Proof-of-Work）是一個用于阻止拒絕服務攻擊和類似垃圾郵件等服務錯誤問題的協議，它在 1993 年被 Cynthia Dwork 和 Moni Naor 提出，它能夠幫助分布式系統達到拜占庭容錯。

工作量證明的關鍵特點就是，分布式系統中的請求服務的節點必須解決一個一般難度但是可行（feasible）的問題，但是驗證問題答案的過程對于服務提供者來說卻非常容易，也就是一個不容易解答但是容易驗證的問題。

這種問題通常需要消耗一定的 CPU 時間來計算某個問題的答案，目前最大的區塊鏈網絡 - 比特幣（Bitcoin）就使用了工作量證明的分布式一致性算法，網絡中的所有節點計算通過以下的謎題來獲得當前區塊的記賬權：

SHA-256 作為一個哈希函數，想要通過 SHA-256 函數的輸出推斷出輸入在目前來看可能性是可以忽略不計的，比特幣網絡就需要每一個節點不斷改變?NONCE?來得到不同的結果?HASH，如果得到的 HASH 結果在小于某個范圍，目前（2017.12.17）的難度是：

0x0000000000000000000000000000000000000000000000000000017268d8a21a

也就是如果只計算一次 SHA-256 的值能夠小于上述結果的可能性是?1.37?10?651.37?10?65，當前的全網算力也達到了 13,919 PH/s，這是一個非常恐怖的數字，隨著網絡算力的不斷改變比特幣也會不斷改變當前問題的難度，保證每個區塊被發現的時間在 10min 左右；在整個比特幣網絡中，誰先得到當前問題的答案就能夠獲得這個區塊的記賬權并將當前區塊通過 Gossip 協議發送給盡可能多的比特幣節點。

工作量證明的原理其實非常簡單，比特幣網絡選擇的謎題非常好的適應了工作量證明定義中的問題，比較難以尋找同時又易于證明，我們可以簡單理解為工作量證明防止錯誤或者無效請求的原理就是增加客戶端請求服務的工作量，而適合難度的謎題又能夠保證合法的請求不會受到影響。

由于工作量證明需要消耗大量的算力，同時比特幣大約 10min 才會產生一個區塊，區塊的大小也只有 1MB，僅僅能夠包含 3、4000 筆交易，平均下來每秒只能夠處理 5~7（個位數）筆交易，所以比特幣網絡的擁堵狀況非常嚴重。

POS(Proof-of-Stake)

權益證明是區塊鏈網絡中的使用的另一種共識算法，在基于權益證明的密碼貨幣中，下一個區塊的選擇是根據不同節點的股份和時間進行隨機選擇的。

由于創造新的區塊并不會消耗大量的 CPU，如果它不誠實也不會失去什么，這也就給了很多節點作弊的理由，每一個節點為了最大化利益會在多條鏈上同時挖礦。

在早期的所有權證明算法中，整個網絡只會獎勵創建區塊的節點，不存在任何懲罰，在這時每個節點在創造的多條鏈上同時投票才能夠最大化利益，在這種情況下網絡中的節點很難對一條鏈達成共識。

有兩種辦法能夠解決缺乏利害關系（nothing-at-stake）造成的問題，一種是使用?Slasher?協議，懲罰同時在多條鏈上投票的節點，第二種方法時直接懲罰在錯誤的鏈上創建塊的節點，總而言之就是通過算法之外的事情解決這個問題，引入激勵和懲罰。

與工作量證明相比，權益證明不需要消耗大量的電力就能夠保證區塊鏈網絡的安全性，同時也不需要在每個區塊中創建新的貨幣來激勵礦工參與當前網絡的運行，這也就在一定程度上縮短了達成共識所需要的時間，基于權益證明的 Ethereum 每秒大概能處理 30 筆交易左右。

DPOS(Delegated Proof-of-Stake)

前面介紹的權益證明算法可以將整個區塊鏈網絡理解為一家公司，出資最多、占比最大的人有更多的機會得到話語權（記賬權）；對于小股東來說，千分之幾甚至萬分之幾的股份很難有什么作為，只能得到股份帶來的分紅和收益。

但是在這里介紹的委托權益證明（DPOS，Delegated Proof-of-Stake）能夠讓每一個人選出可以代表自己利益的人參與到記賬權的爭奪中，這樣多個小股東就能夠通過投票選出自己的代理人，保障自己的利益。整個網絡中選舉出的多個節點能夠在 1s 中之內對 99.9% 的交易進行確認，使用委托權益證明的 EOS 能夠每秒處理幾十萬筆交易，同時也能夠比較監管的干預。

在委托權益證明中，每一個參與者都能夠選舉任意數量的節點生成下一個區塊，得票最多的前 N 個節點會被選擇成為區塊的創建者，下一個區塊的創建者就會從這樣一組當選者中隨機選取，除此之外，N 的數量也是由整個網絡投票決定的，所以可以盡可能地保證網絡的去中心化。

總結

在這篇文章中，我們首先介紹了分布式系統中面對的最重要問題，分布式一致性，隨后又介紹了五種不同的共識算法，從解決非拜占庭問題下一致性的 Paxos 和 Raft 到解決拜占庭問題下的 POW、POS 和 DPOS，簡單回憶一下，解決拜占庭問題的多個共識算法的實現反而更加簡單，這是一件非常有意思的事情。

當整個網絡需要實現拜占庭容錯時，僅靠算法確實是比較難以實現的，往往都需要使用其他方面的激勵或者懲罰，讓誠實表現的節點利益最大化才是解決一致性的最佳方案；從工作量證明、權益證明再到委托權益證明，共識算法的不同導致性能也有著非常大的差異，我們可以看到隨著網絡中進行『投票』的節點越少，網絡的處理能力就會越強和性能就會越快，委托權益證明選舉了 N 個節點來保證性能和去中心化程度確實是一件非常聰明的事情。

中心化的網絡確實能夠帶來性能的提升，但是在密碼貨幣中，參與者往往更相信去中心化的機制，因為沒有激勵和懲罰我們并不能保證下一個負責記賬的節點是否是誠實的，由此來看，如何在保證去中心化的同時提升網絡的性能是每一個區塊鏈網絡都需要考慮的事情。

Reference

• Consensus (computer science)
• 區塊鏈共識算法（POW,POS,DPOS,PBFT）介紹和心得
• Paxos 與 Raft
• Proof-of-work system
• Proof-of-stake
• Proof of Stake FAQ · Ethereum Wiki
• Delegated Proof of Stake
• Delegated Proof-of-Stake Consensus
• DPOS共識算法 – 缺失的白皮書
• 共識算法
• CAP theorem
• Paxos Made Simple
• The Raft Consensus Algorithm
• In Search of an Understandable Consensus Algorithm
• 談談 paxos, multi-paxos, raft
• Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
• “Eventual Consistency” vs “Strong Eventual Consistency” vs “Strong Consistency”?
• Impossibility of Distributed Consensuswith One Faulty Process
• The Byzantine Generals Problem
• Byzantine fault tolerance
• A Brief Tour of FLP Impossibility
• Paxos Made Simple
• Neat Algorithms - Paxos
• FLP Impossibility 的證明
• 白話區塊鏈
• Paxos
• Paxos lecture (Raft user study)
• Bitcoin: A Peer-to-Peer Electronic Cash System
• Proof of Stake · Bitcoin Wiki
• Slasher
• Proof of Stake FAQ

關于圖片和轉載

本作品采用 知識共享署名 4.0 國際許可協議進行許可。 轉載時請注明原文鏈接，圖片在使用時請保留圖片中的全部內容，可適當縮放并在引用處附上圖片所在的文章鏈接，圖片使用 Sketch 進行繪制。

關于評論和留言

如果對本文? 分布式一致性與共識算法?的內容有疑問，請在下面的評論系統中留言，謝謝。

原文鏈接：分布式一致性與共識算法 · 面向信仰編程

Follow:?Draveness · GitHub

總結

以上是生活随笔為你收集整理的分布式一致性与共识算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。