一致性算法Paxos解決了什么問題

這篇文章主要講解了“一致性算法Paxos解決了什么問題”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“一致性算法Paxos解決了什么問題”吧！

一：一致性算法Paxos

Paxos算法是基于消息傳遞且具有高度容錯特性的一致性算法，是目前公認的解決分布式一致性問題最有效的算法之一。

1.1 Paxos解決了什么問題

在常見的分布式系統中，總會發生諸如通信異常、節點故障、網絡分區等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正確地在集群內部對某個數據的值達成一致，并且保證不論發生以上任何異常，都不會破壞整個系統的一致性。

注意：這里某個數據的值并不只是狹義上的某個數，它可以是一條日志，也可以是一條命令（command）。根據應用場景不同，某個數據的值有不同的含義。

1.2 Paxos的相關概念

提案 (Proposal)：Proposal信息包括提案編號 (Proposal ID) 和提案的值 (Value)

在Paxos算法中，有三種角色）：

• Proposer：提案發起者，提案者提倡客戶請求，試圖說服Acceptor對此達成一致，并在發生沖突時充當協調者以推動協議向前發展

• Acceptor：決策者，可以批準提案，Acceptor可以接受（accept）提案；如果某個提案被選定（chosen），那么該提案里的value就被確定了

• Learners：最終決策的學習者，學習者充當該協議的復制因素

1.4 Proposer生成提案規則

Proposer生成提案之前，應該先去『學習』已經被選定或者可能被選定的value，然后以該value作為自己提出的提案的value。如果沒有value被選定，Proposer才可以自己決定value的值。這樣才能達成一致。這個學習的階段是通過一個『Prepare請求』實現的。

下圖為多數Acceptor集合（半數以上）沒有接收提案的情況：

Proposer提案生成算法：

• Proposer選擇一個新的提案編號N，然后向某個Acceptor集合（半數以上）發送請求，要求該集合中的每個Acceptor做出如下響應（response）。
  (a) 向Proposer承諾保證不再接受任何編號小于N的提案。
  (b) 如果Acceptor已經接受過提案，那么就向Proposer響應已經接受過的編號小于N的最大編號的提案。

我們將該請求稱為編號為N的Prepare請求。

• 如果Proposer收到了半數以上的Acceptor的響應，那么它就可以生成編號為N，Value為V的提案[N,V]。這里的V是所有的響應中編號最大的提案的Value。如果所有的響應中都沒有提案，那 么此時V就可以由Proposer自己選擇。
  生成提案后，Proposer將該提案發送給半數以上的Acceptor集合，并期望這些Acceptor能接受該提案。

我們稱該請求為Accept請求。（注意：此時接受Accept請求的Acceptor集合不一定是之前響應Prepare請求的Acceptor集合）

1.5 Acceptor接收提案規則

一個Acceptor可能會收到來自Proposer的兩種請求，分別是Prepare請求和Accept請求，對這兩類請求作出響應的條件分別如下：

• Prepare請求：Acceptor可以在任何時候響應一個Prepare請求

• Accept請求：在不違背Accept現有承諾的前提下，可以任意響應Accept請求

因此，對Acceptor接受提案給出如下約束：

p1a：一個Acceptor只要尚未響應過任何編號大于N的Prepare請求，那么他就可以接受這個編號為N的提案。

Acceptor算法優化

由上面可知，如果Acceptor收到一個編號為N的Prepare請求，在此之前它已經響應過編號大于N的Prepare請求。根據P1a，該 Acceptor不可能接受編號為N的提案。因此，該Acceptor可以忽略編號為N的Prepare請求。

通過這個優化，每個Acceptor只需要記住它已經批準的提案的最大編號以及它已經做出Prepare請求響應的提案的最大編號就行了

1.6 Paxos算法描述

階段一：

• (a) Proposer選擇一個提案編號N，然后向半數以上的Acceptor發送編號為N的Prepare請求。

• (b) 如果一個Acceptor收到一個編號為N的Prepare請求，且N大于該Acceptor已經響應過的所有Prepare請求的編號，那么它就會將它已經接受過的編號最大的提案（如果有的話）作為響應反饋給Proposer，同時該Acceptor承諾不再接受任何編號小于N的提案。

階段二：

• (a) 如果Proposer收到半數以上Acceptor對其發出的編號為N的Prepare請求的響應，那么它就會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編號最大的提案的value，如果響應中不包含任何提案，那么V就由Proposer自己決定。

• (b) 如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過響應，它就接受該提案。

1.7 Learner學習被選定的value

三種方式：

1.8 如何保證Paxos算法的活性

假設存在這樣一種極端情況，有兩個Proposer依次提出了一系列編號遞增的提案，導致最終陷入死循環，沒有value被選定,具體流程如下:

解決：通過選取主Proposer，并規定只有主Proposer才能提出議案。這樣一來只要主Proposer和過半的Acceptor能夠正常進行網絡通信，那么但凡主Proposer提出一個編號更高的提案，該提案終將會被批準，這樣通過選擇一個主Proposer，整套Paxos算法就能夠保持活性。

感謝各位的閱讀，以上就是“一致性算法Paxos解決了什么問題”的內容了，經過本文的學習后，相信大家對一致性算法Paxos解決了什么問題這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！