如何進行paxos算法分析

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

基礎paxos

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

每個acceptor 只chose第一個value，這樣可以嗎？ 不可以。因為這樣可能會出現proposal1的acceptor和proposal2的acceptor的數量一樣多，無法選出哪一個proposal作為chosenproposal。例如server1 選中proposal1，server2 選中proposal1和proposal2，server3 選中proposal2。 解決方案：每個proposer在發起proposal前必須確認當前是否有proposal選中，如果有，則放棄自己的proposal。

chosen過程中會出現沖突，依據沖突不同得出結論： 一旦選中一個proposal，其他競選proposal必須選擇同樣的value；proposal按照proposal number排序，拒絕舊proposal；

通過上述描述， 可設計proposal number 結構如下： 由兩部分組成：

1. round number： paxos執行的回數，每個服務器都必須保持最新的maxRound【保證盡量少的出現沖突，都競爭最大編號】

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

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

• paxos各階段目標：

• prepare階段

• accept階段

1. 使得所有acceptor接受proposal。

1. 發現任任何被選擇的proposal。發現后將自己的value改為發現的Value

2. 阻塞還未完成的proposal。當proposal number較大的proposal進入prepare階段后，舊的proposal在accept階段會被拒絕。

主要邏輯：

所有競爭的proposal必須有一個公共的acceptor，這樣就能發現新舊proposal，并及時終止舊proposal。

paxos活鎖：導致無proposal chosen。 proposal A 早prepare階段通過，另一proposal B進入prepare， acceptor的minProposal增加，導致A在accept階段被拒絕，A立即重試，并進入prepare階段，導致acceptor的minProposal增加，B進入accept階段后被拒絕。。。如此往復。沒有command能正常進行。

解決方案：每次重試必須在隨機的時延后進行。

multi-paxos

如何選擇log entry？

實現步驟：

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

2. 運行basic paxos， value為client command，

3. prepare return 中是否包含acceptedvalue？

• 有：chosen acceptedvalue，并重復步驟1

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

例子：

如上表，當client請求jmp時，假設server3 crashed，此時到slot3，由于server1和server2不同，不知道是否chosen Proposal，于是以client command的值為value； 運行paxos，進入prepare（n），server1 slot3已經有acceptedvalue，所以Proposal的value會改為server 1 slot 3的值，然后進行accept階段，server2 slot3 接收value。將server2 slot3 改為cmp。

同理，server1 slot4 改為sub：

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

注意：上述server3 crashed！

在上述處理過程中：server可以同時接收多個client請求，只要能保證client 請求的log Entry不同即可； 但是在command進入server狀態機執行的時候，必須是順序進行。

如何改善multi-paxos性能？

multi-paxos的問題：

1. 多個proposer進行時，會出現沖突和重試，降低系統chosen效率；

2. 對每個選定的value需要進行2回RPC調用；

解決方案：

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

2. 清除絕大多數的prepare RPC調用

• 進行一次prepare

• 大多數的log entry 能在一個RPC調用完成

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

4. 怎么處理prepare階段

• 將Proposal與logEntry slot關聯，每個Proposal number表示一個slot

• 最大的acceptedProposal 的values；

• 當前log entry slot中，每個server的當前slot都沒有acceptedvalue，返回noMoreAccepted

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

2. 如果leader得知noMoreAccepted，不需要使用prepare了，直接進入accpt階段。因為所有server的該slot均為空，直接通知acceptor accept Proposal。此時只需要一輪accept RPC。

3. 阻塞舊Proposal：

4. 查找可能chosen的value：

5. 為什么需要prepare階段？

6. 改進后：

怎么全備份？ 目標：每個server上的備份都是全備份。

目標細分：

1. log entry沒有full replication：full replication

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

解決步驟：

1. proposer在后臺一直accept 請求RPC，直到到所有server都回應。能保證大多數server都是full replication（為什么只是大多數？因為有可能之前有server crash，有些log entry為空，就算回應一次，并不能把所有slot都都填充完整，操作布恩那個進入狀態機執行，不能達到full replication）

2. track chosen entries

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

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

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

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

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

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

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

客戶端協議

1. 發送command給leader

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

2. 如果聯系的server不是leader，自動重定向到leader

2. leader在command被log entry選中后，在leader的狀態機中執行，執行出結果，然后回應client

3. 請求超時

1. clinet請求別的server

2. 重定向leader server

3. 重新請求command

4. 如果leader在執行后，響應client前crash，一條command不能被執行兩次

1. client為每個command提供唯一的標識

2. server 在log entry中保存command id

3. 狀態機保最近的每個client的commandid

4. 執行command前，狀態機檢查command是否已經執行過，執行過，直接忽略并返回old command的執行結果。

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

配置修改

系統配置：serverid和address 這些直接會改變quorum。造成系統的majority數量的改變。

為什么需要系統設置變化：

1. server crash

2. replication change

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

解決方案：使用paxos中log entry管理配置變動

1. 配置保存為log entry

2. 和其他log entry一樣備份

3. 在choseing log entry i 時 使用log entry index為i-a作為系統配置。（其中a為系統參數，在系統啟動時定義）

引入a后：

1. 系統的并發數量必須在a以內：因為在log 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

關于如何進行paxos算法分析就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。