什么是 CAP

關(guān)于 CAP 理論的背景介紹已經(jīng)很多，這里不過(guò)多介紹，我們談?wù)勅绾卫斫馑膯?wèn)題。

用通俗易懂的話解釋三個(gè)名詞：

一致性

如果剛剛向一個(gè)節(jié)點(diǎn)寫(xiě)入，那么之后，從另外一個(gè)節(jié)點(diǎn)讀取的必須是剛剛寫(xiě)入的數(shù)據(jù)，不能是更老的數(shù)據(jù)。

可用性

如果請(qǐng)求一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)必須能夠給予回復(fù)，如果節(jié)點(diǎn)掛掉了，那就談不上可用性了。

分區(qū)容忍性

是否容忍網(wǎng)絡(luò)分區(qū)，即可以允許節(jié)點(diǎn)和其它節(jié)點(diǎn)無(wú)法通信。

CAP 的意思就是說(shuō)我們最多只能保證其中兩個(gè)條件同時(shí)成立。

下面我們來(lái)看看為什么。

[[314890]]

如圖所示，假如我們滿(mǎn)足了分區(qū)容忍性，即虛線處表示兩個(gè)節(jié)點(diǎn)發(fā)生了分區(qū)。

• 假如要滿(mǎn)足一致性，那么，我們只能讓請(qǐng)求另一個(gè)節(jié)點(diǎn)的操作暫時(shí) hang 住，返回 client 失敗或者超時(shí)的結(jié)果，這種情況多發(fā)生在銀行柜臺(tái)等對(duì)數(shù)據(jù)一致性要求很高的情境下，因?yàn)楸绕鸨ＷC用戶(hù)資金數(shù)目的正確性比暫時(shí)讓用戶(hù)無(wú)法操作要更重要一些。
• 假如要滿(mǎn)足可用性，因?yàn)榫W(wǎng)絡(luò)已經(jīng)隔離，也就沒(méi)辦法達(dá)到一致性，這種情況多發(fā)生在互聯(lián)網(wǎng)行業(yè)中，比如新聞等對(duì)數(shù)據(jù)一致性要求不高但對(duì)可用性要求高的情況下，畢竟，用戶(hù)壓根看不了新聞比看不到及時(shí)新聞要重要的多。

大家可以自己自由組合，最終會(huì)證明，三種條件不可能同時(shí)滿(mǎn)足，其實(shí)大部分情況下，我們都是在一致性和可用性之間取舍而已。

Consistency = Consensus?

Consistency 幾乎被業(yè)界用爛，以至于當(dāng)我們?cè)谟懻撘恢滦缘臅r(shí)候，其實(shí)我們都無(wú)法確定對(duì)方所說(shuō)的一致性是不是和自己的那個(gè)一致。

Consistency：一致性，Consensus：協(xié)同，這兩個(gè)概念極容易混淆。

我們常說(shuō)的一致性(Consistency)在分布式系統(tǒng)中指的是對(duì)于同一個(gè)數(shù)據(jù)的多個(gè)副本，其對(duì)外表現(xiàn)的數(shù)據(jù)一致性，如線性一致性、因果一致性、最終一致性等，都是用來(lái)描述副本問(wèn)題中的一致性的。而共識(shí)(Consensus)則不同，簡(jiǎn)單來(lái)說(shuō)，共識(shí)問(wèn)題是要經(jīng)過(guò)某種算法使多個(gè)節(jié)點(diǎn)達(dá)成相同狀態(tài)的一個(gè)過(guò)程。在我看來(lái)，一致性強(qiáng)調(diào)結(jié)果，共識(shí)強(qiáng)調(diào)過(guò)程。

[[314891]]

共識(shí)?狀態(tài)機(jī)?

[[314892]]

Ken Thompson

共識(shí)有個(gè)更高逼格的稱(chēng)呼：

基于狀態(tài)機(jī)復(fù)制的共識(shí)算法

那么，狀態(tài)機(jī)是什么?

狀態(tài)機(jī)是有限狀態(tài)自動(dòng)機(jī)的簡(jiǎn)稱(chēng)，是現(xiàn)實(shí)事物運(yùn)行規(guī)則抽象而成的一個(gè)數(shù)學(xué)模型。

看下圖，門(mén)，有兩種狀態(tài)，開(kāi)著的和關(guān)著的。因此，在我看來(lái)狀態(tài)是一種靜態(tài)的場(chǎng)景，而轉(zhuǎn)換賦予了其動(dòng)態(tài)的變化。

以此類(lèi)比一下，如果一個(gè)節(jié)點(diǎn)當(dāng)前的數(shù)據(jù)是 X，現(xiàn)在有了 add+1 的操作日志來(lái)了，那么現(xiàn)在的狀態(tài)就是 X+1，好了，狀態(tài)(X)有了，變化(操作日志)有了，這就是狀態(tài)機(jī)。

