水平有限，如有不對之處，麻煩指出。

1 FLP & Consensus

FLP定理[1]是分散式理論中最重要的理論之一，它指出在最小化非同步網路通信場景下，即使只有一個節點失敗，也沒有一種確定性的共識演算法能夠使得在其他節點之間保持數據一致。

這裡的最小化非同步通信網路是對純粹的非同步網路做了限制，這裡的非同步網路與我們編程中的非同步同步不是一個概念，具體可以參考[5] 分散式網路及故障模型。

1.1 safty & liveness & fault tolerance

• safty

「壞」的事情永遠不會發生

• liveness

「好」的事情最終一定會發生

• fault tolerance

容錯，在分散式系統中允許節點失效。

FLP的結論就是在非同步網路模型中不存在允許fault tolerance的既滿足safty，又滿足liveness的一致性演算法。

1.2 consensus

共識演算法需要保證以下三個屬性，共識演算法首先是需要能夠容錯的。

• termination

也就是達成共識的過程一定會結束，這對應著liveness特性

• agreenment

所有的節點都同意一個提議，這對應著safty特性

• validity

這個提議是來自其中一個節點的，這對應著safty特性。

從上面描述可以看出，consensus需要滿足safty、liveness、fault tolerance三個特性，但是FLP定理又證明瞭在非同步網路模型中不存在這樣能夠滿足三個特性的一致性演算法。那麼我們所使用的paxos、raft為什麼能夠在允許少部分節點失效的場景下同時能夠保證節點間的一致性呢？

2 paxos與FLP

既然FLP證明瞭在非同步網路模型中不存在可以滿足safty和liveness的共識演算法，而paxos又是當前分散式系統應用中最重要的共識演算法，那麼paxos是否違背了FLP呢？

首先作為分散式系統的共識演算法，能夠容忍存在節點失效是最基本的需求，safty是paxos必須要保證的，這裡的safty對應consensus的agreenment和validity，paxos保證節點間達成一致的提議必定來自於某一個節點的提議，且所有節點都同意一個提議值。

paxos滿足了safty和fault tolerance，結合FLP定理我們也能猜到paxos不能滿足liveness特性，就是說在一些場景中會使得paxos一直得不到結果，這也就是paxos著名的「live lock」問題，具體場景後面會詳細描述。

Paxos is always safe, and Paxos is very often live BUT not always[7].

3 paxos正常工作流程[1]

paxos要解決的問題：在多個提議者中選出一個提議，並在提議者中達成共識。

paxos其實是一簇共識演算法的統稱，最精髓的也是所有衍生paxos演算法基礎的是basic paxos。basic paxos達成共識的主要流程分為兩個階段，在這個過程中有三個角色，最終隊唯一一個proposal達成共識。

3.1三個角色

• proposer

proposer是提議的發起者，所謂提議可以理解為一條wal log entry。basic paxos的目標就是在一羣proposer發出的proposal（提議）中確定一個唯一的proposal，然後在各個acceptor中達成共識。

• acceptor

acceptor是proposal的接受者，acceptor參與投票，但不參與決策。

• leaner

leaner被動接受已經達成共識的proposal。不參與決策和投票。

paxos中一個節點可以同時擔任這三個角色中的多個角色。

3.2 兩階段

每個階段又分為兩個小階段

3.2.1 階段一

• P1a: prepare

proposer發起一個proposal，這個proposal包含兩部分：proposalid + propose value。proposalid是全局唯一，可比較的且單調遞增的。

proposer將這個proposal發送大多數acceptor節點。

• P1b: response to prepare

acceptor接收到來自proposer的proposal後需要做以下幾件事：

檢查讓proposal攜帶過來的proposalid

• 如果再這個proposal之前該acceptor已經接受了其他proposal，那麼acceptor會比較當前新接收到的proposalid（假設為n），如果大於之前接收的proposalid，那麼acceptor就接收新的proposal。如果新的proposalid小於等於之前接受的proposalid，那麼就拒絕該次proposal
• 如果再這個proposal之前該acceptor並沒有接收其他proposal，那麼該acceptor就接受該proposal，並持久化該proposal（id+value）。

向proposer返回

