大話分布式系統(tǒng)理論進(jìn)階

1、 下篇 大話分布式系統(tǒng)理論進(jìn)階 分布式系統(tǒng)理論進(jìn)階 - Paxos分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC一文介紹了一致性、達(dá)成一致性需要面臨的各種問(wèn)題以及2PC、3PC模型，Paxos協(xié)議在節(jié)點(diǎn)宕機(jī)恢復(fù)、消息無(wú)序或丟失、網(wǎng)絡(luò)分化的場(chǎng)景下能保證決議的一致性，是被討論最廣泛的一致性協(xié)議。Paxos協(xié)議同時(shí)又以其“艱深晦澀”著稱(chēng)，下面結(jié)合Paxos Made Simple、The Part-Time Parliament兩篇論文，嘗試通過(guò)Paxos推演、學(xué)習(xí)和了解Paxos協(xié)議。Basic Paxos何為一致性問(wèn)題？簡(jiǎn)單而言，一致性問(wèn)題是在節(jié)點(diǎn)宕機(jī)、消息無(wú)序等場(chǎng)景可能出現(xiàn)的情況下，相互獨(dú)立的

2、節(jié)點(diǎn)之間如何達(dá)成決議的問(wèn)題，作為解決一致性問(wèn)題的協(xié)議，Paxos的核心是節(jié)點(diǎn)間如何確定并只確定一個(gè)值(value)。也許你會(huì)疑惑只確定一個(gè)值能起什么作用，在Paxos協(xié)議里確定并只確定一個(gè)值是確定多值的基礎(chǔ)，如何確定多值將在第二部分Multi Paxos中介紹，這部分我們聚焦在“Paxos如何確定并只確定一個(gè)值”這一問(wèn)題上。和2PC類(lèi)似，Paxos先把節(jié)點(diǎn)分成兩類(lèi)，發(fā)起提議(proposal)的一方為proposer，參與決議的一方為acceptor。假如只有一個(gè)proposer發(fā)起提議，并且節(jié)點(diǎn)不宕機(jī)、消息不丟包，那么acceptor做到以下這點(diǎn)就可以確定一個(gè)值：P1. 一個(gè)acceptor

3、接受它收到的第一項(xiàng)提議當(dāng)然上面要求的前提條件有些嚴(yán)苛，節(jié)點(diǎn)不能宕機(jī)、消息不能丟包，還只能由一個(gè)proposer發(fā)起提議。我們嘗試放寬條件，假設(shè)多個(gè)proposer可以同時(shí)發(fā)起提議，又怎樣才能做到確定并只確定一個(gè)值呢？首先proposer和acceptor需要滿(mǎn)足以下兩個(gè)條件：1. proposer發(fā)起的每項(xiàng)提議分別用一個(gè)ID標(biāo)識(shí)，提議的組成因此變?yōu)?ID, value)2.acceptor可以接受(accept)不止一項(xiàng)提議，當(dāng)多數(shù)(quorum)acceptor接受一項(xiàng)提議時(shí)該提議被確定(chosen)(注: 注意以上“接受”和“確定”的區(qū)別）我們約定后面發(fā)起的提議的ID比前面提議的ID大，

4、并假設(shè)可以有多項(xiàng)提議被確定，為做到確定并只確定一個(gè)值acceptor要做到以下這點(diǎn)：P2. 如果一項(xiàng)值為v的提議被確定，那么后續(xù)只確定值為v的提議(注: 乍看這個(gè)條件不太好理解，謹(jǐn)記目標(biāo)是“確定并只確定一個(gè)值”)由于一項(xiàng)提議被確定(chosen)前必須先被多數(shù)派acceptor接受(accepted)，為實(shí)現(xiàn)P2，實(shí)質(zhì)上acceptor需要做到：P2a. 如果一項(xiàng)值為v的提議被確定，那么acceptor后續(xù)只接受值為v的提議滿(mǎn)足P2a則P2成立 (P2a = P2)。目前在多個(gè)proposer可以同時(shí)發(fā)起提議的情況下，滿(mǎn)足P1、P2a即能做到確定并只確定一個(gè)值。如果再加上節(jié)點(diǎn)宕機(jī)恢復(fù)、消息丟包

5、的考量呢？假設(shè)acceptor c 宕機(jī)一段時(shí)間后恢復(fù)，c 宕機(jī)期間其他acceptor已經(jīng)確定了一項(xiàng)值為v的決議但c 因?yàn)殄礄C(jī)并不知曉；c 恢復(fù)后如果有proposer馬上發(fā)起一項(xiàng)值不是v的提議，由于條件P1，c 會(huì)接受該提議，這與P2a矛盾。為了避免這樣的情況出現(xiàn)，進(jìn)一步地我們對(duì)proposer作約束：P2b. 如果一項(xiàng)值為v的提議被確定，那么proposer后續(xù)只發(fā)起值為v的提議滿(mǎn)足P2b則P2a成立 (P2b =P2a = P2)。P2b約束的是提議被確定(chosen)后proposer的行為，我們更關(guān)心提議被確定前proposer應(yīng)該怎么做：P2c. 對(duì)于提議(n,v)，accep

