- "拜占庭將軍問題"說明了:試圖在異步系統和不可靠的通道上來達到一致性狀態是不可能的,因此在實際工程中假設都是不存在這個問題的
- 對於一組可以提出提案的進程集合中,一致性算法的核心需求為:
- 只有一個提案會被選定
- 沒有提案提出,就沒有提案選定
- 一個提案選定後,進程可以獲取被選定的提案
- 只有被提出的提案才能被選定
- 只能有一個值被選定
- 如果某個進程認為某個提案被選定了,那麼這個提案必須真的被選定了
- 該算法需要三個角色:Proposer(提案人),Acceptor(接收人),Learner(學習者),他們之間的狀態滿足:
- 每個參與者都可能失敗或重啟,因此除非重啟的參與者可以記錄某些信息,否則將無法確定最終的值
- 消息在傳輸過程中會出現延遲,重複,或者丟失,但不會被篡改或損壞
- Paxos算法推導
- 為了避免單點問題,Acceptor的數量應該是多個的,且當足夠多的Acceptor批准某一提案時,這裡的足夠多為>50%.理由是:任意兩個足夠多的Acceptor至少應該包含一個相同Acceptor,如果再限制每個Acceptor只能批准一個決議內容,那麼就可以確保不會同時出現兩個決議被多數派批准
- 為了滿足只有一個提案被提出的情況下,仍然可以選定一個提案,便導出如下需求:
- P1 一個Acceptor必須批准它收到的第一個提案
- 由此,引出了一個問題:同時被提出的提案中,可能連一個被滿足半數以上acceptor批准的都沒有,因此需要acceptor在批准第一個提案以後還要根據某些規則批准其他的提案.
- 若是能夠批准多個提案,則有新的問題:可能同時選擇出複數的決議內容,與2.a的一致性原則不符
- 解決這個問題,則需要二段提交:先檢查半數以上的acceptor集中有沒有已經被批准的值,如果有,則放棄自己的值,改為提議這個被批准的值
- 但是這個方法帶來新的問題:同時有兩個以上的提案在檢查時發現沒有值被批准,就會都對多數Acceptor發送自己值的提案,導致衝突
- 由於兩個多數Acceptor集合必定有一個以上的Acceptor是重合的,因此需要這些個Acceptor根據一定規則篩選出最終批准的提案
- 將一個提案分為{k,v}其中k為全局遞增的id,v是決議內容
- 當一個提案被多數Acceptor批准,則視這個提案被選定了.為了確保一致性,所有被選定的提案需要保證其value值一樣(P2)
- 為了保證所有選定的提案的value值一樣,則需要保證在選定一個提案以後,後來批准的提案值必須與這個提案值一樣(P2a)
- 為了保證acceptor在選定一個提案以後批准的都是與這個提案一樣值的提案,proposer在Acceptor選定提案後提出的提案必須和選定的提案值一樣(P2b)
- 為了保證proposer能夠提出和已經選定的提案相同值的提案,在提案{Kn,Vn}提出時,需要存在一個多數的Acceptor集合滿足以下任一條件(P2c):
- 集合中的Acceptor沒有批准過編號小於Kn的提案
- 集合中已經批准過的小於Kn的提案中,編號最大的那個值為Vn()
- 在P2C的基礎上,可以確定proposer的生成算法:
- 首先選擇一個提案編號Kn,向Acceptor集合發送請求,稱為Prepare請求
- Acceptor收到Kn,做出回應:保證不再批准編號小於Kn的提案,若是已經批准,將最大編號的value值返回給proposer(階段一)
- proposer收到半數以上響應結果,如果有返回value值,則生成提案{Kn,value},若是響應中沒有value,則可以取任意值
- 生成具體提案後,向Acceptor發送並期望獲得批准,稱為Accept請求
- 根據Prepare和Accept請求,Acceptor的執行策略為
- 對於Prepare請求,可以任意響應
- 對於Accept請求,只要未響應過任何編號>Kn的Prepare請求,則可以接受這個編號為Kn的提案(P1a)(階段二)
- 優化:在極端的情況下,比如兩個proposer相繼提出一系列編號遞增的提案時,因為輪流的prepare和拒絕accept,會導致死循環而最終沒有任何提案被選定,為此必須選擇一個主Proposer,並規定只有主Proposer才能提出提案.
分享到:
閱讀更多 Java程序猿鼓勵師 的文章
