前言

Lamport老爺子的那篇《Paxos Made Simple》論述實(shí)在太跳脫，像極了高數(shù)答案中的“顯然”，“易證”一般，以致于剛開始了解Paxos的人看得一臉懵逼。

本文希望能夠通過(guò)簡(jiǎn)單的圖文，為大家簡(jiǎn)單逐步介紹Paxos涉及的相關(guān)概念、推導(dǎo)過(guò)程、以及算法整體介紹（含編號(hào)生成規(guī)則、活鎖、Leader的引出）等。

1. 基本概念

Paxos算法是Leslie Lamport 于1990年提出的：
一種基于消息傳遞且具有高度容錯(cuò)的共識(shí)（consensus）算法。

• 共識(shí)：簡(jiǎn)單講大家有很多建議，需要統(tǒng)一意見，達(dá)成共識(shí)（選出其中一個(gè)）
• 消息傳遞：請(qǐng)求 + 響應(yīng)，分布式系統(tǒng)中主要基于網(wǎng)絡(luò)消息進(jìn)行通信。
• 高度容錯(cuò)：不管是網(wǎng)絡(luò)消息重復(fù)或丟失、還是某一些服務(wù)器掛掉了，也不會(huì)受到影響。

1.1 少數(shù)服從多數(shù)

小明一家五口，想要春節(jié)到某個(gè)地方游玩，家里人有不同的建議，如果要選出【一個(gè)】游玩的地方，基于投票的“少數(shù)服從多數(shù)”是一個(gè)比較合理的做法。

“多數(shù)”意味著超過(guò)一半，兩個(gè)“多數(shù)”之間肯定會(huì)有交集。比如[小明, 爸爸, 媽媽] 是一個(gè)多數(shù)派，[小明, 爺爺, 奶奶]也是一個(gè)多數(shù)派 。此時(shí)這兩個(gè)多數(shù)派之間的交集就是小明：

兩個(gè)多數(shù)派交集

當(dāng)有一個(gè)“多數(shù)”均同意去A時(shí)，就可以認(rèn)為結(jié)果出來(lái)了，因?yàn)槭Ｏ履切┤丝隙惒粔蛞粋€(gè)“多數(shù)”：

多數(shù)同意即可選出

1.2 角色

我們先來(lái)了解下共識(shí)算法中常涉及到的幾個(gè)角色：

• Proposer：提案者，可多個(gè)；負(fù)責(zé)提出提案(proposal)，每個(gè)提案中會(huì)包含一個(gè)值(value)；
• Acceptor：接收者，可多個(gè)；可以選擇接受（accept） Proposer提出的提案。
  當(dāng)某個(gè)提案被 多數(shù)派 所接受后，我們將這個(gè)提案稱之為被選定（chosen）；當(dāng)某個(gè)提案被選定時(shí)，也就意味著value被最終選定。
• Leaner：學(xué)習(xí)者，可多個(gè)；當(dāng)value被選定后，learner可以學(xué)習(xí)（獲?。┎?yīng)用這個(gè)value。

值（value）可代表的意思是豐富的，它可以是：

• 一個(gè)服務(wù)器ID：如 1、2、 3，從這三臺(tái)服務(wù)器中選出一個(gè)老大；
• 一條命令：如 set key 1、set key 2，從中選一個(gè)執(zhí)行；
• 一條日志：如 某一個(gè)時(shí)期有多條日志，選擇最終應(yīng)用的某條日志。日志可包含任何信息。

注：通常一臺(tái)服務(wù)器 或者 一個(gè)進(jìn)程可包含一個(gè)或多個(gè)角色。

本文主要關(guān)注選值的一個(gè)過(guò)程（主要由Proposer和Acceptor參與），Leaner不做過(guò)多介紹。

1.3 要解決的問(wèn)題

劃分角色后，我們可以定義出算法需要解決或保證的幾個(gè)點(diǎn)（即安全性-Safety）：

