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

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

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

Consistency 一致性

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

Availability 可用性

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

Partition Tolerance 分區(qū)容忍性

Tolerance也可以翻譯為容錯(cuò)，分區(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ū)故障的時(shí)候，仍然能夠?qū)ν馓峁M足一致性和可用性的服務(wù)。

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

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

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

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

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

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

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

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

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

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

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

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

三、兩階段和三階段提交

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

如果想讓分布式部署的多臺(tái)機(jī)器中的數(shù)據(jù)保持一致性，那么就要保證在所有節(jié)點(diǎn)的數(shù)據(jù)寫操作，要不全部都執(zhí)行，要么全部的都不執(zhí)行。但是，一臺(tái)機(jī)器在執(zhí)行本地事務(wù)的時(shí)候無(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ī)的解決辦法就是引入一個(gè)“協(xié)調(diào)者”的組件來(lái)統(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階段。

請(qǐng)求階段

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

提交階段

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

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

同步阻塞

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

單點(diǎn)問(wèn)題

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

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

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

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

Three Phase分別為CanCommit、PreCommit、DoCommit。

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

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

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

四、Paxos算法的提出

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

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

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

Proposer:提案者

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

Acceptor:批準(zhǔn)者

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

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

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

2、約束條件

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

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

Acceptor必須接受它收到的第一個(gè)提案；

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

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

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

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

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

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

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

3、選舉過(guò)程

Phase 1 準(zhǔn)備階段

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

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

Phase 2 選舉階段

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

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

P2c: Proposer統(tǒng)計(jì)投票
經(jīng)過(guò)一段時(shí)間后，Proposer收集到一些 Accept 回復(fù)提交成功，有幾種情況：
(1) 回復(fù)數(shù)量 > 一半的Acceptor數(shù)量，則表示提交value成功。此時(shí)，可以發(fā)一個(gè)廣播給所有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）引入了多個(gè)Acceptor，單個(gè)Acceptor就類似2PC中協(xié)調(diào)者的單點(diǎn)問(wèn)題，避免故障
（2）Proposer用更大ProposalID來(lái)?yè)屨寂R時(shí)的訪問(wèn)權(quán)，可以對(duì)比2PC協(xié)議，防止其中一個(gè)Proposer崩潰宕機(jī)產(chǎn)生阻塞問(wèn)題
（3）保證一個(gè)N值，只有一個(gè)Proposer能進(jìn)行到第二階段運(yùn)行，Proposer按照ProposalID遞增的順序依次運(yùn)行(3) 新ProposalID的proposer比如認(rèn)同前面提交的Value值，遞增的ProposalID的Value是一個(gè)繼承關(guān)系

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

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