最近在思考一致性的問題，網(wǎng)上有很多這方面的資料了，這里談?wù)勎覍?duì)一致性以及paxos算法的理解。

1 一致性

什么是一致性，所謂一致性就是數(shù)據(jù)保持一致，在分布式系統(tǒng)中，可以理解為多個(gè)節(jié)點(diǎn)中數(shù)據(jù)的值是一致的。在單機(jī)系統(tǒng)中多線程程序其實(shí)也有一致性的問題，兩個(gè)線程對(duì)一個(gè)變量的訪問，在JAVA程序中我們有volatile關(guān)鍵字保證內(nèi)存的一致性，也就是說當(dāng)一個(gè)線程修改一個(gè)共享變量時(shí)，我們要確保另外一個(gè)線程能讀到這個(gè)修改的值，當(dāng)然我們還有有其他各種同步機(jī)制。在單機(jī)上的一致性這個(gè)其實(shí)非常好理解。

在分布式系統(tǒng)中，為了提供可用性，通常我們的數(shù)據(jù)在不同節(jié)點(diǎn)上會(huì)有多個(gè)備份，我們是沒辦法保證對(duì)所有副本同時(shí)更新，這樣不同client在讀不同副本的時(shí)候就可能出現(xiàn)讀取的值不一致的情形。根據(jù)CAP理論，一致性，可用性，分區(qū)容忍性，三者只能取其二，三者不可兼得。通常分布式系統(tǒng)都要容忍分區(qū)（即分區(qū)隔離情況下也必須能工作），這樣在工程實(shí)踐上就變成了一致性和可用性只能取其一。理論上講，如果保證100%可用性的情況下不可能達(dá)到強(qiáng)一致，但是這并不意味著就沒有了一致性，一致性可以分為幾種：強(qiáng)一致，弱一致，最終一致性等等。

強(qiáng)一致-總是能讀到最近一次寫的值；

弱一致性-可能讀到舊(Stale)的值;

最終一致性-在一段時(shí)間窗口內(nèi)可能讀到舊的值，最終會(huì)讀到新的值。

對(duì)于應(yīng)用開發(fā)人員來說都是希望強(qiáng)一致的，我寫下去的值我希望立刻能讀到，但是強(qiáng)一致系統(tǒng)往往性能不太好（相對(duì)而言）， 于是就只能tradeoff，幾乎所有流行的NoSQL系統(tǒng)為了追求性能，都犧牲了部分一致性，實(shí)現(xiàn)成一個(gè)弱一致或最終一致性系統(tǒng)，

即BASE（BasicallyAvailable,Soft state,Eventualconsistency），BASE的含義就是指“NoSQL數(shù)據(jù)庫設(shè)計(jì)可以通過犧牲一定的數(shù)據(jù)一致性和容錯(cuò)性來換取高性能的保持甚至提高”。

我們看看工業(yè)界的存儲(chǔ)系統(tǒng)，其實(shí)可以分為CP系統(tǒng)以及AP系統(tǒng)。追求極致可用性（AP）的常見系統(tǒng)包括：

AmazonS3

AmazonDynamo DB

MongoDB/Redis為代表的NoSQL

……

追求強(qiáng)一致的CP系統(tǒng)，比如：

GoogleMegastore / Spanner

MicrosoftAzure Storage

TiDB/CockroachDB

AmazonAurora

……

2 如何實(shí)現(xiàn)強(qiáng)一致性

2.1 協(xié)議

分布式系統(tǒng)實(shí)現(xiàn)強(qiáng)一致的需要某種協(xié)議來保證，經(jīng)典的兩階段提交2PC雖然解決了強(qiáng)一致的問題，但是可用性很差，因?yàn)?PC在協(xié)調(diào)者（TM）宕機(jī)時(shí)無法決定事務(wù)狀態(tài)，系統(tǒng)阻塞，需要等待協(xié)調(diào)者（TM)恢復(fù)才能繼續(xù)下去。

