概述

Paxos算法是Lamport宗師提出的一種基于消息傳遞的分布式一致性算法，是目前公認(rèn)的解決分布式一致性問題最有效的算法之一。本文的目的就是帶領(lǐng)大家深入淺出理解Paxos算法，理解它的執(zhí)行流程，然后通過一個例子來了解Paxos算法在分布式系統(tǒng)中起到的作用。如果有能力的同學(xué)可以直接拜讀原文。

分布式一致性

分布式系統(tǒng)通常由異步網(wǎng)絡(luò)連接的多個節(jié)點構(gòu)成，每個節(jié)點有獨立的計算和存儲。通常來說，分布式一致性一般指的式數(shù)據(jù)的一致性。比如分布式存儲系統(tǒng)，通常以多副本冗余的方式實現(xiàn)數(shù)據(jù)的可靠存儲。同一份數(shù)據(jù)的多個副本必須保證一致，而數(shù)據(jù)的多個副本又存儲在不同的節(jié)點中，這里的分布式一致性問題就是存儲在不同節(jié)點中的數(shù)據(jù)副本的取值必須一致。

如果不保證一致性，那么就說明這個系統(tǒng)中的數(shù)據(jù)根本不可信，數(shù)據(jù)也就沒有意義，那么這個系統(tǒng)也就沒有任何價值可言。

在分布式系統(tǒng)中，各個節(jié)點之間需要進(jìn)行通信來保持?jǐn)?shù)據(jù)的一致性，而通信的實現(xiàn)方式有共享內(nèi)存和消息傳遞兩種模型。基于消息傳遞通信模型的分布式系統(tǒng)，不可避免的會發(fā)生下面的錯誤：機器宕機，進(jìn)程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重復(fù)。那么在這種復(fù)雜的情況下該如何保證一致性呢？

而Paxos算法就是如何快速正確的在一個分布式系統(tǒng)中對某個數(shù)據(jù)的值達(dá)成一致，并且保證不論發(fā)生任何異常，都不會破壞整個系統(tǒng)的一致性。

注： 這里某個數(shù)據(jù)的值并不只是狹義上的某個數(shù)，它可以是一條日志，也可以是一條命令，根據(jù)應(yīng)用場景不同，某個數(shù)據(jù)的值有不同的含義。

Paxos算法描述

Paxos算法的目標(biāo)：在分布式環(huán)境下確定一個值，這個值被所有節(jié)點承認(rèn)。

角色

Paxos將系統(tǒng)中的角色分為提議者 (Proposer)，決策者 (Acceptor)，和最終決策學(xué)習(xí)者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案編號 (Proposal ID) 和提議的值 (Value)。
• Acceptor: 參與決策，回應(yīng)Proposers的提案。收到Proposal后可以接受提案，若Proposal獲得多數(shù)

Acceptors的接受，則稱該Proposal被批準(zhǔn)。

• Learner: 不參與決策，從Proposers/Acceptors學(xué)習(xí)最新達(dá)成一致的提案(Value)。

在具體的實現(xiàn)中，一個進(jìn)程可能同時充當(dāng)多種角色。比如一個進(jìn)程可能既是Proposer又是Acceptor又是Learner。

算法流程

Propser有兩個重要屬性，提案編號N, 提案V, 簡記 Proposer(N, V)。

Acceptor有三個重要屬性，響應(yīng)提案編號ResN, 接受的提案編號AcceptN, 接收的提案AcceptV， 間記Acceptor(ResN, AcceptN, AcceptV)。

第一階段: Prepare準(zhǔn)備階段

Proposer： Proposer生成全局唯一且遞增的提案編號N,，向所有Acceptor發(fā)送Prepare請求，這里無需攜帶提案內(nèi)容，只攜帶提案編號即可, 即發(fā)送 Proposer(N, null)。

Acceptor： Acceptor收到Prepare請求后，有兩種情況：

1. 如果Acceptor首次接收Prepare請求, 設(shè)置ResN=N， 同時響應(yīng)ok
2. 如果Acceptor不是首次接收Prepare請求，則：

