什么是Paxos演算法

?一致性就是資料保持一致，在分布式系統中，理解為多個節點中資料值的一致，而一致性又分為以下兩種：

• 強一致性
  ?在任意時刻所有節點的值都是一樣的，比如在A節點獲取到的key1的值應該和B節點獲取到的key1的值一樣，
• 弱一致性
  ?不保證任意時刻所有節點得值都是一樣的，最廣泛的一種實作是最終一致性，它不保證任意時刻上的任意節點得資料是一樣的，但是隨著時間遷移，不同節點上的同一份資料最侄訓達成一致，
  ?Paxos演算法就是著名的強一致性演算法，它有一個假設前提，在分布式系統中行程間通信會出現延遲、丟失、重復等現象，但是不會出現傳錯的現象，而Paxos就是為了保證在這樣的系統中行程間基于訊息傳遞就某個值達成一致，
  ? 其實在過去很長一段時間，Paxos演算法可以說是分布式共識的代名詞，當前最常用的一批共識演算法，比如，Fast Paxos演算法，Cheap Paxos演算法，Raft演算法等都是基于它來改進的，

?Paxos演算法主要包括兩部分：

• Basic Paxos演算法，該演算法描述的是多節點之間如何就某個值達成共識
• Multi-Paxos思想，它描述了執行多個Basic Paxos實體，就一系列值達成共識，赫赫有名的Raft演算法就是一種基于Multi-Paxos思想的共識演算法，
  ?其實這兩者的關系可以理解為Basic-Paxos是Multi-Paxos思想的核心,而Multi-Paxos就是多執行幾次Basic Paxos，
  ? 由于Paxos的作者蘭伯特提到的Multi-Paxos思想，缺少代碼實作，所以理解起來比較難，

2PC簡介

?假設現在要實作一個分布式集群，這個集群是由N1,N2,N3組成，提供只讀kv存盤服務，當創建只讀變數時，就得對它進行賦值，而且這個值之后是無法修改的，因此一個節點創建只讀變數后就不能再修改它了，所以這三個節點得先對這個只讀變數的值達成共識后，所有節點才一起創建這個只讀變數，
?假設有兩個用戶通過客戶端（比如Client1，Client2）訪問這個系統，試圖創建一個只讀變數，比如A, Client1試圖創建值為5的A，Client2試圖創建值為9的A，這要如何達成共識，實作各個節點上的A值的一致呢？
?這個問題的解決演算法有很多，最經典的就是二階段演算法（2PC），該演算法中，我們將提議的節點稱為協調者（coordinator），其它參與決議的節點稱為參與者（participate），兩階段具體描述如下，

1. 階段一：準備階段
   ?協調者發起一個提議，分別詢問各個參與者是否接受，
   

2. 階段二：提交階段
   ? 協調者根據參與者的反饋，提交或者終止事務，如果參與者全部同意則提交，只要有一個參與者不同意則終止，
   

什么是“角色”

?Paxos其實也類似，它有一個最重要的概念“角色”，在Paxos有三個“角色”，提議者(Proposer)、接受者（Acceptor）和學習者（Learner），
?其中,提議者和接受者是這里最重要的兩個角色，Paxos最核心的就是定義他們之間的通訊規則來保證某個變數在分布式系統中的一致性，下面分別介紹一下他們具體的作用：

• 提議者(Proposer)：提議者是提出議案的人，每個議案都有一個議案號，議案號是區別不同議案的唯一標識，而且議案號是有大小次序的，一般來說，集群中收到客戶端請求的節點，才是提議者，

• 接受者（Acceptor）:對每個提議的值進行投票，并存盤接收的值，通常來說，集群中的所有節點都扮演著接受者的角色，參與共識協商，并接收和存盤資料，
  ? 所以，經常會發現集群中的節點其實可以身兼多個“角色”，如下圖那樣，假設集群中有3個節點，當1個節點收到了請求，那么該節點作為提議者發起了二階段提交，然后這個節點可以和另外兩個節點一起作為接受者進行共識協商，
  

• 學習者（Learner）:被告知投票的結果，接收達成的共識值，并存盤保存，不參與投票的程序，通常，學習者是備份節點，就好比“Master-Slave”中的Slave,被動地接收資料，實作容災備份，

