一致性算法Paxos詳解

分布式系統除了能提升整個系統的性能外還有一個重要的特性就是提高系統的可靠性，可靠性指的是當分布式系統中一臺或N臺機器宕掉后都不會導致系統不可用， 分布式系統是state machine replication的，每個節點都可能是其他節點的快照，這是保證分布式系統高可靠性的關鍵，而存在多個復制節點就會存在數據不一致的問題，這時 一致性 就成了分布式系統的核心；在分布式系統中必須保證：

假如在分布式系統中初始是各個節點的數據是一致的，每個節點都順序執行系列操作，然后每個節點最終的數據還是一致的。

一致性算法：用于保證在分布式系統中每個節點都順序執行相同的操作序列，在每一個指令上執行 一致性算法 就能夠保證最終各個節點的數據都是一致的。

Paxos就是用于解決一致性問題的算法，有多個節點就會存在節點間通信的問題，存在著兩種節點通訊模型：共享內存（Shared memory）、消息傳遞（Messages passing），Paxos是基于消息傳遞的通訊模型的。 Paxos為2014年圖靈獎得主Leslie Lamport在1990年提出的一致性算法，該算法被譽為類似算法中最有效的，Paxos不只適用于分布式系統中，凡是需要達成某種一致性時都可以使用 Paxos；

作用：Paxos用于解決分布式系統中一致性問題。 在一個Paxos過程只批準一個value，只有被prepare的value且被多數Acceptor接受才能被批準，被批準的value才能被learner；下面簡單描述Paxos的流程：

這樣一個場景，有Client一個、Proposer三個、Acceptor三個、Learner一個；Client向prepeare提交一 個data請求入庫，Proposer收到Client請求后生成一個序號1向三個Acceptor（最少兩個）發送序號1請求提交議案，假如三個 Acceptor收到Proposer申請提交的序號為1的請求三個Acceptor都是初次接受到請求，然后向Proposer回復Promise允許 提交議案，Proposer收到三個Acceptor（滿足過半數原則）的Promise回復后接著向三個Accptor正式提交議案（序號 1，value為data），三個Accptor都收到議案（序號1，value為data）請求期間沒有收到其他請求，Acceptor接受議案，回復 Proposer已接受議案，然后向Learner提交議案，Proposer收到回復后回復給Client成功處理請求，Learner收到議案后開始 學習議案（存儲data）；

Paxos中存在三種角色Proposer（提議者）、Acceptor（決策者）、Learner（議案學習者），整個過程（一個實例或稱一個事務或一個Round）分為兩個階段；

phase1（準備階段）

1. Proposer向超過半數（n/2+1）Acceptor發起prepare消息(發送編號)

2. 如果prepare符合協議規則Acceptor回復promise消息，否則拒絕

phase2（決議階段或投票階段）

1. 如果超過半數Acceptor回復promise，Proposer向Acceptor發送accept消息

2. Acceptor檢查accept消息是否符合規則，消息符合則批準accept請求

1. 只有提出的議案才能被選中，沒有議案提出就不會有被選中

2. 多個被提出的議案中只有一個議案會被選中

3. 提案沒選中后Learner就可以學習該提案

P1: Acceptor必須接受他接收到的第一個提案。

有這約束就會出現一個新問題：當多個議案被多個Proposer同時提出，這時每個Acceptor都接收到了他收到的第一個議案，此時沒法選擇最終議案。所以就又存在一個新的約束P2；

P2: 一個提案被選中需要過半數的Acceptor接受。

假設A為整個Acceptor集合，B為一個超過A一半的Acceptor集合，B為A的子集，C也是一個超過A一半的Acceptor集合，C也是A的子集，有此可知任意兩個過半集合中必定有一個共同的成員Acceptor；

此說明了一個Acceptor可以接受不止一個提案，此時需要一個編號來標識每一個提案，提案的格式為：[編號，Value]，編號為不可重復全序的，因為存在著一個一個Paxos過程只能批準一個value這時又推出了一個約束P3；

P3：當編號K0、Value為V0的提案(即[K0,V0])被過半的Acceptor接受后，今后（同一個Paxos或稱一個Round中）所有比K0更高編號且被Acceptor接受的提案，其Value值夜必須為V0。

因為每個Proposer都可提出多個議案，每個議案最初都有一個不同的Value所以要滿足P3就又要推出一個新的約束P4；

P4：只有Acceptor沒有接受過提案Proposer才能采用自己的Value，否者Proposer的Value提案為Acceptor中編號最大的Proposer Value；

Phase1（準備階段）

1. 每個Server都向Proposer發消息稱自己要成為leader，Server1往Proposer1發、Server2往Proposer2發、Server3往Proposer3發；

2. 現在每個Proposer都接收到了Server1發來的消息但時間不一樣，Proposer2先接收到了，然后是Proposer1，接著才是Proposer3；

3. Proposer2首先接收到消息所以他從系統中取得一個編號1，Proposer2向Acceptor2和Acceptor3發送一條，編號為1的消 息；接著Proposer1也接收到了Server1發來的消息，取得一個編號2，Proposer1向Acceptor1和Acceptor2發送一 條，編號為2的消息； 最后Proposer3也接收到了Server3發來的消息，取得一個編號3，Proposer3向Acceptor2和Acceptor3發送一條，編 號為3的消息；

4. 這時Proposer1發送的消息先到達Acceptor1和Acceptor2，這兩個都沒有接收過請求所以接受了請求返回[2,null]給Proposer1，并承諾不接受編號小于2的請求；

5. 此時Proposer2發送的消息到達Acceptor2和Acceptor3，Acceprot3沒有接收過請求返回[1,null]給 Proposer2，并承諾不接受編號小于1的請求，但這時Acceptor2已經接受過Proposer1的請求并承諾不接受編號小于的2的請求了，所 以Acceptor2拒絕Proposer2的請求；

6. 最后Proposer3發送的消息到達Acceptor2和Acceptor3，Acceptor2接受過提議，但此時編號為3大于Acceptor2的承諾2與Accetpor3的承諾1，所以接受提議返回[3,null];

7. Proposer2沒收到過半的回復所以重新取得編號4，并發送給Acceptor2和Acceptor3，然后Acceptor2和Acceptor3 都收到消息，此時編號4大于Acceptor2與Accetpor3的承諾3，所以接受提議返回[4,null]；

1. Proposer3收到過半（三個Server中兩個）的返回，并且返回的Value為null，所以Proposer3提交了[3,server3]的議案；

2. Proposer1收到過半返回，返回的Value為null，所以Proposer1提交了[2,server1]的議案；

3. Proposer2收到過半返回，返回的Value為null，所以Proposer2提交了[4,server2]的議案；

4. Acceptor1、Acceptor2接收到Proposer1的提案[2,server1]請求，Acceptor2承諾編號大于4所以拒絕了通過，Acceptor1通過了請求；

5. Proposer2的提案[4,server2]發送到了Acceptor2、Acceptor3，提案編號為4所以Acceptor2、Acceptor3都通過了提案請求；

6. Acceptor2、Acceptor3接收到Proposer3的提案[3,server3]請求，Acceptor2、Acceptor3承諾編號大于4所以拒絕了提案；

7. 此時過半的Acceptor都接受了Proposer2的提案[4,server2],Larner感知到了提案的通過，Larner學習提案，server2成為Leader；

參考資料

https://en.wikipedia.org/wiki/Paxos_(computer_science)