1. 值（value）只有被提出才能被選定；
2. 只會(huì)有一個(gè)value被選定（共識(shí)）；
3. Leaner 只能學(xué)習(xí)被選定的value。

第1、3點(diǎn)顯得“理所當(dāng)然”，實(shí)現(xiàn)相對(duì)簡(jiǎn)單。
而第2點(diǎn)【只會(huì)有一個(gè)value選定】，成為了Paxos最核心要解決的問(wèn)題。

2. Paxos的推導(dǎo)

P1

當(dāng)Acceptor第一次收到提案時(shí)，因?yàn)闆](méi)有更多的參考信息，直接接受（accept）是一個(gè)很自然的動(dòng)作。于是我們可以給Acceptor的行為定下這么一個(gè)約束：

P1：Acceptor 需要接受（accept）其第一次收到的提案。

針對(duì)只有一個(gè)提案時(shí)（暫不考慮消息丟失）的情況，基于P1，一個(gè)value可以被輕松選出：

選出V1

P2

當(dāng)有多個(gè)提案時(shí)，基于P1，當(dāng)Acceptor收到第二個(gè)提案時(shí)，Acceptor可以選擇：

1. 直接拒絕，即一個(gè)Acceptor只能接受（accept）一個(gè)提案。
2. 選擇接受，即一個(gè)Acceptor可以接受（accept）多個(gè)提案

當(dāng)只能接受（accept）一個(gè)提案時(shí)：如果恰好一半 Acceptor 接受（accept）的提案具有 value v1，另一半接受的提案具有 value v2，將無(wú)法形成多數(shù)派，即無(wú)法選出任何一個(gè) value：

如果只能接受一個(gè)提案無(wú)法達(dá)成多數(shù)派選出value的話，那么我們可以嘗試一個(gè)Acceptor可以接受（accept）多個(gè)提案。
可如果一個(gè)Acceptor可以接受多個(gè)提案的話，不是會(huì)出現(xiàn)多個(gè)提案被選定嗎？如下圖：

當(dāng)這些個(gè)提案的value不一樣時(shí)，最終就會(huì)出現(xiàn)多個(gè)value被選出，這不是我們所期望的。
于是我們二話不說(shuō)，定下這么一個(gè)約束P2：

P2：一旦一個(gè) value 為 v 的提案被選定（chosen），那么之后選定（chosen）的提案，其value也必須為v。

盡管可以通過(guò)多個(gè)提案，但是因?yàn)?strong>后面提案的value和之前選定的一樣，自然可以保證最終【只會(huì)有一個(gè)value選出】。

關(guān)于分布式系統(tǒng)中的先后順序，我們可以通過(guò)為每個(gè)提案分配一個(gè)唯一的遞增編號(hào)，在提案之間建立一個(gè)全序關(guān)系，這里的“之后”指的就是編號(hào)更大的提案。

我們這里用 <編號(hào), value>來(lái)表示一個(gè)提案。
當(dāng)v1 = v2時(shí)，盡管<m1, v1> 和 <m2, v2> 兩個(gè)提案都被選定，但因?yàn)樗麄兊膙alue是一樣的，最終依然是【只會(huì)有一個(gè)value選出】，這是符合我們預(yù)期的。

2.3 P2a

P2只是一個(gè)簡(jiǎn)單的描述，像是老板交到我們手上的需求，真正的可以落地的方案還是得繼續(xù)分析分析。這里的落地指的是Proposer、Acceptor的具體行為是什么，或者說(shuō)他們?cè)撛趺锤刹拍鼙ＷC只選出一個(gè)值。

提案被選定，意味著有多個(gè)Acceptor接受了該提案。于是可以針對(duì)Acceptor的行為進(jìn)行約束：

P2a：一旦 提案 <m, v> 被選定，那么之后被Acceptor接受（accept）的提案，其value必須為v。

P2b

由于通信是異步的，一個(gè)提案被選定（chosen）時(shí)，可能會(huì)有Acceptor還沒(méi)收到過(guò)任何提案。如果此時(shí)有一個(gè)Proposer往這個(gè)Acceptor發(fā)出另外一個(gè)不同value的提案時(shí)：