• 返回當前acceptor接受的proposal
• 承諾不會接受任何proposalid < n的accept請求
• 承諾不會接受任何proposalid <= n的prepare請求

3.2.2 階段二

• P2a: accept

當一個proposer收到來自大多數acceptor的prepare response之後，可以向集羣的大多數節點發送accept請求，這次的大多數與prepare階段的大多數可以不一致。

proposer發送accept請求的內容需要根據其收到的prepare response中攜帶的proposal做決定，如果response有攜帶proposal過來，那麼proposer就從收到的請求中找到最大proposalid對應的value，accept request的value就為該value。如果攜帶過來多個value，如果response中沒有攜帶過來任何value信息，那麼proposer可以自己隨意決定value。

注: 為什麼要選擇最大proposalid對應的value？也可以這樣去想這個問題，proposer收到的reponse中大的proposalid攜帶的value已經被大多數節點接受，也就是這個節點已經」chosen「。

舉個例子：A,B,C,D,E五個節點，A,B兩個proposer，C,D,E三個acceptor。然後A發起的proposal id=3，value=n被D，E接受了，這時候A已經接收到大多數的proposal response，value=『n』被chosen了，如果這時候B攜帶proposalid=4，發起proposal，然後收到的response中選了C在proposalid=1的時候接受的value=m，那麼這樣B攜帶proposalid=4, value=m就會把之前已經被chosen的value=『n覆蓋了

• P2b: response to accept

acceptor接收到來自proposer的accept請求時，需要檢查自己是否已經接收了proposalid大於n的accept請求，如果沒有，那麼就接受這次accept請求，否則拒絕該次請求。

3.3 一個proposal

basic paxos用於在多個proposer間唯一確定一個proposal value，也就是在眾多proposer的proposal中最後只有一個proposal value會被接受。

3.4 什麼纔是」chosen"

一個acceptor接受一個accept request並不能達到chosen，只有多數節點accept一個value，該value才能被稱之為「chosen".

4 paxos異常處理流程

對於異常可以分為以下幾類：並發衝突、消息丟失、消息重複、網路分區、機器宕機。

4.1 並發衝突

並發是指多個proposer同時向acceptor發出prepare request或者accept request，這時候accept 如何處理這種並發場景。

• 場景1：acceptor同時接收到兩個proposer的prepare request

prepare request攜帶proposalid。假設A,B,C,D,E五個節點，A,B是proposer，C,D,E是acceptor。

因為proposer只要得到majority的response就可以了，所以在發送請求的時候proposer也可以只發送給majority的acceptor節點就可以了。由於是majority個節點，所以無論如何並發總會至少有一個節點是重疊的。

假設在prepare階段，t1時間A攜帶proposalid=4發送prepare request到C,D兩個節點，這時候C,D節點的minproposalid<4，那麼他們會接受這個prepare request，然後回復response給A，在t2時間B發送prepare request請求，攜帶的proposalid=5，發送到D,E。D之前接受過A的prepare request，並且minproposalid = 4,因為這時候B的proposalid=5，所以D,E接受這次prepare request，並承諾不再接受proposalid<5的accept請求，和proposalid<=5的prepare請求。t3時間A攜帶proposalid=4和value=a的accept請求，發向C,D,E，因為這時候D,E的minproposalid=5，所以D,E拒絕這次accept請求，並把自己看到的maxround一併隨著response發給proposer A。而C接收到A的accept請求後發現其minproposalid=4，於是便接受這次accept，那麼C的accept value=』a。A收到C的granted response和D,E的reject response，這次的accept 請求未達到大多數節點認可，因此這次accept是失敗的，A選擇遞增proposalid=6（因為他看到了當前最大的proposalid，便遞增這個id）重新發送prepare request。如果B再t4開始發送accept請求，他會遇到A同樣的問題，於是就這樣周而復始的不斷執行下去，最終導致整個系統一直在prepare，不可用。這就是paxos著名的livelock問題。livelock會使集羣喪失可用性，這也說明瞭為什麼paxos為什麼不滿足flp的liveness屬性。

當然這種活鎖問題在現實場景中出現的概率並不大。同時也並不是說acceptor同時接收到兩個prepare request就會出現活鎖問題，活鎖只是這種場景下一種比較極端的場景。

