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

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

一：一致性算法Paxos

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

1.1 Paxos解決了什么問題

在常見的分布式系統(tǒng)中，總會(huì)發(fā)生諸如通信異常、節(jié)點(diǎn)故障、網(wǎng)絡(luò)分區(qū)等情況。Paxos算法需要解決的問題就是如何在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致，并且保證不論發(fā)生以上任何異常，都不會(huì)破壞整個(gè)系統(tǒng)的一致性。

注意：這里某個(gè)數(shù)據(jù)的值并不只是狹義上的某個(gè)數(shù)，它可以是一條日志，也可以是一條命令（command）。根據(jù)應(yīng)用場(chǎng)景不同，某個(gè)數(shù)據(jù)的值有不同的含義。

1.2 Paxos的相關(guān)概念

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

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

• Proposer：提案發(fā)起者，提案者提倡客戶請(qǐng)求，試圖說服Acceptor對(duì)此達(dá)成一致，并在發(fā)生沖突時(shí)充當(dāng)協(xié)調(diào)者以推動(dòng)協(xié)議向前發(fā)展

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

• Learners：最終決策的學(xué)習(xí)者，學(xué)習(xí)者充當(dāng)該協(xié)議的復(fù)制因素

1.4 Proposer生成提案規(guī)則

Proposer生成提案之前，應(yīng)該先去『學(xué)習(xí)』已經(jīng)被選定或者可能被選定的value，然后以該value作為自己提出的提案的value。如果沒有value被選定，Proposer才可以自己決定value的值。這樣才能達(dá)成一致。這個(gè)學(xué)習(xí)的階段是通過一個(gè)『Prepare請(qǐng)求』實(shí)現(xiàn)的。

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

Proposer提案生成算法：

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

我們將該請(qǐng)求稱為編號(hào)為N的Prepare請(qǐng)求。

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

我們稱該請(qǐng)求為Accept請(qǐng)求。（注意：此時(shí)接受Accept請(qǐng)求的Acceptor集合不一定是之前響應(yīng)Prepare請(qǐng)求的Acceptor集合）

1.5 Acceptor接收提案規(guī)則

一個(gè)Acceptor可能會(huì)收到來自Proposer的兩種請(qǐng)求，分別是Prepare請(qǐng)求和Accept請(qǐng)求，對(duì)這兩類請(qǐng)求作出響應(yīng)的條件分別如下：

• Prepare請(qǐng)求：Acceptor可以在任何時(shí)候響應(yīng)一個(gè)Prepare請(qǐng)求

• Accept請(qǐng)求：在不違背Accept現(xiàn)有承諾的前提下，可以任意響應(yīng)Accept請(qǐng)求

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

p1a：一個(gè)Acceptor只要尚未響應(yīng)過任何編號(hào)大于N的Prepare請(qǐng)求，那么他就可以接受這個(gè)編號(hào)為N的提案。

Acceptor算法優(yōu)化

由上面可知，如果Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求，在此之前它已經(jīng)響應(yīng)過編號(hào)大于N的Prepare請(qǐng)求。根據(jù)P1a，該 Acceptor不可能接受編號(hào)為N的提案。因此，該Acceptor可以忽略編號(hào)為N的Prepare請(qǐng)求。

通過這個(gè)優(yōu)化，每個(gè)Acceptor只需要記住它已經(jīng)批準(zhǔn)的提案的最大編號(hào)以及它已經(jīng)做出Prepare請(qǐng)求響應(yīng)的提案的最大編號(hào)就行了

1.6 Paxos算法描述

階段一：

• (a) Proposer選擇一個(gè)提案編號(hào)N，然后向半數(shù)以上的Acceptor發(fā)送編號(hào)為N的Prepare請(qǐng)求。

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

階段二：

• (a) 如果Proposer收到半數(shù)以上Acceptor對(duì)其發(fā)出的編號(hào)為N的Prepare請(qǐng)求的響應(yīng)，那么它就會(huì)發(fā)送一個(gè)針對(duì)[N,V]提案的Accept請(qǐng)求給半數(shù)以上的Acceptor。注意：V就是收到的響應(yīng)中編號(hào)最大的提案的value，如果響應(yīng)中不包含任何提案，那么V就由Proposer自己決定。

• (b) 如果Acceptor收到一個(gè)針對(duì)編號(hào)為N的提案的Accept請(qǐng)求，只要該Acceptor沒有對(duì)編號(hào)大于N的Prepare請(qǐng)求做出過響應(yīng)，它就接受該提案。

1.7 Learner學(xué)習(xí)被選定的value

三種方式：

1.8 如何保證Paxos算法的活性

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

解決：通過選取主Proposer，并規(guī)定只有主Proposer才能提出議案。這樣一來只要主Proposer和過半的Acceptor能夠正常進(jìn)行網(wǎng)絡(luò)通信，那么但凡主Proposer提出一個(gè)編號(hào)更高的提案，該提案終將會(huì)被批準(zhǔn)，這樣通過選擇一個(gè)主Proposer，整套Paxos算法就能夠保持活性。

感謝各位的閱讀，以上就是“一致性算法Paxos解決了什么問題”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)一致性算法Paxos解決了什么問題這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！