分布式系統(tǒng)是網(wǎng)絡(luò)化的計(jì)算機(jī)系統(tǒng)，海量數(shù)據(jù)的互聯(lián)網(wǎng)應(yīng)用只能通過分布式系統(tǒng)協(xié)調(diào)大量計(jì)算機(jī)來支撐。微信后臺(tái)存儲(chǔ)大量使用了分布式數(shù)據(jù)存儲(chǔ)方式的NoSQL集群，比如核心業(yè)務(wù)：賬號(hào)、支付單據(jù)、關(guān)系鏈、朋友圈等。存儲(chǔ)設(shè)備出現(xiàn)異常是必然，分布式系統(tǒng)通過多節(jié)點(diǎn)分布及冗余，避免個(gè)別異常節(jié)點(diǎn)影響到系統(tǒng)的正常服務(wù)，同時(shí)提供平行擴(kuò)展能力。微信自研的分布式存儲(chǔ)在發(fā)展的不同階段，分別依賴過Paxos和Quorum兩種方案維護(hù)一致性。Paxos和Quorum也是互聯(lián)網(wǎng)企業(yè)主要使用的分布式協(xié)議，這里向有興趣的讀者做些分布式算法的粗略介紹，以及為什么需要它們。

關(guān)于一致性

為什么需要Paxos或Quorum算法?分布式系統(tǒng)實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)，是通過多份數(shù)據(jù)副本來保證可靠，假設(shè)部分節(jié)點(diǎn)訪問數(shù)據(jù)失敗，還有其他節(jié)點(diǎn)提供一致的數(shù)據(jù)返回給用戶。對(duì)數(shù)據(jù)存儲(chǔ)而言，怎樣保證副本數(shù)據(jù)的一致性當(dāng)屬分布式存儲(chǔ)最重要的問題。 一致性是分布式理論中的根本性問題，近半個(gè)世紀(jì)以來，科學(xué)家們圍繞著一致性問題提出了很多理論模型，依據(jù)這些理論模型，業(yè)界也出現(xiàn)了很多工程實(shí)踐投影。何為一致性問題?簡而言之，一致性問題就是相互獨(dú)立的節(jié)點(diǎn)之間，在可控的時(shí)間范圍內(nèi)如何達(dá)成一項(xiàng)決議的問題。

強(qiáng)一致寫、多段式提交

強(qiáng)一致寫

解決這個(gè)問題最簡單的方法 ，就是強(qiáng)一致寫。在用戶提交寫請(qǐng)求后，完成所有副本更新再返回用戶，讀請(qǐng)求任意選擇某個(gè)節(jié)點(diǎn)。數(shù)據(jù)修改少節(jié)點(diǎn)少時(shí)，方案看起來很好，但操作頻繁則有寫操作延時(shí)問題，也無法處理節(jié)點(diǎn)宕機(jī)。

兩段式提交(2PC 、Three-Phase Commit)

既然實(shí)際系統(tǒng)中很難保證強(qiáng)一致，便只能通過兩段式提交分成兩個(gè)階段，先由Proposer(提議者)發(fā)起事物并收集Acceptor(接受者)的返回，再根據(jù)反饋決定提交或中止事務(wù)。

***階段：Proposer發(fā)起一個(gè)提議，詢問所有Acceptor是否接受;

第二階段：Proposer根據(jù)Acceptor的返回結(jié)果，提交或中止事務(wù)。如果Acceptor全部同意則提交，否則全部終止。

兩階段提交方案是實(shí)現(xiàn)分布式事務(wù)的關(guān)鍵;但是這個(gè)方案針對(duì)無反饋的情況，除了“死等”，缺乏合理的解決方案。 Proposer在發(fā)起提議后宕機(jī)，階段二的Acceptor資源將鎖定死等。如果部分參與者接受請(qǐng)求后異常，還可能存在數(shù)據(jù)不一致的腦裂問題。

三段式提交(3PC、Three-Phase Commit)

為了解決2PC的死等問題，3PC在提交前增加一次準(zhǔn)備提交(prepare commit)的階段，使得系統(tǒng)不會(huì)因?yàn)樘嶙h者宕機(jī)不知所措。接受者接到準(zhǔn)備提交指令后可以鎖資源，但要求相關(guān)操作必須可回滾。

但3PC并沒有被用在我們的工程實(shí)現(xiàn)上，因?yàn)?PC無法避免腦裂，同時(shí)有其他協(xié)議可以做到更多的特性又解決了死等的問題。

三段式提交，在二段式提交基礎(chǔ)上增加prepare commit階段

主流的Paxos算法

