轉自：https://www.cnblogs.com/linbingdong/p/6253479.html
1、Paxos是什麼
Paxos算法是基于消息傳遞且具有高度容錯特性的一緻性算法，是目前公認的解決分布式一緻性問題最有效的算法之一
2、問題産生的背景
在常見的分布式系統中，總會發生諸如機器當機或網絡異常（包括消息的延遲、丢失、重複、亂序，還有網絡分區）等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正确地在叢集内部對某個資料的值達成一緻，并且保證不論發生以上任何異常，都不會破壞整個系統的一緻性
注：這裡某個資料的值并不隻是狹義上的某個數，它可以是一條日志，也可以是一條指令（command）。根據應用場景不同，某個資料的值有不同的含義
3、相關概念
在Paxos算法中，有三種角色：
- Proposer（提案發起者）
- Acceptor（提案投票者）
- Learners（提案學習者）
在具體的實作中，一個程序可能同時充當多種角色。比如一個程序可能既是Proposer又是Acceptor又是Learner
還有一個很重要的概念叫提案（Proposal）。最終要達成一緻的value就在提案裡
注：
- 暫且認為『提案=value』，即提案隻包含value。在我們接下來的推導過程中會發現如果提案隻包含value，會有問題，于是我們再對提案重新設計
- 暫且認為『Proposer可以直接提出提案』。在我們接下來的推導過程中會發現如果Proposer直接提出提案會有問題，需要增加一個學習提案的過程
Proposer可以提出（propose）提案；Acceptor可以接受（accept）提案；如果某個提案被標明（chosen），那麼該提案裡的value就被標明了
回到剛剛說的『對某個資料的值達成一緻』，指的是Proposer、Acceptor、Learner都認為同一個value被標明（chosen）。那麼，Proposer、Acceptor、Learner分别在什麼情況下才能認為某個value被標明呢？
- Proposer：隻要Proposer發的提案被Acceptor接受（剛開始先認為隻需要一個Acceptor接受即可，在推導過程中會發現需要半數以上的Acceptor同意才行），Proposer就認為該提案裡的value被標明了
- Acceptor：隻要Acceptor接受了某個提案，Acceptor就任務該提案裡的value被標明了
- Learner：Acceptor告訴Learner哪個value被標明，Learner就認為那個value被標明
4、問題描述
假設有一組可以提出（propose）value（value在提案Proposal裡）的程序集合。一個一緻性算法需要保證提出的這麼多value中，隻有一個value被標明（chosen）。如果沒有value被提出，就不應該有value被標明。如果一個value被標明，那麼所有程序都應該能**學習（learn）**到這個被標明的value。對于一緻性算法，**安全性（safaty）**要求如下：
- 隻有被提出的value才能被標明
- 隻有一個value被標明，并且如果某個程序認為某個value被標明了，那麼這個value必須是真的被標明的那個
我們不去精确地定義其活性（liveness）要求。我們的目标是保證最終有一個提出的value被標明。當一個value被標明後，程序最終也能學習到這個value
Paxos的目标：保證最終有一個value會被標明，當value被標明後，程序最終也能擷取到被標明的value
假設不同角色之間可以通過發送消息來進行通信，那麼：
- 每個角色以任意的速度執行，可能因出錯而停止，也可能會重新開機。一個value被標明後，所有的角色可能失敗然後重新開機，除非那些失敗後重新開機的角色能記錄某些資訊，否則等他們重新開機後無法确定被標明的值
- 消息在傳遞過程中可能出現任意時長的延遲，可能會重複，也可能丢失。但是消息不會被損壞，即消息内容不會被篡改（拜占庭将軍問題）
5、Paxos算法描述
Paxos算法分為兩個階段。具體如下：
-
階段一：
(a) Proposer選擇一個提案編号N，然後向半數以上的Acceptor發送編号為N的Prepare請求
(b) 如果一個Acceptor收到一個編号為N的Prepare請求，且N大于該Acceptor已經響應過的所有Prepare請求的編号，那麼它就會将它已經接受過的編号最大的提案（如果有的話）作為響應回報給Proposer，同時該Acceptor承諾不再接受任何編号小于N的提案
-
階段二：
(a) 如果Proposer收到半數以上Acceptor對其發出的編号為N的Prepare請求的響應，那麼它就會發送一個針對**[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編号最大的提案的value**，如果響應中不包含任何提案，那麼V就由Proposer自己決定
(b) 如果Acceptor收到一個針對編号為N的提案的Accept請求，隻要該Acceptor沒有對編号大于N的Prepare請求做出過響應，它就接受該提案
6、Learner學習被標明的value
Learner學習（擷取）被標明的value有如下三種方案：
7、如何保證Paxos算法的活性
通過選取主Proposer，就可以保證Paxos算法的活性。至此，我們得到一個既能保證安全性，又能保證活性的分布式一緻性算法——Paxos算法