概述

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

分布式一致性

分布式系統通常由異步網絡連接的多個節點構成，每個節點有獨立的計算和存儲。通常來說，分布式一致性一般指的式數據的一致性。比如分布式存儲系統，通常以多副本冗余的方式實現數據的可靠存儲。同一份數據的多個副本必須保證一致，而數據的多個副本又存儲在不同的節點中，這里的分布式一致性問題就是存儲在不同節點中的數據副本的取值必須一致。

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

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

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

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

Paxos算法描述

Paxos算法的目標：在分布式環境下確定一個值，這個值被所有節點承認。

角色

Paxos將系統中的角色分為提議者 (Proposer)，決策者 (Acceptor)，和最終決策學習者 (Learner):

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

Acceptors的接受，則稱該Proposal被批準。

Learner: 不參與決策，從Proposers/Acceptors學習最新達成一致的提案(Value)。

在具體的實現中，一個進程可能同時充當多種角色。比如一個進程可能既是Proposer又是Acceptor又是Learner。

算法流程

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

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

第一階段: Prepare準備階段

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

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

如果Acceptor首次接收Prepare請求, 設置ResN=N，同時響應ok
如果Acceptor不是首次接收Prepare請求，則：

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

第二階段: Accept接受階段

Proposer： Proposer收到響應后，有兩種情況：

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

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

如果發送的提案請求N大于此前保存的RespN,接受提案，設置AcceptN = N, AcceptV=V, 并且回復ok。
如果發送的提案請求N小于等于此前保存的RespN，不接受，不回復或者回復error。

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

第三階段: Learn學習階段

Learner: Proposer收到多數Acceptor的Accept后，決議形成，將形成的決議發送給所有Learner。

Paxos應用案例

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

我們以一個分布式的KV數據庫為例，分析Paxos的應用場景。

3個server組成一個分布式內存數據庫，他們的狀態必須保持同步，也就是每個server 節點都需要維護有順序的操作日志，同時保持一致。

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

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

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

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

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

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