微信后臺(tái)近期開始主要推廣Paxos算法用于內(nèi)部分布式存儲(chǔ)。Paxos是Leslie Lamport提出的基于消息傳遞的一致性算法，解決了分布式存儲(chǔ)中多個(gè)副本響應(yīng)讀寫請(qǐng)求的一致性，Paxos在目前的分布式領(lǐng)域幾乎是一致性的代名詞(據(jù)傳Google Chubby的作者M(jìn)ike Burrows曾說過這個(gè)世界上只有一種一致性算法, 那就是Paxos，其他算法都是殘次品)。Paxos算法在可能宕機(jī)或網(wǎng)絡(luò)異常的分布式環(huán)境中，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致，并且保證只要任意多數(shù)節(jié)點(diǎn)存活，都不會(huì)破壞整個(gè)系統(tǒng)的一致性。Paxos的核心能力就是多個(gè)節(jié)點(diǎn)確認(rèn)一個(gè)值，少數(shù)服從多數(shù)，獲得可用性和一致性的均衡。

 Paxos模型，節(jié)點(diǎn)間的交互關(guān)系

Paxos可以說是多節(jié)點(diǎn)交互的二段提交算法，Basic Paxos內(nèi)的角色有Proposer(提議者)、Acceptor(接受提議者)、Learner(學(xué)習(xí)提議者)，以提出Proposal(提議)的方式尋求確定一致的值。

***階段(Prepare)：Proposer對(duì)所有Acceptor廣播自己的Proposal(值+編號(hào))。Acceptor如果收到的Proposal編號(hào)是***的就接受，否則Acceptor必須拒絕。如果Proposer之前已經(jīng)接受過某個(gè)Proposal，就把這個(gè)Proposal返回給Proposer。在Prepare階段Acceptor始終接受編號(hào)***的Proposal，多個(gè)Proposer為了盡快達(dá)成一致，收到Acceptor返回的Proposal編號(hào)比自己的大，就修改為自己的Proposal。因此為了唯一標(biāo)識(shí)每個(gè)Proposal，編號(hào)必須唯一。如果Proposer收到過半數(shù)的Acceptor返回的結(jié)果是接受，算法進(jìn)入第二階段。

第二階段(Accept)：Proposer收到的答復(fù)中，如果過半數(shù)的Acceptor已經(jīng)接受，Proposer把***階段的Proposal廣播給所有Acceptor。而大多Acceptor已經(jīng)接受了其他編號(hào)更大的Proposal時(shí)，Proposer把這個(gè)Proposal作為自己的Proposal提交。Acceptor接到請(qǐng)求后，如果Proposal編號(hào)***則確認(rèn)并返回結(jié)果給所有Proposer，如果Proposer得到多數(shù)派回復(fù)，則認(rèn)為最終一致的值已經(jīng)確定(Chosen)。Learner不參與提議，完成后學(xué)習(xí)這個(gè)最終Proposal。

嚴(yán)格證明是通過數(shù)學(xué)歸納法，本文只做了直觀判斷。Paxos確認(rèn)這個(gè)值利用的是“抽屜原理”，固定數(shù)量的節(jié)點(diǎn)選取任意兩次過半數(shù)的節(jié)點(diǎn)集合，兩次集合交集必定有節(jié)點(diǎn)是重復(fù)的。所以***階段任何已經(jīng)接受的提議，在第二階段任意節(jié)點(diǎn)宕機(jī)或失聯(lián)，都有某節(jié)點(diǎn)已經(jīng)接受提議，而編號(hào)***的提議和確定的值是一致的。遞增的編號(hào)還能減少消息交互次數(shù)，允許消息亂序的情況下正常運(yùn)行。就一個(gè)值達(dá)成一致的方式(Basic Paxos)已經(jīng)明確了，但實(shí)際環(huán)境中并不是達(dá)成一次一致，而是持續(xù)尋求一致，讀者可以自己思考和推導(dǎo)，想深入研究建議閱讀Leslie Lamport的三篇論文《Paxos made simple》、《The Part-Time Parliament》、《Fast Paxos》。實(shí)現(xiàn)多值方式(原文為Multi Paxos)，通過增加Leader角色統(tǒng)一發(fā)起提議Proposal，還能節(jié)約多次網(wǎng)絡(luò)交互的消耗。Paxos協(xié)議本身不復(fù)雜，難點(diǎn)在如何將Paxos協(xié)議工程化。

我們實(shí)現(xiàn)Paxos存儲(chǔ)做了一些改進(jìn)，使用了無租約版Paxos分布式協(xié)議，參考Google MegaStore做了寫優(yōu)化，并通過限制單次Paxos寫觸發(fā)Prepare的次數(shù)避免活鎖問題。雖然Paxos算法下只要多數(shù)派存在，就可以在分布式環(huán)境下達(dá)到嚴(yán)格的一致性。但是犧牲的性能代價(jià)可觀，在大部分應(yīng)用場(chǎng)景中，對(duì)一致性的要求并不是那么嚴(yán)格，這個(gè)時(shí)候有不少簡化的一致性算法，比如Quorum。

簡化的Quorum(NWR)算法

