本文分為4個(gè)部分。第一部分講解分布式系統(tǒng)重要的基本概念和理論，第二部分講解拜占庭將軍問(wèn)題，第三部分講解傳統(tǒng)分布式共識(shí)機(jī)制，最后一部分講解區(qū)塊鏈里的共識(shí)機(jī)制。

Part 1 分布式系統(tǒng)的基本概念和重要理論

分布式系統(tǒng)是用計(jì)算機(jī)集群解決問(wèn)題。

1.1 CAP Theorem:

CAP 原理是由 Eric Brewer 2000年時(shí)在ACM組織的一個(gè)研討會(huì)上面提出的猜想，后來(lái)被證明。被認(rèn)為是分布式系統(tǒng)領(lǐng)域的重要原理。

C 是指 Consistency(一致性):
所有節(jié)點(diǎn)在同一個(gè)時(shí)間看到的數(shù)據(jù)是完全相同的。假設(shè)有兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn) A 與節(jié)點(diǎn) B。當(dāng)我們往節(jié)點(diǎn) A 完成寫(xiě)入數(shù)據(jù)操作后，節(jié)點(diǎn) B 隨之可以讀取到相應(yīng)最新的數(shù)據(jù)。

A 是指 Availability(可用性):
要求在有限的時(shí)間內(nèi)，任何非失敗的節(jié)點(diǎn)都能應(yīng)答請(qǐng)求。

P 是指 Partition Tolerance(分區(qū)容忍性):
即使出現(xiàn)信息丟失，網(wǎng)絡(luò)或者節(jié)點(diǎn)失敗，系統(tǒng)仍然能保持運(yùn)作。

CAP 原理表明在分布式系統(tǒng)里，無(wú)法同時(shí)實(shí)現(xiàn)3個(gè)特性，只能弱化其中一個(gè)而實(shí)現(xiàn)另外兩個(gè)特性。
因此要分實(shí)際的應(yīng)用場(chǎng)景去看待這個(gè)問(wèn)題。

CAP

同時(shí)具備 CAP 三種的系統(tǒng)是不存在的，因此可分為三種系統(tǒng)類(lèi)型:

CA (一致性 + 可用性)，比如完全嚴(yán)格的Quorum協(xié)議，例如兩階段提交。
CP (一致性 + 分區(qū)容錯(cuò)性)，比如 Paxos，Raft。
AP (可用性 + 分區(qū)容錯(cuò)性)， 比如使用沖突解決方案的協(xié)議，Dynamo。

CA 和 CP 系統(tǒng)設(shè)計(jì)都提供相同的一致性模型: 強(qiáng)一致性。唯一的區(qū)別是 CA 系統(tǒng)不能容忍任何節(jié)點(diǎn)故障; 一個(gè)CP系統(tǒng)在非拜占庭故障模型中可以容忍多達(dá) 2f + 1 個(gè)節(jié)點(diǎn)的故障(換句話說(shuō)，只要多數(shù) f + 1 保持不變，它就可以容忍少數(shù)節(jié)點(diǎn) f 的故障)。 原因很簡(jiǎn)單：

CA 系統(tǒng)不區(qū)分節(jié)點(diǎn)故障和網(wǎng)絡(luò)故障，因此必須停止接受各處的寫(xiě)入操作以避免引入分歧(多個(gè)副本)。 它不能分辨出遠(yuǎn)程節(jié)點(diǎn)是否關(guān)閉，或者只是網(wǎng)絡(luò)連接是否中斷: 因此唯一安全的做法就是停止接受寫(xiě)入。

CP 系統(tǒng)通過(guò)強(qiáng)制分區(qū)兩側(cè)的不對(duì)稱(chēng)行為來(lái)防止分歧(例如，保持單一副本一致性)。 它只保留大部分分區(qū)，并且要求少數(shù)分區(qū)變得不可用(例如停止接受寫(xiě)入)，這保留了一定程度的可用性(大部分分區(qū))，并且仍然確保單拷貝一致性。