• 若請求過來的提案編號N小于等于上次持久化的提案編號ResN，則不響應(yīng)或者響應(yīng)error。
• 若請求過來的提案編號N大于上次持久化的提案編號ResN, 則更新ResN=N，同時給出響應(yīng)。響應(yīng)的結(jié)果有兩種，如果這個Acceptor此前沒有接受過提案， 只返回ok。否則如果這個Acceptor此前接收過提案，則返回ok和上次接受的提案編號AcceptN, 接收的提案AcceptV。

第二階段: Accept接受階段

Proposer： Proposer收到響應(yīng)后，有兩種情況：

1. 如果收到了超過半數(shù)響應(yīng)ok, 檢查響應(yīng)中是否有提案，如果有的話，取提案V=響應(yīng)中最大AcceptN對應(yīng)的AcceptV，如果沒有的話，V則有當(dāng)前Proposer自己設(shè)定。最后發(fā)出accept請求，這個請求中攜帶提案V。
2. 如果沒有收到超過半數(shù)響應(yīng)ok, 則重新生成提案編號N, 重新回到第一階段，發(fā)起Prepare請求。

Acceptor： Acceptor收到accept請求后，分為兩種情況：

1. 如果發(fā)送的提案請求N大于此前保存的RespN,接受提案，設(shè)置AcceptN = N, AcceptV=V, 并且回復(fù)ok。
2. 如果發(fā)送的提案請求N小于等于此前保存的RespN，不接受，不回復(fù)或者回復(fù)error。

Proposer： Proposer收到ok超過半數(shù)，則V被選定，否則重新發(fā)起Prepare請求。

第三階段: Learn學(xué)習(xí)階段

Learner: Proposer收到多數(shù)Acceptor的Accept后，決議形成，將形成的決議發(fā)送給所有Learner。

Paxos應(yīng)用案例

前面講述了paxos算法細(xì)節(jié)，可能你還是不明白paxos算法在實際場景中有什么用處，我們現(xiàn)在講個實際的使用案例。

我們以一個分布式的KV數(shù)據(jù)庫為例，分析Paxos的應(yīng)用場景。

3個server組成一個分布式內(nèi)存數(shù)據(jù)庫，他們的狀態(tài)必須保持同步，也就是每個server 節(jié)點都需要維護(hù)有順序的操作日志，同時保持一致。

+---+-------------+
|1  |Put("a", 1)  |
+---+-------------+
|2  |Put("b", 2)  |
+---+-------------+
|3  |Put("c", 3)  |
+---+-------------+

多個客戶端并發(fā)在發(fā)送請求的時候，服務(wù)端多個節(jié)點需要協(xié)商，選擇其中一個大家都認(rèn)可的數(shù)據(jù)(指令), 存入到操作表中，這里協(xié)商確定指令的過程就是Paxos。

比如我們將paxos算法封裝到下面的方法中：

Op doPaxos(int seq, Op v){...}

以上面圖示的例子詳細(xì)分下這個過程：

1. Cient2向集群發(fā)送了請求Put("b", 2),假設(shè)這個請求最終到了server1上。
2. Client3向集群發(fā)送了請求Put("c", 3), 假設(shè)這個求情發(fā)到了server2上。
3. server2調(diào)用doPaxos函數(shù)進(jìn)行協(xié)商，即詢問集群中的所有server咱們的第2個操作能否為Put("c", 2)
4. 此時server3也調(diào)用doPaxos函數(shù)進(jìn)行協(xié)商，即詢問集群中的所有server咱們的第2個操作能否為Put("c", 3)
5. 這是Paxos只會選擇其中1個提案，我們這里假設(shè)server2的議題最終被通過了，集群中所有server的狀態(tài)表都新增Put("c", 2)
6. server3發(fā)現(xiàn)自己的提案沒有選中，他會對自己的database進(jìn)行Put("b", 2)操作，然后重新升級提案編號，再次調(diào)用doPaxos方法，直到自己的提案被通過。

總結(jié)

Paxos算法還是挺難以理解的，如果對整個推導(dǎo)過程感興趣的話，可以閱讀Lamport的原文。

根據(jù)前面講述的Paxos算法流程，不知道大家有沒有發(fā)現(xiàn)一個問題，如果兩個Propser依次提出編號遞增的提案，最終回陷入死循環(huán)，進(jìn)入死鎖狀態(tài)，如下圖：

我們可以通過選取主Proposer，就可以保證Paxos算法的活性， 這樣是ZAB協(xié)議的由來。