• 場景2：acceptor同時接收到兩個proposer的accept request

accept請求實現確定的是在prepare請求之後發出的，prepare請求被接受之後acceptor節點就會確定小於minproposalid的accept請求是直接reject的。

場景一中的A,B如果在接收到prepare response之後同時發起了accept request（A的value=『a，B的value=』b），這時候acceptor C,D,E都有自己的minproposalid，A的accept request被D,E reject，C接受。B的accept被D，E接受。那麼這時候集羣就是兩種狀態，C的value是a，D,E的value是b，這樣看集羣的節點是不一致的。A接收到D，E的response之後重新發起prepare請求，這時候prepare response中肯定包含了D或者E的狀態，那麼A的下次accept請求就是攜帶D或者E的value，這時候C接收到A的accept後會覆蓋之前的value，那麼A的accept request結束之後集羣就處於一致狀態了。這也就是為什麼prepare請求需要返回acceptor節點已經accepted的proposal value的原因。

4.2 消息丟包

消息丟包是指proposer在發送prepare request、accept request或者acceptor在回復prepare response、accept response的時候消息在網路中走丟了。這個與具體工程實現相關，通常超時的請求都會重試。如果重試導致在接收端接收到兩次相同的請求，該如何處理？

這也就是消息重複的場景。

4.3 消息重複

消息重複是指同一個request因為重試策略可能導致在接收端接收到兩次相同的消息。這種情況與工程實現有很大關係，工程實現中如果每次重試都遞增proposalid，那麼對於對端來說就不存在消息重複的場景了，我們這裡討論的是如果我們重試時攜帶的內容與上一次一樣會出現什麼問題。

• prepare request重複

也就是acceptor收到兩個proposalid = 1和value相同的兩個prepare request，其中一個prepare request被acceptor接受之後，該acceptor就會做出承諾，不再接受proposalid小於1的prepare請求了。所以另外一個prepare request請求會被reject，導致其自增proposalid並再次proposal。但是這樣顯然就低效了。

• prepare response重複

acceptor在回復prepare request的時候由於重試策略，發送了兩個相同的response。prepare response中會包含該acceptor接受過的proposalid和proposalvalue。proposer在接收到的prepare response中遍歷proposalid和proposalvalue，然後決定accept request的內容，所以即使收到兩個相同的prepare response並不影響proposer發送accept request的正確性。

但是考慮一種情況，在初始化階段，第一次發起prepare請求，acceptor回復response，這個時候acceptor還沒接受任何proposal，所以其response中的acceptedproposal和acceptedvalue是空的，那麼當第一次response在網路中丟失以後，如果acceptor重新發起一樣的response，這時候proposer接受到majority的然後發起accepted，並隨意選取一個value（』a）（因為acceptor還沒接受任何值），那麼本次接受的消息就是a，這個a就是一個確定的值，如果這時候proposer宕機重啟了，重新發起了proposer請求proposalid還是宕機之前的，那麼他有可能接收到之前acceptor發送的在網路中丟失的response，這時候proposer認為集羣還沒接受任何value，於是隨意選擇一個值發起accept，因為這次的proposalid與acceptor接受的proposalid相等，所以acceptor會覆蓋之前已接受的確定的值，那麼確定的值就被覆蓋了。

• accept request重複

acceptor在接收accept request之前會對proposer作出承諾（參考上節的兩個承諾內容），相同accept request對於acceptor來說一樣，處理方式一樣。不影響正確性。

• accept response重複

proposer接收accept response，如果滿足majority的要求就向client返回已寫入。majority是以acceptor為單位的，不以response數量為參考，所以重複的accept response對於proposer來說也是冪等的。

4.4 網路分區

網路分區是指因為網路故障導致節點間出現網路連接問題。在分散式系統中網路分區和機器宕機可能對於對端來說其實是一樣的，他感知不到當前時網路分區還是機器宕機。

• proposer與acceptor分區

proposer與acceptor分區會導致當前proposer的wal落後於其他proposer。

少部分的acceptor與proposer分區會導致這少部分的acceptor的wal比其他acceptor要落後。

4.5 機器宕機

顧名思義，機器宕機就是機器掛了或者進程掛了，進程掛了與機器掛了存在一些區別。