• 根據(jù)P2a：因?yàn)橐延刑岚副贿x定，Acceptor不能再接受這個(gè)value不同的提案；
• 根據(jù)P1：這個(gè)Acceptor則需要接受這個(gè)第一次收到的提案的。此時(shí)P1和P2a沖突。

解決這個(gè)問(wèn)題很簡(jiǎn)單，從源頭抓起：當(dāng)提出提案m2時(shí)，只要保證[ v2 = v1 ] 即可。
于是我們轉(zhuǎn)向約束Proposer的行為：

P2b：一旦 提案 <m, v> 被選定，那么之后任何 Proposer 提出的提案的value必須為v。

雖然<m1,v1> 和 <m2, v2>都被選定，但因?yàn)樗麄兊膙alue是一樣的，最終依然是【只會(huì)有一個(gè)value選出】。

P2c

可以看到，P2b對(duì)Proposer新提案的要求，其實(shí)都是基于之前的提案來(lái)的：之前有提案選定（chosen）了，則需要提出相同的value。否則，新提案的value沒(méi)什么要求，可以任意值。

注：提案<n, v> 之前的提案，其實(shí)就是指 編號(hào)小于n的提案。

基于P2b，我們可以提出對(duì)Proposer的行為做出完整的約束（無(wú)論之前的提案選定與否）：

P2c：如果要提出提案<n, v>,則Acceptors中的一個(gè)多數(shù)派S必須滿足以下兩種情況之一：

• 要么S中均沒(méi)有接受過(guò)小于n的提案；
• 要么這些個(gè)小于n的提案中，編號(hào)最大的那個(gè)提案的值為v。

換一種描述，本次提案<n, v> 中的value v，是根據(jù)Acceptors中的一個(gè)多數(shù)派S來(lái)決定的：

1. S中均沒(méi)有接受過(guò)小于n的提案，此時(shí)v沒(méi)要求，隨便提。
2. S中有一些Acceptor接受過(guò)小于n的提案，取編號(hào)最大（最新）的那個(gè)提案的值作為本次提案的值。

第一種情況：【S中均沒(méi)有接受過(guò)小于n的提案】
這表明之前的提案中，沒(méi)有已經(jīng)被選定的。這是顯然易見的：如果之前有提案已經(jīng)被選定，那Acceptors中必然有一個(gè)多數(shù)派C是全部都接受（accept）該提案的了。S和C兩個(gè)多數(shù)派之間肯定有交集。 此時(shí)提案的value可以為任意值，如直接提出<m1,v1>。

第二種情況：【S中有一些Acceptor接受過(guò)小于n的提案】
如果之前的提案已經(jīng)有被accept了，說(shuō)明這些個(gè)提案有可能已經(jīng)被選定（chosen）了，比較安全且符合預(yù)期（P2b）的辦法，就是直接基于這些提案的value提出自己的提案。之所以取編號(hào)最大的值：

• 如果之前的未被選定，我們偏向于選出最新（編號(hào)最大）的提案；
• 如果之前的已被選定，則后面的提案是基于前面最大的，這樣可以保證value的"延續(xù)"。即一個(gè)value被選定后，后面的value均和前面的這個(gè)value一致（見下例）。

舉個(gè)例子： 基于<m1,v1>已提出（可能被選定或 未被選定）。
當(dāng) <m2,v2> 想要提出時(shí)，主要分以下幾種情形：

基于<m1, v1> 已選定，<m2,v2>已提出：
當(dāng) <m3,v3> 想要提出時(shí)，顯然屬于P2c的第二種情況，我們看看多數(shù)派S的不同情形：

同理，基于<m1, v1> 已選定，當(dāng) m4,m5... 提出時(shí)，其提案的Value也會(huì)為v1，從而最終選出的value為v1。

