一、前言
繼續(xù)前面的學(xué)習(xí)，這篇我們來(lái)學(xué)習(xí)在分布式系統(tǒng)中最重要的一塊，一致性協(xié)議，其中就包括了大名鼎鼎的Paxos算法。
二、2PC與3PC
在分布式系統(tǒng)中，每一個(gè)機(jī)器節(jié)點(diǎn)雖然能夠明確知道自己在進(jìn)行事務(wù)操作過程中的結(jié)果是成功或是失敗，但是卻無(wú)法直接獲取到其他分布式節(jié)點(diǎn)的操作結(jié)果，因此，當(dāng)一個(gè)事務(wù)操作需要跨越多個(gè)分布式節(jié)點(diǎn)的時(shí)候，為了保持事務(wù)處理的ACID的特性，需要引入?yún)f(xié)調(diào)者的組件來(lái)統(tǒng)一調(diào)度所有分布式節(jié)點(diǎn)的執(zhí)行邏輯，而被調(diào)度的節(jié)點(diǎn)則被稱為參與者，協(xié)調(diào)者負(fù)責(zé)調(diào)度參與者的行為并最終決定這些參與者是否要把事務(wù)真正進(jìn)行提交，基于這個(gè)思想，衍生出了二階段提交和三階段提交兩種協(xié)議。
2.1 2PC
2PC為Two-Phase Commit的簡(jiǎn)寫，為二階段提交協(xié)議將事務(wù)的提交過程分成了兩個(gè)階段來(lái)進(jìn)行處理，并執(zhí)行如下流程：
階段一：提交事務(wù)請(qǐng)求
① 事務(wù)詢問，協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
② 執(zhí)行事務(wù)，各參與者節(jié)點(diǎn)執(zhí)行事務(wù)操作（已經(jīng)執(zhí)行），并將Undo和Redo信息記入事務(wù)日志中。
③ 各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)，如果參與者成功執(zhí)行了事務(wù)操作，那么就反饋給協(xié)調(diào)者Yes響應(yīng)，表示事務(wù)可以執(zhí)行；如果參與者沒有成功執(zhí)行事務(wù)，那么就反饋給協(xié)調(diào)者No響應(yīng)，表示事務(wù)不可以執(zhí)行。
第一階段近似于是協(xié)調(diào)者組織各參與者對(duì)一次事務(wù)操作的投票表態(tài)的過程，因此二階段提交協(xié)議的階段一也被稱為投票階段。
階段二：執(zhí)行事務(wù)提交
協(xié)調(diào)者會(huì)根據(jù)各參與者的反饋情況來(lái)決定最終是否可以進(jìn)行事務(wù)提交操作，正常情況包含如下兩種可能：
1. 執(zhí)行事務(wù)提交，假如協(xié)調(diào)者從所有的參與者獲得的反饋都是Yes響應(yīng)，那么就會(huì)執(zhí)行事務(wù)提交。
① 發(fā)送提交請(qǐng)求，協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出Commit請(qǐng)求。
② 事務(wù)提交，參與者接收到Commit請(qǐng)求后，會(huì)正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放在整個(gè)事務(wù)執(zhí)行期間占用的事務(wù)資源。
③ 反饋事務(wù)提交結(jié)果，參與者在完成事務(wù)提交之后，向協(xié)調(diào)者發(fā)送Ack消息。
④ 完成事務(wù)，協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)。
2. 中斷事務(wù)，假如任意一個(gè)參與者向協(xié)調(diào)者反饋了No響應(yīng)，或者在等待超時(shí)之后，協(xié)調(diào)者尚無(wú)法接收到參與者的反饋?lái)憫?yīng)，就會(huì)中斷事務(wù)。
① 發(fā)送回滾請(qǐng)求，協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出Rollback請(qǐng)求。
② 事務(wù)回滾，參與者接收到Rollback請(qǐng)求后，會(huì)利用其在階段一中記錄的Undo信息來(lái)執(zhí)行事務(wù)回滾，并在完成回滾之后釋放在整個(gè)事務(wù)執(zhí)行期間占用的資源。
③ 反饋事務(wù)回滾結(jié)果，參與者在完成事務(wù)回滾后，向協(xié)調(diào)者發(fā)送Ack消息。
④ 中斷事務(wù)，協(xié)調(diào)者接收所有參與者反饋的Ack消息后，完成事務(wù)中斷。
二階段提交協(xié)議的優(yōu)點(diǎn)：原理簡(jiǎn)單，實(shí)現(xiàn)方便。缺點(diǎn)：同步阻塞，單點(diǎn)問題，數(shù)據(jù)不一致，太過保守。
同步阻塞：在二階段提交的執(zhí)行過程中，所有參與該事務(wù)操作的邏輯都處于阻塞狀態(tài)，即當(dāng)參與者占有公共資源時(shí)，其他節(jié)點(diǎn)訪問公共資源不得不處于阻塞狀態(tài)。
單點(diǎn)問題：若協(xié)調(diào)器出現(xiàn)問題，那么整個(gè)二階段提交流程將無(wú)法運(yùn)轉(zhuǎn)，若協(xié)調(diào)者是在階段二中出現(xiàn)問題時(shí)，那么其他參與者將會(huì)一直處于鎖定事務(wù)資源的狀態(tài)中，而無(wú)法繼續(xù)完成事務(wù)操作。
數(shù)據(jù)不一致：在二階段的階段二，執(zhí)行事務(wù)提交的時(shí)候，當(dāng)協(xié)調(diào)者向所有的參與者發(fā)送Commit請(qǐng)求之后，發(fā)生了局部網(wǎng)絡(luò)異常或者是協(xié)調(diào)者在尚未發(fā)送完Commit請(qǐng)求之前自身發(fā)生了崩潰，導(dǎo)致最終只有部分參與者收到了Commit請(qǐng)求，于是會(huì)出現(xiàn)數(shù)據(jù)不一致的現(xiàn)象。
太過保守：在進(jìn)行事務(wù)提交詢問的過程中，參與者出現(xiàn)故障而導(dǎo)致協(xié)調(diào)者始終無(wú)法獲取到所有參與者的響應(yīng)信息的話，此時(shí)協(xié)調(diào)者只能依靠自身的超時(shí)機(jī)制來(lái)判斷是否需要中斷事務(wù)，這樣的策略過于保守，即沒有完善的容錯(cuò)機(jī)制，任意一個(gè)結(jié)點(diǎn)的失敗都會(huì)導(dǎo)致整個(gè)事務(wù)的失敗。
2.2 3PC
三階段提交，將二階段提交協(xié)議的提交事務(wù)請(qǐng)求過程分為CanCommit、PreCommit、doCommit三個(gè)階段組成的事務(wù)處理協(xié)議。
階段一：canCommit
① 事務(wù)詢問，協(xié)調(diào)者向所有的參與者發(fā)送一個(gè)包含事務(wù)內(nèi)容的canCommit請(qǐng)求，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
② 各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)，參與者在接收到來(lái)自協(xié)調(diào)者的canCommit請(qǐng)求后，正常情況下，如果自身認(rèn)為可以順利執(zhí)行事務(wù)，則反饋Yes響應(yīng)，并進(jìn)入預(yù)備狀態(tài)，否則反饋No響應(yīng)。
階段二：preCommit
該階段會(huì)根據(jù)反饋情況決定是否可以進(jìn)行事務(wù)preCommit操作，正常情況下，包含如下兩種可能：
執(zhí)行事務(wù)預(yù)提交，假如所有參與反饋的都是Yes，那么就會(huì)執(zhí)行事務(wù)預(yù)提交。
① 發(fā)送預(yù)提交請(qǐng)求，協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出preCommit請(qǐng)求，并進(jìn)入prepared階段。
② 事務(wù)預(yù)提交，參與者接收到preCommit請(qǐng)求后，會(huì)執(zhí)行事務(wù)操作，并將Undo和Redo信息記錄到事務(wù)日志中。
③ 各參與者向協(xié)調(diào)者反饋事務(wù)執(zhí)行的響應(yīng)，若參與者成功執(zhí)行了事務(wù)操作，那么反饋Ack，同時(shí)等待最終的指令：提交（commit）或終止（abort）。
中斷事務(wù)，若任一參與反饋了No響應(yīng)，或者在等待超時(shí)后，協(xié)調(diào)者尚無(wú)法接收到所有參與者反饋，則中斷事務(wù)。
① 發(fā)送中斷請(qǐng)求，協(xié)調(diào)者向所有參與者發(fā)出abort請(qǐng)求。
② 中斷事務(wù)，無(wú)論是收到來(lái)自協(xié)調(diào)者的abort請(qǐng)求或者等待協(xié)調(diào)者請(qǐng)求過程中超時(shí)，參與者都會(huì)中斷事務(wù)。
階段三：doCommit
該階段會(huì)進(jìn)行真正的事務(wù)提交，也會(huì)存在如下情況。
1. 執(zhí)行提交
① 發(fā)送提交請(qǐng)求，進(jìn)入這一階段，若協(xié)調(diào)者處于正常工作狀態(tài)，并且他接收到了來(lái)自所有參與者的Ack響應(yīng)，那么他將從預(yù)提交狀態(tài)轉(zhuǎn)化為提交狀態(tài)，并向所有的參與者發(fā)送doCommit請(qǐng)求。
② 事務(wù)提交，參與者接收到doCommit請(qǐng)求后，會(huì)正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放整個(gè)事務(wù)執(zhí)行過程中占用的事務(wù)資源。
③ 反饋事務(wù)提交結(jié)果，參與者在完成事務(wù)提交后，向協(xié)調(diào)者發(fā)送Ack響應(yīng)。
④ 完成事務(wù)，協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)。
2. 中斷事務(wù)
① 發(fā)送中斷請(qǐng)求，協(xié)調(diào)者向所有的參與者節(jié)點(diǎn)發(fā)送abort請(qǐng)求。
② 事務(wù)回滾，參與者收到abort請(qǐng)求后，會(huì)根據(jù)記錄的Undo信息來(lái)執(zhí)行事務(wù)回滾，并在完成回滾之后釋放整個(gè)事務(wù)執(zhí)行期間占用的資源。
③ 反饋事務(wù)回滾結(jié)果，參與者在完成事務(wù)回滾后，向協(xié)調(diào)者發(fā)送Ack消息。
④ 中斷事務(wù)，協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，中斷事務(wù)。
三階段提交協(xié)議降低了參與者的阻塞范圍，能夠在發(fā)生單點(diǎn)故障后繼續(xù)達(dá)成一致。但是其可能還是會(huì)發(fā)生數(shù)據(jù)不一致問題。
三、Paxos算法
Paxos算法是一種基于消息傳遞且具有高度容錯(cuò)特性的一致性算法，其需要解決的問題就是如何在一個(gè)可能發(fā)生異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致，并且保證不論發(fā)生以上任何異常，都不會(huì)破壞整個(gè)系統(tǒng)的一致性。
和2PC類似，Paxos先把節(jié)點(diǎn)分成兩類，發(fā)起提議(proposal)的一方為proposer，參與決議的一方為acceptor。
在沒有失敗和消息丟失的情況下，假如只有一個(gè)提議被提出的情況，如何確定一個(gè)提議，做到如下就可以保證
P1:一個(gè)acceptor必須接受它收到的第一個(gè)提議。
P1會(huì)引入一個(gè)問題，若果多個(gè)提議被不同的proposer同時(shí)提出，這可能會(huì)導(dǎo)致雖然每個(gè)acceptor都批準(zhǔn)了它收到的第一個(gè)提議，但是沒有一個(gè)提議是由多數(shù)acceptor都接受的，因此無(wú)法確定一個(gè)提議。
上圖無(wú)法確定一個(gè)提議。即使只有兩個(gè)提議被提出，如果每個(gè)提議都被差不多一半的acceptor批準(zhǔn)了，此時(shí)也可能無(wú)法確定哪個(gè)提議，如下圖所示
如上圖所示，若acceptor5出現(xiàn)故障，則無(wú)法確定哪個(gè)提議。
在P1的基礎(chǔ)上，增加如下條件：
a. proposer發(fā)起的每項(xiàng)提議分別用一個(gè)ID標(biāo)識(shí)，提議的組成因此變?yōu)?ID, value)
b. 若確定一個(gè)提議，需要由半數(shù)以上的acceptor接受，當(dāng)某個(gè)提議被半數(shù)以上的acceptor接受后，我們就認(rèn)為該提議就被確定了。
我們約定后面發(fā)起的提議的ID比前面提議的ID大，并假設(shè)可以有多項(xiàng)提議被確定，為做到確定并只確定一個(gè)值acceptor要做到以下這點(diǎn)：
P2：如果一項(xiàng)值為v的提議被確定，那么后續(xù)只確定值為v的提議。
由于一項(xiàng)提議被確定(chosen)前必須先被多數(shù)派acceptor接受(accepted)，為實(shí)現(xiàn)P2，實(shí)質(zhì)上acceptor需要做到：
P2a：如果一項(xiàng)值為v的提議被確定，那么acceptor后續(xù)只接受值為v的提議。
如上圖所示，在acceptor1沒有收到任何提議的情況下，其他4個(gè)acceptor已經(jīng)批準(zhǔn)了來(lái)自proposer2的提議[M0,V1]，而此時(shí)，proposer1產(chǎn)生了一個(gè)具有其他value值的，編號(hào)更高的提議[M1,V2]，并發(fā)送給了acceptor1，根據(jù)P1，就需要接受該提議，但是這與P2a矛盾，因此如果要同時(shí)滿足P1和P2a，需要進(jìn)入如下強(qiáng)化
P2b：如果一項(xiàng)值為v的提議被確定，那么proposer后續(xù)只發(fā)起值為v的提議。
P2b約束的是提議被確定(chosen)后proposer的行為，我們更關(guān)心提議被確定前proposer應(yīng)該怎么做。
P2c：對(duì)于提議(n,v)，acceptor的多數(shù)派S中，如果存在acceptor最近一次(即ID值最大)接受的提議的值為v'，那么要求v = v'；否則v可為任意值。
3.1 proposer生成提議
在proposer產(chǎn)生一個(gè)編號(hào)為Mn的提議時(shí)，必須要知道當(dāng)前某一個(gè)將要或已經(jīng)被半數(shù)以上acceptor接受的編號(hào)小于Mn但為最大編號(hào)的提議，并且，proposer會(huì)要求所有的acceptor都不要再接受任何編號(hào)小于Mn的提議，這也就是如下提議生成算法。
1. proposer選擇一個(gè)新的提議編號(hào)為Mn，然后向某個(gè)acceptor集合的成員發(fā)送請(qǐng)求，要求該集合中的acceptor做出如下回應(yīng)。
① 向proposer承諾，保證不再接受任何編號(hào)小于Mn的提議。
② 如果acceptor已經(jīng)接受過任何提議，那么其就向proposer反饋當(dāng)前該acceptor已經(jīng)接受的編號(hào)小于Mn但為最大編號(hào)的那個(gè)提議的值。
我們將請(qǐng)求稱為編號(hào)Mn的提議的Prepare請(qǐng)求。
2. 如果proposer收到了來(lái)自半數(shù)以上的acceptor的響應(yīng)結(jié)果，那么它就可以產(chǎn)生編號(hào)為Mn、Value值為Vn的提議，這里的Vn是所有響應(yīng)中編號(hào)最大的提議Value的值，當(dāng)然，如果半數(shù)以上的acceptor都沒有接受過任何提議，即響應(yīng)中不包含任何提議，那么此時(shí)Vn值就可以由proposer任意選擇。
在確定了proposer的提議后，proposer就會(huì)將該提議再次發(fā)送給某個(gè)acceptor集合，并期望獲得它們的接受，此請(qǐng)求稱為accept請(qǐng)求，此時(shí)接受accept請(qǐng)求的acceptor集合不一定是之前響應(yīng)prepare請(qǐng)求的acceptor集合。
3.2 acceptor接受提議
一個(gè)acceptor可能會(huì)收到來(lái)自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)大于Mn的prepare請(qǐng)求，那么它就可以接受這個(gè)編號(hào)為Mn的提議。
3.3 算法描述
階段一：
① proposer選擇一個(gè)提議編號(hào)Mn，然后向acceptor的某個(gè)超過半數(shù)的子集成員發(fā)送編號(hào)為Mn的prepare請(qǐng)求。
② 如果一個(gè)acceptor收到編號(hào)為Mn的prepare請(qǐng)求，且編號(hào)Mn大于該acceptor已經(jīng)響應(yīng)的所有prepare請(qǐng)求的編號(hào)，那么它就會(huì)將它已經(jīng)接受過的最大編號(hào)的提議作為響應(yīng)反饋給proposer，同時(shí)該acceptor承諾不會(huì)再接受任何編號(hào)小于Mn的提議。
階段二：
① 如果proposer收到來(lái)自半數(shù)以上的acceptor對(duì)于其發(fā)出的編號(hào)為Mn的prepare請(qǐng)求響應(yīng)，那么它就會(huì)發(fā)送一個(gè)針對(duì)[Mn,Vn]提議的accept請(qǐng)求給acceptor，注意，Vn的值就是收到的響應(yīng)中編號(hào)最大的提議的值，如果響應(yīng)中不包含任何提議，那么它就是任意值。
② 如果acceptor收到這個(gè)針對(duì)[Mn,Vn]提議的accept請(qǐng)求，只要該accept尚未對(duì)編號(hào)大于Mn的prepare請(qǐng)求作出響應(yīng)，它就可以接受這個(gè)提議。
3.4 提議的獲取
使learner獲取提議，有如下方案
① 一旦acceptor接受了一個(gè)提議，就將該提議發(fā)送給所有的learner，通信開銷很大。
② 讓所有的acceptor將它們對(duì)提議的接受情況，統(tǒng)一發(fā)送給一個(gè)特定的learner（主learner），當(dāng)該learner被通知一個(gè)提議已經(jīng)被確定時(shí)，它就負(fù)責(zé)通知其他的learner。主learner可能會(huì)出現(xiàn)單點(diǎn)故障。
③ 將主learner范圍擴(kuò)大至一個(gè)特定的learner集合，該集合中的每個(gè)learner都可以在一個(gè)提議被選定后通知所有其他的learner，集合learner越多，越可靠，但是通信開銷越大。
3.5 選取主proposer保證算法的活性
假設(shè)存在如下的極端情況，有兩個(gè)proposer依次提出了一系列編號(hào)遞增的提議，但是最終都無(wú)法被確定，具體流程如下：
proposer1提出了編號(hào)為M1的提議，然后完成了上述的第一階段，與此同時(shí)，proposer2提出了編號(hào)為M2的提議，同樣完成了第一階段，于是acceptor承諾不再接受編號(hào)小于M2的提議，因此，當(dāng)proposer1進(jìn)入階段二時(shí)，其發(fā)出的accept請(qǐng)求會(huì)被acceptor忽略，于是proposer1又進(jìn)入第一階段并提出了編號(hào)為M3的提議，這導(dǎo)致proposer2的accept請(qǐng)求被忽略，一次類推，提議的確定過程將陷入死循環(huán)。
為了保證Paxos算法的活性，就必須選擇一個(gè)主proposer，并規(guī)定只有主proposer才能提出提議。
四、總結(jié)
本篇分析了一致性協(xié)議，并且從理論上著重分析了Paxos算法，理解了其含義，也謝謝各位園友的觀看~
參考鏈接：
http://www.cnblogs.com/bangerlee/p/5655754.html
http://flychao88.iteye.com/blog/2262326
http://www.tudou.com/programs/view/e8zM8dAL6hM/