paxos集羣允許acceptor節點有小部分宕機（<N/2）,這些節點宕機並不影響集羣正常工作，這也是paxos的容錯機制。當acceptor節點宕機超過一半時，這時候集羣無法正常工作，處於不可用狀態。

proposer也會出現宕機，proposer宕機時集羣中的其他proposer可以繼續對外提供服務，當宕機的proposer重啟之後其wal可能回落後於其他proposer。

5 持久化信息[8]

paxos持久化哪些信息，這些信息的作用是什麼？

持久化的目的都是為了重啟之後能夠知道重啟前的狀態，從而保證性能和演算法正確性。

5.1 proposalid

保存接受的proposal value的proposalid目的是為了在重啟後告訴proposer自己接受的value的id，因為proposer會從prepare request的response中遍歷找到最大的proposalid和其對應的proposalvalue來作為下一次發送accept request的內容。如果不保存這個id，那麼proposer就無法確定accept請求發送哪個value。

考慮一種場景：

A,B,C,D,E五個節點，A,B為proposer，C,D,E為acceptor，A發送propoalid = 5， value=『a，然後受到D,E兩個節點的accept response，然後A發現目前已經達到大多數的條件，然後返回成功給客戶端，而這時候D,E都重啟了，假設C在A發送accept request之前已經接受了proposalid = 4， value=b的accept請求，A再發送prepare request請求的時候發現收到的response中，proposalid最大的是C的4，然後就將value=b發到所有節點，就會覆蓋已經」確定「的值。這對用戶而言是不可接受的。

5.2 proposalvalue

當前節點接受的value，value值必須持久化，否則所有的寫入重啟之後都丟失了。

5.3 minproposal

basic paxos分為兩個階段，階段1用來確定哪個proposer可以繼續發送accept request請求，acceptor的承諾是，如果在這次prepare request之前已經有其他prepare request發到了該節點，並且該節點接受了其prepare請求，那麼該acceptor就不會再接受後面小於等於當前接受的proposalid的prepare request，所以acceptor要記錄當前prepare的proposalid，這個就是minproposalid，後續的prepare proposalid必須大於minproposalid，acceptor才能接受。那麼acceptor需要持久化這個minproposalid信息。那麼如果acceptor不持久化這條信息會出現什麼狀況？

如果不持久化minproposalid，那麼acceptor在重啟之後不知道當前接受過proposalid是多少，那麼假設他從0開始。假設集羣還是A,B,C,D,E五個節點，A,B是兩個proposer，假設A節點在t1時間發起prepare request請求，proposalid = 5，然後C,D,E都接受了該請求，並承諾不在接受proposalid小於等於5的prepare request（假設這時候C,D,E的acceptedproposalid與acceptedvalue都為空），然後在t2時間C,D,E都重啟了，這時候其原有的承諾不再接受proposalid小於5已經失效了，如果在t3時間B攜帶proposalid=4，發起prepare request請求過來，然後C,D,E發現比自己的minproposalid(重啟後為0)大，於是接受這個prepare請求，然後t4時間B發起accept請求，然後C,D,E接收到該accept請求時接受該請求，並返回給B，於是B返回給客戶端，這時候C,D,E的minproposalid=4，acceptedproposaid=4，而在t5時間A發起了其accept請求，其攜帶的proposalid=5，acceptor發現比自己的acceptedproposaid要大，然後就接受了該accept request，那麼原來B已經返回給用戶的acceptvalue就被A的acceptvalue覆蓋了。

5.4 maxround

proposer需要持久化的信息，proposer需要保持proposalid單調遞增，那麼他需要知道自己上一次發送的proposalid（round, serverID）。這個maxround不僅是自己的round，acceptor也會把自己見到的proposalid返回給proposer。

6 leaner的作用

為什麼需要有leaner這個角色？

paxos paper中大篇幅的描述了proposer和acceptor的執行邏輯，對於leaner角色描述較少。

raft leaner：etcd leaner

etcd在新版本中加入了leaner角色，主要解決的問題就是在配置變更的時候新節點加入可能引入的不可用問題。leaner以一個非投票節點的身份加入集羣，在其wal catch up之後promote為follower，參與投票。

paxos leaner：

