如何進(jìn)行paxos算法分析

這篇文章給大家介紹如何進(jìn)行paxos算法分析，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

基礎(chǔ)paxos

只有一個(gè)acceptor可以嗎？ 不可以。所有的proposer都往一個(gè)acceptor上發(fā)消息，這個(gè)acceptor crashed，那么整個(gè)系統(tǒng)就crashed。 解決方法：使用quorum （仲裁人數(shù)）。多個(gè)acceptor， 只需要大多數(shù)acceptor選中某個(gè)value就可以了，萬一某一個(gè)acceptor crashed，不影響系統(tǒng)。

每個(gè)acceptor 只chose第一個(gè)value，這樣可以嗎？ 不可以。因?yàn)檫@樣可能會出現(xiàn)proposal1的acceptor和proposal2的acceptor的數(shù)量一樣多，無法選出哪一個(gè)proposal作為chosenproposal。例如server1 選中proposal1，server2 選中proposal1和proposal2，server3 選中proposal2。 解決方案：每個(gè)proposer在發(fā)起proposal前必須確認(rèn)當(dāng)前是否有proposal選中，如果有，則放棄自己的proposal。

chosen過程中會出現(xiàn)沖突，依據(jù)沖突不同得出結(jié)論： 一旦選中一個(gè)proposal，其他競選proposal必須選擇同樣的value；proposal按照proposal number排序，拒絕舊proposal；

通過上述描述， 可設(shè)計(jì)proposal number 結(jié)構(gòu)如下： 由兩部分組成：

1. round number： paxos執(zhí)行的回?cái)?shù)，每個(gè)服務(wù)器都必須保持最新的maxRound【保證盡量少的出現(xiàn)沖突，都競爭最大編號】

2. server id：每個(gè)服務(wù)器有唯一的id【保證proposal編號不會相同 】

maxRound必須保存在永久存儲介質(zhì)上，一段server crash，可以重新使用 round number 發(fā)起proposal

• paxos各階段目標(biāo)：

• prepare階段

• accept階段

1. 使得所有acceptor接受proposal。

1. 發(fā)現(xiàn)任任何被選擇的proposal。發(fā)現(xiàn)后將自己的value改為發(fā)現(xiàn)的Value

2. 阻塞還未完成的proposal。當(dāng)proposal number較大的proposal進(jìn)入prepare階段后，舊的proposal在accept階段會被拒絕。

主要邏輯：

所有競爭的proposal必須有一個(gè)公共的acceptor，這樣就能發(fā)現(xiàn)新舊proposal，并及時(shí)終止舊proposal。

paxos活鎖：導(dǎo)致無proposal chosen。 proposal A 早prepare階段通過，另一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)步驟：

1. 找到第一個(gè)log entry 不知道是否chosen的entry slot，（不一定是第一個(gè)為空的slot）

2. 運(yùn)行basic paxos， value為client command，

3. prepare return 中是否包含acceptedvalue？

• 有：chosen acceptedvalue，并重復(fù)步驟1

• 無:chosen client請求，該slot即是尋找的slot

例子：

如上表，當(dāng)client請求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會改為server 1 slot 3的值，然后進(jìn)行accept階段，server2 slot3 接收value。將server2 slot3 改為cmp。

同理，server1 slot4 改為sub：

然后slot5， acceptedValue=null；次次Proposal的value為元定義的value，即client的command。

注意：上述server3 crashed！

在上述處理過程中：server可以同時(shí)接收多個(gè)client請求，只要能保證client 請求的log Entry不同即可； 但是在command進(jìn)入server狀態(tài)機(jī)執(zhí)行的時(shí)候，必須是順序進(jìn)行。

如何改善multi-paxos性能？

multi-paxos的問題：

1. 多個(gè)proposer進(jìn)行時(shí)，會出現(xiàn)沖突和重試，降低系統(tǒng)chosen效率；

2. 對每個(gè)選定的value需要進(jìn)行2回RPC調(diào)用；

解決方案：

1. 選擇learder。一次只有一個(gè)leader，這樣就不會有多proposer發(fā)生沖突

2. 清除絕大多數(shù)的prepare RPC調(diào)用

• 進(jìn)行一次prepare

• 大多數(shù)的log entry 能在一個(gè)RPC調(diào)用完成

3. 如何選擇leader？ 1.讓serverid最大的作為leader； 2.每隔Tms，每個(gè)server發(fā)送心跳包給其他server， 3.如果server在2Tms內(nèi)沒有收到比它大的server心跳，那么它可以作為leader，接受client 請求，擁有proposer角色 4.不是leader的server，拒絕client請求將請求重新定向到leader，acceptor角色。

4. 怎么處理prepare階段

• 將Proposal與logEntry slot關(guān)聯(lián)，每個(gè)Proposal number表示一個(gè)slot

• 最大的acceptedProposal 的values；