當(dāng)然，當(dāng)m2以任意值v2提出時(shí)，<m2, v2>也有可能走在<m1,v1>前面，最先成為被chosen的提案，后續(xù)的提案自然基于v2來(lái)進(jìn)行了，最終選出的value為v2.

可以看到，滿足P2c后，便可以保證P2b；而保證P2b，就能保證P2a、P2；
即：P2c ? P2b ? P2a ? P2：

P2c為P2的一個(gè)子集

基于P2c，我們已經(jīng)可以看到Paxos的雛形了，主要包括兩個(gè)階段：

• 第一階段：Proposer提出Prepare請(qǐng)求（編號(hào)n），獲取Acceptors中多數(shù)派S的接受情況；

• 第二階段：根據(jù)S + P2c選擇value；Proposer提出Accept請(qǐng)求（編號(hào)n + value），當(dāng)?shù)玫蕉鄶?shù)Acceptor所接受（accept）后，認(rèn)為提案被選定。

Proposer行為已經(jīng)基本完備，我們下面再看下Acceptor怎么“接”這些prepare/accept請(qǐng)求。

P1a

回顧P1中對(duì)Acceptor的行為約束：【Acceptor 需要接受（accept）其第一次收到的提案】。

考慮一種情況：

1. 第一階段時(shí)，Proposer通過(guò)prepare請(qǐng)求，獲取到Acceptor的一個(gè)多數(shù)派S的接受情況。假設(shè)S中均無(wú)接受（accept）過(guò)任何提案。
2. Proposer基于P2c的第一種情況，提出了自己的提案<n, v>（v為任意值）。
3. 此時(shí)集合S中的一個(gè)Acceptor收到了一個(gè)小于n的提案<n-1, v'>的accept請(qǐng)求：
   • 根據(jù)P1，需要accept，因?yàn)槭堑谝淮问盏教岚浮?/li>
   • 根據(jù)P2c，不能accept，因?yàn)橐坏┙邮埽琍roposer收到集合S就遭到破壞，P2c就違背了。

P1和P2c沖突，因此我們要增強(qiáng)對(duì)Acceptor的行為約束： 當(dāng)Acceptor正常響應(yīng)編號(hào)為n的prepare請(qǐng)求時(shí)也應(yīng)作出承諾：不會(huì)再接受（accept）那些編號(hào)小于n的提案，從而保證集合S一直都是正確的。即約束P1a：

P1a：只有Acceptor沒(méi)有回應(yīng)過(guò)編號(hào)大于n的prepare請(qǐng)求時(shí)，才能接受（accept）編號(hào)為n的提案。

關(guān)于Prepare請(qǐng)求的一個(gè)小優(yōu)化

基于P1a + P2c，完整Paxos算法已經(jīng)基本成型.
這里再提一個(gè)關(guān)于Acceptor對(duì)Prepare請(qǐng)求的小優(yōu)化，即盡可能忽略Prepare請(qǐng)求：

1. 假設(shè)一個(gè)Acceptor收到了一個(gè)編號(hào)為 N 的Prepare請(qǐng)求，并做出了正常響應(yīng)。根據(jù)P1a，該Acceptor不能再接受（accept）任何小于 N 的提案。
2. 當(dāng)該Acceptor在收到小于 N 的Prepare請(qǐng)求時(shí)，是可以選擇直接忽略該P(yáng)repare請(qǐng)求的，因?yàn)榫退鉖repare放行，到了第二階段該Acceptor也不會(huì)接受的。這樣可以盡可能提高第二階段過(guò)半數(shù)接受（accept）的成功率。

另外忽略這樣的Prepare請(qǐng)求還有個(gè)好處，就是Acceptor僅需要保存：

1. 已經(jīng)接受（accept）的最大提案（<max_accepted_id, max_accepted_value>）；
2. 已經(jīng)正常響應(yīng)Prepare請(qǐng)求的最大編號(hào)(max_prepared_id）。

對(duì)于之前已經(jīng)接受（accept）的提案，就沒(méi)有記錄的必要了，因?yàn)锳cceptor會(huì)直接忽略小于 max_prepared_id 的Prepare請(qǐng)求。

