后臺回復(fù)”加群“獲取公眾號專屬群聊入口
關(guān)于 CAP 理論的背景介紹已經(jīng)很多，這里不過多介紹，我們談?wù)勅绾卫斫馑膯栴}。
用通俗易懂的話解釋三個名詞：
一致性
如果剛剛向一個節(jié)點寫入，那么之后，從另外一個節(jié)點讀取的必須是剛剛寫入的數(shù)據(jù)，不能是更老的數(shù)據(jù)。
可用性
如果請求一個節(jié)點，這個節(jié)點必須能夠給予回復(fù)，如果節(jié)點掛掉了，那就談不上可用性了。
分區(qū)容忍性
是否容忍網(wǎng)絡(luò)分區(qū)，即可以允許節(jié)點和其它節(jié)點無法通信。
CAP 的意思就是說我們最多只能保證其中兩個條件同時成立。
下面我們來看看為什么。
如圖所示，假如我們滿足了分區(qū)容忍性，即虛線處表示兩個節(jié)點發(fā)生了分區(qū)。
假如要滿足一致性，那么，我們只能讓請求另一個節(jié)點的操作暫時 hang 住，返回 client 失敗或者超時的結(jié)果，這種情況多發(fā)生在銀行柜臺等對數(shù)據(jù)一致性要求很高的情境下，因為比起保證用戶資金數(shù)目的正確性比暫時讓用戶無法操作要更重要一些。
假如要滿足可用性，因為網(wǎng)絡(luò)已經(jīng)隔離，也就沒辦法達到一致性，這種情況多發(fā)生在互聯(lián)網(wǎng)行業(yè)中，比如新聞等對數(shù)據(jù)一致性要求不高但對可用性要求高的情況下，畢竟，用戶壓根看不了新聞比看不到及時新聞要重要的多。
大家可以自己自由組合，最終會證明，三種條件不可能同時滿足，其實大部分情況下，我們都是在一致性和可用性之間取舍而已。
Consistency 幾乎被業(yè)界用爛，以至于當我們在討論一致性的時候，其實我們都無法確定對方所說的一致性是不是和自己的那個一致。
Consistency：一致性，Consensus：協(xié)同，這兩個概念極容易混淆。
我們常說的一致性（Consistency）在分布式系統(tǒng)中指的是對于同一個數(shù)據(jù)的多個副本，其對外表現(xiàn)的數(shù)據(jù)一致性，如線性一致性、因果一致性、最終一致性等，都是用來描述副本問題中的一致性的。而共識（Consensus）則不同，簡單來說，共識問題是要經(jīng)過某種算法使多個節(jié)點達成相同狀態(tài)的一個過程。在我看來，一致性強調(diào)結(jié)果，共識強調(diào)過程。
共識？狀態(tài)機？
共識有個更高逼格的稱呼：
基于狀態(tài)機復(fù)制的共識算法
那么，狀態(tài)機是什么？
狀態(tài)機是有限狀態(tài)自動機的簡稱，是現(xiàn)實事物運行規(guī)則抽象而成的一個數(shù)學(xué)模型。
看下圖，門，有兩種狀態(tài)，開著的和關(guān)著的。因此，在我看來狀態(tài)是一種靜態(tài)的場景，而轉(zhuǎn)換賦予了其動態(tài)的變化。
以此類比一下，如果一個節(jié)點當前的數(shù)據(jù)是 X，現(xiàn)在有了 add+1 的操作日志來了，那么現(xiàn)在的狀態(tài)就是 X+1，好了，狀態(tài)（X）有了，變化（操作日志）有了，這就是狀態(tài)機。
分布式共識，簡單來說，就是在一個或多個節(jié)點提議了一個狀態(tài)應(yīng)當是什么后，系統(tǒng)中所有節(jié)點對這個狀態(tài)達成一致意見的整個過程。
共識是過程，一致是結(jié)果。
主從同步：
我們都知道 MySQL 等業(yè)界常見數(shù)據(jù)庫的主從同步（Master-Slave Replication)，主從同步分三個階段：
Master 接受寫請求
Master 復(fù)制日志至 Slave
Master 等待，直到所有從庫返回。
可見，主從同步模型存在致命問題：只要一個節(jié)點失敗，則 Master 就會阻塞，導(dǎo)致整個集群不可用，保證了一致性，可用性缺大大降低了。
多數(shù)派：
每次寫入大于 N/2 個節(jié)點，每次讀也保證從 N/2 個節(jié)點中讀。多數(shù)派的模型看似完美解決了多節(jié)點的一致性問題，不就是性能差點嘛，可是在并發(fā)的情況下就不一定了，如下圖：
在并發(fā)環(huán)境下，因為每個節(jié)點的操作日志寫入順序無法保證一致，也就無法保證最終的一致性。如圖，都是向三個節(jié)點
inc5、set0 兩個操作，但因為順序不一樣，最終狀態(tài)兩個是 0，一個是 5。因此我們需要引入一種機制，給每個操作日志編上號，這個號從小到大生成，這樣，每個節(jié)點就不會弄錯。（是否想到了網(wǎng)絡(luò)中的分包與重組？）那么，現(xiàn)在關(guān)鍵問題又來了，怎么協(xié)同這個編號？貌似這是雞生蛋、蛋生雞的問題。
Paxos 模型試圖探討分布式共識問題的一個更一般的形式。
Lesile Lamport，Latex 的發(fā)明者，提出了 Paxos 算法。他虛擬了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制定法律，但是沒有人愿意將自己的全部時間和精力放在這件事上。所以無論是議員、議長或者傳遞紙條的服務(wù)員都不能承諾別人需要時一定會出現(xiàn)，也無法承諾批準決議后者傳遞消息的時間。由于 Paxos 讓人太難以理解，Lamport 覺得同行不能理解他的幽默感，于是后來又重新發(fā)表了樸實的算法描述版本《Paxos Made Simple》。
該共識算法就整體來說，存在兩個階段，如圖，第一個階段是提議，第二個階段是決定。
分布式系統(tǒng)要做到 fault tolorence，就需要共識模型，而節(jié)點達成共識，不僅需要節(jié)點之間的算法，還會取決于 client 的行為。比如即使副本系統(tǒng)使用 multi-paxos 在所有副本服務(wù)器上同步了日志序號，但如果 Client 被允許從非 Leader 節(jié)點寫入數(shù)據(jù)，則整個副本系統(tǒng)仍然不是強一致的。
下面，重頭戲來了，詳細介紹 Paxos。
角色介紹：
Client：系統(tǒng)外部角色，請求發(fā)起者。如民眾。
Proposer: 接受 Client 請求，向集群提出提議（propose）。并在沖突發(fā)生時，起到?jīng)_突調(diào)節(jié)的作用。如議員，替民眾提出議案。
Accpetor: 提議投票和接收者，只有在形成法定人數(shù)（Quorum，即 Majority 多數(shù)派）時，提議才會最終被接受。如國會。
Learner: 提議接受者，backup，備份，對集群的一致性沒影響。如記錄員。
步驟、階段：
1.Phase1a: Prepare
proposer 提出一個議案，編號為 N，N 一定大于這個 proposer 之前提出的提案編號，請求 acceptor 的 quorum（大多數(shù)） 接受。
2.Phase1b: Promise
如果 N 大于此 acceptor 之前接受的任何提案編號則接受，否則拒絕。
3.Phase2a: Accept
如果達到了多數(shù)派，proposer 會發(fā)出 accept 請求，此請求包含上一步的提案編號和提案內(nèi)容。
4.Phase2b: Accepted
如果此 acceptor 在此期間沒有收到任何大于 N 的提案，則接受此提案內(nèi)容，否則忽略。
還記得上文中我們提到過，同步編號是非常重要的問題，綠色框出來的實際上就是同步編號的過程。通過這個編號，就知道每條操作日志的先后順序。簡單說來，第一階段，獲取編號，第二階段，寫入日志。可以看出來，Paxos 通過兩輪交互，犧牲時間和性能來達到彌補一致性的問題。
現(xiàn)在我們考慮部分節(jié)點 down 掉的情景。
由于是多數(shù)派 accptor 達成了一致，第一階段仍然成功獲得了編號，所有最終還是成功的。
考慮 proposer down 掉的情景。
沒關(guān)系，雖然第一個 proposer 失敗，但下一個 proposer 用更大的提案編號，所以下一次 proposer 最終還是成功了，仍然保證了可用性和一致性。
潛在問題：活鎖
Paxos 存在活鎖問題。如圖，當 第一個 proposer 在第一階段發(fā)出請求，還沒來得及后續(xù)的第二階段請求，緊接著第二個 proposer 在第一階段也發(fā)出請求，如果這樣無窮無盡，acceptor 始終停留在決定順序號的過程上，那大家誰也成功不了，遇到這樣的問題，其實很好解決，如果發(fā)現(xiàn)順序號被新的 proposer 更新了，則引入一個隨機的等待的超時時間，這樣就避免了多個 proposer 發(fā)生沖突的問題。
Multi Paxos
由于 Paxos 存在的問題：難實現(xiàn)、效率低（2 輪 rpc）、活鎖。
因此又引入了 Multi Paxos，Multi Paxos 引入 Leader，也就是唯一的 proposer，所有的請求都需經(jīng)過此 Leader。
因為只有一個節(jié)點維護提案編號，這樣，就省略了第一輪討論提議編號的過程。
然后進一步簡化角色。
Servers 中第左邊的就是 Proposer，另外兩個和自身充當 acceptor，這樣就更像我們真實的系統(tǒng)了。Raft 和 ZAB 協(xié)議其實基本上和這個一致，兩者的差別很小，就是心跳的方向不一樣。
Raft 和 ZAB
Raft 和 ZAB 協(xié)議將 Multi Paxos 劃分了三個子問題：
Leader Election
Log Replication
Safety
在 leader 選舉的過程中，也重定義角色：
Leader
Follower
Candidate
這個動畫網(wǎng)站生動展示了 leader 選舉和日志復(fù)制的過程。在這里就不多講了。
另外，raft 官方網(wǎng)站可以自己操作模擬選舉的過程。
今天，我們從 CAP 談到 Raft 和 ZAB，中間穿插了各種名詞，模型無論怎么變化，我們始終只有一個目的，那就是在一個
fault torlerance 的分布式架構(gòu)下，如何盡量保證其整個系統(tǒng)的可用性和一致性。最理想的模型當然是 Paxos，然而理論到落地還是有差距的，所以誕生了 Raft 和 ZAB，雖然只有一個 leader，但我們允許 leader 掛掉可以重新選舉 leader，這樣，中心式和分布式達到了一個妥協(xié)。
參考資料：
http://blog.kongfy.com/2016/08/被誤用的一致性/
http://blog.kongfy.com/2016/05/分布式共識 consensus：viewstamped、raft 及 paxos/
https://lotabout.me/2019/Raft-Consensus-Algorithm/
https://raft.github.io/
http://thesecretlivesofdata.com/raft/