分布式共識(shí)，簡(jiǎn)單來(lái)說(shuō)，就是在一個(gè)或多個(gè)節(jié)點(diǎn)提議了一個(gè)狀態(tài)應(yīng)當(dāng)是什么后，系統(tǒng)中所有節(jié)點(diǎn)對(duì)這個(gè)狀態(tài)達(dá)成一致意見(jiàn)的整個(gè)過(guò)程。

共識(shí)是過(guò)程，一致是結(jié)果。

共識(shí)模型

主從同步：

我們都知道 MySQL 等業(yè)界常見(jiàn)數(shù)據(jù)庫(kù)的主從同步(Master-Slave Replication)，主從同步分三個(gè)階段：

• Master 接受寫(xiě)請(qǐng)求
• Master 復(fù)制日志至 Slave
• Master 等待，直到所有從庫(kù)返回。

可見(jiàn)，主從同步模型存在致命問(wèn)題：只要一個(gè)節(jié)點(diǎn)失敗，則 Master 就會(huì)阻塞，導(dǎo)致整個(gè)集群不可用，保證了一致性，可用性缺大大降低了。

多數(shù)派：

每次寫(xiě)入大于 N/2 個(gè)節(jié)點(diǎn)，每次讀也保證從 N/2 個(gè)節(jié)點(diǎn)中讀。多數(shù)派的模型看似完美解決了多節(jié)點(diǎn)的一致性問(wèn)題，不就是性能差點(diǎn)嘛，可是在并發(fā)的情況下就不一定了，如下圖：

在并發(fā)環(huán)境下，因?yàn)槊總€(gè)節(jié)點(diǎn)的操作日志寫(xiě)入順序無(wú)法保證一致，也就無(wú)法保證最終的一致性。如圖，都是向三個(gè)節(jié)點(diǎn)

inc5、set0 兩個(gè)操作，但因?yàn)轫樞虿灰粯?，最終狀態(tài)兩個(gè)是 0，一個(gè)是 5。因此我們需要引入一種機(jī)制，給每個(gè)操作日志編上號(hào)，這個(gè)號(hào)從小到大生成，這樣，每個(gè)節(jié)點(diǎn)就不會(huì)弄錯(cuò)。(是否想到了網(wǎng)絡(luò)中的分包與重組?)那么，現(xiàn)在關(guān)鍵問(wèn)題又來(lái)了，怎么協(xié)同這個(gè)編號(hào)?貌似這是雞生蛋、蛋生雞的問(wèn)題。

Paxos

Paxos 模型試圖探討分布式共識(shí)問(wèn)題的一個(gè)更一般的形式。

Lesile Lamport，Latex 的發(fā)明者，提出了 Paxos 算法。他虛擬了一個(gè)叫做 Paxos 的希臘城邦，這個(gè)島按照議會(huì)民主制的政治模式制定法律，但是沒(méi)有人愿意將自己的全部時(shí)間和精力放在這件事上。所以無(wú)論是議員、議長(zhǎng)或者傳遞紙條的服務(wù)員都不能承諾別人需要時(shí)一定會(huì)出現(xiàn)，也無(wú)法承諾批準(zhǔn)決議后者傳遞消息的時(shí)間。由于 Paxos 讓人太難以理解，Lamport 覺(jué)得同行不能理解他的幽默感，于是后來(lái)又重新發(fā)表了樸實(shí)的算法描述版本《Paxos Made Simple》。

該共識(shí)算法就整體來(lái)說(shuō)，存在兩個(gè)階段，如圖，第一個(gè)階段是提議，第二個(gè)階段是決定。

分布式系統(tǒng)要做到 fault tolorence，就需要共識(shí)模型，而節(jié)點(diǎn)達(dá)成共識(shí)，不僅需要節(jié)點(diǎn)之間的算法，還會(huì)取決于 client 的行為。比如即使副本系統(tǒng)使用 multi-paxos 在所有副本服務(wù)器上同步了日志序號(hào)，但如果 Client 被允許從非 Leader 節(jié)點(diǎn)寫(xiě)入數(shù)據(jù)，則整個(gè)副本系統(tǒng)仍然不是強(qiáng)一致的。

下面，重頭戲來(lái)了，詳細(xì)介紹 Paxos。

角色介紹：

Client：系統(tǒng)外部角色，請(qǐng)求發(fā)起者。如民眾。

Proposer: 接受 Client 請(qǐng)求，向集群提出提議(propose)。并在沖突發(fā)生時(shí)，起到?jīng)_突調(diào)節(jié)的作用。如議員，替民眾提出議案。

Accpetor: 提議投票和接收者，只有在形成法定人數(shù)(Quorum，即 Majority 多數(shù)派)時(shí)，提議才會(huì)最終被接受。如國(guó)會(huì)。

Learner: 提議接受者，backup，備份，對(duì)集群的一致性沒(méi)影響。如記錄員。