• 當(dāng)前l(fā)og entry slot中，每個(gè)server的當(dāng)前slot都沒有acceptedvalue，返回noMoreAccepted

1. 如果acceptor返回noMoreAccepted，則跳過同slot當(dāng)前server 后的所有的prepare RPC（直到accept拒絕Proposal，拒絕Proposal說明acceptro層接受過Proposal，存在acceptedvalue）。

2. 如果leader得知noMoreAccepted，不需要使用prepare了，直接進(jìn)入accpt階段。因?yàn)樗衧erver的該slot均為空，直接通知acceptor accept Proposal。此時(shí)只需要一輪accept RPC。

3. 阻塞舊Proposal：

4. 查找可能chosen的value：

5. 為什么需要prepare階段？

6. 改進(jìn)后：

怎么全備份？ 目標(biāo)：每個(gè)server上的備份都是全備份。

目標(biāo)細(xì)分：

1. log entry沒有full replication：full replication

2. 只有proposer知道那個(gè)entry被chosen：所有server都知道那個(gè)entry被選中。

解決步驟：

1. proposer在后臺一直accept 請求RPC，直到到所有server都回應(yīng)。能保證大多數(shù)server都是full replication（為什么只是大多數(shù)？因?yàn)橛锌赡苤坝衧erver crash，有些log entry為空，就算回應(yīng)一次，并不能把所有slot都都填充完整，操作布恩那個(gè)進(jìn)入狀態(tài)機(jī)執(zhí)行，不能達(dá)到full replication）

2. track chosen entries

1. 使得entries能被知道是否已經(jīng)chosen：acceptedEntry[i] = 無窮大 表示第i個(gè)entry被chosen。

2. 每個(gè)server都維護(hù)一個(gè)firstUnchosenIndex，該索引是entry的索引，表示該索引前的entry均被chosen。

3. proposer（也就是leader）告知acceptor選擇entry：

1. proposer在accept RPC時(shí)，發(fā)送firstUnchosenIndex。那么acceptor知道entry索引小于firstUnchosenIndex的均被chosen。

2. acceptor標(biāo)記同時(shí)滿足以下條件的entry為chosen：i<firstUnchosenIndex && accptedProposal[i] == proposal【proposal相等即表示是同一個(gè)leader發(fā)送的proposal，又index < firstUnchosenIndex,可知前面均chosen，】

4. acceptor不能確認(rèn)proposal number不同的log entry 是否chosen。 解決方案：acceptor在返回時(shí)，返回acceptor的firstUnchosenIndex，若proposer的firstUnchosenIndex 大于acceptor的firstUnchosenIndex, 那么proposer在后臺發(fā)送[success] RPC。

success(Index, v):
acceptedValue[index] = v;
acceptedProposal[index]=無窮大
return firstUnchosenIndex

客戶端協(xié)議

1. 發(fā)送command給leader

1. 如果leader down， 發(fā)送消息給任意的server

2. 如果聯(lián)系的server不是leader，自動重定向到leader

2. leader在command被log entry選中后，在leader的狀態(tài)機(jī)中執(zhí)行，執(zhí)行出結(jié)果，然后回應(yīng)client

3. 請求超時(shí)

1. clinet請求別的server

2. 重定向leader server

3. 重新請求command

4. 如果leader在執(zhí)行后，響應(yīng)client前crash，一條command不能被執(zhí)行兩次

1. client為每個(gè)command提供唯一的標(biāo)識

2. server 在log entry中保存command id

3. 狀態(tài)機(jī)保最近的每個(gè)client的commandid

4. 執(zhí)行command前，狀態(tài)機(jī)檢查command是否已經(jīng)執(zhí)行過，執(zhí)行過，直接忽略并返回old command的執(zhí)行結(jié)果。

如果client在發(fā)送command后，接受響應(yīng)前crash， 然后重新登陸，會遇到同樣的問題。client會提交兩次command，使用上述措施可以保證每條command只執(zhí)行一次。

配置修改

系統(tǒng)配置：serverid和address 這些直接會改變quorum。造成系統(tǒng)的majority數(shù)量的改變。

為什么需要系統(tǒng)設(shè)置變化：

1. server crash

2. replication change

安全原則：在配置變動時(shí)，避免對同一個(gè)log entry 有不同數(shù)量的majority和不同的value選擇。

解決方案：使用paxos中l(wèi)og entry管理配置變動

1. 配置保存為log entry

2. 和其他log entry一樣備份

3. 在choseing log entry i 時(shí) 使用log entry index為i-a作為系統(tǒng)配置。（其中a為系統(tǒng)參數(shù)，在系統(tǒng)啟動時(shí)定義）

引入a后：

1. 系統(tǒng)的并發(fā)數(shù)量必須在a以內(nèi)：因?yàn)樵趌og entry i 被chosen后才能 chosen entry a+i; 可以使用一些無操作的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)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。