本文是Paxos、Raft分佈式一致性最佳實踐的第一篇文章，說明分佈式一致性問題與分佈式一致性算法的典型應用場景，幫助後面大家更好的理解Paxos、Raft等分佈式一致性算法。
一、分佈式一致性 (Consensus)
分佈式一致性問題，簡單的說，就是在一個或多個進程提議了一個值應當是什麼後，使系統中所有進程對這個值達成一致意見。
這樣的協定問題在分佈式系統中很常用，比如：
- 領導者選舉（leader election）：進程對leader達成一致；
- 互斥（mutual exclusion）：進程對進入臨界區的進程達成一致；
- 原子廣播（atomic broadcast）：進程對消息傳遞（delivery）順序達成一致。
對於這些問題有一些特定的算法，但是，分佈式一致性問題試圖探討這些問題的一個更一般的形式，如果能夠解決分佈式一致性問題，則以上的問題都可以解決。
分佈式一致性問題的定義如下圖所示：
分佈式一致性問題
為了達成一致，每個進程都提出自己的提議（propose），最終通過分佈式一致性算法，所有正確運行的進程決定（decide）相同的值。
分佈式一致性實例
如果在一個不出現故障的系統中，很容易解決分佈式一致性問題。但是實際分佈式系統一般是基於消息傳遞的異步分佈式系統，進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複、亂序等。
在一個可能發生上述異常的分佈式系統中如何就某個值達成一致，形成一致的決議，保證不論發生以上任何異常，都不會破壞決議的一致性，這些正是一致性算法要解決的問題。
二、分佈式一致性算法典型應用場景
我們在分佈式存儲系統中經常使用多副本的方式實現容錯，每一份數據都保存多個副本，這樣部分副本的失效不會導致數據的丟失。每次更新操作都需要更新數據的所有副本，使多個副本的數據保持一致。那麼問題來了，如何在一個可能出現各種故障的異步分佈式系統中保證同一數據的多個副本的一致性 (Consistency) 呢？
以最簡單的兩副本為例，首先來看看傳統的主從同步方式。
傳統的主從同步
寫請求首先發送給主副本，主副本同步更新到其它副本後返回。這種方式可以保證副本之間數據的強一致性，寫成功返回之後從任意副本讀到的數據都是一致的。但是可用性很差，只要任意一個副本寫失敗，寫請求將執行失敗。
主從同步的弱可用性
如果採用異步複製的方式，主副本寫成功後立即返回，然後在後臺異步的更新其它副本。
主從異步複製
寫請求首先發送給主副本，主副本寫成功後立即返回，然後異步的更新其它副本。這種方式可用性較好，只要主副本寫成功，寫請求就執行成功。但是不能保證副本之間數據的強一致性，寫成功返回之後從各個副本讀取到的數據不保證一致，只有主副本上是最新的數據，其它副本上的數據落後，只提供最終一致性。
異步複製失敗
如果出現斷網導致後臺異步複製失敗，則主副本和其它副本將長時間不一致，其它副本上的數據一直無法更新，直到網絡重新連通。
主副本寫成功後立即宕機
如果主副本在寫請求成功返回之後和更新其它副本之前宕機失效，則會造成成功寫入的數據丟失，一致性被破壞。
熟悉Oracle的朋友應該對上述同步方式非常熟悉，上述同步和異步複製方式分別對應Oracle Data Guard的一種數據保護模式。
同步複製為最高保護模式 (Maximum Protection)，異步複製為最高性能模式 (Maximum Performance)，還有一種最高可用性模式 (Maximum Availability) 介於兩者之間，在正常情況下，它和最高保護模式一樣，但一旦同步出現故障，立即切換成最高性能模式。
傳統的主從同步無法同時保證數據的一致性和可用性，此問題是典型的分佈式系統中一致性和可用性不可兼得的例子，分佈式系統中著名的CAP理論從理論上證明了這個問題。
而Paxos、Raft等分佈式一致性算法則可在一致性和可用性之間取得很好的平衡，在保證一定的可用性的同時，能夠對外提供強一致性，因此Paxos、Raft等分佈式一致性算法被廣泛的用於管理副本的一致性，提供高可用性。
三、CAP理論
CAP理論是分佈式系統、特別是分佈式存儲領域中被討論的最多的理論。其中C代表一致性 (Consistency)，A代表可用性 (Availability)，P代表分區容錯性 (Partition tolerance)。CAP理論告訴我們C、A、P三者不能同時滿足，最多隻能滿足其中兩個。
CAP理論
- 一致性 (Consistency)：一個寫操作返回成功，那麼之後的讀請求都必須讀到這個新數據；如果返回失敗，那麼所有讀操作都不能讀到這個數據。所有節點訪問同一份最新的數據。
- 可用性 (Availability)：對數據更新具備高可用性，請求能夠及時處理，不會一直等待，即使出現節點失效。
- 分區容錯性 (Partition tolerance)：能容忍網絡分區，在網絡斷開的情況下，被分隔的節點仍能正常對外提供服務。
理解CAP理論最簡單的方式是想象兩個副本處於分區兩側，即兩個副本之間的網絡斷開，不能通信。
- 如果允許其中一個副本更新，則會導致數據不一致，即喪失了C性質。
- 如果為了保證一致性，將分區某一側的副本設置為不可用，那麼又喪失了A性質。
- 除非兩個副本可以互相通信，才能既保證C又保證A，這又會導致喪失P性質。
一般來說使用網絡通信的分佈式系統，無法捨棄P性質，那麼就只能在一致性和可用性上做一個艱難的選擇。
CAP理論的表述很好地服務了它的目的，開闊了分佈式系統設計者的思路，在多樣化的取捨方案下設計出多樣化的系統。在過去的十幾年裡確實湧現了不計其數的新系統，也隨之在一致性和可用性的相對關係上產生了相當多的爭論。
既然在分佈式系統中一致性和可用性只能選一個。那Paxos、Raft等分佈式一致性算法是如何做到在保證一定的可用性的同時，對外提供強一致性呢。
在CAP理論提出十二年之後，其作者又出來闢謠。“三選二”的公式一直存在著誤導性，它會過分簡單化各性質之間的相互關係：
- 首先，由於分區很少發生，那麼在系統不存在分區的情況下沒什麼理由犧牲C或A。
- 其次，C與A之間的取捨可以在同一系統內以非常細小的粒度反覆發生，而每一次的決策可能因為具體的操作，乃至因為牽涉到特定的數據或用戶而有所不同。
- 最後，這三種性質都可以在程度上衡量，並不是非黑即白的有或無。可用性顯然是在0%到100%之間連續變化的，一致性分很多級別，連分區也可以細分為不同含義，如系統內的不同部分對於是否存在分區可以有不一樣的認知。
所以一致性和可用性並不是水火不容，非此即彼的。Paxos、Raft等分佈式一致性算法就是在一致性和可用性之間做到了很好的平衡的見證。
四、多副本狀態機
將多副本管理的模型抽象出來，可得到一個通用的模型：多副本狀態機 (Replicated State Machine) 。
多副本狀態機是指多臺機器具有完全相同的狀態，並且運行完全相同的確定性狀態機。
通過使用這樣的狀態機，可以解決很多分佈式系統中的容錯問題。因為多副本狀態機通常可以容忍半數節點故障，且所有正常運行的副本節點狀態都完全一致，所以可以使用多副本狀態機來實現需要避免單點故障的組件。
高可用"單點"的集中式架構
多副本狀態機在分佈式系統中被用於解決各種容錯問題。如集中式的選主或是互斥算法中的協調者 (Coordinator)。集中式的領導者或互斥算法邏輯簡單，但最大的問題是協調者的單點故障問題，通過採用多副本狀態機來實現協調者實現了高可用的“單點”，迴避了單點故障。
GFS，HDFS，RAMCloud等典型地使用一個獨立的多副本狀態機來管理領導者選舉與保存集群配置信息，以備節點宕機後信息能夠保持。
Chubby與ZooKeeper以及Boxwood等都是使用多副本狀態機的例子。
多副本狀態機的每個副本上都保存有完全相同的操作日誌，保證所有狀態機副本按照相同的順序執行相同的操作，這樣由於狀態機是確定性的，則會得到相同的狀態。
多副本狀態機結構
每個服務器在日誌中保存一系列命令，所有的狀態機副本按照同樣的順序執行，分佈式一致性算法管理著來自客戶端的包含狀態機命令的日誌複製，每條日誌以同樣的順序保存同樣的命令，因此每個狀態機執行同樣的命令序列。因為狀態機是確定的，每個都計算出同樣的狀態與同樣的輸出。
保證複製到各個服務器上的日誌的一致性正是分佈式一致性算法的工作。一致性算法保證所有狀態機副本上的操作日誌具有完全相同的順序，如果狀態機的任何一個副本在本地狀態機上執行了一個操作，則絕對不會有別的副本在操作序列相同位置執行一個不同的操作。
服務器上的一致性模塊，接收來自客戶端的命令，並且添加到他們的日誌中。它與其它服務器的一致性模塊通訊，以確保每個日誌最終以同樣的順序保存同樣的請求，即使有些服務器失敗。一旦命令被適當地複製，每臺服務器的狀態機以日誌的順序執行，將輸出返回給客戶端。結果多臺服務器就像來自單個高度一致的高可用狀態機。
閱讀更多 程序員王哥 的文章
