分布式系統(tǒng)的CAP和數(shù)據(jù)一致性模型

一、分布式系統(tǒng)的挑戰(zhàn)

關(guān)于分布式系統(tǒng)有一個經(jīng)典的CAP理論，

CAP理論的核心思想是任何基于網(wǎng)絡(luò)的數(shù)據(jù)共享系統(tǒng)最多只能滿足數(shù)據(jù)一致性(Consistency)、可用性(Availability)和網(wǎng)絡(luò)分區(qū)容忍(Partition Tolerance)三個特性中的兩個。

Consistency 一致性

一致性指“all nodes see the same data at the same time”，即更新操作成功并返回客戶端完成后，所有節(jié)點(diǎn)在同一時間的數(shù)據(jù)完全一致。等同于所有節(jié)點(diǎn)擁有數(shù)據(jù)的最新版本。

Availability 可用性

可用性指“Reads and writes always succeed”，即服務(wù)一直可用，而且是正常響應(yīng)時間。
對于一個可用性的分布式系統(tǒng)，每一個非故障的節(jié)點(diǎn)必須對每一個請求作出響應(yīng)。也就是，該系統(tǒng)使用的任何算法必須最終終止。當(dāng)同時要求分區(qū)容忍性時，這是一個很強(qiáng)的定義：即使是嚴(yán)重的網(wǎng)絡(luò)錯誤，每個請求必須終止。

Partition Tolerance 分區(qū)容忍性

Tolerance也可以翻譯為容錯，分區(qū)容忍性具體指“the system continues to operate despite arbitrary message loss or failure of part of the system”，即系統(tǒng)容忍網(wǎng)絡(luò)出現(xiàn)分區(qū)，分區(qū)之間網(wǎng)絡(luò)不可達(dá)的情況，分區(qū)容忍性和擴(kuò)展性緊密相關(guān)，Partition Tolerance特指在遇到某節(jié)點(diǎn)或網(wǎng)絡(luò)分區(qū)故障的時候，仍然能夠?qū)ν馓峁M足一致性和可用性的服務(wù)。

提高分區(qū)容忍性的辦法就是一個數(shù)據(jù)項(xiàng)復(fù)制到多個節(jié)點(diǎn)上，那么出現(xiàn)分區(qū)之后，這一數(shù)據(jù)項(xiàng)就可能分布到各個區(qū)里。分區(qū)容忍就提高了。然而，要把數(shù)據(jù)復(fù)制到多個節(jié)點(diǎn)，就會帶來一致性的問題，就是多個節(jié)點(diǎn)上面的數(shù)據(jù)可能是不一致的。要保證一致，每次寫操作就都要等待全部節(jié)點(diǎn)寫成功，而這等待又會帶來可用性的問題。

如圖，Client A可以發(fā)送指令到Server并且設(shè)置更新X的值，Client 1從Server讀取該值，在單點(diǎn)情況下，即沒有網(wǎng)絡(luò)分區(qū)的情況下，或者通過簡單的事務(wù)機(jī)制，可以保證Client 1讀到的始終是最新的值，不存在一致性的問題。

如果在系統(tǒng)中增加一組節(jié)點(diǎn)，Write操作可能在Server 1上成功，在Server 1上失敗，這時候?qū)τ贑lient 1和Client 2，就會讀取到不一致的值，出現(xiàn)不一致。如果要保持x值的一致性，Write操作必須同時失敗，降低系統(tǒng)的可用性。

可以看到，在分布式系統(tǒng)中，同時滿足CAP定律中“一致性”、“可用性”和“分區(qū)容錯性”三者是不可能的。

在通常的分布式系統(tǒng)中，為了保證數(shù)據(jù)的高可用，通常會將數(shù)據(jù)保留多個副本(replica)，網(wǎng)絡(luò)分區(qū)是既成的現(xiàn)實(shí)，于是只能在可用性和一致性兩者間做出選擇。CAP理論關(guān)注的是絕對情況下，在工程上，可用性和一致性并不是完全對立，我們關(guān)注的往往是如何在保持相對一致性的前提下，提高系統(tǒng)的可用性。

二、數(shù)據(jù)一致性模型

在互聯(lián)網(wǎng)領(lǐng)域的絕大多數(shù)的場景，都需要犧牲強(qiáng)一致性來換取系統(tǒng)的高可用性，系統(tǒng)往往只需要保證“最終一致性”，只要這個最終時間是在用戶可以接受的范圍內(nèi)即可。

