一致性問(wèn)題
一致性問(wèn)題是分布式領(lǐng)域最重要、最基礎(chǔ)的問(wèn)題。
一致性/Consistency,是說(shuō)在有多個(gè)服務(wù)節(jié)點(diǎn)的情況下，執(zhí)行一些列操作，在約定協(xié)議的保障下，使得他們對(duì)外的處理結(jié)果，能達(dá)到一定程度的協(xié)同。
規(guī)范的說(shuō)，理想的分布式系統(tǒng)一致性應(yīng)該滿足：
- 可終止性（Termination）：一致的結(jié)果在有限時(shí)間內(nèi)能完成；
- 共識(shí)性（Consensus）：不同節(jié)點(diǎn)最終完成決策的結(jié)果應(yīng)該相同；
- 合法性（Validity）：決策的結(jié)果必須是其它進(jìn)程提出的提案。
第一點(diǎn)很容易理解
第二點(diǎn)看似容易，但是隱藏了一些潛在信息。算法考慮的是任意的情形，凡事一旦推廣到任意情形，就往往有一些驚人的結(jié)果。例如現(xiàn)在就剩一張票了，中關(guān)村和西單的電影院也分別剛確認(rèn)過(guò)這張票的存在，然后兩個(gè)電影院同時(shí)來(lái)了一個(gè)顧客要買(mǎi)票，從各自“觀察”看來(lái)，自己的顧客都是第一個(gè)到的……怎么能達(dá)成結(jié)果的共識(shí)呢？記住我們的唯一秘訣：核心在于需要把兩件事情進(jìn)行排序，而且這個(gè)順序還得是大家都認(rèn)可的。
第三點(diǎn)看似繞口，但是其實(shí)比較容易理解，即達(dá)成的結(jié)果必須是節(jié)點(diǎn)執(zhí)行操作的結(jié)果。仍以賣(mài)票為例，如果兩個(gè)影院各自賣(mài)出去一千張，那么達(dá)成的結(jié)果就是還剩八千張，決不能認(rèn)為票售光了。
做過(guò)分布式系統(tǒng)的讀者應(yīng)該能意識(shí)到，絕對(duì)理想的強(qiáng)一致性（Strong Consistency）代價(jià)很大。除非不發(fā)生任何故障，所有節(jié)點(diǎn)之間的通信無(wú)需任何時(shí)間，這個(gè)時(shí)候其實(shí)就等價(jià)于一臺(tái)機(jī)器了。實(shí)際上，越強(qiáng)的一致性要求往往意味著越弱的性能。
一般的，強(qiáng)一致性（Strong Consistency）主要包括下面兩類(lèi)：
順序一致性：限制了各進(jìn)程內(nèi)指令的偏序關(guān)系，但不在進(jìn)程間按照物理時(shí)間進(jìn)行全局排序
線性一致性：在順序一致性前提下加強(qiáng)了進(jìn)程間的操作排序，形成唯一的全局順序
強(qiáng)一致的系統(tǒng)往往比較難實(shí)現(xiàn)。很多時(shí)候，人們發(fā)現(xiàn)實(shí)際需求并沒(méi)有那么強(qiáng)，可以適當(dāng)放寬一致性要求，降低系統(tǒng)實(shí)現(xiàn)的難度。例如在一定約束下實(shí)現(xiàn)所謂最終一致性（Eventual Consistency），即總會(huì)存在一個(gè)時(shí)刻（而不是立刻），系統(tǒng)達(dá)到一致的狀態(tài)，這對(duì)于大部分的 Web 系統(tǒng)來(lái)說(shuō)已經(jīng)足夠了。這一類(lèi)弱化的一致性，被籠統(tǒng)稱(chēng)為弱一致性（Weak Consistency）。
共識(shí)算法
實(shí)踐中，要保障系統(tǒng)滿足不同程度的一致性，往往需要通過(guò)共識(shí)算法來(lái)達(dá)成。
共識(shí)算法解決的是分布式系統(tǒng)對(duì)某個(gè)提案（Proposal），大部分節(jié)點(diǎn)達(dá)成一致意見(jiàn)的過(guò)程。
理論上，如果分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)都能保證以十分強(qiáng)大的性能（瞬間響應(yīng)、高吞吐）無(wú)故障的運(yùn)行，則實(shí)現(xiàn)共識(shí)過(guò)程并不復(fù)雜，簡(jiǎn)單通過(guò)多播過(guò)程投票即可。
很可惜的是，現(xiàn)實(shí)中這樣“完美”的系統(tǒng)并不存在，如響應(yīng)請(qǐng)求往往存在時(shí)延、網(wǎng)絡(luò)會(huì)發(fā)生中斷、節(jié)點(diǎn)會(huì)發(fā)生故障、甚至存在惡意節(jié)點(diǎn)故意要破壞系統(tǒng)。
一般地，把故障（不響應(yīng)）的情況稱(chēng)為“非拜占庭錯(cuò)誤”，惡意響應(yīng)的情況稱(chēng)為“拜占庭錯(cuò)誤”（對(duì)應(yīng)節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)）。
常見(jiàn)算法
對(duì)于非拜占庭錯(cuò)誤的情況，已經(jīng)存在不少經(jīng)典的算法，包括 Paxos（1990 年）、Raft（2014 年）及其變種等。這類(lèi)容錯(cuò)算法往往性能比較好，處理較快，容忍不超過(guò)一半的故障節(jié)點(diǎn)。
對(duì)于要能容忍拜占庭錯(cuò)誤的情況，包括 PBFT（Practical Byzantine Fault Tolerance，1999 年）為代表的確定性系列算法、PoW（1997 年）為代表的概率算法等。確定性算法一旦達(dá)成共識(shí)就不可逆轉(zhuǎn)，即共識(shí)是最終結(jié)果；而概率類(lèi)算法的共識(shí)結(jié)果則是臨時(shí)的，隨著時(shí)間推移或某種強(qiáng)化，共識(shí)結(jié)果被推翻的概率越來(lái)越小，最終成為事實(shí)上結(jié)果。拜占庭類(lèi)容錯(cuò)算法往往性能較差，容忍不超過(guò) 1/3 的故障節(jié)點(diǎn)。
此外，XFT（Cross Fault Tolerance，2015 年）等最近提出的改進(jìn)算法可以提供類(lèi)似 CFT 的處理響應(yīng)速度，并能在大多數(shù)節(jié)點(diǎn)正常工作時(shí)提供 BFT 保障。
Algorand 算法（2017 年）基于 PBFT 進(jìn)行改進(jìn)，通過(guò)引入可驗(yàn)證隨機(jī)函數(shù)解決了提案選擇的問(wèn)題，理論上可以在容忍拜占庭錯(cuò)誤的前提下實(shí)現(xiàn)更好的性能（1000+ TPS）。
FLP不可能原理
FLP 不可能原理告訴我們，不要浪費(fèi)時(shí)間，去試圖為異步分布式系統(tǒng)設(shè)計(jì)面向任意場(chǎng)景的共識(shí)算法。
異步：導(dǎo)致我們無(wú)法判斷某個(gè)消息遲遲沒(méi)有被響應(yīng)是哪里出了問(wèn)題（節(jié)點(diǎn)故障還是傳輸故障？）
學(xué)術(shù)研究，往往考慮地是數(shù)學(xué)和物理意義上理想化的情形，很多時(shí)候現(xiàn)實(shí)世界要穩(wěn)定得多（感謝這個(gè)世界如此魯棒！）。例如，上面例子中描述的最壞情形，每次都發(fā)生的概率其實(shí)并沒(méi)有那么大。工程實(shí)現(xiàn)上某次共識(shí)失敗，再?lài)L試幾次，很大可能就成功了。
科學(xué)告訴你什么是不可能的；工程則告訴你，付出一些代價(jià)，可以把它變成可行。
這就是科學(xué)和工程不同的魅力。FLP 不可能原理告訴大家不必浪費(fèi)時(shí)間去追求完美的共識(shí)方案，而要根據(jù)實(shí)際情況設(shè)計(jì)可行的工程方案。
那么，退一步講，在付出一些代價(jià)的情況下，共識(shí)能做到多好？
回答這一問(wèn)題的是另一個(gè)很出名的原理：CAP 原理。
CAP原理
該原理被認(rèn)為是分布式系統(tǒng)領(lǐng)域的重要原理之一，深刻影響了分布式計(jì)算與系統(tǒng)設(shè)計(jì)的發(fā)展。
CAP 原理：分布式系統(tǒng)無(wú)法同時(shí)確保一致性（Consistency）、可用性（Availability）和分區(qū)容忍性（Partition），設(shè)計(jì)中往往需要弱化對(duì)某個(gè)特性的需求。
一致性、可用性和分區(qū)容忍性的具體含義如下：
- 一致性（Consistency）：任何事務(wù)應(yīng)該都是原子的，所有副本上的狀態(tài)都是事務(wù)成功提交后的結(jié)果，并保持強(qiáng)一致；
- 可用性（Availability）：系統(tǒng)（非失敗節(jié)點(diǎn)）能在有限時(shí)間內(nèi)完成對(duì)操作請(qǐng)求的應(yīng)答；
- 分區(qū)容忍性（Partition）：系統(tǒng)中的網(wǎng)絡(luò)可能發(fā)生分區(qū)故障（成為多個(gè)子網(wǎng)，甚至出現(xiàn)節(jié)點(diǎn)上線和下線），即節(jié)點(diǎn)之間的通信無(wú)法保障。而網(wǎng)絡(luò)故障不應(yīng)該影響到系統(tǒng)正常服務(wù)。
CAP 原理認(rèn)為，分布式系統(tǒng)最多只能保證三項(xiàng)特性中的兩項(xiàng)特性。
比較直觀地理解，當(dāng)網(wǎng)絡(luò)可能出現(xiàn)分區(qū)時(shí)候，系統(tǒng)是無(wú)法同時(shí)保證一致性和可用性的。要么，節(jié)點(diǎn)收到請(qǐng)求后因?yàn)闆](méi)有得到其它節(jié)點(diǎn)的確認(rèn)而不應(yīng)答（犧牲可用性），要么節(jié)點(diǎn)只能應(yīng)答非一致的結(jié)果（犧牲一致性）。
由于大部分時(shí)候網(wǎng)絡(luò)被認(rèn)為是可靠的，因此系統(tǒng)可以提供一致可靠的服務(wù)；當(dāng)網(wǎng)絡(luò)不可靠時(shí)，系統(tǒng)要么犧牲掉一致性（多數(shù)場(chǎng)景下），要么犧牲掉可用性。
注意：網(wǎng)絡(luò)分區(qū)是可能存在的，出現(xiàn)分區(qū)情況后很可能會(huì)導(dǎo)致發(fā)生“腦裂”現(xiàn)象。
關(guān)鍵就在于網(wǎng)絡(luò)，網(wǎng)絡(luò)大部分情況是可靠的，但也總是不可靠的。
所以，cap可以簡(jiǎn)單理解為，因?yàn)榫W(wǎng)絡(luò)總會(huì)出故障，當(dāng)網(wǎng)絡(luò)故障時(shí)，我們保一致性，還是要可用性。
要可用性：例如網(wǎng)站靜態(tài)頁(yè)面內(nèi)容、實(shí)時(shí)性較弱的查詢類(lèi)數(shù)據(jù)庫(kù)等，簡(jiǎn)單分布式同步協(xié)議如 Gossip，以及 CouchDB、Cassandra 數(shù)據(jù)庫(kù)等，都為此設(shè)計(jì)。
要一致性：對(duì)結(jié)果一致性很敏感的應(yīng)用，例如銀行取款機(jī)，當(dāng)系統(tǒng)故障時(shí)候會(huì)拒絕服務(wù)。MongoDB、redis、MapReduce 等為此設(shè)計(jì)。Paxos、Raft 等共識(shí)算法，主要處理這種情況。在 Paxos 類(lèi)算法中，可能存在著無(wú)法提供可用結(jié)果的情形，同時(shí)允許少數(shù)節(jié)點(diǎn)離線。
ACID 原則與多階段提交
ACID，即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔離性）、Durability（持久性）四種特性的縮寫(xiě)。
ACID 原則描述了分布式數(shù)據(jù)庫(kù)需要滿足的一致性需求，同時(shí)允許付出可用性的代價(jià)。
與 ACID 相對(duì)的一個(gè)原則是 eBay 技術(shù)專(zhuān)家 Dan Pritchett 提出的 BASE（Basic Availability，Soft-state，Eventual Consistency）原則。BASE 原則面向大型高可用分布式系統(tǒng)，主張犧牲掉對(duì)強(qiáng)一致性的追求，而實(shí)現(xiàn)最終一致性，來(lái)?yè)Q取一定的可用性。
兩階段提交
對(duì)于分布式事務(wù)一致性的研究成果包括著名的兩階段提交算法（Two-phase Commit，2PC）和三階段提交算法（Three-phase Commit，3PC）。
兩階段提交算法，其基本思想十分簡(jiǎn)單，既然在分布式場(chǎng)景下，直接提交事務(wù)可能出現(xiàn)各種故障和沖突，那么可將其分解為預(yù)提交和正式提交兩個(gè)階段，規(guī)避沖突的風(fēng)險(xiǎn)。
- 預(yù)提交：協(xié)調(diào)者（Coordinator）發(fā)起提交某個(gè)事務(wù)的申請(qǐng)，各參與執(zhí)行者（Participant）需要嘗試進(jìn)行提交并反饋是否能完成；
- 正式提交：協(xié)調(diào)者如果得到所有執(zhí)行者的成功答復(fù)，則發(fā)出正式提交請(qǐng)求。如果成功完成，則算法執(zhí)行成功。
在此過(guò)程中任何步驟出現(xiàn)問(wèn)題（例如預(yù)提交階段有執(zhí)行者回復(fù)預(yù)計(jì)無(wú)法完成提交），則需要回退。
兩階段提交算法因?yàn)槠浜?jiǎn)單容易實(shí)現(xiàn)的優(yōu)點(diǎn)，在關(guān)系型數(shù)據(jù)庫(kù)等系統(tǒng)中被廣泛應(yīng)用。當(dāng)然，其缺點(diǎn)也很明顯。整個(gè)過(guò)程需要同步阻塞導(dǎo)致性能一般較差；同時(shí)存在單點(diǎn)問(wèn)題，較壞情況下可能一直無(wú)法完成提交；另外可能產(chǎn)生數(shù)據(jù)不一致的情況（例如協(xié)調(diào)者和執(zhí)行者在第二個(gè)階段出現(xiàn)故障）。
三階段提交
三階段提交針對(duì)兩階段提交算法第一階段中可能阻塞部分執(zhí)行者的情況進(jìn)行了優(yōu)化。具體來(lái)說(shuō)，將預(yù)提交階段進(jìn)一步拆成兩個(gè)步驟：嘗試預(yù)提交和預(yù)提交。
完整過(guò)程如下：
- 嘗試預(yù)提交：協(xié)調(diào)者詢問(wèn)執(zhí)行者是否能進(jìn)行某個(gè)事務(wù)的提交。執(zhí)行者需要返回答復(fù)，但無(wú)需執(zhí)行提交。這就避免出現(xiàn)部分執(zhí)行者被無(wú)效阻塞住的情況。
- 預(yù)提交：協(xié)調(diào)者檢查收集到的答復(fù)，如果全部為真，則發(fā)起提交事務(wù)請(qǐng)求。各參與執(zhí)行者（Participant）需要嘗試進(jìn)行提交并反饋是否能完成；
- 正式提交：協(xié)調(diào)者如果得到所有執(zhí)行者的成功答復(fù)，則發(fā)出正式提交請(qǐng)求。如果成功完成，則算法執(zhí)行成功。
其實(shí)，無(wú)論兩階段還是三階段提交，都只是一定程度上緩解了提交沖突的問(wèn)題，并無(wú)法一定保證系統(tǒng)的一致性。首個(gè)有效的算法是后來(lái)提出的 Paxos 算法。
Paxos 算法
Paxos 問(wèn)題是指分布式的系統(tǒng)中存在故障（crash fault），但不存在惡意（corrupt）節(jié)點(diǎn)的場(chǎng)景（即可能消息丟失或重復(fù)，但無(wú)錯(cuò)誤消息）下的共識(shí)達(dá)成問(wèn)題。這也是分布式共識(shí)領(lǐng)域最為常見(jiàn)的問(wèn)題。
Paxos 是首個(gè)得到證明并被廣泛應(yīng)用的共識(shí)算法，其原理類(lèi)似 兩階段提交 算法，進(jìn)行了泛化和擴(kuò)展，通過(guò)消息傳遞來(lái)逐步消除系統(tǒng)中的不確定狀態(tài)。zookeeper中有使用。
作為后來(lái)很多共識(shí)算法（如 Raft、ZAB 等）的基礎(chǔ)，Paxos 算法基本思想并不復(fù)雜。
基本原理
算法中存在三種邏輯角色的節(jié)點(diǎn)，在實(shí)現(xiàn)中同一節(jié)點(diǎn)可以擔(dān)任多個(gè)角色。
- 提案者（Proposer）：提出一個(gè)提案，等待大家批準(zhǔn)（Chosen）為結(jié)案（Value）。系統(tǒng)中提案都擁有一個(gè)自增的唯一提案號(hào)。往往由客戶端擔(dān)任該角色。（只有是被提案者提出的提案才可能被最終批準(zhǔn)）
- 接受者（Acceptor）：負(fù)責(zé)對(duì)提案進(jìn)行投票，接受（Accept）提案。往往由服務(wù)端擔(dān)任該角色。
- 學(xué)習(xí)者（Learner）：獲取批準(zhǔn)結(jié)果，并幫忙傳播，不參與投票過(guò)程。可為客戶端或服務(wù)端。
基本思路類(lèi)似兩階段提交：
多個(gè)提案者先要爭(zhēng)取到提案的權(quán)利（得到大多數(shù)接受者的支持）；
成功的提案者發(fā)送提案給所有人進(jìn)行確認(rèn)，得到大部分人確認(rèn)的提案成為批準(zhǔn)的結(jié)案。
Raft 算法
Paxos 算法雖然給出了共識(shí)設(shè)計(jì)，但并沒(méi)有討論太多實(shí)現(xiàn)細(xì)節(jié)，也并不重視工程上的優(yōu)化，因此后來(lái)在學(xué)術(shù)界和工程界出現(xiàn)了一些改進(jìn)工作，包括 Fast Paxos、Multi-Paxos，Zookeeper Atomic Broadcast（ZAB）和 Raft 等。這些算法重點(diǎn)在于改進(jìn)執(zhí)行效率和可實(shí)現(xiàn)性。
Raft 算法的主要設(shè)計(jì)思想與 ZAB 類(lèi)似，通過(guò)先選出領(lǐng)導(dǎo)節(jié)點(diǎn)來(lái)簡(jiǎn)化流程和提高效率。實(shí)現(xiàn)上分解了領(lǐng)導(dǎo)者選舉、日志復(fù)制和安全方面的考慮，并通過(guò)約束減少了不確定性的狀態(tài)空間。
算法包括三種角色：領(lǐng)導(dǎo)者（Leader）、候選者（Candidate） 和跟隨者（Follower），每個(gè)任期內(nèi)選舉一個(gè)全局的領(lǐng)導(dǎo)者。領(lǐng)導(dǎo)者角色十分關(guān)鍵，決定日志（log）的提交。每個(gè)日志都會(huì)路由到領(lǐng)導(dǎo)者，并且只能由領(lǐng)導(dǎo)者向跟隨者單向復(fù)制。
典型的過(guò)程包括兩個(gè)主要階段：
- 領(lǐng)導(dǎo)者選舉：開(kāi)始所有節(jié)點(diǎn)都是跟隨者，在隨機(jī)超時(shí)發(fā)生后未收到來(lái)自領(lǐng)導(dǎo)者或候選者消息，則轉(zhuǎn)變角色為候選者（中間狀態(tài)），提出選舉請(qǐng)求。最近選舉階段（Term）中得票超過(guò)一半者被選為領(lǐng)導(dǎo)者；如果未選出，隨機(jī)超時(shí)后進(jìn)入新的階段重試。領(lǐng)導(dǎo)者負(fù)責(zé)從客戶端接收請(qǐng)求，并分發(fā)到其他節(jié)點(diǎn)；
- 同步日志：領(lǐng)導(dǎo)者會(huì)決定系統(tǒng)中最新的日志記錄，并強(qiáng)制所有的跟隨者來(lái)刷新到這個(gè)記錄，數(shù)據(jù)的同步是單向的，確保所有節(jié)點(diǎn)看到的視圖一致。
此外，領(lǐng)導(dǎo)者會(huì)定期向所有跟隨者發(fā)送心跳消息，跟隨者如果發(fā)現(xiàn)心跳消息超時(shí)未收到，則可以認(rèn)為領(lǐng)導(dǎo)者已經(jīng)下線，嘗試發(fā)起新的選舉過(guò)程。
拜占庭問(wèn)題
拜占庭是古代東羅馬帝國(guó)的首都，由于地域?qū)拸V，假設(shè)其守衛(wèi)邊境的多個(gè)將軍（系統(tǒng)中的多個(gè)節(jié)點(diǎn)）需要通過(guò)信使來(lái)傳遞消息，達(dá)成某些一致決定。但由于將軍中可能存在叛徒（系統(tǒng)中節(jié)點(diǎn)出錯(cuò)），這些叛徒將向不同的將軍發(fā)送不同的消息，試圖干擾共識(shí)的達(dá)成。
拜占庭問(wèn)題即討論在此情況下，如何讓忠誠(chéng)的將軍們能達(dá)成行動(dòng)的一致。
在大多數(shù)的分布式系統(tǒng)中，拜占庭的場(chǎng)景并不多見(jiàn)。然而在特定場(chǎng)景下存在意義，例如允許匿名參與的系統(tǒng)（如比特幣），或是出現(xiàn)欺詐可能造成巨大損失的情況。
根據(jù) FLP 不可能原理，這個(gè)問(wèn)題無(wú)通用解。
拜占庭問(wèn)題之所以難解，在于任何時(shí)候系統(tǒng)中都可能存在多個(gè)提案（因?yàn)樘岚赋杀竞艿停⑶以诖笠?guī)模場(chǎng)景下要完成最終確認(rèn)的過(guò)程容易受干擾，難以達(dá)成共識(shí)。
比特幣網(wǎng)絡(luò)在設(shè)計(jì)時(shí)使用了 PoW（Proof of Work）的概率型算法思路，從如下兩個(gè)角度解決大規(guī)模場(chǎng)景下的拜占庭容錯(cuò)問(wèn)題。
首先，限制一段時(shí)間內(nèi)整個(gè)網(wǎng)絡(luò)中出現(xiàn)提案的個(gè)數(shù)（通過(guò)工作量證明來(lái)增加提案成本）；其次是丟掉最終確認(rèn)的約數(shù)，約定好始終沿著已知最長(zhǎng)的鏈進(jìn)行拓展。共識(shí)的最終確認(rèn)是概率意義上的存在。這樣，即便有人試圖惡意破壞，也會(huì)付出相應(yīng)的經(jīng)濟(jì)代價(jià)（超過(guò)整體系統(tǒng)一半的工作量）。
后來(lái)的各種 PoX 系列算法，也都是沿著這個(gè)思路進(jìn)行改進(jìn)，采用經(jīng)濟(jì)博弈來(lái)制約攻擊者。