6、tor的多數(shù)派S中，如果存在acceptor最近一次(即ID值最大)接受的提議的值為v，那么要求v = v；否則v可為任意值滿(mǎn)足P2c則P2b成立 (P2c =P2b = P2a = P2)。條件P2c是Basic Paxos的核心，光看P2c的描述可能會(huì)覺(jué)得一頭霧水，我們通過(guò)The Part-Time Parliament中的例子加深理解：假設(shè)有AE 5個(gè)acceptor，- 表示acceptor因宕機(jī)等原因缺席當(dāng)次決議，x 表示acceptor不接受提議，o 表示接受提議；多數(shù)派acceptor接受提議后提議被確定，以上表格對(duì)應(yīng)的決議過(guò)程如下：ID為2的提議最早提出，根據(jù)P2c其提議值可為

7、任意值，這里假設(shè)為aacceptor A/B/C/E 在之前的決議中沒(méi)有接受(accept)任何提議，因而ID為5的提議的值也可以為任意值，這里假設(shè)為bacceptor B/D/E，其中D曾接受ID為2的提議，根據(jù)P2c，該輪ID為14的提議的值必須與ID為2的提議的值相同，為aacceptor A/C/D，其中D曾接受ID為2的提議、C曾接受ID為5的提議，相比之下ID 5較ID 2大，根據(jù)P2c，該輪ID為27的提議的值必須與ID為5的提議的值相同，為b；該輪決議被多數(shù)派acceptor接受，因此該輪決議得以確定acceptor B/C/D，3個(gè)acceptor之前都接受過(guò)提議，相比之下C

8、、D曾接受的ID 27的ID號(hào)最大，該輪ID為29的提議的值必須與ID為27的提議的值相同，為b以上提到的各項(xiàng)約束條件可以歸納為3點(diǎn)，如果proposer/acceptor滿(mǎn)足下面3點(diǎn)，那么在少數(shù)節(jié)點(diǎn)宕機(jī)、網(wǎng)絡(luò)分化隔離的情況下，在“確定并只確定一個(gè)值”這件事情上可以保證一致性(consistency)：B1():中每一輪決議都有唯一的ID標(biāo)識(shí)B2(): 如果決議B被acceptor多數(shù)派接受，則確定決議BB3():對(duì)于中的任意提議B(n,v)，acceptor的多數(shù)派中如果存在acceptor最近一次(即ID值最大)接受的提議的值為v，那么要求v = v；否則v可為任意值(注: 希臘字母表示多

9、輪決議的集合，字母B表示一輪決議)另外為保證P2c，我們對(duì)acceptor作兩個(gè)要求：1. 記錄曾接受的ID最大的提議，因proposer需要問(wèn)詢(xún)?cè)撔畔⒁詻Q定提議值2. 在回應(yīng)提議ID為n的proposer自己曾接受過(guò)ID最大的提議時(shí)，acceptor同時(shí)保證(promise)不再接受ID小于n的提議至此，proposer/acceptor完成一輪決議可歸納為prepare和accept兩個(gè)階段。prepare階段proposer發(fā)起提議問(wèn)詢(xún)提議值、acceptor回應(yīng)問(wèn)詢(xún)并進(jìn)行promise；accept階段完成決議，圖示如下：還有一個(gè)問(wèn)題需要考量，假如proposer A發(fā)起ID為n的提議

10、，在提議未完成前proposer B又發(fā)起ID為n+1的提議，在n+1提議未完成前proposer C又發(fā)起ID為n+2的提議 如此acceptor不能完成決議、形成活鎖(livelock)，雖然這不影響一致性，但我們一般不想讓這樣的情況發(fā)生。解決的方法是從proposer中選出一個(gè)leader，提議統(tǒng)一由leader發(fā)起。最后我們?cè)僖胍粋€(gè)新的角色：learner，learner依附于acceptor，用于習(xí)得已確定的決議。以上決議過(guò)程都只要求acceptor多數(shù)派參與，而我們希望盡量所有acceptor的狀態(tài)一致。如果部分acceptor因宕機(jī)等原因未知曉已確定決議，宕機(jī)恢復(fù)后可經(jīng)本機(jī)le

11、arner采用pull的方式從其他acceptor習(xí)得。Multi Paxos通過(guò)以上步驟分布式系統(tǒng)已經(jīng)能確定一個(gè)值，“只確定一個(gè)值有什么用？這可解決不了我面臨的問(wèn)題。” 你心中可能有這樣的疑問(wèn)。其實(shí)不斷地進(jìn)行“確定一個(gè)值”的過(guò)程、再為每個(gè)過(guò)程編上序號(hào)，就能得到具有全序關(guān)系(total order)的系列值，進(jìn)而能應(yīng)用在數(shù)據(jù)庫(kù)副本存儲(chǔ)等很多場(chǎng)景。我們把單次“確定一個(gè)值”的過(guò)程稱(chēng)為實(shí)例(instance)，它由proposer/acceptor/learner組成，下圖說(shuō)明了A/B/C三機(jī)上的實(shí)例：不同序號(hào)的實(shí)例之間互相不影響，A/B/C三機(jī)輸入相同、過(guò)程實(shí)質(zhì)等同于執(zhí)行相同序列的狀態(tài)機(jī)(state machine)指令 ，因而將得到一致的結(jié)果。proposer leader在Multi Paxos中還有助于提升性能，常態(tài)下統(tǒng)一由leader發(fā)起提議，可節(jié)省prepare步驟(leader不用問(wèn)詢(xún)a