對于一致性，可以分為從服務(wù)端和客戶端兩個不同的視角，即內(nèi)部一致性和外部一致性。
沒有全局時鐘，絕對的內(nèi)部一致性是沒有意義的，一般來說，我們討論的一致性都是外部一致性。外部一致性主要指的是多并發(fā)訪問時更新過的數(shù)據(jù)如何獲取的問題。

強(qiáng)一致性：
當(dāng)更新操作完成之后，任何多個后續(xù)進(jìn)程或者線程的訪問都會返回最新的更新過的值。這種是對用戶最友好的，就是用戶上一次寫什么，下一次就保證能讀到什么。根據(jù) CAP 理論，這種實(shí)現(xiàn)需要犧牲可用性。

弱一致性：
系統(tǒng)并不保證續(xù)進(jìn)程或者線程的訪問都會返回最新的更新過的值。用戶讀到某一操作對系統(tǒng)特定數(shù)據(jù)的更新需要一段時間，我們稱這段時間為“不一致性窗口”。系統(tǒng)在數(shù)據(jù)寫入成功之后，不承諾立即可以讀到最新寫入的值，也不會具體的承諾多久之后可以讀到。

最終一致性：
是弱一致性的一種特例。系統(tǒng)保證在沒有后續(xù)更新的前提下，系統(tǒng)最終返回上一次更新操作的值。在沒有故障發(fā)生的前提下，不一致窗口的時間主要受通信延遲，系統(tǒng)負(fù)載和復(fù)制副本的個數(shù)影響。

最終一致性模型根據(jù)其提供的不同保證可以劃分為更多的模型，包括因果一致性和讀自寫一致性等。

三、兩階段和三階段提交

在分布式系統(tǒng)中，各個節(jié)點(diǎn)之間在物理上相互獨(dú)立，通過網(wǎng)絡(luò)進(jìn)行溝通和協(xié)調(diào)。典型的比如關(guān)系型數(shù)據(jù)庫，由于存在事務(wù)機(jī)制，可以保證每個獨(dú)立節(jié)點(diǎn)上的數(shù)據(jù)操作可以滿足ACID。但是，相互獨(dú)立的節(jié)點(diǎn)之間無法準(zhǔn)確的知道其他節(jié)點(diǎn)中的事務(wù)執(zhí)行情況，所以兩臺機(jī)器理論上無法達(dá)到一致的狀態(tài)。

如果想讓分布式部署的多臺機(jī)器中的數(shù)據(jù)保持一致性，那么就要保證在所有節(jié)點(diǎn)的數(shù)據(jù)寫操作，要不全部都執(zhí)行，要么全部的都不執(zhí)行。但是，一臺機(jī)器在執(zhí)行本地事務(wù)的時候無法知道其他機(jī)器中的本地事務(wù)的執(zhí)行結(jié)果。所以節(jié)點(diǎn)并不知道本次事務(wù)到底應(yīng)該commit還是roolback。

所以實(shí)現(xiàn)分布式事務(wù)，需要讓當(dāng)前節(jié)點(diǎn)知道其他節(jié)點(diǎn)的任務(wù)執(zhí)行狀態(tài)。常規(guī)的解決辦法就是引入一個“協(xié)調(diào)者”的組件來統(tǒng)一調(diào)度所有分布式節(jié)點(diǎn)的執(zhí)行。著名的是二階段提交協(xié)議（Two Phase Commitment Protocol）和三階段提交協(xié)議（Three Phase Commitment Protocol）。

1、二階段提交協(xié)議

Two Phase指的是Commit-request階段和Commit階段。

請求階段

在請求階段，協(xié)調(diào)者將通知事務(wù)參與者準(zhǔn)備提交或取消事務(wù)，然后進(jìn)入表決過程。在表決過程中，參與者將告知協(xié)調(diào)者自己的決策：同意（事務(wù)參與者本地作業(yè)執(zhí)行成功）或取消（本地作業(yè)執(zhí)行故障）。

提交階段

在該階段，協(xié)調(diào)者將基于第一個階段的投票結(jié)果進(jìn)行決策：提交或取消。當(dāng)且僅當(dāng)所有的參與者同意提交事務(wù)協(xié)調(diào)者才通知所有的參與者提交事務(wù)，否則協(xié)調(diào)者將通知所有的參與者取消事務(wù)。參與者在接收到協(xié)調(diào)者發(fā)來的消息后將執(zhí)行響應(yīng)的操作。

可以看出，兩階段提交協(xié)議存在明顯的問題：

同步阻塞

執(zhí)行過程中，所有參與節(jié)點(diǎn)都是事務(wù)獨(dú)占狀態(tài)，當(dāng)參與者占有公共資源時，第三方節(jié)點(diǎn)訪問公共資源被阻塞。