如果不忽略，則需要找到小于Prepare請(qǐng)求編號(hào) 且 已經(jīng)接受（accept）的最大編號(hào)的提案（用于服務(wù)P2c），相應(yīng)地Acceptor需要記錄之前接受（accept）過(guò)的所有提案。

至此，完整的Paxos算法呼之欲出。

3. Paxos完整算法

3.1 算法陳述

先約定Acceptor需要保存信息的命名：

1. max_prepared_id：Acceptor 已經(jīng)正常響應(yīng)Prepare請(qǐng)求的最大提案編號(hào)
2. <max_accepted_id, max_accepted_value>：Acceptor 已經(jīng)接受（accept）的最大提案

階段一（Prepare請(qǐng)求）：

1. Proposer：生成提案編號(hào)N，然后向Acceptors多數(shù)派發(fā)送Prepare請(qǐng)求（含編號(hào)N）；
2. Acceptor：收到編號(hào)為N的Prepare請(qǐng)求，如果N大于 max_prepared_id，則：
   • max_prepared_id更新為N；承諾不再接受（accept）編號(hào)小于N的提案；
   • 將 <max_accepted_id, max_accepted_value>響應(yīng)給Proposer；

當(dāng)Proposer收到Acceptors超半數(shù)的Prepare正常（成功）的響應(yīng)后：進(jìn)行階段二；
如果收不到超半數(shù)的正常響應(yīng)，則生成新的編號(hào)，則重新進(jìn)行階段一。

階段二（Accept請(qǐng)求）：

1. Proposer：選擇其中編號(hào)最大的提案value作為本次提案的value（如果沒(méi)有則自由定義值），向Acceptors多數(shù)派發(fā)送Accept請(qǐng)求（含編號(hào)N和value）；
2. Acceptor：收到提案<N, value> 的Accept請(qǐng)求，如果N大于或等于 max_prepared_id，則：
   • <max_accepted_id, max_accepted_value>更新為 <N, value>；
   • 正常響應(yīng)Proposer，表示該提案已被接受（Accept）

當(dāng)Proposer收到Acceptors超半數(shù)的Accept正常（成功）響應(yīng)后：該提案被選定。
如果收不到超半數(shù)的正常響應(yīng)，則生成新的編號(hào)，重新進(jìn)行階段一。

3.2 全局遞增的唯一編號(hào)

在不依賴中間件的前提下，生成一個(gè)全局唯一的遞增序號(hào)其實(shí)并不復(fù)雜。

比如可以通過(guò) 時(shí)間戳 + 各個(gè)Proposer的標(biāo)識(shí)生成，如：

1. 時(shí)間戳 + Proposer的IP端口的hash值；
2. 時(shí)間戳 + 分配到某個(gè)Proposer的ID（如：0、1、2）。

生成提案編號(hào)時(shí)，只要獲取本機(jī)器當(dāng)前的時(shí)間戳，再拼上Proposer的區(qū)分標(biāo)識(shí)即可。前提是各個(gè)機(jī)器之間的時(shí)間是一致的。當(dāng)然了，短暫的時(shí)間不一致通常不會(huì)造成非常惡劣的后果。

還有一些不依賴時(shí)間的，可以通過(guò)【相對(duì)更大】的一種方式生成的（如Google的Chubby）：

1. 確定一個(gè)編號(hào)生成算法，算法需要保證各個(gè)機(jī)器不會(huì)生成重復(fù)的編號(hào)：
   如：【M * Proposer數(shù)量 + Proposer ID】；初始時(shí)，M = 0；
