背景回複”加群“擷取公衆号專屬群聊入口
什麼是 CAP
關于 CAP 理論的背景介紹已經很多，這裡不過多介紹，我們談談如何了解它的問題。
用通俗易懂的話解釋三個名詞：
一緻性
如果剛剛向一個節點寫入，那麼之後，從另外一個節點讀取的必須是剛剛寫入的資料，不能是更老的資料。
可用性
如果請求一個節點，這個節點必須能夠給予回複，如果節點挂掉了，那就談不上可用性了。
分區容忍性
是否容忍網絡分區，即可以允許節點和其它節點無法通信。
CAP 的意思就是說我們最多隻能保證其中兩個條件同時成立。
下面我們來看看為什麼。
如圖所示，假如我們滿足了分區容忍性，即虛線處表示兩個節點發生了分區。
- 假如要滿足一緻性，那麼，我們隻能讓請求另一個節點的操作暫時 hang 住，傳回 client 失敗或者逾時的結果，這種情況多發生在銀行櫃台等對資料一緻性要求很高的情境下，因為比起保證使用者資金數目的正确性比暫時讓使用者無法操作要更重要一些。
- 假如要滿足可用性，因為網絡已經隔離，也就沒辦法達到一緻性，這種情況多發生在網際網路行業中，比如新聞等對資料一緻性要求不高但對可用性要求高的情況下，畢竟，使用者壓根看不了新聞比看不到及時新聞要重要的多。
大家可以自己自由組合，最終會證明，三種條件不可能同時滿足，其實大部分情況下，我們都是在一緻性和可用性之間取舍而已。
Consistency = Consensus?
Consistency 幾乎被業界用爛，以至于當我們在讨論一緻性的時候，其實我們都無法确定對方所說的一緻性是不是和自己的那個一緻。
Consistency：一緻性，Consensus：協同，這兩個概念極容易混淆。
我們常說的一緻性（Consistency）在分布式系統中指的是對于同一個資料的多個副本，其對外表現的資料一緻性，如線性一緻性、因果一緻性、最終一緻性等，都是用來描述副本問題中的一緻性的。而共識（Consensus）則不同，簡單來說，共識問題是要經過某種算法使多個節點達成相同狀态的一個過程。在我看來，一緻性強調結果，共識強調過程。
共識？狀态機？
Ken Thompson
共識有個更高逼格的稱呼：
基于狀态機複制的共識算法
那麼，狀态機是什麼？
狀态機是有限狀态自動機的簡稱，是現實事物運作規則抽象而成的一個數學模型。
看下圖，門，有兩種狀态，開着的和關着的。是以，在我看來狀态是一種靜态的場景，而轉換賦予了其動态的變化。
以此類比一下，如果一個節點目前的資料是 X，現在有了 add+1 的記錄檔來了，那麼現在的狀态就是 X+1，好了，狀态（X）有了，變化（記錄檔）有了，這就是狀态機。
分布式共識，簡單來說，就是在一個或多個節點提議了一個狀态應當是什麼後，系統中所有節點對這個狀态達成一緻意見的整個過程。
共識是過程，一緻是結果。
共識模型
主從同步：
我們都知道 MySQL 等業界常見資料庫的主從同步（Master-Slave Replication)，主從同步分三個階段：
- Master 接受寫請求
- Master 複制日志至 Slave
- Master 等待，直到所有從庫傳回。
可見，主從同步模型存在緻命問題：隻要一個節點失敗，則 Master 就會阻塞，導緻整個叢集不可用，保證了一緻性，可用性缺大大降低了。
多數派：
每次寫入大于 N/2 個節點，每次讀也保證從 N/2 個節點中讀。多數派的模型看似完美解決了多節點的一緻性問題，不就是性能差點嘛，可是在并發的情況下就不一定了，如下圖：
在并發環境下，因為每個節點的記錄檔寫入順序無法保證一緻，也就無法保證最終的一緻性。如圖，都是向三個節點
inc5、set0 兩個操作，但因為順序不一樣，最終狀态兩個是 0，一個是 5。是以我們需要引入一種機制，給每個記錄檔編上号，這個号從小到大生成，這樣，每個節點就不會弄錯。（是否想到了網絡中的分包與重組？）那麼，現在關鍵問題又來了，怎麼協同這個編号？貌似這是雞生蛋、蛋生雞的問題。
Paxos
Paxos 模型試圖探讨分布式共識問題的一個更一般的形式。
Lesile Lamport，Latex 的發明者，提出了 Paxos 算法。他虛拟了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制定法律，但是沒有人願意将自己的全部時間和精力放在這件事上。是以無論是議員、議長或者傳遞紙條的服務員都不能承諾别人需要時一定會出現，也無法承諾準許決議後者傳遞消息的時間。由于 Paxos 讓人太難以了解，Lamport 覺得同行不能了解他的幽默感，于是後來又重新發表了樸實的算法描述版本《Paxos Made Simple》。
該共識算法就整體來說，存在兩個階段，如圖，第一個階段是提議，第二個階段是決定。
分布式系統要做到 fault tolorence，就需要共識模型，而節點達成共識，不僅需要節點之間的算法，還會取決于 client 的行為。比如即使副本系統使用 multi-paxos 在所有副本伺服器上同步了日志序号，但如果 Client 被允許從非 Leader 節點寫入資料，則整個副本系統仍然不是強一緻的。
下面，重頭戲來了，詳細介紹 Paxos。
角色介紹：
Client：系統外部角色，請求發起者。如群眾。
Proposer: 接受 Client 請求，向叢集提出提議（propose）。并在沖突發生時，起到沖突調節的作用。如議員，替群眾提出議案。
Accpetor: 提議投票和接收者，隻有在形成法定人數（Quorum，即 Majority 多數派）時，提議才會最終被接受。如國會。
Learner: 提議接受者，backup，備份，對叢集的一緻性沒影響。如記錄員。
步驟、階段：
1.Phase1a: Prepare
proposer 提出一個議案，編号為 N，N 一定大于這個 proposer 之前提出的提案編号，請求 acceptor 的 quorum（大多數） 接受。
2.Phase1b: Promise
如果 N 大于此 acceptor 之前接受的任何提案編号則接受，否則拒絕。
3.Phase2a: Accept
如果達到了多數派，proposer 會發出 accept 請求，此請求包含上一步的提案編号和提案内容。
4.Phase2b: Accepted
如果此 acceptor 在此期間沒有收到任何大于 N 的提案，則接受此提案内容，否則忽略。
還記得上文中我們提到過，同步編号是非常重要的問題，綠色框出來的實際上就是同步編号的過程。通過這個編号，就知道每條記錄檔的先後順序。簡單說來，第一階段，擷取編号，第二階段，寫入日志。可以看出來，Paxos 通過兩輪互動，犧牲時間和性能來達到彌補一緻性的問題。
現在我們考慮部分節點 down 掉的情景。
由于是多數派 accptor 達成了一緻，第一階段仍然成功獲得了編号，所有最終還是成功的。
考慮 proposer down 掉的情景。
沒關系，雖然第一個 proposer 失敗，但下一個 proposer 用更大的提案編号，是以下一次 proposer 最終還是成功了，仍然保證了可用性和一緻性。
潛在問題：活鎖
Paxos 存在活鎖問題。如圖，當 第一個 proposer 在第一階段送出請求，還沒來得及後續的第二階段請求，緊接着第二個 proposer 在第一階段也送出請求，如果這樣無窮無盡，acceptor 始終停留在決定順序号的過程上，那大家誰也成功不了，遇到這樣的問題，其實很好解決，如果發現順序号被新的 proposer 更新了，則引入一個随機的等待的逾時時間，這樣就避免了多個 proposer 發生沖突的問題。
Multi Paxos
由于 Paxos 存在的問題：難實作、效率低（2 輪 rpc）、活鎖。
是以又引入了 Multi Paxos，Multi Paxos 引入 Leader，也就是唯一的 proposer，所有的請求都需經過此 Leader。
因為隻有一個節點維護提案編号，這樣，就省略了第一輪讨論提議編号的過程。
然後進一步簡化角色。
Servers 中第左邊的就是 Proposer，另外兩個和自身充當 acceptor，這樣就更像我們真實的系統了。Raft 和 ZAB 協定其實基本上和這個一緻，兩者的差别很小，就是心跳的方向不一樣。
Raft 和 ZAB
Raft 和 ZAB 協定将 Multi Paxos 劃分了三個子問題：
- Leader Election
- Log Replication
- Safety
在 leader 選舉的過程中，也重定義角色：
- Leader
- Follower
- Candidate
這個動畫網站生動展示了 leader 選舉和日志複制的過程。在這裡就不多講了。
另外，raft 官方網站可以自己操作模拟選舉的過程。
總結
今天，我們從 CAP 談到 Raft 和 ZAB，中間穿插了各種名詞，模型無論怎麼變化，我們始終隻有一個目的，那就是在一個
fault torlerance 的分布式架構下，如何盡量保證其整個系統的可用性和一緻性。最理想的模型當然是 Paxos，然而理論到落地還是有差距的，是以誕生了 Raft 和 ZAB，雖然隻有一個 leader，但我們允許 leader 挂掉可以重新選舉 leader，這樣，中心式和分布式達到了一個妥協。
想知道更多？掃描下面的二維碼關注我
-
咱們從頭到尾說一次Java垃圾回收
-
Netty、Kafka中的零拷貝技術到底有多牛？
-
go為什麼這麼快？
-
面試前，我們要複習多少Redis知識？
-
《深入了解Java虛拟機》第2版挖的坑終于在第3版中被R大填平了
-
Redis性能問題分析