基本原則與理論
CAP（Consistency一緻性，Availability可用性，Partition tolerance分區容錯性）理論是目前分布式系統公認的理論，亦即一個分布式系統不可能同時滿足這三個特性，隻能三求其二。對于分布式系統，P是基本要求，如果沒有P就不是分布式系統了，是以一般都是在滿足P的情況下，在C和A之間尋求平衡。
ACID（Atomicity原子性，Consistency一緻性，Isolation隔離性，Durability持久性）是事務的特點，具有強一緻性，一般用于單機事務，分布式事務若采用這個原則會喪失一定的可用性，屬于CP系統。
BASE（Basically Availabe基本可用，Soft state軟狀态，Eventually consistency最終一緻性）理論是對大規模的網際網路分布式系統實踐的總結，用弱一緻性來換取可用性，不同于ACID，屬于AP系統。
2PC
2 Phase Commit，兩階段送出，系統有兩個角色協調者和參與者，事務送出過程分為兩階段：
送出事務請求（投票階段）
協調者向參與者發送事務内容，詢問是否可以執行事務送出操作，等待響應
參與者執行事務操作，并将undo和redo日志記錄
參與者回複協調者，執行成功則回Yes否則No
執行事務送出（執行階段）
如果都是參與者都回複Yes，則協調者向參與者發送送出請求，否則發送復原請求
參與者根據協調者的請求執行事務送出或復原，并向協調者發送Ack消息
協調者收到所有的Ack消息過後判斷事務的完成或者中斷
該協定可以視為強一緻的算法，通常用來保證多份資料操作的原子性，也可以實作資料副本之間的一緻性，實作簡單，但是缺點也很多，比如單點故障（協調者挂了整個系統就沒法對外服務，任一節點挂了事務就沒法執行，沒有容錯機制）、阻塞（兩個階段都涉及同步等待阻塞，極大降低了吞吐量）、資料不一緻（參與者回複Yes/No後如果因為網絡原因沒有收到送出/中斷請求，此時它就不知道該如何操作了，導緻叢集資料不一緻）……
2PC有些優化手段：逾時判斷機制，比如協調者發出事務請求後等待所有參與者回報，若超過時間沒有搜集完畢所有回複則可以多點傳播消息取消本次事務；互詢機制，參與者P回複yes後，等待協調者發起最終的commitabort，如果沒收到那麼可以詢問其他參與者Q來決定自身下一步操作，避免一直阻塞（如果其他參與者全都是等待狀态，那麼P也隻能一直阻塞了）。是以2PC的阻塞問題是沒辦法徹底解決的。
當然，如果網絡環境較好，該協定一般還是能很好的工作的，2PC廣泛應用于關系資料庫的分布式事務處理，如mysql的内部與外部XA都是基于2PC的，一般想要把多個操作打包未原子操作也可以用2PC。
3PC
3 Phase Commit，三階段送出，是二階段送出的改進，系統也有兩個角色協調者和參與者，事務送出過程分為三階段：
事務詢問（canCommit）
協調者向參與者發送一個包含事務内容的詢問請求，詢問是否可以執行事務并等待
參與者根據自己狀态判斷并回複yes、no
執行事務預送出（preCommit）
若協調者收到全是yes，就發送preCommit請求否則釋出abort請求
參與者若收到preCommit則執行事務操作并記錄undo和redo然後發送Ack，若收到abort或者逾時則中斷事務
執行事務送出（doCommit）
協調者收到所有的Ack則發送doCommit請求，若收到了No或者逾時則發送abort請求
參與者收到doCommit就執行送出并發送ACk，否則執行復原并發送Ack
協調者收到Ack判斷是完成事務還是中斷事務
三階段相對于兩階段的改善就是把準備階段一分為二，亦即多了一個canCommit階段，按我了解這樣就類似于TCP的三步握手，多了一次确認，增大了事務執行成功的機率。而且3PC的協調者即使出了故障，參與者也能繼續執行事務是以解決了2PC的阻塞問題，但是也可能是以導緻叢集資料不一緻。
Paxos
上面兩個協定的協調者都需要人為設定而無法自動生成，是不完整的分布式協定，而Paxos 就是一個真正的完整的分布式算法。系統一共有幾個角色：Proposer（提出提案）、Acceptor（參與決策）、Learner（不參與提案，隻負責接收已确定的提案，一般用于提高叢集對外提供讀服務的能力），實踐中一個節點可以同時充當多個角色。提案標明過程也大概分為2階段：
Prepare階段
Proposer選擇一個提案編号M，向Acceptor某個超過半數的子內建員發送該編号的Prepare請求
Acceptor收到M編号的請求時，若M大于該Acceptor已經響應的所有Prepare請求的編号中的最大編号N，那麼他就将N回報給Proposer，同時承諾不會再準許任何編号小于M的提案
Accept階段
如果Proposer收到超過半數的Acceptor對于M的prepare請求的響應，就發送一個針對[M,V]提案的Accept請求給Acceptor，其中V是收到的響應編号中編号的最大的提案值，如果響應中不包括任何提案值，那麼他就是任意值
Acceptor收到這個針對[M,V]的Accept請求隻要改Acceptor尚未對大于M編号的提案做出過響應，他就通過這個提案
Learn階段（本階段不屬于標明提案的過程）
Proposer将通過的提案同步到所有的Learner
Paxos協定的容錯性很好，隻要有超過半數的節點可用，整個叢集就可以自己進行Leader選舉，也可以對外服務，通常用來保證一份資料的多個副本之間的一緻性，适用于建構一個分布式的一緻性狀态機。
Google的分布式鎖服務Chubby就是用了Paxos協定，而開源的ZooKeeper使用的是Paxos的變種ZAB協定。
Raft
Raft協定對标Paxos，容錯性和性能都是一緻的，但是Raft比Paxos更易了解和實施。系統分為幾種角色：Leader（發出提案）、Follower（參與決策）、Candidate（Leader選舉中的臨時角色）。
剛開始所有節點都是Follower狀态，然後進行Leader選舉。成功後Leader接受所有用戶端的請求，然後把日志entry發送給所有Follower，當收到過半的節點的回複（而不是全部節點）時就給用戶端傳回成功并把commitIndex設定為該entry的index，是以是滿足最終一緻性的。
Leader同時還會周期性地發送心跳給所有的Follower（會通過心跳同步送出的序号commitIndex），Follower收到後就保持Follower狀态（并應用commitIndex及其之前對應的日志entry），如果Follower等待心跳逾時了，則開始新的Leader選舉：首先把目前term計數加1，自己成為Candidate，然後給自己投票并向其它結點發投票請求。直到以下三種情況：
它赢得選舉；
另一個節點成為Leader；
一段時間沒有節點成為Leader。
在選舉期間，Candidate可能收到來自其它自稱為Leader的寫請求，如果該Leader的term不小于Candidate的目前term，那麼Candidate承認它是一個合法的Leader并回到Follower狀态，否則拒絕請求。
如果出現兩個Candidate得票一樣多，則它們都無法擷取超過半數投票，這種情況會持續到逾時，然後進行新一輪的選舉，這時同時的機率就很低了，那麼首先發出投票請求的的Candidate就會得到大多數同意，成為Leader。
在Raft協定出來之前，Paxos是分布式領域的事實标準，但是Raft的出現打破了這一個現狀（raft作者也是這麼想的，請看論文），Raft協定把Leader選舉、日志複制、安全性等功能分離并子產品化，使其更易了解和工程實作，将來發展怎樣我們拭目以待（挺看好）。
Raft協定目前被用于 cockrouchDB，TiKV等項目中，據我聽的一些報告來看，一些大廠自己造的分布式資料庫也在使用Raft協定。
Gossip
Gossip協定與上述所有協定最大的差別就是它是去中心化的，上面所有的協定都有一個類似于Leader的角色來統籌安排事務的響應、送出與中斷，但是Gossip協定中就沒有Leader，每個節點都是平等的。
每個節點存放了一個key,value,version構成的清單，每隔一定的時間，節點都會主動挑選一個線上節點進行上圖的過程（不線上的也會挑一個嘗試），兩個節點各自修改自己較為落後的資料，最終資料達成一緻并且都較新。節點加入或退出都很容易。
去中心化的Gossip看起來很美好：沒有單點故障，看似無上限的對外服務能力……本來随着Cassandra火了一把，但是現在Cassandra也被抛棄了，去中心化的架構貌似難以真正應用起來。歸根到底我覺得還是因為去中心化本身管理太複雜，節點之間溝通成本高，最終一緻等待時間較長……往更高處看，一個企業（甚至整個社會）不也是需要中心化的上司（或者制度）來管理嗎，如果沒有上司（或者制度）管理，大家就是一盤散沙，難成大事啊。
事實上現代網際網路架構隻要把單點做得足夠強大，再加上若幹個強一緻的熱備，一般問題都不大。
NWR 機制
首先看看這三個字母在分布式系統中的含義：
N：有多少份資料副本； W：一次成功的寫操作至少有w份資料寫入成功； R：一次成功的讀操作至少有R份資料讀取成功。
NWR值的不同組合會産生不同的一緻性效果，當W+R>N的時候，讀取操作和寫入操作成功的資料一定會有交集，這樣就可以保證一定能夠讀取到最新版本的更新資料，資料的強一緻性得到了保證，如果R+W<=N，則無法保證資料的強一緻性，因為成功寫和成功讀集合可能不存在交集，這樣讀操作無法讀取到最新的更新數值，也就無法保證資料的強一緻性。
版本的新舊需要版本控制算法來判别，比如向量時鐘。
當然R或者W不能太大，因為越大需要操作的副本越多，耗時越長。
Quorum 機制
Quorom機制，是一種分布式系統中常用的，用來保證資料備援和最終一緻性的投票算法，主要思想來源于鴿巢原理。在有備援資料的分布式存儲系統當中，備援資料對象會在不同的機器之間存放多份拷貝。但是同一時刻一個資料對象的多份拷貝隻能用于讀或者用于寫。
分布式系統中的每一份資料拷貝對象都被賦予一票。每一個操作必須要獲得最小的讀票數（Vr）或者最小的寫票數(Vw）才能讀或者寫。如果一個系統有V票（意味着一個資料對象有V份備援拷貝），那麼這最小讀寫票必須滿足：
Vr + Vw > V
Vw > V/2
第一條規則保證了一個資料不會被同時讀寫。當一個寫操作請求過來的時候，它必須要獲得Vw個備援拷貝的許可。而剩下的數量是V-Vw 不夠Vr，是以不能再有讀請求過來了。同理，當讀請求已經獲得了Vr個備援拷貝的許可時，寫請求就無法獲得許可了。
第二條規則保證了資料的串行化修改。一份資料的備援拷貝不可能同時被兩個寫請求修改。
Quorum機制其實就是NWR機制。
Lease機制
master給各個slave配置設定不同的資料，每個節點的資料都具有有效時間比如1小時，在lease時間内，用戶端可以直接向slave請求資料，如果超過時間用戶端就去master請求資料。一般而言，slave可以定時主動向master要求續租并更新資料，master在資料發生變化時也可以主動通知slave，不同方式的選擇也在于可用性與一緻性之間進行權衡。
租約機制也可以解決主備之間網絡不通導緻的雙主腦裂問題，亦即：主備之間本來心跳連線的，但是突然之間網絡不通或者暫停又恢複了或者太繁忙無法回複，這時備機開始接管服務，但是主機依然存活能對外服務，這是就發生争奪與分區，但是引入lease的話，老主機頒發給具體server的lease必然較舊，請求就失效了，老主機自動退出對外服務，備機完全接管服務。
參考：
https://en.wikipedia.org/wiki/Two-phase_commit_protocol https://en.wikipedia.org/wiki/Three-phase_commit_protocol https://en.wikipedia.org/wiki/Paxos_(computer_science) https://raft.github.io/ https://en.wikipedia.org/wiki/Raft_(computer_science) https://lamport.azurewebsites.net/pubs/paxos-simple.pdf http://www.infoq.com/cn/articles/raft-paper https://en.wikipedia.org/wiki/Gossip_protocol https://book.douban.com/subject/26292004/ https://book.douban.com/subject/4848587/ https://book.douban.com/subject/25984046/ http://m635674608.iteye.com/blog/2343038