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

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

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

Consistency 一致性

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

Availability 可用性

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

Partition Tolerance 分區(qū)容忍性

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

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

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

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

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

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

二、數據一致性模型

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

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

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

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

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

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

三、兩階段和三階段提交

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

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

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

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

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

請求階段

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

提交階段

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

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

同步阻塞

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

單點問題

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

數據不一致性

在第二階段中，假設協(xié)調者發(fā)出了事務commit的通知，但是因為網絡問題該通知僅被一部分參與者所收到并執(zhí)行commit，其余的參與者沒有收到通知一直處于阻塞狀態(tài)，這段時間就產生了數據的不一致性。

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

Three Phase分別為CanCommit、PreCommit、DoCommit。

三階段提交針對兩階段提交做了改進：

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

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

四、Paxos算法的提出

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

1、節(jié)點角色

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

Proposer:提案者

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

Acceptor:批準者

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

Learner:學習者

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

2、約束條件

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

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

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

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

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

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

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

這4類消息對應于paxos算法的兩個階段4個過程：

Phase 1
a) proposer向網絡內超過半數的acceptor發(fā)送prepare消息
b) acceptor正常情況下回復promise消息

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

3、選舉過程

Phase 1 準備階段

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

如果否：不回復或者回復Error。

Phase 2 選舉階段

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

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

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

4.相關討論

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

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

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