步驟、階段：

1.Phase1a: Prepare

proposer 提出一個(gè)議案，編號(hào)為 N，N 一定大于這個(gè) proposer 之前提出的提案編號(hào)，請(qǐng)求 acceptor 的 quorum(大多數(shù)) 接受。

2.Phase1b: Promise

如果 N 大于此 acceptor 之前接受的任何提案編號(hào)則接受，否則拒絕。

3.Phase2a: Accept

如果達(dá)到了多數(shù)派，proposer 會(huì)發(fā)出 accept 請(qǐng)求，此請(qǐng)求包含上一步的提案編號(hào)和提案內(nèi)容。

4.Phase2b: Accepted

如果此 acceptor 在此期間沒(méi)有收到任何大于 N 的提案，則接受此提案內(nèi)容，否則忽略。

還記得上文中我們提到過(guò)，同步編號(hào)是非常重要的問(wèn)題，綠色框出來(lái)的實(shí)際上就是同步編號(hào)的過(guò)程。通過(guò)這個(gè)編號(hào)，就知道每條操作日志的先后順序。簡(jiǎn)單說(shuō)來(lái)，第一階段，獲取編號(hào)，第二階段，寫(xiě)入日志。可以看出來(lái)，Paxos 通過(guò)兩輪交互，犧牲時(shí)間和性能來(lái)達(dá)到彌補(bǔ)一致性的問(wèn)題。

現(xiàn)在我們考慮部分節(jié)點(diǎn) down 掉的情景。

由于是多數(shù)派 accptor 達(dá)成了一致，第一階段仍然成功獲得了編號(hào)，所有最終還是成功的。

考慮 proposer down 掉的情景。

沒(méi)關(guān)系，雖然第一個(gè) proposer 失敗，但下一個(gè) proposer 用更大的提案編號(hào)，所以下一次 proposer 最終還是成功了，仍然保證了可用性和一致性。

潛在問(wèn)題：活鎖

Paxos 存在活鎖問(wèn)題。如圖，當(dāng) 第一個(gè) proposer 在第一階段發(fā)出請(qǐng)求，還沒(méi)來(lái)得及后續(xù)的第二階段請(qǐng)求，緊接著第二個(gè) proposer 在第一階段也發(fā)出請(qǐng)求，如果這樣無(wú)窮無(wú)盡，acceptor 始終停留在決定順序號(hào)的過(guò)程上，那大家誰(shuí)也成功不了，遇到這樣的問(wèn)題，其實(shí)很好解決，如果發(fā)現(xiàn)順序號(hào)被新的 proposer 更新了，則引入一個(gè)隨機(jī)的等待的超時(shí)時(shí)間，這樣就避免了多個(gè) proposer 發(fā)生沖突的問(wèn)題。

Multi Paxos

由于 Paxos 存在的問(wèn)題：難實(shí)現(xiàn)、效率低(2 輪 rpc)、活鎖。

因此又引入了 Multi Paxos，Multi Paxos 引入 Leader，也就是唯一的 proposer，所有的請(qǐng)求都需經(jīng)過(guò)此 Leader。

因?yàn)橹挥幸粋€(gè)節(jié)點(diǎn)維護(hù)提案編號(hào)，這樣，就省略了第一輪討論提議編號(hào)的過(guò)程。

然后進(jìn)一步簡(jiǎn)化角色。

Servers 中第左邊的就是 Proposer，另外兩個(gè)和自身充當(dāng) acceptor，這樣就更像我們真實(shí)的系統(tǒng)了。Raft 和 ZAB 協(xié)議其實(shí)基本上和這個(gè)一致，兩者的差別很小，就是心跳的方向不一樣。

Raft 和 ZAB

Raft 和 ZAB 協(xié)議將 Multi Paxos 劃分了三個(gè)子問(wèn)題：

• Leader Election
• Log Replication
• Safety

在 leader 選舉的過(guò)程中，也重定義角色：

• Leader
• Follower
• Candidate

這個(gè)動(dòng)畫(huà)網(wǎng)站生動(dòng)展示了 leader 選舉和日志復(fù)制的過(guò)程。在這里就不多講了。

另外，raft 官方網(wǎng)站可以自己操作模擬選舉的過(guò)程。

總結(jié)

今天，我們從 CAP 談到 Raft 和 ZAB，中間穿插了各種名詞，模型無(wú)論怎么變化，我們始終只有一個(gè)目的，那就是在一個(gè)

fault torlerance 的分布式架構(gòu)下，如何盡量保證其整個(gè)系統(tǒng)的可用性和一致性。最理想的模型當(dāng)然是 Paxos，然而理論到落地還是有差距的，所以誕生了 Raft 和 ZAB，雖然只有一個(gè) leader，但我們?cè)试S leader 掛掉可以重新選舉 leader，這樣，中心式和分布式達(dá)到了一個(gè)妥協(xié)。