共識算法：Paxos 算法
1. 目錄
[TOC]
2. 共識問題 [1]
- 什么是共識問題覆享？
粗略地說昔驱，該問題是在一個或多個進程提議了一個值應(yīng)當(dāng)是什么后黍瞧，使進程對這個值達(dá)成一致協(xié)定躬翁。 - 解決什么問題昧旨？
- 在一個計算機提議一個動作后拜轨，控制引擎的所有計算機要決定“繼續(xù)”還是“放棄”抽减。
- 在互斥中，進程對哪個進程可以進入臨界區(qū)達(dá)成協(xié)定橄碾。
- 在選舉中卵沉，進程對當(dāng)選進程達(dá)成協(xié)定。
- 在全排序組播中法牲，進程對消息傳遞順序達(dá)成協(xié)定史汗。
2.1 一個例子：問題描述 [2]
假設(shè)有兩支（或多支）軍隊，他們必須做到同時進攻或同時防守拒垃，否則就會失敗停撞。所有軍隊組成一個系統(tǒng)，他們必須共同動作悼瓮。問題是戈毒，如何讓他們步調(diào)一致？
現(xiàn)在不妨把軍隊看做”進程“横堡，把進攻或防守看做一個變量”行動“埋市。
在單機系統(tǒng)中，這個問題很容易解決命贴。用一個互斥量就搞定了道宅，類似于多線程食听。
在分布式系統(tǒng)中，這個問題就麻煩啦污茵。假設(shè)每個進程都在不同的服務(wù)器上樱报，他們就無法通過共享內(nèi)存達(dá)到同步。如果進程是軍隊的話省咨，軍隊之間只能通過通信兵來進行通信（消息傳遞）＄枋遥基于消息傳遞的分布式軍隊系統(tǒng)會有這些問題：
- 如何確定另一支軍隊是否被干掉零蓉？（服務(wù)器崩潰）
- 如何知道通信兵是否被殺死（消息丟失）或久久未到達(dá)其他軍隊（延遲不可預(yù)知）？
- 如果馬路等通信信道被切斷怎么辦穷缤？（網(wǎng)絡(luò)分割）
2.2 另一個例子
在一個分布式數(shù)據(jù)庫系統(tǒng)中敌蜂，如果各節(jié)點（server，或進程）的初始狀態(tài)一致津肛，每個節(jié)點都執(zhí)行相同的操作序列章喉，那么他們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點執(zhí)行相同的命令序列身坐，需要在每一條指令上執(zhí)行一個“一致性算法”以保證每個節(jié)點看到的指令一致秸脱，是分布式計算中的重要問題。
3. Paxos 的一致性原則 [3]
- Safety （壞的事情一定不會發(fā)生）
- 只有被提議的值才會被選擇部蛇；
- 只能有一個值被批準(zhǔn)摊唇，不能出現(xiàn)第二個值把第一個覆蓋的情況；
- 每個節(jié)點只能學(xué)習(xí)到已經(jīng)被批準(zhǔn)的值涯鲁，不能學(xué)習(xí)沒有被批準(zhǔn)的值 巷查。
- Liveness （好的事情最終一定會發(fā)生）
- 最終會批準(zhǔn)某個被提議的值；
- 一個值被批準(zhǔn)了抹腿，其他進程最終會學(xué)習(xí)到這個值岛请。
Paxos 只保證Safety，而不能保證Liveness警绩。
4. Paxos算法描述
4.1 假設(shè) [3]
每個server都可以擔(dān)任三種角色：提案者（Proposer）崇败、接受者（Acceptor）、學(xué)習(xí)者（Learner）肩祥。提案者負(fù)責(zé)提出提案(proposal)僚匆，接受者負(fù)責(zé)通過提案，而學(xué)習(xí)者負(fù)責(zé)更新提案搭幻。
每個提案都會被分配一個自然數(shù)$n$作為ID咧擂，以及一個需要提出的值$v$。
4.2 選擇一個值(Choosing a Value) [3]
階段一
a. 提案者選擇一個提案(proposal)編號$n$檀蹋，向接受者多數(shù)派組播一個prepare請求松申。
b. 如果一個接受者收到一個prepare請求云芦，并且編號$n$是所有他已經(jīng)通過的prepare請求中最大的，那么他會同意這個新的prepare請求贸桶，并承諾不會再同意任何比$n$小的prepare請求和accept請求舅逸。
階段二
a. 如果提案者收到一個接受者多數(shù)派的回應(yīng)prepare_ok(n，na, va)皇筛，那么他就選出最大的$n_a$所對應(yīng)的$v_a$琉历。或者水醋，若所有回應(yīng)中$v_a$都為空旗笔，也就是還沒有同意過任何提案，那么就選擇自己的$v$拄踪。然后發(fā)送accept(n,v)請求蝇恶。
b. 如果一個接受者收到一個 accept(n,v) 請求，并且$n$大于所有它 prepare 過的$n_p$惶桐，那么他就接受這個$v$撮弧，然后回復(fù) accept_ok(n)。
4.3 學(xué)習(xí)一個值(Learning a Chosen Value)
當(dāng)一個提案被多數(shù)派通過姚糊，這提案者就向所有人（servers）發(fā)送decided(v)贿衍，貫徹與落實這個$v$。
4.4 Paxos偽代碼[4]
# Proposer
proposer(v):
while not decided:
n = heigher(N[:]) # 嘗試分配一個當(dāng)前最大的n值給這個proposal
send prepare(n) # 向所有acceptor發(fā)送prepare request
# 若大部分返回ok：
if prepare_ok(n, na, va) from majority:
# 從{na...}中選出最大的那個和對應(yīng)的va救恨，令v=va舌厨；否則，就選自己的v
v = va with heighest na; otherwise choose its own v
send accept(n, v) to all # 向所有acceptor發(fā)送accept request
if accept_ok(n) from majority:
send decided(v) to all # 決定v并通知所有成員
# Acceptor
acceptor state on each node (persistent):
np # 最大的promise值
na, va # 最大的accepted值
prepare(n) handler:
if n > np:
n = np
send prepare_ok(n) # 承諾不再接受任何比 n 小的proposal
else:
send prepare_reject
accept(n, v) handler:
if n >= np:
na = n
va = v
send accept_ok(n)
else:
send accept_reject
直觀理解
容錯性分析(Fault tolerant) [5]
究竟Paxos是如何保證一致性的呢忿薇？例子如下裙椭。
3.1服務(wù)器崩潰(crash)
若有 $2f+1$ 臺服務(wù)器，則最多可以容忍 $f$ 臺服務(wù)器崩潰署浩。下面舉一個簡單的例子揉燃，假設(shè)一個分布式系統(tǒng)由5個servers組成，其中2個在任意時刻崩潰筋栋。存在兩種情況：1.Acceptor或Learner崩潰了炊汤；2.Leader崩潰了。
3.1.1. Acceptor 崩潰
如下圖所示弊攘，S1為Leader抢腐，當(dāng)其發(fā)出Accept請求時，S4和S5崩潰了襟交。但是S1迈倍，S2，S3仍然構(gòu)成多數(shù)派捣域，所以$v$仍然可以被決定下來啼染。
3.1.2. Leader 崩潰
Learder崩潰要稍微麻煩一點宴合。首先要有錯誤檢測，發(fā)現(xiàn)leader S1掛了迹鹅。然后卦洽，因為沒有l(wèi)eader了，所以要重新選舉斜棚。如圖阀蒂，S1，S5掛了弟蚀，但是S2蚤霞，S2，S3仍然構(gòu)成多數(shù)派粗梭。S2發(fā)出prepare請求争便，S3级零，S4返回最近接受的$v_1$断医，$v_1$再次被S2請求接受。于是$v_1$還是成功被決定下來了奏纪。
3.2 網(wǎng)絡(luò)分割(network partitioning)
另一種常見錯誤是網(wǎng)絡(luò)分割鉴嗤。如下圖所示，S1序调，S2與S3醉锅，S4，S5之間的通信被斷開发绢，分成了兩個子網(wǎng)絡(luò)硬耍。在這種悲催的情況下，系統(tǒng)仍然可以達(dá)成共識边酒。
一旦發(fā)生分割经柴，通過錯誤檢測是可以發(fā)現(xiàn)的，例如超時墩朦。然后多數(shù)派一方就會進行重新選舉坯认，如圖，S3成為新leader氓涣。系統(tǒng)又可以正常運作了牛哺。
不過，問題還沒完劳吠。如果網(wǎng)絡(luò)通信在某一時刻又恢復(fù)正常引润，分布式系統(tǒng)中就會同時存在兩個leader！Paxos還可以保證共識嗎痒玩？是可以的椰拒。因為$n_2>n_1$晶渠，S3～S4 已經(jīng)承諾不再接受比$n_2$小的提案了。所以老leader S1的提案$(n_1,v_1)$會被拒絕燃观，而S3的提案$(n_2,v')$會獲得通過褒脯。
3.3 消息丟失(message lost)
由于網(wǎng)絡(luò)層是不可靠的，消息丟失和延時是無法避免的缆毁。應(yīng)對這類錯誤的主要方法還是重傳番川。