?通過總結，這三個角色的功能如下：

Basic Paxos如何達成共識

?在Basic Paxos是通過2PC演算法達成共識的，它使用議案代表一個提議，不過在議案中除了議案號，還包括議案值，在這里，假設用[n,v]表示一個議案，其中k表示議案號，v表示議案值，
?整個共識協商分兩個階段完成，分別為**準備階段（prepare）和接受階段（Accept）**那么如何達成的呢，下面，我們通過一個歷史故事來簡單講解下，
? 戰國中期，秦國商鞅變法后迅速崛起對外擴張，在函谷關外拉開大軍，準備全面入侵山東國家，山東諸國惶惶不可終日，此時公孫衍犀首游說列國，并先后出任魏國韓國趙國等多個國相，提議欲抵抗秦國必須結成同盟，合縱方可破秦，最終有三個國家魏國，楚國，韓國集兵于函谷關外，各占一個山頭準備攻打秦國，但是任意一個國家和秦國對抗必敗，必須在三個國家中至少有兩個國家達成一致，同時進攻，每個國家都有主帥(魏王，楚王，韓王)和參謀(魏相犀首，春申君黃歇)，參謀給出的進攻時間必須得到魏楚韓中任意兩個國家的同意，才可決議，但是派出信使有可能被秦國密探捕獲，而導致資訊丟失，所以達成一致的進攻時間是個難題，那么這里考慮采用Paxos協議來決議，

1. 在準備階段，參謀犀首派出信使送信給魏楚韓（議案號為1），魏王楚王收到資訊，由于信使被捕，韓王未收到資訊；
2. 魏王楚王收到訊息后，派信使告訴犀首已經收到資訊，等待具體指示；
3. 同時，參謀黃歇也派出信使給送信給魏楚韓（議案號2），這次魏王未收到，楚王、韓王收到資訊；
4. 楚王韓王收到訊息后，派信使告訴參謀黃歇已經收到資訊，等待具體指示，

準備階段完成后進入接受階段
5. 參謀犀首收到訊息后，派信使告訴魏楚王具體攻打日期是1號；
6. 魏王收到后覺得可以，告訴犀首1號進攻可以；
7. 楚王收到后，因他保存的最新指示議案號是2，而犀首的議案號1小于2，所以告訴犀首，1號方案不可行，正在等待2號方案；
8. 參謀黃歇派出信使告訴楚王韓王進攻時間為下個月2號；
9. 楚王收到后和自己的議案號對比，發現一致，則告訴參謀黃歇方案可行；
10. 韓王收到后，覺得參謀黃歇方案可行，則告訴參謀黃歇方案可行；
11. 參謀犀首得到的議案不是一半以上（魏王認可、楚王不認可，韓王未知），因此只有再次派出信使，通知最新的議案號為3，這里就進入了新一輪的準備階段，如下圖所示

12. 新一輪的準備階段，魏王收到資訊后，告訴參謀犀首，我上次收到你的資訊，是否更改，等待最新指示；
13. 楚王收到資訊后，告訴參謀犀首，我已經收到了議案編號3，我之前的議案值為2號，等待最新指示；
    
14. 進入新一輪的接受階段，參謀犀首收到資訊后，通過楚王的通知已經最新議案號為2，其對應的議案值為2號，所以這次派出信使發出資訊“議案號為3，議案值為進攻日期2號”；
15. 魏王收到后，按最新的指示執行，并回復參謀犀首；
16. 楚王收到后，同自己保存的議案號對比，發現收到的議案號和保存的一致，則接受指示，并回復參謀犀首；
17. 這樣達成一致，半數以上同意2號，

所以通過這個例子，總結如下：

• 如果準備請求的議案編號小于等于接受者已經回應的準備請求的議案編號，那么接受者將不回應該準備請求；
• 如果接受請求的議案編號小于等于接受者已經回應的接受請求的議案編號，那么接受者將不通過這個議案
• 如果接受者之前有通過議案，那么接受者會在準備請求的回應中，包含之前已經通過的最大議案編號的議案資訊，

Basic Paxos的容錯

?除了實作了共識，Basic Paxos還實作了容錯，它不像其它常用的分布式事務演算法那樣，要所有節點都同意河駁交操作，而是只要少于一半節點出錯集群也是能正常作業的，