注：
這裡談論的2PC不同于事務中的2PC，而是專門為了同步和高可用改過的2PC協定
問題：
尋求一種能夠保證，在給定多台計算機，并且他們之間由網絡互相連通，中間的資料沒有拜占庭将軍問題(資料不會被僞造)的前提下，能夠做到以下兩個特性的方法：
1)資料每次成功的寫入，資料不會丢失，并且按照寫入的順序排列
2）給定安全級别，保證服務可用性，并盡可能減少機器的消耗
基礎場景：
假定有兩個人,李雷和韓梅梅，李雷讓韓梅梅去把隔壁班的電燈關掉，這時候，韓梅梅可能有以下三種回報：
1）“好了，關了”（成功）
2）“開關壞了，沒法關”（失敗）
3）（因為網絡原因，無回報）
兩階段送出
假如我有兩台機器A和B,A是Coordinator(協調者)，B是Cohorts(同伴，支援者)
A将某個事件通知給B，B會有以下幾種回報：
1.成功
2.失敗，比如硬碟滿了？不符合某些條件？為了解決這個情況，是以我們必須讓Ａ多一個步驟：準備，準備意味着如果Ｂ失敗，那麼Ａ也自然不應該繼續進行，應該将Ａ的所有已經做得修改復原，然後通知用戶端：錯誤啦。
是以，我們為了能做到能夠讓Ａ應付Ｂ失敗的這個情況，需要将同步協定設計為：
PrepareA -> CommitB -> Commit A
使用這個協定，就可以保證B就算出現了某些異常情況，資料還能夠復原
我們再看一些異常情況：
PA->CB(B機器挂掉)：在CommitB失敗，復原PrepareA
PA->CB->CA(A機器挂掉)：CommitA失敗，在A這個機器重新恢複後，因為自己的狀态是PA,是以它必須詢問B機器，你送出了沒有？如果B回答送出成功，那麼A也必須将自己的資料進行送出，以達到一緻。
其實，我們排除了一種最惡心的情況，這就是網絡上最臭名昭著的問題，無回報
無回報這個情況，在2PC中隻會在一個地方出現，因為隻有一次網絡傳輸過程：A把自己的狀态設定為prepare,然後傳遞消息給B機器，讓B機器做送出操作，然後B回報A結果
那麼，這無回報意味着什麼呢？
1.B成功送出
2.B失敗
3.網絡斷開
以A機器的角度來看，有兩類事情無法區分出來：
1）B機器是挂掉了呢？還是網絡斷掉了？
2）要求B做的操作，是成功了呢？還是失敗了呢？
在無回報的情況下，無法區分是成功了還是失敗了，于是最安全和保險的方式就是等…等到B給個回報，這種在可用性上基本上是0分了；A得不到B的回報，又為了保證自己的可用性，唯一的選擇就是：等待一段時間，逾時以後，認為B機器挂掉了，于是自己繼續接收新的請求，而不再嘗試同步給B。
然而，這個選擇會帶來更大的問題，左腦和右腦被分開了。我們假定A所在的機房有一組clientA,B機房有一組clientB。開始時，A是master:
一旦發生斷網：
在這種情況下,A無法給B傳遞資訊，為了可用性，隻好認為B挂掉了。允許所有clientA送出請求到自己，不再嘗試同步給B。而B與A的心跳也因為斷網而中斷，他也無法知道，A到底是挂掉了呢？還是隻是網斷了，但為了可用性，隻好也把自己設定為主機，允許所有clientB寫入資料。于是，出現了兩個master。
兩階段送出解決了什麼問題，以及存在什麼問題？
兩階段送出協定是實作分布式事務的關鍵；存在的問題是針對無回報的情況，除了“死等”,缺乏合理的解決方案。
針對“死等”問題，有人提出了三階段送出協定，增加一段來減少死等的情況。不過3PC基本上沒有人在用，因為有其他協定可以做到更多的特性的同時又解決了死等的問題。同時3PC是無法解決腦裂問題的。
針對腦裂，最簡單的解決方法是：引入第三視點，Observer.如果問到無回報時，就去詢問Observer.
3PC标準協定是canCommit/preCommit/doCommit三個階段，2PC是preCommit和doCommit兩個階段，Paxos算是比較典型的2PC,在preCommit階段voting
3PC之于2PC的差異在于多了第一次canCommit通訊，使得Coordinator和Cohorts能夠按照約定在相應階段的timeout時做出準确的操作，而避免了2PC改中coordinator在逾時發生時不知所措的窘态
統一思想，做出統一決策–解決腦裂問題->Paxos算法
思路：信使就是消息傳遞，也就是通過網絡将消息傳遞給其他人的機制；通過parliament（議會）做出決議，基于“少數服從多數”
假設有兩個機房，A機房和B機房，A機房有5台機器，B機房有3台機器，他們的網絡被實體隔離了，我們來看看有哪些選擇：
1.A，B機房獨立的都可以提供服務。
這種方式明顯是不靠譜的，會出現不可逆轉的不一緻問題。
2.A，B機房都不可以提供服務
合理的方式，但在高可用上是0分，隻保持了一緻性而已
3.讓B機房的機器服務
好吧，你真的認為剩下三台機器提供服務的安全性比5台高
4.讓A機房的機器服務
“民主并不是什麼好東西，但它是我們迄今為止所能找到的最不壞的一種”
這就是quorum産生的核心原因
Paxos
當機器變得更多的時候Observer不能隻有一個，必須有更多個Observer，但Observer多了，到底聽誰的又成了問題。這時候，我們就需要“少數服從多數”。這就是quorum模型。
我們假定有A，B，C，D，E五台機器，KV系統需要put一個資料[key=Whisper,val=3306]到我們這5台機器上，要保證隻要回報為真，任意兩台機器挂掉都不會丢失資料，并且保證高可用。怎麼做：
1.首先，用戶端随機選擇一個結點，進行寫入送出，這裡我們随機選擇了C這個結點，這時候C結點就是這次提議的發起人(也叫proposer,在老的2pc協定裡也叫coodinator),當C收到這個提議的時候，C首先要做的事情是根據目前結點的最新全局global id,做一次自增操作。我們假定，在當時的全局global id為0，是以，這個議案就被對應了一個編号：1–>[key=Whisper,val=3306].
這裡有兩個我們經常犯的錯誤：
1)global id問題，在老的論文裡，Lamport沒有描述這個自增id是怎麼生成的。從我目前能夠看到的所有實作裡面，基本上就是選擇哪一台機器，就是以那台機器目前所保持的全局id(可能不是全局來看的最高值)，然後做一下自增就行了。我們後面會看到協定如何保證非全局最高值的globalID提議會被拒絕以至于不能形成決議。
2)golbal id隻是對paxos協定有意義，對于資料庫，其實隻需要關心KeyValue即可，golbal id的作用隻是告訴你這些資料的順序是按照global id來排列的
回到文中，我們已經将這個新的議案标記了從C這台機器看起來最大的global id:1–>[key=Whisper,val=3306].然後，它會嘗試将這個資訊發送給其餘的A，B，D，E這幾台機器。
在這個過程中，Paxos将A，B，D，E叫做accepter(老的協定叫做參與者，cohorts),他們的行為模式如下：
如果A，B，D，E這幾台機器的globalID小于C給出的決議的GID(1–>[key=Whisper,val=3306]),那麼就告訴C，這個決議被準許了。而如果A,B,D,E這幾台機器的globalID大于或等于C給出決議的GID，那麼就告訴C這個決議不能被準許
我們假定A，B兩台機器當時的Max(GID)是0，而D，E的Max(GID)是1。那麼，A，B兩台機器會回報給C說協定被接受，這時候，C的議案有3票：A，B，C（算自己的）。是以這個議案有三票，5台機器的半數是3，超過法定人數，于是決議就被同意了。
我們保持這個上下文，來看看D，E這邊的情況。首先，要思考的問題是，為什麼D，E的Max(GID)是1呢？
其實很簡單，D可能在C發起決議的同時，也發起了一個決議，我們假定這個決議是由D發起的，決議是1–>[key=taobao,val=1234].既然D,E的Max(GID)是1，那麼意味着E已經告知D，它同意了D的決議，但D馬上會發現，A，B，C裡面的任意一個都傳回了不同意，它的議案隻拿到兩票，沒有通過。
這時候C的決議已經被多數派接受，是以它需要告訴所有人，我的議案1–>[key=Whisper,val=3306]已經被接受，你們去學習吧
這時候還有一個問題是需要被考慮的，如果在C已經達到法定人數，在告知所有人接受之前，C挂了，應該怎麼辦？
為了解決這個問題，需要要求所有的accepter在接受某個人提出的議案後，額外的記錄一個資訊：目前accepter接受了哪個提議者的議案。
為什麼要記錄這個？很簡單，我們看一下上面出現這個情況時候的判斷标準
A機器：角色accepter,準許的議案1–>[key=Whisper,val=3306],提議人：C
B機器：角色accepter,準許的議案1–>[key=Whisper,val=3306],提議人：C
C機器：角色proposer,挂了
D機器：角色accepter,準許的議案1–>[key=taobao,val=1234],提議人：自己
E機器：角色proposer,“提議的”議案1–>[key=taobao,val=1234],提議人：D
因為有了提議人這個記錄，是以在逾時後很容易可以判斷，議案1–>[key=Whisper,val=3306]是取得了多數派的議案，因為雖然D，E兩台機器也是可以達成一緻的議案的，但因為有個人本身是提議者，是以可以算出這個議案是少數派。
在這之後，提議者還需要做一件事，就是告訴D，E，被決定的決議已經是什麼了。這個過程在文章中叫做Learn。D，E被稱為Learner。
這個過程是變數最大的過程，有不少方法可以減少網絡傳輸的量
下面，我們讨論下載下傳2pc/3pc中面臨的問題，在paxos裡面是怎麼被解決的
2pc最主要的問題是死等、腦裂，兩個問題。
對于腦裂，paxos給出的解決方案是，少數服從多數，決議發給所有人，盡一切努力送達，總有一個決議會得到多數派肯定，是以，不在糾結于某一台機器的回報，網絡無響應？沒有就沒有吧，其他人有回報就行了。
是以，如果出現機房隔離的情況，比如A，B，C在機房1，D，E在機房2，機房1和機房2實體隔離了，那麼你會發現，D，E永遠也不可能提出能夠得到多數派同意的提案。
是以，少數派的利益被犧牲了，換來了多數派的可用性。這是唯一能夠既保證資料的一緻性，又盡可能提高可用性的唯一方法。
而對于死等問題，解決方法也是一樣的，對于某一台機器的無響應，完全不用去管，其他機器有響應就可以了，隻要能拿到多數。
以上是沈詢大哥以多台機器資料同步為背景，提出2PC改和3PC改，以及它們存在問題，最後引出Paxos算法和quorum模型
那麼下面談談我對Paxos算法和quorum模型的了解
階段一：系統隻有一個資料結點，不存在資料一緻性的問題，但在可用性和可靠性上存在較大的問題，先說可用性，随着系統使用者規模（或者說是TPS）的升高，很快就會達到系統瓶頸，延遲增大，響應性急速下降，最終導緻系統可用性下降，或不可用。再說可靠性，很明顯，資料結點存在單點問題
階段二：系統有兩個資料結點（master-slave模式），提升了系統的可靠性，可以做讀寫分離，提升系統的可用性，但随着寫壓力的上升，master很快就會達到瓶頸
階段三：系統中多個資料結點，沒有主次之分，平等關系，這樣的分布式系統設計是scalable的，大大的提升了系統的可用性和可靠性，但多個結點資料的一緻性問題暴露了出來；但如果要求系統結點的強一緻性，那麼在資料的同步過程中，系統的可用性就會降低（CAP理論）
而Paxos算法就是為了在分布式系統中的系統可用性和一緻性之間尋求一種平衡
Paxos算法是一種基于消息傳遞的一緻性算法（一緻性算法有兩種實作方式：通過基于鎖的共享記憶體和消息傳遞），用來解決在分布式系統中的資料一緻性問題。
Paxos算法的思想是基于Quorum（法定人數）機制，少數服從多數，對于少數結點的網絡異常、當機、資料不一緻，it doesn’t matter,消息盡一切努力送達，資料達到最終一緻性
實際案例：
分布式系統中資料存儲采用多份資料副本來提供可靠性。當使用者送出了一次修改後，那麼原先儲存的副本顯然就和目前資料不一緻了。解決這個問題最簡單的方案是read only after write all，就是在使用者送出修改操作後，系統确儲存儲的資料所有副本全部完成更新後，再告訴使用者操作成功；而讀取資料的時候隻需要查詢其中一個副本資料傳回給使用者就行了。在很少對存儲的資料進行修改的情況下，這種方案很好。但遇到經常需要修改的情形，寫操作時延遲就很明顯，系統可用性下降。
那麼有沒有一種方案能夠不需要更新完全部資料，但又保證傳回給使用者的是有效的資料的方案呢？Quorum機制（鴿籠原理）便是其中一種選擇，其實質是将write all負載均衡到read only上。
假設共有N個資料副本，其中K個已經更新，N-K個未更新，那麼我們任意讀取N-K+1個資料的時候就必定至少有一個是屬于更新了的K個裡面的，也就是quorum的交集，我們隻需要比較讀取的N-K+1中版本最高的那個資料傳回給使用者就可以得到最新更新的資料了（滿足W+R>N，叢集的讀寫就是強一緻的）。
對于寫模型，我們隻需要完成K個副本的更新後，就可以告訴使用者操作完成而不需要write all了，當然告訴使用者完成操作後，系統内部還是會慢慢的把剩餘的副本更新，這對于使用者是透明的。即write上的部分負載轉移到了read身上。至于具體轉移多少負載比較合适，取決于系統的讀寫通路比。
那麼Paxos有沒有什麼值得改進的地方？有的，很簡單，你會發現，如果在一個決議提議的過程中，其他決議會被否決，否決本身意味着更多的網絡io，意味着更多的沖突，這些沖突都是需要額外的開銷的，代價很大。
為了解決類似的問題，所有才會有zookeeper對paxos協定的改進。zookeeper的協定叫zab協定
其實，這也是在我們現實生活中經常能夠發現的，如果每個議案都要經過議會的讨論和表決，那麼這個國家的決策無疑是低效的，怎麼解決這個問題呢？弄個總統就行了。zab協定就是本着這個思路來改進paxos協定的
zab協定把整個過程分為兩個部分，第一部分叫選總統，第二部分叫進行決議。
選總統的過程比較特殊，這種模式，相對的給人感覺思路來源于lamport的面包房算法，選擇的主要依據是：
1.如果有gid最大的機器，那麼它就是主機
2.如果好幾台主機的gid相同，那麼按照序号選擇最小的那個
是以，在開始的時候，給A,B,C,D,E進行編号，0,1,2,3,4.第一輪的時候，因為大家的Max(gid)都是0，是以自然而然按照第二個規則，選擇A作為主機
然後，所有人都知道A是主機以後，無論誰收到的請求，都直接轉發給A，由A機器去做後續的分發，這個分發的過程，叫進行決議。
進行決議的規則就簡單很多了，對其他機器進行3pc送出，但與3pc不同的是，因為是群發議案給所有其他機器，是以一個機器無回報對大局是沒有影響的，隻有當在一段時間以後，超過半數沒有回報，才是有問題的時候，這時候要做的事情是，重新選擇總統。
具體過程是，A會将決議precommit給B,C,D,E。然後等待，當B,C,D,E裡面的任意兩個傳回收到後，就可以進行doCommit()。否則進行doAbort()
為什麼要任意兩個？原因其實也是一樣的，為了防止腦裂，原則上隻能大于半數，因為一旦決議成立的投票數少于半數，那麼就存在另立中央的可能，兩個總統可不是鬧着玩的。
定兩個，就能夠保證，任意“兩台”機器挂掉，資料不丢，能夠做到quorum.
寫zab協定的人否認自己的協定是paxos變種，其實他們是針對一個問題的兩種解決方法：
因為他們解決的問題的領域相同
解決網絡傳輸無響應這個問題的方法也一樣：也即不在乎一城一池的得失，盡一切努力傳遞給其他人，然後用少數服從多數的方式，要求網絡隔離或自己挂掉的機器，在恢複可用以後，從其他主機那裡學習和領會先進經驗。
并且也都使用了quorum方式防止腦裂的情況
核心思路是類似的，但解決問題的方法完全是兩套。
ps:
活鎖，指的是任務或執行者沒有被阻塞，由于某些條件沒有滿足，導緻一直重複嘗試，活鎖可以自行解開，可以認為是一種特殊的饑餓。活鎖的程序不會block,這會導緻耗盡CPU資源。
Dynamo and Cassandra
共性1:
W+R>N
N表示叢集中副本的總數
W表示寫入的份數
R表示一次一緻性讀所需要的份數
這個公式表示為：如果滿足W+R>N(W,R,N屬于不為負數的整數且R,W小于N，那麼叢集的讀寫是強一緻的。
共性2:
gossip算法（适用于資料之間沖突很小的情況）
有“流言蜚語，謠言”的意思，A gossip protocol is a style of computer-to-computer communication protocol inspired by a form of gossip seen in social network.應該降低節點之間的溝通頻率，否則網絡開銷較大。
gossip算法被稱為反熵(Anti-Entropy)，熵是實體學上的一個概念，代表雜亂無章，而反熵就是在雜亂無章中尋求一緻：在一個有界網絡中，每個節點都随機地與其他節點通信，經過一番雜亂無章的通信，最終所有節點的狀态都會達成一緻。每個節點可能知道所有其他節點，也可能僅知道幾個鄰居節點，隻要這些節點可以通過網絡連通，最終他們的狀态都是一緻的。即使有的節點因當機而重新開機，有新節點加入，但經過一段時間後，這些節點的狀态也會與其他節點達成一緻，即Gossip天然具有分布式容錯的優點。
Gossip是一個帶備援的容錯算法，也是一個最終一緻性算法。因為Gossip不要求節點知道所有其他節點，是以具有去中心化的特點，節點之間完全對等，不需要任何的中心節點。
但Gossip的缺點也很明顯，備援通信會對網絡帶寬、CPU資源造成很大的負載，而這些負載又受限于通信頻率，該頻率又影響着算法收斂的速度。
根據原論文，Gossip的兩個節點（A,B）存在三種通信方式：
push:A節點将資料(key,value,version)推送給B節點，B節點更新A中比自己新的資料（一次通信）
pull:A僅将資料key,version推送給B，B将本地比A新的資料(key,value,version)推送給A,A更新本地（兩次通信）
push/pull:與pull類似，隻是多了一步，A再将本地比B新的資料推送給B，B更新本地（三次通信）
dynamo,資料同步使用了gossip+Merkletree,使用vector clock來标記沖突資料，沖突資料會交給使用者做出處理。
cassanra,與dynamo類似，在選擇上，放棄了vectorclock,使用timestamp來進行沖突合并
參考資源：
1、2pc，http://qing.blog.sina.com.cn/1765738567/693f084733002i99.html
2、3pc，http://qing.blog.sina.com.cn/1765738567/693f084733002ibn.html
3、paxos，http://qing.blog.sina.com.cn/1765738567/693f084733002idr.html
4、Quorum？Quorum！，http://blog.csdn.net/turkeyzhou/article/details/9307551
5.Gossip算法，http://blog.csdn.net/chen77716/article/details/6275762
6.Dynamo and Cassandra，http://qing.blog.sina.com.cn/1765738567/693f084733002ihe.html