重要的是，CP 系統(tǒng)將網(wǎng)絡(luò)分區(qū)合并到他們的故障模型中，并使用像Paxos，Raft 或 viewstamped 的復(fù)制等算法來(lái)區(qū)分多數(shù)分區(qū)和少數(shù)分區(qū)。 CA 系統(tǒng)不具備分區(qū)感知能力，并且歷史上更常見(jiàn)，它們通常使用兩階段提交算法，在傳統(tǒng)分布式關(guān)系數(shù)據(jù)庫(kù)中很常見(jiàn)。

Part 2 拜占庭將軍問(wèn)題

拜占庭將軍問(wèn)題，討論的是允許存在少數(shù)不誠(chéng)實(shí)節(jié)點(diǎn)(作惡，偽造消息)的場(chǎng)景下達(dá)成一致性的問(wèn)題。
這個(gè)問(wèn)題用文字來(lái)表達(dá)是很難描述清楚的，因此推薦大家看這個(gè)視頻 Byzantine Fault Tolerance 來(lái)了解這個(gè)問(wèn)題?？赐赀@個(gè)視頻，相信你一定會(huì)對(duì)拜占庭問(wèn)題有個(gè)整體清晰的概念。
總的來(lái)說(shuō)，就是當(dāng)叛變者不超過(guò) 3分之1時(shí)，存在有效的算法，不論叛變者怎么折騰搞破壞，忠誠(chéng)的將軍們總能達(dá)到一致的結(jié)果。
用數(shù)學(xué)公式來(lái)表達(dá)就是，假設(shè)節(jié)點(diǎn)總數(shù)為 N, 叛變將軍數(shù)為 F, 當(dāng) N >= 3F + 1，問(wèn)題就有解。
Byzantine Fault Tolerant (BFT) 算法就是解決這個(gè)問(wèn)題的。

Part 3 分布式一致性共識(shí)機(jī)制

1. Paxos

1.1 Paxos算法背景

Paxos算法是Lamport宗師提出的一種基于消息傳遞的分布式一致性算法，使其獲得2013年圖靈獎(jiǎng)。

Paxos由Lamport于1998年在《The Part-Time Parliament》論文中首次公開(kāi)，最初的描述使用希臘的一個(gè)小島Paxos作為比喻，描述了Paxos小島中通過(guò)決議的流程，并以此命名這個(gè)算法，但是這個(gè)描述理解起來(lái)比較有挑戰(zhàn)性。后來(lái)在2001年，Lamport覺(jué)得同行不能理解他的幽默感，于是重新發(fā)表了樸實(shí)的算法描述版本《Paxos Made Simple》。

自Paxos問(wèn)世以來(lái)就持續(xù)壟斷了分布式一致性算法，Paxos這個(gè)名詞幾乎等同于分布式一致性。Google的很多大型分布式系統(tǒng)都采用了Paxos算法來(lái)解決分布式一致性問(wèn)題，如Chubby、Megastore以及Spanner等。開(kāi)源的ZooKeeper，以及MySQL 5.7推出的用來(lái)取代傳統(tǒng)的主從復(fù)制的MySQL Group Replication等紛紛采用Paxos算法解決分布式一致性問(wèn)題。

然而，Paxos的最大特點(diǎn)就是難，不僅難以理解，更難以實(shí)現(xiàn)。

1.2 Paxos算法流程

Paxos算法解決的問(wèn)題正是分布式一致性問(wèn)題，即一個(gè)分布式系統(tǒng)中的各個(gè)進(jìn)程如何就某個(gè)值（決議）達(dá)成一致。

Paxos算法運(yùn)行在允許宕機(jī)故障的異步系統(tǒng)中，不要求可靠的消息傳遞，可容忍消息丟失、延遲、亂序以及重復(fù)。它利用大多數(shù) (Majority) 機(jī)制保證了2F+1的容錯(cuò)能力，即2F+1個(gè)節(jié)點(diǎn)的系統(tǒng)最多允許F個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)故障。