paxos論文中沒有過多描述leaner角色，其leaner角色也是無投票權，只是被動的從集羣中獲取已經被chosen的值，在工程實現中也可以像raft用於節點加入是緩和集羣可用性。

7 multi paxos[1]

basic paxos用來確定一個值，而我們常用的場景都是確定多個值，比如我們的WAL。那我們如何用paxos確定多個值呢？所以就引入了multi paxos。multi paxos就是多個paxos instance。

7.1 leader

multi paxos與leader並沒有直接關係，leader只是multi paxos優化的一種方式，multi paxos沒有leader照樣工作。我們該如何理解這個leader？那麼引入leader的作用是什麼呢？

加入leader的目的一方面就是為了讓這個具有多個instance的系統就像只有一個paxos instance一樣工作，就像把這個wal整體當做一個value，另外一方面是為了提高工作效率。paxos對

7.2 線性一致性read

共識演算法目的是在多個node之間確定一個值，只有修改這個值的時候纔有可能導致集羣間不一致，所以如果只是讀，並不會對集羣的一致性有威脅，因此讀並沒有必要再走一遍共識演算法的全部流程。但是讀請求需要根據業務場景需求選擇讀的方式，業務場景需求有線性一致要求，最終一致性，因果一致性等，所以需要根據實際場景設計不同的讀請求邏輯。

• 線性一致性讀
• 最終一致性讀

7.3 並行propose，並行apply？

multi paxos能接受並行propose，但是不允許並行apply到狀態機。很簡單，並發apply無法確定多個節點之間對一個offset的修改的順序是一致的，就是說在這個地方無法做到節點保序。

7.4 日誌空洞？

• 什麼情況下會出現日誌空洞？

就像前面說的，multi paxos中引入leader來提高性能，其並沒有限制leader個數，也就是說在集羣中是可能存在多個leader的，如果這多個leader針對同一log entry進行propose，就退化為basic paxos了。

當集羣中存在多個leader時，這些leader可以並發發起propose，然後發起accept。如果這些leader是針對不同的log進行propose的時候，那麼可能就會導致有些leader在某個logid上是空洞的。

• 日誌空洞如何處理？

空洞日誌處理其實與具體的multi paxos工程實現有關了，有哪幾個點可以處理這個空洞呢？

1. 新的write到來的時候，就像上圖中新的日誌到來，需要判斷將這個日誌存放在哪個地方，首先需要對每個entry執行一次basic paxos，如果發現這個id上已經有確定的值，那就嘗試下一個，在這個過程中可以發現有哪些節點存在空洞的，比如index=3的日誌，S2就沒有持久化信息，那麼就可以將S1或者S3的內容複製過去。
2. 重啟回放的時候，重啟回放會對WAL的entry執行basic paxos，同樣可以像1那樣的發現空洞並填充
3. 在read請求來的時候，也可以通過執行一次basic paxos得到空洞信息。
4. 從leaner獲取chosen的value

7.5 multi paxos vs raft

raft 是基於對multi paxos 的兩個限制形成的[9]

• 發送的請求的是連續的, 也就是說raft 的append 操作必須是連續的. 而paxos 可以並發的. (其實這裡並發只是append log 的並發提高, 應用的state machine 還是必須是有序的)
• 選主是有限制的, 必須有最新, 最全的日誌節點纔可以當選. 而multi-paxos 是隨意的 所以raft 可以看成是簡化版本的multi paxos(這裡multi-paxos 因為允許並發的寫log, 因此不存在一個最新, 最全的日誌節點, 因此只能這麼做. 這樣帶來的麻煩就是選主以後, 需要將主裡面沒有的log 給補全, 並執行commit 過程)
• raft term VS poxos minproposalid

• paxos並行 raft串列？multi paxos分析
• raft與paxos詳細對比raft與paxos相比的優勢
• raft配置變更與paxos配置變更

reference：

1. FLP paper
2. paxos made simple
3. paxos made live
4. paxos Wikipedia
5. 分散式網路故障模型
6. 分散式系統一致性的發展歷史
7. consensus paxos and FLP
8. paxos summary
9. 談談paxos、multi paxos、raft
10. 用paxos實現多副本日誌系統--multi paxos部分

推薦閱讀：

相關文章