在工作中會(huì)議室預(yù)定系統(tǒng)就是一個(gè)2PC系統(tǒng)，會(huì)議發(fā)起方（TM）會(huì)詢問所有會(huì)議參與者是否有空，如果所有參會(huì)者都有空（OK），那么提交(commit)此次預(yù)訂，此次會(huì)議預(yù)定成功。如果有任意一個(gè)參會(huì)者(RM)沒空，那次此次預(yù)定失敗。這里有個(gè)問題是，假設(shè)在與會(huì)者回應(yīng)之后，會(huì)議發(fā)起方中途有事離開，那么與會(huì)者是沒法知道此次預(yù)定是否成功的，沒法完成也沒法中途取消，系統(tǒng)會(huì)阻塞，必須等等發(fā)起方回來之后才能繼續(xù)下去。

后續(xù)改良版的三階段提交（3PC）增加了一個(gè)中間狀態(tài)方便判斷事務(wù)狀態(tài)，協(xié)調(diào)者宕機(jī)，選出新的協(xié)調(diào)者，新的協(xié)調(diào)者不用等宕機(jī)者恢復(fù)就能決定事務(wù)狀態(tài)，但是在網(wǎng)絡(luò)分區(qū)的情況下，可能出現(xiàn)不一致的問題。比如在某些情況下可能會(huì)出現(xiàn)，比如兩個(gè)節(jié)點(diǎn)都宣稱自己是新的協(xié)調(diào)者的情況，這時(shí)候3PC仍然沒有提出一個(gè)好的解決辦法。因此可以說2PC/3PC都存在一些先天缺陷，2PC有可用性的問題，3PC有一致性的缺陷。于是Lamport大神提出的Paxos協(xié)議就可以派上用場(chǎng)，發(fā)揮它的威力了。

2.2 Paxos協(xié)議

Paxos協(xié)議是Lamport大神在80年代提出的解決分布式一致性多個(gè)節(jié)點(diǎn)之間就某個(gè)值達(dá)成一致的經(jīng)典通信協(xié)議。協(xié)議也分為兩個(gè)階段：

第一階段P1 Prepare階段

P1a：Proposer發(fā)送Prepare請(qǐng)求

Proposer發(fā)送全局唯一且遞增的提案ID(Proposal ID或者叫Ballot)，向所有節(jié)點(diǎn)（即Acceptor）發(fā)送Prepare Request,這里無需提交提案內(nèi)容，只需要攜帶Proposal ID即可。

P1b : Acceptor應(yīng)答Prepare Request

Acceptor收到Prepare Request之后，檢查自己之前是否接受過大于等于該提案ID(ProposalID或者Ballot)的請(qǐng)求，如果沒有，則Accept該P(yáng)repare請(qǐng)求，并且做出以下兩個(gè)承諾：

第二階段P2 Accept階段

P2a：Proposer發(fā)送Accept請(qǐng)求

首先，Proposer根據(jù)P1b結(jié)果決定是否繼續(xù)到下一階段，即第二階段。如果在P1b階段沒有收到多數(shù)Acceptor的相應(yīng)，此次Paxos實(shí)例結(jié)束。如果收到了多數(shù)Acceptor節(jié)點(diǎn)應(yīng)答的PrepareResponse，才會(huì)進(jìn)入到P2a階段。在P2a階段，proposal發(fā)起Accept請(qǐng)求，該Accept請(qǐng)求除了攜帶當(dāng)前ProposalID,即在P1階段被多數(shù)節(jié)點(diǎn)接受的Proposal ID,還需要攜帶提案內(nèi)容。注意，此處提案內(nèi)容不是隨心所欲，提案內(nèi)容的生成是有規(guī)則的，這個(gè)規(guī)則就是：

Proposer收集到多數(shù)派應(yīng)答的PrepareResponse后，從中選擇proposalid最大的提案內(nèi)容，作為要發(fā)起Accept的提案，如果這個(gè)提案為空，則proposer可以隨意決定提案內(nèi)容.

這個(gè)規(guī)則非常重要，是paxos算法保證準(zhǔn)確性的最重要的原則，需要好好理解。

