一、分布式系統的挑戰

關于分布式系統有一個經典的CAP理論，

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

Consistency 一致性

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

Availability 可用性

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

Partition Tolerance 分區容忍性

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

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

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

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

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

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

二、數據一致性模型

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

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

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

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

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

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

三、兩階段和三階段提交

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

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

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

1、二階段提交協議

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

請求階段

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

提交階段

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

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

同步阻塞

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

單點問題

一旦協調者發生故障，參與者會一直阻塞下去。

數據不一致性

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

2、三階段提交協議

Three Phase分別為CanCommit、PreCommit、DoCommit。

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

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

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

四、Paxos算法的提出

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

1、節點角色

Paxos 協議中，有三類節點:

Proposer:提案者

Proposer可以有多個，Proposer 提出議案(value)。所謂 value，在工程中可以是任何操作，例如“修改某個變量的值為某個值”、“設置當前 primary 為某個節點”等等。Paxos 協議中統一將這些操作抽象為 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、約束條件

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

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

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

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

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

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

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

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

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

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

3、選舉過程

Phase 1 準備階段

Proposer 生成全局唯一且遞增的ProposalID，向 Paxos 集群的所有機器發送 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發送 Accept
經過一段時間后，Proposer 收集到一些 Prepare 回復，有下列幾種情況：
(1) 回復數量 > 一半的Acceptor數量，且所有的回復的value都為空，則Porposer發出accept請求，并帶上自己指定的value。
(2) 回復數量 > 一半的Acceptor數量，且有的回復value不為空，則Porposer發出accept請求，并帶上回復中ProposalID最大的value(作為自己的提案內容)。
(3) 回復數量 <= 一半的Acceptor數量，則嘗試更新生成更大的ProposalID，再轉P1a執行。

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

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

4.相關討論

Paxos算法的核心思想：
（1）引入了多個Acceptor，單個Acceptor就類似2PC中協調者的單點問題，避免故障
（2）Proposer用更大ProposalID來搶占臨時的訪問權，可以對比2PC協議，防止其中一個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都從不相交的數據集合中進行選擇，例如系統有5個Proposer，則可為每一個Proposer分配一個標識j(0~4)，則每一個proposer每次提出決議的編號可以為5*i + j(i可以用來表示提出議案的次數)。