作者：莫曉東，微信支付進階DBA，擁有豐富的資料架構和運維實戰經驗，擅長大規模MySQL資料庫叢集的架構、優化和高可用。2010年起在騰訊從事DBA工作，目前專注于微信社交支付的存儲層運維和架構優化。
責編：仲培藝，關注資料庫領域，尋求報道或者投稿請發郵件[email protected]，或微信zhongpy_0921。
本文為《程式員》原創文章，未經允許不得轉載，更多精彩文章請訂閱2017年《程式員》
分布式系統是網絡化的計算機系統，海量資料的網際網路應用隻能通過分布式系統協調大量計算機來支撐。微信背景存儲大量使用了分布式資料存儲方式的NoSQL叢集，比如核心業務：賬号、支付單據、關系鍊、朋友圈等。儲存設備出現異常是必然，分布式系統通過多節點分布及備援，避免個别異常節點影響到系統的正常服務，同時提供平行擴充能力。微信自研的分布式存儲在發展的不同階段，分别依賴過Paxos和Quorum兩種方案維護一緻性。Paxos和Quorum也是網際網路企業主要使用的分布式協定，這裡向有興趣的讀者做些分布式算法的粗略介紹，以及為什麼需要它們。
關于一緻性
為什麼需要Paxos或Quorum算法？分布式系統實作資料存儲，是通過多份資料副本來保證可靠，假設部分節點通路資料失敗，還有其他節點提供一緻的資料傳回給使用者。對資料存儲而言，怎樣保證副本資料的一緻性當屬分布式存儲最重要的問題。 一緻性是分布式理論中的根本性問題，近半個世紀以來，科學家們圍繞着一緻性問題提出了很多理論模型，依據這些理論模型，業界也出現了很多工程實踐投影。何為一緻性問題？簡而言之，一緻性問題就是互相獨立的節點之間，在可控的時間範圍内如何達成一項決議的問題。
強一緻寫、多段式送出
強一緻寫
解決這個問題最簡單的方法 ，就是強一緻寫。在使用者送出寫請求後，完成所有副本更新再傳回使用者，讀請求任意選擇某個節點。資料修改少節點少時，方案看起來很好，但操作頻繁則有寫操作延時問題，也無法處理節點當機。
兩段式送出（2PC 、Three-Phase Commit）
既然實際系統中很難保證強一緻，便隻能通過兩段式送出分成兩個階段，先由Proposer（提議者）發起事物并收集Acceptor（接受者）的傳回，再根據回報決定送出或中止事務。
- 第一階段：Proposer發起一個提議，詢問所有Acceptor是否接受；
- 第二階段：Proposer根據Acceptor的傳回結果，送出或中止事務。如果Acceptor全部同意則送出，否則全部終止。
兩階段送出方案是實作分布式事務的關鍵；但是這個方案針對無回報的情況，除了“死等”，缺乏合理的解決方案。 Proposer在發起提議後當機，階段二的Acceptor資源将鎖定死等。如果部分參與者接受請求後異常，還可能存在資料不一緻的腦裂問題。
三段式送出（3PC、Three-Phase Commit）
為了解決2PC的死等問題，3PC在送出前增加一次準備送出（prepare commit）的階段，使得系統不會因為提議者當機不知所措。接受者接到準備送出指令後可以鎖資源，但要求相關操作必須可復原。
但3PC并沒有被用在我們的工程實作上，因為3PC無法避免腦裂，同時有其他協定可以做到更多的特性又解決了死等的問題。
圖1 三段式送出，在二段式送出基礎上增加prepare commit階段
主流的Paxos算法
微信背景近期開始主要推廣Paxos算法用于内部分布式存儲。Paxos是Leslie Lamport提出的基于消息傳遞的一緻性算法，解決了分布式存儲中多個副本響應讀寫請求的一緻性，Paxos在目前的分布式領域幾乎是一緻性的代名詞（據傳Google Chubby的作者Mike Burrows曾說過這個世界上隻有一種一緻性算法, 那就是Paxos，其他算法都是殘次品）。Paxos算法在可能當機或網絡異常的分布式環境中，快速且正确地在叢集内部對某個資料的值達成一緻，并且保證隻要任意多數節點存活，都不會破壞整個系統的一緻性。Paxos的核心能力就是多個節點确認一個值，少數服從多數，獲得可用性和一緻性的均衡。
圖2 Paxos模型，節點間的互動關系
Paxos可以說是多節點互動的二段送出算法，Basic Paxos内的角色有Proposer（提議者）、Acceptor（接受提議者）、Learner（學習提議者），以提出Proposal（提議）的方式尋求确定一緻的值。
- 第一階段（Prepare）：Proposer對所有Acceptor廣播自己的Proposal（值+編号）。Acceptor如果收到的Proposal編号是最大的就接受，否則Acceptor必須拒絕。如果Proposer之前已經接受過某個Proposal，就把這個Proposal傳回給Proposer。在Prepare階段Acceptor始終接受編号最大的Proposal，多個Proposer為了盡快達成一緻，收到Acceptor傳回的Proposal編号比自己的大，就修改為自己的Proposal。是以為了唯一辨別每個Proposal，編号必須唯一。如果Proposer收到過半數的Acceptor傳回的結果是接受，算法進入第二階段。
- 第二階段（Accept）：Proposer收到的答複中，如果過半數的Acceptor已經接受，Proposer把第一階段的Proposal廣播給所有Acceptor。而大多Acceptor已經接受了其他編号更大的Proposal時，Proposer把這個Proposal作為自己的Proposal送出。Acceptor接到請求後，如果Proposal編号最大則确認并傳回結果給所有Proposer，如果Proposer得到多數派回複，則認為最終一緻的值已經确定（Chosen）。Learner不參與提議，完成後學習這個最終Proposal。
嚴格證明是通過數學歸納法，本文隻做了直覺判斷。Paxos确認這個值利用的是“抽屜原理”，固定數量的節點選取任意兩次過半數的節點集合，兩次集合交集必定有節點是重複的。是以第一階段任何已經接受的提議，在第二階段任意節點當機或失聯，都有某節點已經接受提議，而編号最大的提議和确定的值是一緻的。遞增的編号還能減少消息互動次數，允許消息亂序的情況下正常運作。就一個值達成一緻的方式（Basic Paxos）已經明确了，但實際環境中并不是達成一次一緻，而是持續尋求一緻，讀者可以自己思考和推導，想深入研究建議閱讀Leslie Lamport的三篇論文《Paxos made simple》、《The Part-Time Parliament》、《Fast Paxos》。實作多值方式（原文為Multi Paxos），通過增加Leader角色統一發起提議Proposal，還能節約多次網絡互動的消耗。Paxos協定本身不複雜，難點在如何将Paxos協定工程化。
我們實作Paxos存儲做了一些改進，使用了無租約版Paxos分布式協定，參考Google MegaStore做了寫優化，并通過限制單次Paxos寫觸發Prepare的次數避免活鎖問題。雖然Paxos算法下隻要多數派存在，就可以在分布式環境下達到嚴格的一緻性。但是犧牲的性能代價可觀，在大部分應用場景中，對一緻性的要求并不是那麼嚴格，這個時候有不少簡化的一緻性算法，比如Quorum。
簡化的Quorum（NWR）算法
Quorum借鑒了Paxos的思想，實作上更加簡潔，同樣解決了在多個節點并發寫入時的資料一緻性問題。比如Amazon的Dynamo雲存儲系統中，就應用NWR來控制一緻性。微信也有大量分布式存儲使用這個協定保證一緻性。Quorum最初的思路來自“鴿巢原理”，同一份資料雖然在多個節點擁有多份副本，但是同一時刻這些副本隻能用于讀或者隻能用于寫。
圖3 Quorum模型：微信改進的版本、資料分離結構
- Quorum控制同一份資料不會同時讀寫，寫請求需要的副本數要求超過半數，寫操作時就沒有足夠的副本給讀操作；
- Quorum控制同一份資料的串行化修改，因為副本數要求，同一份資料不會被兩個寫請求同時修改。
Quorum又被稱為NWR協定：R表示讀取副本的數量；W表示寫入副本的數量；N表示總的節點數量。
- 假設N=2，R=1，W=1，R+W=N=2，在節點1寫入，節點2讀取，無法得到一緻性的資料；
- 假設N=2，R=2，W=1，R+W>N，任意寫入某個節點，則必須同時讀取所有節點；
- 假設N=2，W=2，R=1，R+W>N，同時寫入所有節點，則讀取任意節點就可以得到結果。
要滿足一緻性，必須滿足R+W>N。NWR值的不同組合有不同效果，當W+R>N時能實作強一緻性。是以工程實作上需要N>=3，因為備援資料是保證可靠性的手段，如果N=2，損失一個節點就退化為單節點。寫操作必須更新所有副本資料才能操作完成，對于寫頻繁的系統，少數節點被寫入的資料副本可以異步同步，但是隻更新部分節點，讀取則需要通路多個節點，讀寫總和超過總節點數才能保證讀到最新資料。可以根據請求類型調整BWR，需要可靠性則加大NR，需要平衡讀寫性能則調整RW。
微信有大量分布式存儲（QuorumKV）使用這個算法保證一緻性，我們對這個算法做了改進，創造性地把資料副本分離出版本編号和資料存到不同裝置，其中N=3（資料隻有2份，版本編号有3份），在R=W=2時仍然可以保證強一緻性。因為版本編号存放3份，對版本編号使用Quorum方式，通過版本編号協商，隻有版本序号達成一緻的情況下讀寫單機資料，進而在保證強一緻性的同時實作高讀寫性能。實際資料隻寫入一台資料節點，使用流水日志的方式進行同步，并更新版本編号。但是我們的分布式存儲（QuorumKV）仍存在資料可靠性比Paxos低的問題，因為資料隻寫一份副本，依靠異步同步。如果資料節點故障，故障節點上沒有同步到另一個節點，資料将無法通路。版本節點故障時，如果Quorum協定沒有設定W=3，也可能無法通路正确的資料節點副本。
後記
分布式存儲選用不同的一緻性算法，和業務的具體情況相關。我們的分布式存儲在發展的不同階段，使用過不同的算法：業務的發展初期使用Quorum算法，成本壓力減少而業務穩定需求變大後，就開始使用Paxos算法。如果業務模型對資料一緻性要求不高，使用Quorum則具有一定的成本和開發資源優勢。
訂閱2017年程式員（含iOS、Android及印刷版）請通路 http://dingyue.programmer.com.cn
由CSDN主辦的中國雲計算技術大會（CCTC 2017）将于5月18-19日在北京召開，Spark、Container、區塊鍊、大資料四大主題峰會震撼襲來，包括Mesosphere CTO Tobi Knaup，Rancher labs 創始人梁勝、Databricks 工程師 Spark commiter 範文臣等近60位技術大牛齊聚京城，為雲計算、大資料以及人工智能領域開發者帶來一場技術的盛大Party。現在報名，隻需399元就可以聆聽近60場的頂級技術專家分享，還等什麼，登陸官網（http://cctc.csdn.net/），趕快報名吧！