這里再思考一下，為什么需要兩個(gè)階段？第一個(gè)階段Prepare的目的是什么？其實(shí)可以這樣想，兩個(gè)階段目的就是是為了解決提案沖突，試想如果只用一個(gè)階段一次提交提交顯然無法達(dá)到一致的狀態(tài)。而兩個(gè)階段各有作用，第一個(gè)階段Prepare的作用其實(shí)就是拿到一個(gè)授權(quán)，誰的Prepare ID最大誰就有權(quán)利去發(fā)起第二個(gè)階段的accept請(qǐng)求。而第二個(gè)階段，有權(quán)利的節(jié)點(diǎn)發(fā)生accept請(qǐng)求，該請(qǐng)求內(nèi)容可能不是自己的，而是從所有已經(jīng)accept中的提案選出提案號(hào)最大的那個(gè)，這就保證了最終被接受的提案的唯一性，換句話說，如果一個(gè)提案被大多數(shù)節(jié)點(diǎn)同意(accepted)了，那么該提案一定會(huì)被最終popugate到所有節(jié)點(diǎn)，而這樣的提案只可能有一個(gè)，這樣就保證了正確性(safety)。

可能這樣解釋還是很抽象，舉個(gè)生活中的例子。很多同事中午吃飯都有一個(gè)疑惑，不知道午飯到哪里吃，一群人需要決定到哪家餐館吃午飯，對(duì)這個(gè)問題達(dá)成一致，這其實(shí)就是一個(gè)典型的一致性問題。讓我們用paxos協(xié)議來決定午飯到哪里吃。假設(shè)有5位同學(xué)A,B,C,D,E,有這樣幾種情形：

情形一：

A提議說："我來說個(gè)餐廳吧？"（P1a)

BCDE四個(gè)同學(xué)自己也沒有想法，那就同意吧："聽你的。"(P1b)

A說：“去吃望湘源吧？”（P2a）

BC沒有想法：“好吧，就吃望湘源”。（P2b）

DE沒有說話。A看看大家的結(jié)果，BC同意，包括自己總共3個(gè)人同意，已經(jīng)達(dá)到多數(shù)票，那就這樣決定了，然后A告訴所有人中午一起去吃望湘源了。

情形二：

A提議說："我來說個(gè)餐廳吧？"（P1a)(Ballot=1)

B,C說：“好啊”。（P1b）

但是E不同意了，E馬上說：“不行，昨天吃你推薦的望湘源把我辣死啦，還是不聽你的了”。（P1b，A的Prepare請(qǐng)求被E拒絕）

A看看其他3個(gè)人沒有反對(duì)自己，仍然固執(zhí)地提出自己的想法：“我們今天不吃辣的，吃本幫菜，豐收日怎么樣？”。（P2a）

B表示同意：“豐收日不錯(cuò)的”（P2b）

E把手舉得高高的說：“還是我來推薦個(gè)人氣餐廳吧”（P1a，Ballot=2）

C,D兩位同學(xué)說：“好啊，你說吃啥？”(P1b,由于C,D響應(yīng)了E的請(qǐng)求，將不再響應(yīng)A的請(qǐng)求)

B說：“我已經(jīng)答應(yīng)A去吃豐收日了耶”

E看看提議號(hào)最高并且已經(jīng)接受過的應(yīng)答中（Ballot=1優(yōu)先級(jí)最高），B已經(jīng)接受請(qǐng)求了，那勉為其難的說：“好吧，豐收日就豐收日吧”

C，D：“行！”

于是大家就愉快地去豐收日了。

注意這里很重要的一點(diǎn)，也是理解paxos的核心，就是按照提案生成規(guī)則，當(dāng)E看到別人已經(jīng)接受的請(qǐng)求了，就不能提出自己的請(qǐng)求。但是假設(shè)E沒有聽到B的回答，而是只聽到C,D同意的響應(yīng)，E仍然可以提出自己的想法。這兩種情況，雖然結(jié)果不一樣，但是都達(dá)成一致了。

上述是basic paxos的理論模型，在工程實(shí)踐上實(shí)現(xiàn)paxos是有很多坑，google的megastore和chubby，以及后來的spanner實(shí)現(xiàn)都采用了paxos，在其論文'Paxos made live'也描述了工程實(shí)現(xiàn)上遇到的問題。

3 Leader or not Leader

