分布式系統中的一緻性協定總結

分布式系統中的一緻性協定總結

本文詳細介紹目前分布式系統中常見的一些一緻性協定：兩階段送出協定，三階段送出協定，向量時鐘，RWN協定，paxos協定，Raft協定。下面就一個個詳細講解下。

一. 兩階段送出協定(2PC)

兩階段送出協定，簡稱2PC，是比較常用的解決分布式事務問題的方式，要麼所有參與程序都送出事務，要麼都取消事務，即實作ACID中的原子性(A)的常用手段。

兩階段送出将送出過程劃分為連續的兩個階段：表決階段(Voting)和送出階段(Commit)。假設在沒有故障發生的情形下，兩階段送出協定由下列操作序列構成，如下圖所示：

協調者的有限狀态機如下圖：

如上圖所示：協調者初始處于INIT狀态，當接收到系統發出的Commit消息後，向參與者多點傳播Vote-request消息後轉入WAIT狀态，在此進入阻塞狀态，因為要等待所有參與者發送傳回的消息，當收到所有參與者的傳回消息後，如果其中包含Vote-Abort消息，則多點傳播Global-abort消息後轉入ABORT狀态，否則多點傳播Global-commit消息後轉入COMMIT狀态。

參與者的有限狀态機如下圖：

如上圖所示：參與者初始處于INIT狀态，當接收到Vote-Request消息時，發出Vote-commit會轉入READY狀态，告訴協調者已經準備做好送出準備，否則就傳回一個VOTE-ABORT消息。等待協調者行為，如果收到Global-Abort消息，就會進入Abort狀态，如果收到Global-commit消息，就會轉入COMMIT狀态。

從兩者的有限狀态機可以看出，在所有可能狀态中，存在三個阻塞狀态：協調者的WAIT狀态，參與者的INIT狀态和READY狀态。

二. 三階段送出協定(3PC)

3PC就是在2PC基礎上将2PC的送出階段細分位兩個階段：預送出階段和送出階段。

3PC中協調者的有限狀态機如下圖：

3PC中參與者的有限狀态機如下圖：

三. 向量時鐘

通過向量空間祖先繼承的關系比較, 使資料保持最終一緻性,這就是向量時鐘的基本定義。

下面給出一個場景來說明向量時鐘的作用：

Vector Clock就是為了解決這種問題而設計的，簡單來說，就是為每個商議結果加上一個時間戳，當結果改變時，更新時間戳。是以加上時間戳之後，我們再一次描述上面的場景，如下：

以上這個決策用到了向量時鐘，有個圖還比較清晰了說明整個過程：

四. NWR協定

NWR是一種在分布式存儲系統中用于控制一緻性級别的一種政策。在Amazon的Dynamo雲存儲系統中，就應用NWR來控制一緻性。

讓我們先來看看這三個字母的含義：

N：在分布式存儲系統中，有多少份備份資料

W：代表一次成功的更新操作要求至少有w份資料寫入成功

R： 代表一次成功的讀資料操作要求至少有R份資料成功讀取

NWR值的不同組合會産生不同的一緻性效果，當W+R>N的時候，整個系統對于用戶端來講能保證強一緻性。當W+R 以常見的N=3、W=2、R=2為例：

N=3，表示，任何一個對象都必須有三個副本（Replica），W=2表示，對資料的修改操作（Write）隻需要在3個Replica中的2個上面完成就傳回，R=2表示，從三個對象中要讀取到2個資料對象，才能傳回。

在分布式系統中，資料的單點是不允許存在的。即線上正常存在的Replica數量是1的情況是非常危險的，因為一旦這個Replica再次錯誤，就 可能發生資料的永久性錯誤。假如我們把N設定成為2，那麼，隻要有一個存儲節點發生損壞，就會有單點的存在。是以N必須大于2。N約高，系統的維護和整體 成本就越高。工業界通常把N設定為3。

當W是2、R是2的時候，W+R>N，這種情況對于用戶端就是強一緻性的。

在上圖中，如果R+W>N,則讀取操作和寫入操作成功的資料一定會有交集（如圖中的B），這樣就可以保證一定能夠讀取到最新版本的更新資料，資料的強一緻性得到了保證。在滿足資料一緻性協定的前提下，R或者W設定的越大，則系統延遲越大，因為這取決于最慢的那份備份資料的響應時間。而如果R+W<=N，則無法保證資料的強一緻性，因為成功寫和成功讀集合可能不存在交集，這樣讀操作無法讀取到最新的更新數值，也就無法保證資料的強一緻性。

在具體實作系統時，僅僅依靠NWR協定還不能完成一緻性保證，因為在上述過程中，當讀取到多個備份資料時，需要判斷哪些資料是最新的，如何判斷資料的新舊？這需要向量時鐘來配合，是以對于Dynamo來說，是通過NWR協定結合向量時鐘來共同完成一緻性保證的。

五. paxos協定

Paxos協定的基礎比較難以了解，這裡就不枯燥無味的介紹paxos協定的理論基礎，這方面的資料也是非常多的。估計大家也不希望看到很多理論，公式很多。這裡給出幾個參考資料供閱讀：

1.  架構師需要了解的Paxos原理，曆程及實踐：http://chuansong.me/n/2189245

2.  微信自研生産級Paxos類庫Phxpaxos實作原理介紹：http://mp.weixin.qq.com/s?__biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e#rd  

3.  資料一緻性與Paxos算法(上，中，下三篇文章): http://blog.csdn.net/yinwenjie/article/details/60584554

六. Raft協定

1.  Raft協定的動畫： http://thesecretlivesofdata.com/raft/

2.  https://raft.github.io/

參考資料：

1. Vector Clock. http://en.wikipedia.org/wiki/Vector_clock
2. Leslie Lamport. Paxos Made Simple. ACM SIGACT News
3. The chubby lock service for loosely-coupled distributed systems.pdf
4. Diego Ongaro and John Ousterhout. In Search of an Understandable Consensus Algorithm
5. http://www.cnblogs.com/yanghuahui/p/3767365.html
6. other resources