單點(diǎn)問題

一旦協(xié)調(diào)者發(fā)生故障，參與者會一直阻塞下去。

數(shù)據(jù)不一致性

在第二階段中，假設(shè)協(xié)調(diào)者發(fā)出了事務(wù)commit的通知，但是因?yàn)榫W(wǎng)絡(luò)問題該通知僅被一部分參與者所收到并執(zhí)行commit，其余的參與者沒有收到通知一直處于阻塞狀態(tài)，這段時間就產(chǎn)生了數(shù)據(jù)的不一致性。

2、三階段提交協(xié)議

Three Phase分別為CanCommit、PreCommit、DoCommit。

三階段提交針對兩階段提交做了改進(jìn)：

引入超時機(jī)制。在2PC中，只有協(xié)調(diào)者擁有超時機(jī)制，3PC同時在協(xié)調(diào)者和參與者中都引入超時機(jī)制。

在第一階段和第二階段中插入一個準(zhǔn)備階段。保證了在最后提交階段之前各參與節(jié)點(diǎn)的狀態(tài)是一致的。

四、Paxos算法的提出

二階段提交還是三階段提交都無法很好的解決分布式的一致性問題，直到Paxos算法的提出，Paxos協(xié)議由Leslie Lamport最早在1990年提出，目前已經(jīng)成為應(yīng)用最廣的分布式一致性算法。Google Chubby的作者M(jìn)ike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

1、節(jié)點(diǎn)角色

Paxos 協(xié)議中，有三類節(jié)點(diǎn):

Proposer:提案者

Proposer可以有多個，Proposer 提出議案(value)。所謂 value，在工程中可以是任何操作，例如“修改某個變量的值為某個值”、“設(shè)置當(dāng)前 primary 為某個節(jié)點(diǎn)”等等。Paxos 協(xié)議中統(tǒng)一將這些操作抽象為 value。不同的 Proposer 可以提出不同的甚至矛盾的 value，例如某個 Proposer 提議“將變量 X 設(shè)置為 1”，另一個 Proposer 提議“將變量 X設(shè)置為2”，但對同一輪 Paxos 過程，最多只有一個 value 被批準(zhǔn)。

Acceptor:批準(zhǔn)者

Acceptor有N個，Proposer提出的value必須獲得超過半數(shù)(N/2+1)的Acceptor批準(zhǔn)后才能通過。Acceptor之間完全對等獨(dú)立。

Learner:學(xué)習(xí)者

Learner學(xué)習(xí)被批準(zhǔn)的value。所謂學(xué)習(xí)就是通過讀取各個 Proposer 對 value 的選擇結(jié)果，如果某個 value 被超過半數(shù) Proposer 通過，則 Learner 學(xué)習(xí)到了這個 value。這里類似 Quorum 議會機(jī)制，某個 value 需要獲得 W=N/2 + 1 的 Acceptor 批準(zhǔn)，Learner 需要至少讀取 N/2+1 個 Accpetor，至多讀取N 個Acceptor的結(jié)果后，能學(xué)習(xí)到一個通過的value。

2、約束條件

上述三類角色只是邏輯上的劃分，實(shí)踐中一個節(jié)點(diǎn)可以同時充當(dāng)這三類角色。有些文章會添加一個Client角色，作為產(chǎn)生議題者，實(shí)際不參與選舉過程。Paxos中 proposer 和acceptor是算法的核心角色，paxos描述的就是在一個由多個 proposer 和多個 acceptor 構(gòu)成的系統(tǒng)中，如何讓多個 acceptor 針對 proposer 提出的多種提案達(dá)成一致的過程，而 learner 只是“學(xué)習(xí)”最終被批準(zhǔn)的提案。

Paxos協(xié)議流程還需要滿足幾個約束條件：

Acceptor必須接受它收到的第一個提案；

如果一個提案的v值被大多數(shù)Acceptor接受過，那后續(xù)的所有被接受的提案中也必須包含v值（v值可以理解為提案的內(nèi)容，提案由一個或多個v和提案編號組成）；

如果某一輪 Paxos 協(xié)議批準(zhǔn)了某個 value，則以后各輪 Paxos 只能批準(zhǔn)這個value；

每輪 Paxos 協(xié)議分為準(zhǔn)備階段和批準(zhǔn)階段，在這兩個階段 Proposer 和 Acceptor 有各自的處理流程。

Proposer與Acceptor之間的交互主要有4類消息通信，如下圖：

這4類消息對應(yīng)于paxos算法的兩個階段4個過程：

Phase 1
a) proposer向網(wǎng)絡(luò)內(nèi)超過半數(shù)的acceptor發(fā)送prepare消息
b) acceptor正常情況下回復(fù)promise消息

