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