一個(gè)或多個(gè)提議進(jìn)程 (Proposer) 可以發(fā)起提案 (Proposal)，Paxos算法使所有提案中的某一個(gè)提案，在所有進(jìn)程中達(dá)成一致。系統(tǒng)中的多數(shù)派同時(shí)認(rèn)可該提案，即達(dá)成了一致。最多只針對(duì)一個(gè)確定的提案達(dá)成一致。

Paxos將系統(tǒng)中的角色分為提議者 (Proposer)，決策者 (Acceptor)，和最終決策學(xué)習(xí)者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案編號(hào) (Proposal ID) 和提議的值 (Value)。
• Acceptor：參與決策，回應(yīng)Proposers的提案。收到Proposal后可以接受提案，若Proposal獲得多數(shù)Acceptors的接受，則稱(chēng)該P(yáng)roposal被批準(zhǔn)。
• Learner：不參與決策，從Proposers/Acceptors學(xué)習(xí)最新達(dá)成一致的提案（Value）。

在多副本狀態(tài)機(jī)中，每個(gè)副本同時(shí)具有Proposer、Acceptor、Learner三種角色。

Paxos中的角色

Paxos算法通過(guò)一個(gè)決議分為兩個(gè)階段（Learn階段之前決議已經(jīng)形成）：

1. 第一階段：Prepare階段。Proposer向Acceptors發(fā)出Prepare請(qǐng)求，Acceptors針對(duì)收到的Prepare請(qǐng)求進(jìn)行Promise承諾。
2. 第二階段：Accept階段。Proposer收到多數(shù)Acceptors承諾的Promise后，向Acceptors發(fā)出Propose請(qǐng)求，Acceptors針對(duì)收到的Propose請(qǐng)求進(jìn)行Accept處理。
3. 第三階段：Learn階段。Proposer在收到多數(shù)Acceptors的Accept之后，標(biāo)志著本次Accept成功，決議形成，將形成的決議發(fā)送給所有Learners。

Paxos算法中的流程

Paxos算法流程中的每條消息描述如下：

• Prepare: Proposer生成全局唯一且遞增的Proposal ID (可使用時(shí)間戳加Server ID)，向所有Acceptors發(fā)送Prepare請(qǐng)求，這里無(wú)需攜帶提案內(nèi)容，只攜帶Proposal ID即可。
• Promise: Acceptors收到Prepare請(qǐng)求后，做出“兩個(gè)承諾，一個(gè)應(yīng)答”。

兩個(gè)承諾：

1. 不再接受Proposal ID小于等于（注意：這里是<= ）當(dāng)前請(qǐng)求的Prepare請(qǐng)求。

2. 不再接受Proposal ID小于（注意：這里是< ）當(dāng)前請(qǐng)求的Propose請(qǐng)求。

一個(gè)應(yīng)答：

不違背以前作出的承諾下，回復(fù)已經(jīng)Accept過(guò)的提案中Proposal ID最大的那個(gè)提案的Value和Proposal ID，沒(méi)有則返回空值。

• Propose: Proposer 收到多數(shù)Acceptors的Promise應(yīng)答后，從應(yīng)答中選擇Proposal ID最大的提案的Value，作為本次要發(fā)起的提案。如果所有應(yīng)答的提案Value均為空值，則可以自己隨意決定提案Value。然后攜帶當(dāng)前Proposal ID，向所有Acceptors發(fā)送Propose請(qǐng)求。
• Accept: Acceptor收到Propose請(qǐng)求后，在不違背自己之前作出的承諾下，接受并持久化當(dāng)前Proposal ID和提案Value。
• Learn: Proposer收到多數(shù)Acceptors的Accept后，決議形成，將形成的決議發(fā)送給所有Learners。

Paxos算法偽代碼描述如下：

Paxos偽代碼