Phase 2
a) 在有足夠多acceptor回復(fù)promise消息時，proposer發(fā)送accept消息
b) 正常情況下acceptor回復(fù)accepted消息

3、選舉過程

Phase 1 準(zhǔn)備階段

Proposer 生成全局唯一且遞增的ProposalID，向 Paxos 集群的所有機(jī)器發(fā)送 Prepare請求，這里不攜帶value，只攜帶N即ProposalID 。Acceptor 收到 Prepare請求 后，判斷：收到的ProposalID 是否比之前已響應(yīng)的所有提案的N大：
如果是，則：
(1) 在本地持久化 N，可記為Max_N。
(2) 回復(fù)請求，并帶上已Accept的提案中N最大的value（若此時還沒有已Accept的提案，則返回value為空）。
(3) 做出承諾：不會Accept任何小于Max_N的提案。

如果否：不回復(fù)或者回復(fù)Error。

Phase 2 選舉階段

P2a：Proposer發(fā)送 Accept
經(jīng)過一段時間后，Proposer 收集到一些 Prepare 回復(fù)，有下列幾種情況：
(1) 回復(fù)數(shù)量 > 一半的Acceptor數(shù)量，且所有的回復(fù)的value都為空，則Porposer發(fā)出accept請求，并帶上自己指定的value。
(2) 回復(fù)數(shù)量 > 一半的Acceptor數(shù)量，且有的回復(fù)value不為空，則Porposer發(fā)出accept請求，并帶上回復(fù)中ProposalID最大的value(作為自己的提案內(nèi)容)。
(3) 回復(fù)數(shù)量 <= 一半的Acceptor數(shù)量，則嘗試更新生成更大的ProposalID，再轉(zhuǎn)P1a執(zhí)行。

P2b：Acceptor應(yīng)答Accept
Accpetor 收到 Accpet請求 后，判斷：
(1) 收到的N >= Max_N (一般情況下是 等于)，則回復(fù)提交成功，并持久化N和value。
(2) 收到的N < Max_N，則不回復(fù)或者回復(fù)提交失敗。

P2c: Proposer統(tǒng)計(jì)投票
經(jīng)過一段時間后，Proposer收集到一些 Accept 回復(fù)提交成功，有幾種情況：
(1) 回復(fù)數(shù)量 > 一半的Acceptor數(shù)量，則表示提交value成功。此時，可以發(fā)一個廣播給所有Proposer、Learner，通知它們已commit的value。
(2) 回復(fù)數(shù)量 <= 一半的Acceptor數(shù)量，則 嘗試 更新生成更大的 ProposalID，再轉(zhuǎn)P1a執(zhí)行。
(3) 收到一條提交失敗的回復(fù)，則嘗試更新生成更大的 ProposalID，再轉(zhuǎn)P1a執(zhí)行。

4.相關(guān)討論

Paxos算法的核心思想：
（1）引入了多個Acceptor，單個Acceptor就類似2PC中協(xié)調(diào)者的單點(diǎn)問題，避免故障
（2）Proposer用更大ProposalID來搶占臨時的訪問權(quán)，可以對比2PC協(xié)議，防止其中一個Proposer崩潰宕機(jī)產(chǎn)生阻塞問題
（3）保證一個N值，只有一個Proposer能進(jìn)行到第二階段運(yùn)行，Proposer按照ProposalID遞增的順序依次運(yùn)行(3) 新ProposalID的proposer比如認(rèn)同前面提交的Value值，遞增的ProposalID的Value是一個繼承關(guān)系

為什么在Paxos運(yùn)行過程中，半數(shù)以內(nèi)的Acceptor失效都能運(yùn)行？
(1) 如果半數(shù)以內(nèi)的Acceptor失效時 還沒確定最終的value，此時，所有Proposer會競爭 提案的權(quán)限，最終會有一個提案會 成功提交。之后，會有半過數(shù)的Acceptor以這個value提交成功。
(2) 如果半數(shù)以內(nèi)的Acceptor失效時 已確定最終的value，此時，所有Proposer提交前 必須以 最終的value 提交，此值也可以被獲取，并不再修改。

如何產(chǎn)生唯一的編號呢？
在《Paxos made simple》中提到的是讓所有的Proposer都從不相交的數(shù)據(jù)集合中進(jìn)行選擇，例如系統(tǒng)有5個Proposer，則可為每一個Proposer分配一個標(biāo)識j(0~4)，則每一個proposer每次提出決議的編號可以為5*i + j(i可以用來表示提出議案的次數(shù))。