Quorum借鑒了Paxos的思想，實(shí)現(xiàn)上更加簡潔，同樣解決了在多個(gè)節(jié)點(diǎn)并發(fā)寫入時(shí)的數(shù)據(jù)一致性問題。比如Amazon的Dynamo云存儲(chǔ)系統(tǒng)中，就應(yīng)用NWR來控制一致性。微信也有大量分布式存儲(chǔ)使用這個(gè)協(xié)議保證一致性。Quorum最初的思路來自“鴿巢原理”，同一份數(shù)據(jù)雖然在多個(gè)節(jié)點(diǎn)擁有多份副本，但是同一時(shí)刻這些副本只能用于讀或者只能用于寫。

Quorum模型：微信改進(jìn)的版本、數(shù)據(jù)分離結(jié)構(gòu)

Quorum控制同一份數(shù)據(jù)不會(huì)同時(shí)讀寫，寫請(qǐng)求需要的副本數(shù)要求超過半數(shù)，寫操作時(shí)就沒有足夠的副本給讀操作;

Quorum控制同一份數(shù)據(jù)的串行化修改，因?yàn)楦北緮?shù)要求，同一份數(shù)據(jù)不會(huì)被兩個(gè)寫請(qǐng)求同時(shí)修改。

Quorum又被稱為NWR協(xié)議：R表示讀取副本的數(shù)量;W表示寫入副本的數(shù)量;N表示總的節(jié)點(diǎn)數(shù)量。

假設(shè)N=2，R=1，W=1，R+W=N=2，在節(jié)點(diǎn)1寫入，節(jié)點(diǎn)2讀取，無法得到一致性的數(shù)據(jù);

假設(shè)N=2，R=2，W=1，R+W>N，任意寫入某個(gè)節(jié)點(diǎn)，則必須同時(shí)讀取所有節(jié)點(diǎn);

假設(shè)N=2，W=2，R=1，R+W>N，同時(shí)寫入所有節(jié)點(diǎn)，則讀取任意節(jié)點(diǎn)就可以得到結(jié)果。

要滿足一致性，必須滿足R+W>N。NWR值的不同組合有不同效果，當(dāng)W+R>N時(shí)能實(shí)現(xiàn)強(qiáng)一致性。所以工程實(shí)現(xiàn)上需要N>=3，因?yàn)槿哂鄶?shù)據(jù)是保證可靠性的手段，如果N=2，損失一個(gè)節(jié)點(diǎn)就退化為單節(jié)點(diǎn)。寫操作必須更新所有副本數(shù)據(jù)才能操作完成，對(duì)于寫頻繁的系統(tǒng)，少數(shù)節(jié)點(diǎn)被寫入的數(shù)據(jù)副本可以異步同步，但是只更新部分節(jié)點(diǎn)，讀取則需要訪問多個(gè)節(jié)點(diǎn)，讀寫總和超過總節(jié)點(diǎn)數(shù)才能保證讀到***數(shù)據(jù)?？梢愿鶕?jù)請(qǐng)求類型調(diào)整BWR，需要可靠性則加大NR，需要平衡讀寫性能則調(diào)整RW。

微信有大量分布式存儲(chǔ)(QuorumKV)使用這個(gè)算法保證一致性，我們對(duì)這個(gè)算法做了改進(jìn)，創(chuàng)造性地把數(shù)據(jù)副本分離出版本編號(hào)和數(shù)據(jù)存到不同設(shè)備，其中N=3(數(shù)據(jù)只有2份，版本編號(hào)有3份)，在R=W=2時(shí)仍然可以保證強(qiáng)一致性。因?yàn)榘姹揪幪?hào)存放3份，對(duì)版本編號(hào)使用Quorum方式，通過版本編號(hào)協(xié)商，只有版本序號(hào)達(dá)成一致的情況下讀寫單機(jī)數(shù)據(jù)，從而在保證強(qiáng)一致性的同時(shí)實(shí)現(xiàn)高讀寫性能。實(shí)際數(shù)據(jù)只寫入一臺(tái)數(shù)據(jù)節(jié)點(diǎn)，使用流水日志的方式進(jìn)行同步，并更新版本編號(hào)。但是我們的分布式存儲(chǔ)(QuorumKV)仍存在數(shù)據(jù)可靠性比Paxos低的問題，因?yàn)閿?shù)據(jù)只寫一份副本，依靠異步同步。如果數(shù)據(jù)節(jié)點(diǎn)故障，故障節(jié)點(diǎn)上沒有同步到另一個(gè)節(jié)點(diǎn)，數(shù)據(jù)將無法訪問。版本節(jié)點(diǎn)故障時(shí)，如果Quorum協(xié)議沒有設(shè)置W=3，也可能無法訪問正確的數(shù)據(jù)節(jié)點(diǎn)副本。

后記

分布式存儲(chǔ)選用不同的一致性算法，和業(yè)務(wù)的具體情況相關(guān)。我們的分布式存儲(chǔ)在發(fā)展的不同階段，使用過不同的算法：業(yè)務(wù)的發(fā)展初期使用Quorum算法，成本壓力減少而業(yè)務(wù)穩(wěn)定需求變大后，就開始使用Paxos算法。如果業(yè)務(wù)模型對(duì)數(shù)據(jù)一致性要求不高，使用Quorum則具有一定的成本和開發(fā)資源優(yōu)勢(shì)。