2. 當(dāng)Acceptor響應(yīng)拒絕時(shí)，把當(dāng)前自己當(dāng)前的max_prepared_id也帶上；
3. 當(dāng)Proposer收不到超半數(shù)的成功響應(yīng)信息、需要生成新的編號(hào)時(shí)：從所有拒絕信息中，獲取其中最大的提案id，然后根據(jù)生成算法，生成一個(gè)比這個(gè)更大的新編號(hào)即可。
   如Proposer數(shù)量=3，當(dāng)前Proposer ID = 2；某個(gè)Proposer收到了拒絕信息中提案id包含 [1, 3, 7]，此時(shí)只要M = 2 時(shí)，即可獲取到 2 * 3 + 2 = 8 ( >7) 的編號(hào)。

這種編號(hào)的生成類似于拍賣的叫價(jià)，在前一個(gè)叫價(jià)的基礎(chǔ)上，新叫價(jià)會(huì)高一點(diǎn)。

3.3 活鎖-永遠(yuǎn)選不出值

假設(shè)有兩個(gè)Proposer，一個(gè)Acceptor：

1. P0發(fā)起prepare(0)，Acceptor收到，max_prepared_id更新為0，響應(yīng)pok；
2. P1發(fā)起prepare(1)，Acceptor收到，max_prepared_id更新為1，響應(yīng)pok；
3. P0發(fā)起accept(0,v)，Acceptor收到，發(fā)現(xiàn)小于當(dāng)前的max_prepared_id(1)，拒絕；
4. P0生成更大提案編號(hào)2，發(fā)起prepare(2)，Acceptor收到，max_prepared_id更新為2，響應(yīng)pok；
5. P1發(fā)起accept(1,v)，Acceptor收到，發(fā)現(xiàn)小于當(dāng)前的max_prepared_id(2)，拒絕；
6. P1生成更大提案編號(hào)3，發(fā)起prepare(3)...

此時(shí)就出現(xiàn)了活鎖。這個(gè)鎖可能會(huì)解除；也有可能一直都在循環(huán)。

解決方案主要有兩種：

1. Proposer重新發(fā)起Prepare前，隨機(jī)等待一段時(shí)間。因?yàn)槊總€(gè)Proposer等待的時(shí)間不一樣，等待時(shí)間短的會(huì)有較大的幾率被最終選出。
2. 將Proposer數(shù)量定為一個(gè)。提案者只有一個(gè)，沒(méi)有爭(zhēng)搶，自然不會(huì)有活鎖了。這個(gè)其實(shí)就是我們常說(shuō)的Leader。

值得一提的是，當(dāng)只有一個(gè)Proposer時(shí)（即Leader），第一階段的Prepare是可以省略的，這將會(huì)帶來(lái)較大的性能提升。另外編號(hào)生成、value應(yīng)用的順序性等實(shí)現(xiàn)會(huì)相對(duì)方便。Multi-Paxos、Raft等衍生的協(xié)議均有Leader的概念。

使用Leader的前提是：要選出一個(gè)Leader。選Leader這個(gè)操作如果使用Paxos算法實(shí)現(xiàn)的話，多個(gè)服務(wù)器爭(zhēng)搶Leader，其實(shí)就是相當(dāng)于有多個(gè)Proposer存在了，這時(shí)只能使用第一種解決方案處理了。

工程實(shí)現(xiàn)上，Proposer往往并不是完全公平的，所以Leader選舉方式通常會(huì)根據(jù)具體場(chǎng)景決定。
有些衍生協(xié)議（以Raft為例）為了簡(jiǎn)化場(chǎng)景，單純使用 隨機(jī)等待 + Acceptor只能接受一個(gè)提案的方式（即上文推導(dǎo)中的P1）來(lái)進(jìn)行Leader選舉也是可行的，只是有可能出現(xiàn)上文中提到的，V1和V2可能都無(wú)法獲取多數(shù)票，這時(shí)會(huì)選擇再各等一個(gè)隨機(jī)時(shí)間，然后進(jìn)行下一輪選舉。

參考資料

• Paxos Made Simple
• Implementing Replicated Logswith Paxos
• 維基百科-Paxos算法
• 《從Paxos到Zookeeper 分布式一致性原理與實(shí)踐》