一緻性算法Paxos詳解

分布式系統除了能提升整個系統的性能外還有一個重要的特性就是提高系統的可靠性，可靠性指的是當分布式系統中一台或N台機器宕掉後都不會導緻系統不可用，分布式系統是state machine replication的，每個節點都可能是其他節點的快照，這是保證分布式系統高可靠性的關鍵，

而存在多個複制節點就會存在資料不一緻的問題，這時一緻性就成了分布式系統的核心；在分布式系統中必須保證：

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

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

　　Paxos就是用于解決一緻性問題的算法，有多個節點就會存在節點間通信的問題，存在着兩種節點通訊模型：共享記憶體（Shared memory）、消息傳遞（Messages passing），Paxos是基于消息傳遞的通訊模型的。

　　Paxos為2014年圖靈獎得主Leslie Lamport在1990年提出的一緻性算法，該算法被譽為類似算法中最有效的，Paxos不隻适用于分布式系統中，凡是需要達成某種一緻性時都可以使用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請求

Paxos詳解

Paxos保證:

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；

Paxos流程

　　這裡具體例子來說明Paxos的整個具體流程：

　　假如有Server1、Server2、Server3這樣三台伺服器，我們要從中選出leader，這時候Paxos派上用場了。

　　整個選舉的結構圖如下：

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]；

Phase2（決議階段）

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；

一個Paxos過程隻會産生一個議案是以至此這個流程結束，選舉結果server2為Leader；

參考資料

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

http://zh.wikipedia.org/zh-cn/Paxos算法

文章首發位址：Solinx

http://www.solinx.co/archives/403