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