共計(jì) 5995 個(gè)字符，預(yù)計(jì)需要花費(fèi) 15 分鐘才能閱讀完成。
這篇文章給大家介紹如何進(jìn)行 paxos 算法分析，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。
基礎(chǔ) paxos
只有一個(gè) acceptor 可以嗎？不可以。所有的 proposer 都往一個(gè) acceptor 上發(fā)消息，這個(gè) acceptor crashed，那么整個(gè)系統(tǒng)就 crashed。解決方法：使用 quorum（仲裁人數(shù)）。多個(gè) acceptor，只需要大多數(shù) acceptor 選中某個(gè) value 就可以了，萬(wàn)一某一個(gè) acceptor crashed，不影響系統(tǒng)。
每個(gè) acceptor 只 chose 第一個(gè) value，這樣可以嗎？不可以。因?yàn)檫@樣可能會(huì)出現(xiàn) proposal1 的 acceptor 和 proposal2 的 acceptor 的數(shù)量一樣多，無(wú)法選出哪一個(gè) proposal 作為 chosenproposal。例如 server1 選中 proposal1，server2 選中 proposal1 和 proposal2，server3 選中 proposal2。解決方案：每個(gè) proposer 在發(fā)起 proposal 前必須確認(rèn)當(dāng)前是否有 proposal 選中，如果有，則放棄自己的 proposal。
chosen 過(guò)程中會(huì)出現(xiàn)沖突，依據(jù)沖突不同得出結(jié)論：一旦選中一個(gè) proposal，其他競(jìng)選 proposal 必須選擇同樣的 value；proposal 按照 proposal number 排序，拒絕舊 proposal；
通過(guò)上述描述，可設(shè)計(jì) proposal number 結(jié)構(gòu)如下：由兩部分組成：
round number：paxos 執(zhí)行的回?cái)?shù)，每個(gè)服務(wù)器都必須保持最新的 maxRound【保證盡量少的出現(xiàn)沖突，都競(jìng)爭(zhēng)最大編號(hào)】
server id：每個(gè)服務(wù)器有唯一的 id【保證 proposal 編號(hào)不會(huì)相同】
maxRound 必須保存在永久存儲(chǔ)介質(zhì)上，一段 server crash，可以重新使用 round number 發(fā)起 proposal
paxos 各階段目標(biāo)：
prepare 階段
accept 階段
使得所有 acceptor 接受 proposal。
發(fā)現(xiàn)任任何被選擇的 proposal。發(fā)現(xiàn)后將自己的 value 改為發(fā)現(xiàn)的 Value
阻塞還未完成的 proposal。當(dāng) proposal number 較大的 proposal 進(jìn)入 prepare 階段后，舊的 proposal 在 accept 階段會(huì)被拒絕。
主要邏輯：
proposeracceptor1. 選擇 proposal number n
2. 廣播給 acceptor prepare(n)
3. 響應(yīng) prepare(n): if (n minProposol) then minProposol=n; Return(acceptedProposol,acceptedValue)4. 獲取大多數(shù) acceptor 回復(fù)：如果有返回，選擇返回中最大的 proposal number 對(duì)應(yīng)的 value 作為本次 proposal 的 value；如果沒有返回，可繼續(xù)使用之前的 value
5. 向所有 acceptor 廣播 accept(n,value)
6. 響應(yīng) accept(n,value)：if(n = minProposol) then acceptedProposol = minProposol = n; accptedValue = value; Return minProposol7. 獲取大多數(shù) acceptor 返回：如果存在 result n；表示 proposal 被拒絕，重復(fù) 1~6，且下次設(shè)置的 n 比 result 大，否則 chosen proposal
所有競(jìng)爭(zhēng)的 proposal 必須有一個(gè)公共的 acceptor，這樣就能發(fā)現(xiàn)新舊 proposal，并及時(shí)終止舊 proposal。
paxos 活鎖：導(dǎo)致無(wú) proposal chosen。proposal A 早 prepare 階段通過(guò)，另一 proposal B 進(jìn)入 prepare，acceptor 的 minProposal 增加，導(dǎo)致 A 在 accept 階段被拒絕，A 立即重試，并進(jìn)入 prepare 階段，導(dǎo)致 acceptor 的 minProposal 增加，B 進(jìn)入 accept 階段后被拒絕。。。如此往復(fù)。沒有 command 能正常進(jìn)行。
解決方案：每次重試必須在隨機(jī)的時(shí)延后進(jìn)行。
multi-paxos 如何選擇 log entry？
實(shí)現(xiàn)步驟：
找到第一個(gè) log entry 不知道是否 chosen 的 entry slot，（不一定是第一個(gè)為空的 slot）
運(yùn)行 basic paxos，value 為 client command，
prepare return 中是否包含 acceptedvalue？
有：chosen acceptedvalue，并重復(fù)步驟 1
無(wú):chosen client 請(qǐng)求，該 slot 即是尋找的 slot
例子：
1234567server 1movaddcmp
ret
server 2movadd
sub
ret
server 3movaddcmp
cmpret
如上表，當(dāng) client 請(qǐng)求 jmp 時(shí)，假設(shè) server3 crashed，此時(shí)到 slot3，由于 server1 和 server2 不同，不知道是否 chosen Proposal，于是以 client command 的值為 value；運(yùn)行 paxos，進(jìn)入 prepare（n），server1 slot3 已經(jīng)有 acceptedvalue，所以 Proposal 的 value 會(huì)改為 server 1 slot 3 的值，然后進(jìn)行 accept 階段，server2 slot3 接收 value。將 server2 slot3 改為 cmp。
1234567server 1movaddcmp
ret
server 2movaddcmpsub
ret
server 3movaddcmp
cmpret
同理，server1 slot4 改為 sub：
1234567server 1movaddcmpsub
ret
server 2movaddcmpsub
ret
server 3movaddcmp
cmpret
然后 slot5，acceptedValue=null；次次 Proposal 的 value 為元定義的 value，即 client 的 command。
1234567server 1movaddcmpsubjmpret
server 2movaddcmpsubjmpret
server 3movaddcmp
cmpret
找到 log entry slot。
注意：上述 server3 crashed！
在上述處理過(guò)程中：server 可以同時(shí)接收多個(gè) client 請(qǐng)求，只要能保證 client 請(qǐng)求的 log Entry 不同即可；但是在 command 進(jìn)入 server 狀態(tài)機(jī)執(zhí)行的時(shí)候，必須是順序進(jìn)行。
如何改善 multi-paxos 性能？
multi-paxos 的問(wèn)題：
多個(gè) proposer 進(jìn)行時(shí)，會(huì)出現(xiàn)沖突和重試，降低系統(tǒng) chosen 效率；
對(duì)每個(gè)選定的 value 需要進(jìn)行 2 回 RPC 調(diào)用；
解決方案：
選擇 learder。一次只有一個(gè) leader，這樣就不會(huì)有多 proposer 發(fā)生沖突
清除絕大多數(shù)的 prepare RPC 調(diào)用
進(jìn)行一次 prepare
大多數(shù)的 log entry 能在一個(gè) RPC 調(diào)用完成
如何選擇 leader？1. 讓 serverid 最大的作為 leader；2. 每隔 Tms，每個(gè) server 發(fā)送心跳包給其他 server，3. 如果 server 在 2Tms 內(nèi)沒有收到比它大的 server 心跳，那么它可以作為 leader，接受 client 請(qǐng)求，擁有 proposer 角色 4. 不是 leader 的 server，拒絕 client 請(qǐng)求將請(qǐng)求重新定向到 leader，acceptor 角色。
怎么處理 prepare 階段
將 Proposal 與 logEntry slot 關(guān)聯(lián)，每個(gè) Proposal number 表示一個(gè) slot
最大的 acceptedProposal 的 values；
當(dāng)前 log entry slot 中，每個(gè) server 的當(dāng)前 slot 都沒有 acceptedvalue，返回 noMoreAccepted
如果 acceptor 返回 noMoreAccepted，則跳過(guò)同 slot 當(dāng)前 server 后的所有的 prepare RPC（直到 accept 拒絕 Proposal，拒絕 Proposal 說(shuō)明 acceptro 層接受過(guò) Proposal，存在 acceptedvalue）。
如果 leader 得知 noMoreAccepted，不需要使用 prepare 了，直接進(jìn)入 accpt 階段。因?yàn)樗?server 的該 slot 均為空，直接通知 acceptor accept Proposal。此時(shí)只需要一輪 accept RPC。
阻塞舊 Proposal：
查找可能 chosen 的 value：
為什么需要 prepare 階段？
改進(jìn)后：
怎么全備份？目標(biāo)：每個(gè) server 上的備份都是全備份。
目標(biāo)細(xì)分：
log entry 沒有 full replication：full replication
只有 proposer 知道那個(gè) entry 被 chosen：所有 server 都知道那個(gè) entry 被選中。
解決步驟：
proposer 在后臺(tái)一直 accept 請(qǐng)求 RPC，直到到所有 server 都回應(yīng)。能保證大多數(shù) server 都是 full replication（為什么只是大多數(shù)？因?yàn)橛锌赡苤坝?server crash，有些 log entry 為空，就算回應(yīng)一次，并不能把所有 slot 都都填充完整，操作布恩那個(gè)進(jìn)入狀態(tài)機(jī)執(zhí)行，不能達(dá)到 full replication）
track chosen entries
使得 entries 能被知道是否已經(jīng) chosen：acceptedEntry[i] = 無(wú)窮大 表示第 i 個(gè) entry 被 chosen。
每個(gè) server 都維護(hù)一個(gè) firstUnchosenIndex，該索引是 entry 的索引，表示該索引前的 entry 均被 chosen。
proposer（也就是 leader）告知 acceptor 選擇 entry：
proposer 在 accept RPC 時(shí)，發(fā)送 firstUnchosenIndex。那么 acceptor 知道 entry 索引小于 firstUnchosenIndex 的均被 chosen。
acceptor 標(biāo)記同時(shí)滿足以下條件的 entry 為 chosen：i firstUnchosenIndex accptedProposal[i] == proposal【proposal 相等即表示是同一個(gè) leader 發(fā)送的 proposal，又 index firstUnchosenIndex, 可知前面均 chosen，】
acceptor 不能確認(rèn) proposal number 不同的 log entry 是否 chosen。解決方案：acceptor 在返回時(shí)，返回 acceptor 的 firstUnchosenIndex，若 proposer 的 firstUnchosenIndex 大于 acceptor 的 firstUnchosenIndex, 那么 proposer 在后臺(tái)發(fā)送 [success] RPC。
success(Index, v):
acceptedValue[index] = v;
acceptedProposal[index]= 無(wú)窮大
return firstUnchosenIndex客戶端協(xié)議
發(fā)送 command 給 leader
如果 leader down，發(fā)送消息給任意的 server
如果聯(lián)系的 server 不是 leader，自動(dòng)重定向到 leader
leader 在 command 被 log entry 選中后，在 leader 的狀態(tài)機(jī)中執(zhí)行，執(zhí)行出結(jié)果，然后回應(yīng) client
請(qǐng)求超時(shí)
clinet 請(qǐng)求別的 server
重定向 leader server
重新請(qǐng)求 command
如果 leader 在執(zhí)行后，響應(yīng) client 前 crash，一條 command 不能被執(zhí)行兩次
client 為每個(gè) command 提供唯一的標(biāo)識(shí)
server 在 log entry 中保存 command id
狀態(tài)機(jī)保最近的每個(gè) client 的 commandid
執(zhí)行 command 前，狀態(tài)機(jī)檢查 command 是否已經(jīng)執(zhí)行過(guò)，執(zhí)行過(guò)，直接忽略并返回 old command 的執(zhí)行結(jié)果。
如果 client 在發(fā)送 command 后，接受響應(yīng)前 crash，然后重新登陸，會(huì)遇到同樣的問(wèn)題。client 會(huì)提交兩次 command，使用上述措施可以保證每條 command 只執(zhí)行一次。
配置修改
系統(tǒng)配置：serverid 和 address 這些直接會(huì)改變 quorum。造成系統(tǒng)的 majority 數(shù)量的改變。
為什么需要系統(tǒng)設(shè)置變化：
server crash
replication change
安全原則：在配置變動(dòng)時(shí)，避免對(duì)同一個(gè) log entry 有不同數(shù)量的 majority 和不同的 value 選擇。
解決方案：使用 paxos 中 log entry 管理配置變動(dòng)
配置保存為 log entry
和其他 log entry 一樣備份
在 choseing log entry i 時(shí) 使用 log entry index 為 i - a 作為系統(tǒng)配置。（其中 a 為系統(tǒng)參數(shù)，在系統(tǒng)啟動(dòng)時(shí)定義）
引入 a 后：
系統(tǒng)的并發(fā)數(shù)量必須在 a 以內(nèi)：因?yàn)樵?log entry i 被 chosen 后才能 chosen entry a+i; 可以使用一些無(wú)操作的 command 加速配置改變。
核心為代碼
核心邏輯偽代碼：
--- Paxos Proposer ---
proposer(v):
while not decided:
choose n, unique and higher than any n seen so far
send prepare(n) to all servers including self
if prepare_ok(n, na, va) from majority:
v’ = va with highest na; choose own v otherwise
send accept(n, v’) to all
if accept_ok(n) from majority:
send decided(v’) to all--- Paxos Acceptor ---
acceptor state on each node (persistent):
np --- highest prepare seen
na, va --- highest accept seen
acceptor’s prepare(n) handler:
if n np
np = n
reply prepare_ok(n, na, va)
else
reply prepare_reject
acceptor’s accept(n, v) handler:
if n = np
np = n
na = n
va = v
reply accept_ok(n)
else
reply accept_reject關(guān)于如何進(jìn)行 paxos 算法分析就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。
