為了解決分布式系統(tǒng)的一致性問題刽酱，在長期的探索研究過程中，涌現(xiàn)出了一大批經(jīng)典的一致性協(xié)議和算法瞧捌，其中最著名的就是二階段提交協(xié)議棵里、三階段提交協(xié)議和Paxos算法。
2PC與3PC
在分布式系統(tǒng)中姐呐，每一個機器節(jié)點雖然都能夠明確地知道自己在進行事務(wù)操作過程中的結(jié)果是成功或失敗殿怜，但卻無法直接獲取到其他分布式節(jié)點的操作結(jié)果。因此曙砂，當一個事務(wù)操作需要跨越多個分布式節(jié)點的時候头谜，為了保持事務(wù)處理的ACID特性，就需要引入一個稱為”協(xié)調(diào)者“的組件來統(tǒng)一調(diào)度所有分布式節(jié)點的執(zhí)行邏輯鸠澈，這些被調(diào)度的分布式節(jié)點則被稱為“參與者”柱告。協(xié)調(diào)者負責調(diào)度參與者的行為，并最終決定這些參與者是否要把事務(wù)真正進行提交笑陈〖识龋基于這個思想，衍生出了二階段提交和三階段提交兩種協(xié)議涵妥。
2PC
2PC乖菱，是Two-Phase Commit的縮寫，即二階段提交，是計算機網(wǎng)絡(luò)尤其是在數(shù)據(jù)庫領(lǐng)域內(nèi)窒所，為了使基于分布式系統(tǒng)架構(gòu)下的所有節(jié)點在進行事務(wù)處理過程中能夠保持原子性和一致性而設(shè)計的一種算法娜氏。通常，二階段提交協(xié)議也被認為是一種強一致性協(xié)議墩新，用來保證分布式系統(tǒng)數(shù)據(jù)的一致性贸弥。
2PC執(zhí)行流程
二階段提交協(xié)議是將事務(wù)的提交過程拆分成了兩個階段來進行處理，其執(zhí)行流程如下：
階段一：提交事務(wù)請求
1海渊、事務(wù)詢問
協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容绵疲，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者響應(yīng)臣疑。
2盔憨、執(zhí)行事務(wù)
各參與者節(jié)點執(zhí)行事務(wù)操作，并將Undo和Redo信息記入事務(wù)日志中讯沈。
3郁岩、各參與者向協(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í)行如叼。
階段二：執(zhí)行事務(wù)提交
協(xié)調(diào)者會根據(jù)各參與者的反饋情況來決定最終是否可以進行事務(wù)提交操作，正常情況下穷劈，包含以下兩種可能：
執(zhí)行事務(wù)提交：假如協(xié)調(diào)者從所有的參與者獲得的反饋都是Yes響應(yīng)笼恰，那么就會執(zhí)行事務(wù)提交。
1歇终、 發(fā)送提交請求
協(xié)調(diào)者向所有參與者節(jié)點發(fā)出Commit請求社证。
2、事務(wù)提交
參與者接收到Commit請求后评凝，會正式執(zhí)行事務(wù)提交操作追葡，并在完成提交之后釋放在整個事務(wù)執(zhí)行期間占用的事務(wù)資源。
3肥哎、 反饋事務(wù)提交結(jié)果
參與者在完成事務(wù)提交之后辽俗，向協(xié)調(diào)者發(fā)送Ack消息疾渣。
4篡诽、完成事務(wù)
協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)榴捡。
中斷事務(wù)：假如任何一個參與者向協(xié)調(diào)者反饋了No響應(yīng)杈女，或者在等待超時之后，協(xié)調(diào)者尚無法接收到所有參與者的反饋響應(yīng)，那么就會中斷事務(wù)达椰。
1翰蠢、發(fā)送回滾請求
協(xié)調(diào)者向所有參與者節(jié)點發(fā)出Rollback請求。
2啰劲、事務(wù)回滾
參與者接收到Rollback請求后梁沧，會利用其在階段一中記錄的Undo信息來執(zhí)行事務(wù)回滾操作，并在完成回滾之后釋放在整個事務(wù)執(zhí)行期間占用的資源蝇裤。
3廷支、反饋事務(wù)回滾結(jié)果
參與者在完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送Ack消息栓辜。
4恋拍、中斷事務(wù)
協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)中斷藕甩。
簡單地講施敢，二階段提交將一個事務(wù)的處理過程分為了投票和執(zhí)行兩個階段，其核心是對每個事務(wù)都采用先嘗試后提交的處理方式狭莱，因此也可以將二階段提交看作一個強一致性的算法僵娃。
2PC存在的問題
1、同步阻塞
在執(zhí)行過程中腋妙，所有參與該事務(wù)操作的邏輯都處理于阻塞狀態(tài)悯许。即節(jié)點之間在等待對方的相應(yīng)消息時，它將什么也做不了辉阶。特別是先壕，當一個節(jié)點在已經(jīng)占有了某項資源的情況下，為了等待其他節(jié)點的響應(yīng)消息而陷入阻塞狀態(tài)時谆甜，當?shù)谌齻€節(jié)點嘗試訪問該節(jié)點占有的資源時垃僚，這個節(jié)點也將連帶陷入阻塞狀態(tài)。
2规辱、 單點問題
一旦協(xié)調(diào)者出現(xiàn)問題谆棺，那么整個二階段提交流程將無法運轉(zhuǎn)，更為嚴重的是罕袋，如果協(xié)調(diào)者是在階段二中出現(xiàn)問題的話改淑，那么其他參與者將會一直處于鎖定事務(wù)資源的狀態(tài)中，而無法繼續(xù)完成事務(wù)操作浴讯。
3朵夏、 數(shù)據(jù)不一致
當協(xié)調(diào)者向所有的參與者發(fā)送Commit請求之后發(fā)生了局部網(wǎng)絡(luò)異常或者是協(xié)調(diào)者在尚未發(fā)送完Commit請求之前自身發(fā)生了崩貴榆纽，導(dǎo)致最終只有部分參與者收到了Commit請求仰猖，于是整個分布式系統(tǒng)便出現(xiàn)了數(shù)據(jù)不一致性現(xiàn)象捏肢。
3、太過保守
二階段提交沒有設(shè)計較為完善的容錯機制饥侵，任意一個節(jié)點的失敗都會導(dǎo)致整個事務(wù)的失敗鸵赫。
3PC
3PC，是Three-Phase Commit的縮寫躏升，即三階段提交辩棒，是2PC的改進版。由CanCommit膨疏、PreCommit和doCommit三個階段組成的事務(wù)處理協(xié)議盗温。
3PC執(zhí)行流程
階段一：CanCommit
1、事務(wù)詢問成肘。
協(xié)調(diào)者向所有的參與者發(fā)送一個包含事務(wù)內(nèi)容的canCommit請求卖局，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)双霍。
2砚偶、各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)。
參與者在接收到來自協(xié)調(diào)者的canCommit請求后洒闸，正常情況下染坯，如果其自身認為可以順利執(zhí)行事務(wù)，那么會反饋Yes響應(yīng)丘逸，并進入預(yù)備狀態(tài)单鹿，否則反饋No響應(yīng)。
階段二：PreCommit
協(xié)調(diào)者會根據(jù)各參與者的反饋情況來決定最終是否可以進行事務(wù)提交操作深纲，正常情況下仲锄，包含以下兩種可能：
執(zhí)行事務(wù)預(yù)提交；假如協(xié)調(diào)者從所有的參與者獲得的反饋都是Yes響應(yīng)湃鹊，那么就會執(zhí)行事務(wù)的預(yù)執(zhí)行儒喊。
1、發(fā)送預(yù)提交請求
協(xié)調(diào)者向所有參與者節(jié)點出preCommit的請求币呵，并進入prepared階段怀愧。
2、事務(wù)預(yù)提交
參與者接收到preCommit請求后余赢，會執(zhí)行事務(wù)操作芯义，并將Undo和Redo信息記錄到事務(wù)日志中。
3妻柒、各參與者向協(xié)調(diào)者反饋事務(wù)執(zhí)行的響應(yīng)
如果參與者成功執(zhí)行了事務(wù)操作扛拨，那么就會反饋給協(xié)調(diào)者Ack響應(yīng)，同時等待最終的指令：提交（commit）或中止（abort）蛤奢。
中斷事務(wù)：假如任何一個參與者向協(xié)調(diào)者反饋了No響應(yīng)鬼癣，或者在等待超時之后陶贼，協(xié)調(diào)者尚無法接收到所有者的反饋響應(yīng)啤贩，那么就會中斷事務(wù)待秃。。
1痹屹、發(fā)送中斷請求
協(xié)調(diào)者向所有參與者節(jié)點發(fā)生abort請求章郁。
2、中斷事務(wù)
無論是收到來自協(xié)調(diào)者的abort請求志衍，或者是在等待協(xié)調(diào)者請求過程中出現(xiàn)超時暖庄，參與者都會中斷事務(wù)。
階段三：doCommit
該階段將進行真正的事務(wù)提交楼肪，會存在以下兩種可能的情況培廓。
執(zhí)行提交
1、發(fā)送提交請求
進入這一階段春叫，假如協(xié)調(diào)者處于正常狀態(tài)肩钠，并且它接收到了來自所有參與者的Ack響應(yīng)，那么它將從“預(yù)提交”狀態(tài)轉(zhuǎn)換到“提交”狀態(tài)暂殖，并向所有參與者發(fā)送doCommit請求价匠。
2、事務(wù)提交
參與者接收到doCommit請求后呛每，會正式執(zhí)行事務(wù)提交操作踩窖，并在完成提交之后釋放在整個事務(wù)執(zhí)行期間占用的事務(wù)資源。
3晨横、反饋事務(wù)提交結(jié)果
參與者在完成事務(wù)提交之后洋腮，向協(xié)調(diào)者發(fā)送Ack消息。
4手形、完成事務(wù)
協(xié)調(diào)者接收到所有參與者反饋的Ack消息后徐矩，完成事務(wù)。
中斷事務(wù)
進入這一階段叁幢，假設(shè)協(xié)調(diào)者處于正常工作狀態(tài)滤灯，并且有任意一個參與者向協(xié)調(diào)者反饋了No響應(yīng)，或者在等待超時之后曼玩，協(xié)調(diào)者尚無法接收到所有參與者的反饋響應(yīng)鳞骤。
1、發(fā)送中斷請求
協(xié)調(diào)者向所有的參與者節(jié)點發(fā)送abort請求黍判。
2豫尽、事務(wù)回滾
參與者接收到abort請求后，會利用其在階段二中記錄的Undo信息來執(zhí)行事務(wù)回滾操作顷帖，并在完成回滾之后釋放在整個事務(wù)執(zhí)行期間占用的資源美旧。
3渤滞、反饋事務(wù)回滾結(jié)果
參與者在完成事務(wù)會滾之后，向協(xié)調(diào)者發(fā)送Ack消息榴嗅。
4妄呕、中斷事務(wù)
協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，中斷事務(wù)嗽测。
在doCommit階段绪励，如果參與者無法及時接收到來自協(xié)調(diào)者的doCommit或者abort請求時，在等待超時之后唠粥，會繼續(xù)進行事務(wù)的提交疏魏。即當進入第三階段時，由于網(wǎng)絡(luò)超時等原因晤愧，雖然參與者沒有收到協(xié)調(diào)者的doCommit或者abort請求大莫，但事務(wù)仍然會提交。
3PC存在的問題
三階段提交協(xié)議與兩階段提交協(xié)議有兩個主要的不同：
增加了一個詢問階段官份，詢問階段可以確保盡可能早的發(fā)現(xiàn)無法執(zhí)行操作而需要中止的行為只厘，但是它并不能發(fā)現(xiàn)所有的這種行為，只會減少這種情況的發(fā)生贯吓。
在準備階段以后懈凹，協(xié)調(diào)者和參與者執(zhí)行的任務(wù)中都增加了超時，一旦超時悄谐，協(xié)調(diào)者和參與者都繼續(xù)提交事務(wù)介评，默認為成功，這也是根據(jù)概率統(tǒng)計上超時后默認成功的正確性最大爬舰。
三階段提交協(xié)議在去除阻塞的同時也引入了新的問題们陆，那就是在參與者接收到preCommit消息后，如果網(wǎng)絡(luò)出現(xiàn)分區(qū)情屹，此時協(xié)調(diào)者所在的節(jié)點和參與者無法進行正常的網(wǎng)絡(luò)通信坪仇，在這種情況下，該參與者依然會進行事務(wù)的提交垃你，這必然出現(xiàn)數(shù)據(jù)的不一致性椅文。
Paxos算法
Paxos算法是一種基于消息傳遞且具有高度容錯特性的一致性算法，是目前公認的解決分布式一致性問題最有效的算法之一惜颇。
問題描述
在古希臘的有一個叫做Paxos的小島皆刺，島上采用會議的形式來通過法令，議會中的議員通過信使進行消息的傳遞凌摄。值得注意的是羡蛾，議員和信使都是兼職的，他們隨時有可能會離開議會廳锨亏，并且信使可能會重復(fù)的傳遞信息痴怨，也可能一去不復(fù)返忙干。因此，議會協(xié)議要保證在這個情況下法令仍然能夠正確的產(chǎn)生浪藻，并且不會出現(xiàn)沖突捐迫。
首先將議員的角色分為Proposer，Acceptor珠移，和Learner（允許身兼數(shù)職）弓乙。Proposer提出提案末融，提案信息包括提案編號和提議的value钧惧；Acceptor收到提案后可以接受（accept）提案，如果提案獲得多數(shù)Acceptors的接受勾习，則稱該提案被批準（chosen）浓瞪；Learner只能“學習”被批準的提案。劃分角色后巧婶，就可以更精確的定義問題：
決議（value）只有在被Proposers提出后才能被批準（未經(jīng)批準的決議稱為“提案”（proposal）乾颁；
在一次Paxos算法的執(zhí)行實例中，只批準（chosen）一個value艺栈；
learners只能獲得被批準（chosen）的value英岭。
由上面的三個語義可演化為下面幾個約束：
P1：一個Acceptor必須接受（accept）第一次收到的提案。
P2：一旦一個具有value v的提案被批準（chosen）湿右，那么之后批準（chosen）的提案必須具有value v诅妹。
P2a：一旦一個具有value v的提案被批準（chosen），那么之后任何Acceptor再次接受（accept）的提案必須具有value v毅人。
P2b：一旦一個具有value v的提案被批準（chosen）吭狡，那么以后任何Proposer提出的提案必須具有value v。
P2c：如果一個編號為n的提案具有value v丈莺，那么存在一個多數(shù)派划煮，要么他們中所有人都沒有接受（accept）編號小于n的任何提案，要么他們已經(jīng)接受（accept）的所有編號小于n的提案中編號最大的那個提案具有value v缔俄。
P1a：當且僅當Acceptor沒有回應(yīng)過編號大于n的prepare請求時弛秋，Acceptor接受（accept）編號為n的提案。
Paxos算法內(nèi)容
決議的提出與批準
階段一（決議提出）
1俐载、Proposer選擇一個提案編號M蟹略，然后向Acceptors的某個超過半數(shù)的子集成員發(fā)送編號為M的prepare請求。
2瞎疼、如果一個Acceptor接收到一個編號為M的pepare請求科乎，且編號M大于該Acceptor已經(jīng)響應(yīng)的所有prepare請求的編號，那么它就會將它已經(jīng)批準過的最大編號的提案作為響應(yīng)反饋給Proposer贼急，同時該Acceptor會承諾不會再批準任何編號小于M的提案茅茂。
階段二（批準階段）
1捏萍、如果Proposer收到來自半數(shù)以上的Acceptor對其發(fā)出的編號為M的prepare請求的響應(yīng)，那么它就會發(fā)送一個針對[M空闲，V]提案的accept請求給Acceptor令杈。注意，V的值就是收到響應(yīng)中編號最大的提案的值碴倾，如果響應(yīng)中不包含任何提案逗噩，那么它就是任意值。
2跌榔、如果Acceptor收到這個針對[M,V]提案的Accept請求异雁，只要該Acceptor尚未對編號大于M的prepare請求做出響應(yīng)，它就可以通過這個提案僧须。
提案的獲取
如何讓Learner獲取提案纲刀，大體可以有以下幾種方案：
-
方案一
Learner獲取一個已經(jīng)被選定的提案的前提是，該提案已經(jīng)被半數(shù)以上的Acceptor批準了担平。因此示绊，最簡單的做法就是一旦Acceptor批準了一個提案，就將該提案發(fā)送給所有的Learner暂论。這種做法雖然可以讓Learner盡快地獲取被選定的提案面褐，但是卻需要讓每個Acceptor與所有Learner逐個進行一次通信，通信的次數(shù)至少為二者個數(shù)的乘積取胎。
-
方案二
我們可以讓所有的Acceptor將它們對提案的批準情況展哭，統(tǒng)一發(fā)送給一個特定的Learner（這樣的Learner稱為“主Learner”），假定Learner之間可以通過消息通信來互相感知提案的選定情況扼菠。當主Learner被通知一個提案被選定時摄杂，它會負責通知其他的Learner。
方案二雖然需要多一個步驟才能將提案通知到所有的Learner循榆，但其通信次數(shù)卻大大減少了析恢，通常只是Acceptor和Learner的個數(shù)總和。但同時秧饮，該方案引入了一個新的不穩(wěn)定因素映挂；主Learner隨時可能出現(xiàn)故障。
-
方案三
將主Learner的范圍擴大盗尸，即Acceptor可以將批準的提案發(fā)送給一個特定的Learner集合柑船，該集合中的每個Learner都可以在一個提案被選定后通知所有其他的Learner。這個Learner集合中的Learner個數(shù)越多泼各，可靠性就越好鞍时，但同時網(wǎng)絡(luò)通信的復(fù)雜度也就越高。
通過選取主Proposer保證算法的活性
假設(shè)存在這樣一種極端情況，有兩個Proposer依次提出了一系列編號遞增的議案逆巍，但是最終都無法被選定及塘，具體流程如下：
Proposer P1提出了一個編號為M1的提案，并完成了上述階段一的流程锐极。但與此同時笙僚，另外一個Proposer P2提出了一個編號為M2（M2>M1）的提案，同樣也完成了階段一的流程灵再，于是Acceptor已經(jīng)承諾不再批準編號小于M2的提案了肋层。因此，當P1進入階段二的時候翎迁，其發(fā)出的accept請求將被Acceptor忽略栋猖，于是P1再次進入階段一并提出了一個編號為M3，（M3>M2）的提案鸳兽，而這又導(dǎo)致P2在第二階段的accept請求被忽略掂铐，以此類推罕拂，提案的選定過程將陷入死循環(huán)揍异。
為了保證Paxos算法流程的可持續(xù)性，以避免陷入上述提到的“死循環(huán)”爆班，就必須選擇一個主Proposer衷掷，并規(guī)定只有主Proposer才能提出議案。這樣一來柿菩，只要主Proposer和過半的Acceptor能夠正常進行網(wǎng)絡(luò)通信戚嗅，那么但凡主Proposer提出一個編號更高的提案被提出或正在接受批準，那么它會丟棄當前這個編號較小的提案枢舶，并最終能夠選出一個編號足夠大的提案懦胞。因此，如果系統(tǒng)中有足夠多的組建（包括Proposer凉泄、Acceptor和其他網(wǎng)絡(luò)通信組建）能夠正常工作躏尉，那么通過選擇一個主Proposer，整套Paxos算法流程就能夠保持活性后众。
參考資料
從Paxos到Zookeeper分布式一致性原理與實踐
