分布式一致性算法Paxos

最近在學習zookeeper原理的時候了解到了paxos算法,看了幾篇文章之后還是感覺有些迷糊,后來看了知行學社的 paxos視頻 才對這個算法有了一定的了解,這里就做一下總結.

Paxos簡介

Paxos是Lamport于1990年提出的一種基于消息傳遞而具有高度容錯特性的分布式一致性算法.這個算法是分布式中最為重要的算法,Google Chubby的作者Mike Burrows說過這個世界上只有一種一致性算法,那就是Paxos,其他算法都是殘次品.具體Paxos算法的詳細內涵和故事背景大家可以參考知乎上的 回答 ;

Paxos的使用場景和假設

我們都知道基于消息傳遞通信模型的分布式系列,不可避免的會發生以下錯誤:進程可能會慢,被殺死或在重啟,消息可能會有延遲,丟失和重復.Paxos算法解決的問題就是在一個可能發生上述異常的分布式系統中如何就某個值達成一致,保證無論發生以上任何異常,都不會破壞決議的一致性。但是Paxos算法也有一定的使用假設。一個假設是在消息傳遞的過程中不會出現拜占庭將軍問題：即雖然有可能一個消息被傳遞兩次，但是絕對不會出現錯誤的消息。另一個假設是提議不會被反對，只能被同意或在被更新的提議替換。

Paxos協議中有三種角色，每個節點可以扮演多個角色：

• 倡議者(Proposer):提議者可以提出提議(數值或在操作命令)以供投票表決。
• 接受者(Acceptor):接受者可以對提議者提出的提議進行投票表決，提議有超過半數的接收者投票即被選中。
• 學習者(Learner):學習者無投票者，只是從接收者那里獲取哪個提議被選中。

在Paxos算法中，一個或在多個Proposer都可以并發的提出提議；系統必須針對所有提議中的某個提議達成一致（超過半數大的接受者選中）；最多只能對一個確定的提議達成一致；只要超過半數的節點存活且可以互相通信，整個系統一定可以達成一致，即選擇一個確定的提議。

如果直接講解Paxos算法，大家可能會有些難以理解，這里我們就按著視頻里的順序，先從簡單的分布式一致性算法開始，然后不斷進行優化，最后將其演變成Paxos算法。

圖解Paxos主要流程

Paxoso算法分為兩個的階段，我們就將其分別記為Phase1和Phase2.每個Proposer都持有一個獨有的變量epoch,每個Acceptor都保存三個狀態：lastest_prepared__epoch,accepted_epoch和accepted_value.lastest_prepared_epoch是指Acceptor授予訪問權的Proposer的epoch值，accepted_epoch是Acceptor接受提議的Proposer的epoch值，而accepted_value就是Acceptor接受的提議值嘍，他們的初始值都為null。

階段一

Phase1過程中，Proposer向Acceptor發起 Prepare(epoch) 請求來獲取訪問權。將自己的epoch發送給Acceptor.而Acceptor只會接受比lastest_prepared_epoch更大的epoch,并給予訪問權，并將epoch記錄到lastest_prepared_epoch的值中，返回當前的accepted_epoch和accepted_value的值。在初始化狀態下，二者都是null,所以返回的是 。如果epoch小于lastest_prepared_epoch則不授予訪問權，并返回

。

如上圖所示，Proposer1向5個Acceptor發送了Prepare(#1)的請求，其中前三個請求順利到達，Acceptor授予訪問權，返回

，并修改lastest_prepared_epoch為1。而后兩個請求發生了網絡延遲,一直未到達相應的Acceptor。

在階段一中，Proposer需要獲得半數以上的Acceptor的訪問權和對應的一組value的取值才會進行第二階段，這樣才會確保，一個Proposer提出的確定的議案會被另外一個Proposer發現，從而在階段二中會進行正確的操作。

 

階段二

第二階段采取“后者認同前者”的原則進行。在肯定舊epoch無法生成確定性取值時，新的epoch會提交自己的取值，不會沖突；一旦舊epoch形成了確定性取值，那么該proposer一定可以獲得該取值，并且會認同該取值，不會破壞。

如果Proposer在第一階段獲取的value值都是null,則舊epoch無法形成確定性取值，此時讓自己的 成為確定性取值：

• 向epoch對應的所有acceptor提交取值
• 如果收到半數以上的成功應答，則返回
• 否則返回

如果value的取值不為null,則認同最大accepted_epoch對應的取值f,使 成為確定性取值，其中epoch是自己的epoch.

• 如果f出現半數以上，則說明f已經是確定性取值了，直接返回
• 否則，向epoch所對應的acceptor提交取值

Acceptor在接收到accept(epoch,V)的請求之后，先查看epoch是不是自己記錄的lastest_prepared_epoch，如果是則設置 = 。否在則會返回error

如上圖所示，由于在階段一中Proposer1接受到的 和 值都為null,所以，決定將自己的值設置為確定值，于是發送accept(1,V1)請求。Acceptor1接受到了這個請求，檢查lastest_prepared_epoch也等于1,所以將自己存儲的

設置為<1,v1>。而Proposer1的另外兩個accept請求發生了網絡延遲。

如果此時，Proposer2向Acceptor進行propose會怎么樣呢？我們來模擬propose來分析一下。

 

如上圖所示，Proposer2向Acceptor發送了prepare(#2)的請求，Acceptor1先檢測一下發現2大于現在的lastest_prepared_epoch,所以同意發送訪問權，將lastest_prepared_epoch修改為2，并將自己保存的accepted_epoch和acceped_value返回給Proposer2；Acceptor3的操作也是類似，只不過因為Proposer1發送的accept請求發生了延遲，所以Acceptor3返回的是

；而Acceptor5的操作和我們在文章第一張圖中的Acceptor1的操作相同，他們都是第一次接收到prepare請求。

然后Proposer2進行第二階段的操作，從所有的返回數據中，找到accepted_epoch最大的那個accepted_value.這里就是Acceptor返回的<1,v1>，所以，Proposer2會盡力讓V1成為確定值，所以它向Acceptor發送accept(2,V1)的請求。然后Acceptor1,Acceptor3,Acceptor5三個Acceptor接受了這個accept請求，更新自己的

。此時，已經有三個acceptor形成了一致性的值，所以V1就成了整個系統的確定性取值。

那么Proposer1對Acceptor3發送的accept請求在此時達到Acceptor3會怎么樣呢？Acceptor3發現當前lastest_prepared_epoch是2,所以直接拒絕了這個請求。

后記

不清楚大家現在對Paxos算法的過程是否已經有了清楚的了解啊？那么我來問幾個問題，大家可以考慮一下：

• 在本文的情景下，假如Proposer2向Acceptor2,3,4發送了prepare請求，而不是向Acceptor1,3,5發送的請求，會怎么樣呢？
• 為什么強調prepare階段時必須接受到一般以上Acceptor的返回，才能進行第二階段?
  后續希望能夠分析一下 Zookeeper 關于Paxos的具體使用場景和算法，希望大家多多關注。

 

來自：http://remcarpediem.com/2017/04/16/分布式一致性算法Paxos/