1. 獲取一個(gè)Proposal ID n，為了保證Proposal ID唯一，可采用時(shí)間戳+Server ID生成；
2. Proposer向所有Acceptors廣播Prepare(n)請(qǐng)求；
3. Acceptor比較n和minProposal，如果n>minProposal，minProposal=n，并且將 acceptedProposal 和 acceptedValue 返回；
4. Proposer接收到過(guò)半數(shù)回復(fù)后，如果發(fā)現(xiàn)有acceptedValue返回，將所有回復(fù)中acceptedProposal最大的acceptedValue作為本次提案的value，否則可以任意決定本次提案的value；
5. 到這里可以進(jìn)入第二階段，廣播Accept (n,value) 到所有節(jié)點(diǎn)；
6. Acceptor比較n和minProposal，如果n>=minProposal，則acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否則，返回minProposal。
7. 提議者接收到過(guò)半數(shù)請(qǐng)求后，如果發(fā)現(xiàn)有返回值result >n，表示有更新的提議，跳轉(zhuǎn)到1；否則value達(dá)成一致。

下面舉幾個(gè)例子，實(shí)例1如下圖：

Paxos算法示例1

圖中P代表Prepare階段，A代表Accept階段。3.1代表Proposal ID為3.1，其中3為時(shí)間戳，1為Server ID。X和Y代表提議Value。

實(shí)例1中P 3.1達(dá)成多數(shù)派，其Value(X)被Accept，然后P 4.5學(xué)習(xí)到Value(X)，并Accept。

Paxos算法示例2

實(shí)例2中P 3.1沒(méi)有被多數(shù)派Accept（只有S3 Accept），但是被P 4.5學(xué)習(xí)到，P 4.5將自己的Value由Y替換為X，Accept（X）。

Paxos算法示例3

實(shí)例3中P 3.1沒(méi)有被多數(shù)派Accept（只有S1 Accept），同時(shí)也沒(méi)有被P 4.5學(xué)習(xí)到。由于P 4.5 Propose的所有應(yīng)答，均未返回Value，則P 4.5可以Accept自己的Value (Y)。后續(xù)P 3.1的Accept (X) 會(huì)失敗，已經(jīng)Accept的S1，會(huì)被覆蓋。

Paxos算法可能形成活鎖而永遠(yuǎn)不會(huì)結(jié)束，如下圖實(shí)例所示：

Paxos算法示例4

回顧兩個(gè)承諾之一，Acceptor不再應(yīng)答Proposal ID小于等于當(dāng)前請(qǐng)求的Prepare請(qǐng)求。意味著需要應(yīng)答Proposal ID大于當(dāng)前請(qǐng)求的Prepare請(qǐng)求。

兩個(gè)Proposers交替Prepare成功，而Accept失敗，形成活鎖（Livelock）。

1.3 Multi-Paxos算法

原始的Paxos算法（Basic Paxos）只能對(duì)一個(gè)值形成決議，決議的形成至少需要兩次網(wǎng)絡(luò)來(lái)回，在高并發(fā)情況下可能需要更多的網(wǎng)絡(luò)來(lái)回，極端情況下甚至可能形成活鎖。如果想連續(xù)確定多個(gè)值，Basic Paxos搞不定了。因此Basic Paxos幾乎只是用來(lái)做理論研究，并不直接應(yīng)用在實(shí)際工程中。

實(shí)際應(yīng)用中幾乎都需要連續(xù)確定多個(gè)值，而且希望能有更高的效率。Multi-Paxos正是為解決此問(wèn)題而提出。Multi-Paxos基于Basic Paxos做了兩點(diǎn)改進(jìn)：