經(jīng)典的paxos協(xié)議是沒有l(wèi)eader的概念的，各個(gè)角色完全對(duì)等，任何節(jié)點(diǎn)都可以發(fā)起proposal請(qǐng)求，但這樣的實(shí)現(xiàn)往往性能不會(huì)太好。在具體工程應(yīng)用中大多會(huì)考慮Leader based的paxos實(shí)現(xiàn)，完全沒有l(wèi)eader的paxos目前僅僅存在于理論上。根據(jù)Leader的作用，具體可以分為兩類：強(qiáng)leader和弱leader。

所謂leader，實(shí)際就將第一階段的prepare的權(quán)利賦予某一個(gè)節(jié)點(diǎn)，即Leader，又稱coordinator,或者叫Master。這樣由于系統(tǒng)中只有一個(gè)節(jié)點(diǎn)有發(fā)起提議的權(quán)利，就無需運(yùn)行paxos的第一階段P1，直接進(jìn)行第二階段accept，除非有沖突發(fā)生。所謂沖突就是accept過程發(fā)現(xiàn)有其他并發(fā)請(qǐng)求，這樣就必須回退到第一階段。另外在原Leader節(jié)點(diǎn)宕機(jī)，就需要重新選Leader，當(dāng)然重新選Leader期間系統(tǒng)是不可服務(wù)的。Multi-Paxos是基于強(qiáng)Leader的實(shí)現(xiàn)，依靠leader進(jìn)行日志復(fù)制同步和恢復(fù)。

在Paxos早期應(yīng)用中 像Google的Meagstore是最早將Paxos協(xié)議大規(guī)模應(yīng)用在工程實(shí)踐中的系統(tǒng)，從Megastore論文可以看出其paxos實(shí)現(xiàn)，其弱化了Leader（coordinator）的作用，其coorinator只是用來保存哪些replica是up-to-date的，如果是，則直接進(jìn)行l(wèi)ocal read，不需要再走paxos流程來獲得最新的數(shù)據(jù)。其Fast Write優(yōu)化是如果當(dāng)前這輪paxos寫成功，將自動(dòng)獲得下一輪paxos寫的prepapre的權(quán)利，這樣下輪寫直接accept。這樣實(shí)現(xiàn)的好處是多點(diǎn)可寫，不需要一個(gè)delicated的leader，服務(wù)實(shí)現(xiàn)完全的高可用。當(dāng)然缺點(diǎn)也是很明顯的，當(dāng)存在寫沖突時(shí)就會(huì)大量重試導(dǎo)致沖突進(jìn)一步加劇，甚至“雪崩”，因此Megastore論文中也提到限制單個(gè)Entity Group的寫頻率來降低沖突。

Google后來的Spanner系統(tǒng)重新了設(shè)計(jì)Paxos的工程實(shí)現(xiàn)，采用了“l(fā)ong-lived Paxos Leader”，所有的寫都從Leader發(fā)起，保證順序apply。這樣大大降低latency，提高系統(tǒng)throughput。

再換個(gè)角度想想Leader的作用，第一點(diǎn)，leader必須要有全局視角，擁有最新的信息；第二點(diǎn)，將所有的寫請(qǐng)求串行化，避免了沖突。對(duì)照現(xiàn)實(shí)生活中，leader就像沒有紅綠燈時(shí)十字路口的交警，沒有交警維護(hù)交通秩序，交通會(huì)非常擁擠。

4 總結(jié)

總體來說，Paxos是一個(gè)經(jīng)典的一致性協(xié)議，目前已經(jīng)成為分布式系統(tǒng)的實(shí)現(xiàn)高可用強(qiáng)一致的標(biāo)配，由于其實(shí)現(xiàn)的復(fù)雜性，工程應(yīng)用中層出不窮出現(xiàn)Paxos的各種變種和優(yōu)化，包括Raft其也是paxos的一種簡(jiǎn)化實(shí)現(xiàn)。Leader or not Leader這只是工程實(shí)現(xiàn)上的選擇，不影響正確性，各自有優(yōu)缺點(diǎn)，但可以說Leader base的實(shí)現(xiàn)還是目前工程實(shí)踐中的大多數(shù)系統(tǒng)的選擇以及未來的方向。

Reference: