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