1. 針對(duì)每一個(gè)要確定的值，運(yùn)行一次Paxos算法實(shí)例（Instance），形成決議。每一個(gè)Paxos實(shí)例使用唯一的Instance ID標(biāo)識(shí)。
2. 在所有Proposers中選舉一個(gè)Leader，由Leader唯一地提交Proposal給Acceptors進(jìn)行表決。這樣沒(méi)有Proposer競(jìng)爭(zhēng)，解決了活鎖問(wèn)題。在系統(tǒng)中僅有一個(gè)Leader進(jìn)行Value提交的情況下，Prepare階段就可以跳過(guò)，從而將兩階段變?yōu)橐浑A段，提高效率。

Multi-Paxos流程

Multi-Paxos首先需要選舉Leader，Leader的確定也是一次決議的形成，所以可執(zhí)行一次Basic Paxos實(shí)例來(lái)選舉出一個(gè)Leader。選出Leader之后只能由Leader提交Proposal，在Leader宕機(jī)之后服務(wù)臨時(shí)不可用，需要重新選舉Leader繼續(xù)服務(wù)。在系統(tǒng)中僅有一個(gè)Leader進(jìn)行Proposal提交的情況下，Prepare階段可以跳過(guò)。

Multi-Paxos通過(guò)改變Prepare階段的作用范圍至后面Leader提交的所有實(shí)例，從而使得Leader的連續(xù)提交只需要執(zhí)行一次Prepare階段，后續(xù)只需要執(zhí)行Accept階段，將兩階段變?yōu)橐浑A段，提高了效率。為了區(qū)分連續(xù)提交的多個(gè)實(shí)例，每個(gè)實(shí)例使用一個(gè)Instance ID標(biāo)識(shí)，Instance ID由Leader本地遞增生成即可。

Multi-Paxos允許有多個(gè)自認(rèn)為是Leader的節(jié)點(diǎn)并發(fā)提交Proposal而不影響其安全性，這樣的場(chǎng)景即退化為Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的變形。

Part 4 區(qū)塊鏈里的共識(shí)機(jī)制

1.1 POW

PoW 是Proof of Work 即工作量證明，目前運(yùn)用在比特幣與以太坊區(qū)塊鏈，通過(guò)解答數(shù)學(xué)問(wèn)題來(lái)實(shí)現(xiàn)。
請(qǐng)看我之前的一篇用Go語(yǔ)言實(shí)現(xiàn)的帶工作量證明的區(qū)塊鏈
跟著實(shí)現(xiàn)一遍，就會(huì)對(duì) PoW 有一個(gè)非常清晰的理解。

1.2 POS

PoS 是權(quán)益證明，即通過(guò)節(jié)點(diǎn)所擁有的代幣數(shù)量來(lái)獲得爭(zhēng)取生成區(qū)塊的權(quán)利。比起 PoW， PoS的優(yōu)點(diǎn)是在于不用浪費(fèi)那么多計(jì)算資源，電力能源去解答數(shù)學(xué)問(wèn)題來(lái)爭(zhēng)取生成區(qū)塊的權(quán)力。但是缺點(diǎn)是容易導(dǎo)致生成區(qū)塊權(quán)利的中心化，比如代幣數(shù)量多的人，永遠(yuǎn)都擁有很高的概率獲得生成區(qū)塊的權(quán)利。

1.3 DPOS

DPoS 是代理權(quán)益證明，假設(shè)某個(gè)區(qū)塊鏈有120個(gè)節(jié)點(diǎn)，那會(huì)選出20個(gè)節(jié)點(diǎn)來(lái)作為代理節(jié)點(diǎn)，即只有這20個(gè)節(jié)點(diǎn)擁有生成新區(qū)塊的權(quán)力。他們會(huì)輪流去生成新的區(qū)塊。DPoS的優(yōu)點(diǎn)是提高了區(qū)塊鏈的TPS,代理節(jié)點(diǎn)只有20個(gè)，那么效率肯定會(huì)高很多。缺點(diǎn)是這些代理節(jié)點(diǎn)都是通過(guò)投票產(chǎn)生，那當(dāng)有人或者組織控制多數(shù)的投票權(quán)時(shí)，就相當(dāng)與控制了整個(gè)區(qū)塊鏈了。