本文從普遍認為的分布式系統(tǒng)中最最重要的數(shù)據(jù)一致性開始。內(nèi)容適合經(jīng)驗>=0年技術相關經(jīng)驗的人群。

一、對數(shù)據(jù)一致性問題的剖析

1為什么需要分布式系統(tǒng)?

任何事物能夠被持續(xù)的運用和發(fā)展，必然有其價值，分布式系統(tǒng)也是一樣。分布式系統(tǒng)的產(chǎn)生我認為主要的目的就是“快”和“海量”。這個“快”可以分為兩個方面：

• 系統(tǒng)的處理速度快
• 開發(fā)的速度快(歷時短)

這2點本質(zhì)都是相同的，把一個動作或者一件事情拆成兩部分或者多個部分去同時進行，使得整體的耗時縮短。比如：原本一件事情要一個人做的話要兩分鐘。那么我雇傭兩個人幫我各自做一部分，那么最理想情況下一分鐘就可以完成了。

當然這兩個方面中第二項從某種意義上來說是可以克服的，但是第一項是無法克服的。因為沒有一個程序或計算機的性能是無窮大的，如果有，那分布式系統(tǒng)也不會像現(xiàn)在這么普遍了(很多時候用錢能解決的問題都不是問題)。

“海量”則是由于不存在無窮大的硬盤，所以我們需要把數(shù)據(jù)分別存儲到不同的硬盤上，才能滿足需求。這些硬盤可能在不同主機、不同機房、不同地域(未來或許還可能會在不同的星球)。

2分布式系統(tǒng)的副作用

所謂每個事物都是矛盾統(tǒng)一的結(jié)合體，都具有兩面性。分布式系統(tǒng)再帶來了前面提到的好處的同時，也帶來了業(yè)界普遍認為最大的問題——數(shù)據(jù)一致性問題。

系統(tǒng)是給人用的，構(gòu)成使用場景的概念叫業(yè)務。業(yè)務是核心，對一個系統(tǒng)來說，業(yè)務的發(fā)展歸根到底是建立在數(shù)據(jù)之上的。我可以慢，可以宕機，可以搞得很復雜，這些都能忍。但唯獨不能忍的就是數(shù)據(jù)問題——數(shù)據(jù)錯誤、數(shù)據(jù)不一致等等。

分布式就意味著分治與協(xié)作，一件事一個人只負責一部分。

生活中這樣的例子也無處不在，就拿舉辦一個Party來說：一部分人去準備吃的，一部分人去準備喝的，一部分人去準備場地布置。這些事情大家都可以同時進行，但是任一環(huán)節(jié)掉鏈子了，或者說不符合Party主題的話，都是失敗的。(不知道為什么，腦子里浮現(xiàn)的是一場發(fā)布會，大家喊著cheers，一口干了高腳杯里的二鍋頭。。。)。

再舉個電商場景中的程序案例：

這里的4個操作以目標來看，其實先后順序并不重要，重要的是要么都成功，要么都失敗，其中任意一個程序不一致那么就會出問題。這個問題本質(zhì)上和人與人之間的溝通問題是類似的，與溝通唯一的不同在于，對程序來說，不一定都要得到響應，都沒響應也是一致。當一個事情分成100個部分去做的時候，很可怕，從概率的角度來看，達到一致的概率是2/5050。

這里舉的程序例子并不是嚴謹，因為實際的分布式系統(tǒng)中因為除了“write”操作還有“read”操作，所以一致性問題比這個更復雜，后面會有更詳細的說明。

3產(chǎn)生數(shù)據(jù)不一致的原因

那么是什么原因?qū)е铝藬?shù)據(jù)不一致的產(chǎn)生呢?

有一種原因是程序設計問題(代碼寫錯了)。這點很好理解，也很容易想到解決方案——多做測試，驗證是否符合預期咯。常見的單元測試、接口測試、自動化測試、集成測試等都是為了更具性價比地將BUG降低到無限接近于0，也造就了“測試工程師”這個崗位更大的作用。

但是，假設真的沒有BUG，卻還是會產(chǎn)生數(shù)據(jù)不一致。因為軟件是運行在硬件之上的，所以還有硬件的因素存在。對我們這里的大部分人來說，我們對硬件的掌控力相比對軟件，更弱。

這其中，最嚴重的屬網(wǎng)絡問題。網(wǎng)絡相比其它而言是一個更大、更復雜的組織，未知性會隨著局域網(wǎng)、廣域網(wǎng)這樣范圍越大越嚴重。想象一下，每一臺主機僅僅是一張大網(wǎng)中的一個渺小的連接點，它所承載的鏈接越多越容易出現(xiàn)問題。

可能有的小伙伴會有疑問，其它像硬盤、電源斷電什么的，也有出現(xiàn)問題的可能性，為什么網(wǎng)絡問題最為嚴重呢?

其實硬盤、電源好比是你身體的一部分，如手和腳。而網(wǎng)絡是人與人之間溝通的渠道，比如手機通話，雖然你沒有主動掛斷電話，但是整個通話過程是有很多可能性導致中斷的，對方的主觀意愿也好、信號不好也罷，甚至被第三者給攔截了。相信大家也能認可，打電話出現(xiàn)異常的概率相比自己的手腳不聽使喚是高很多的吧。

現(xiàn)實中網(wǎng)絡的特點，常遇到的問題如：延遲、丟包、亂序等問題。為了解決這些問題，從互聯(lián)網(wǎng)第一次出現(xiàn)的1969年(當年美軍在ARPA制定的協(xié)定下用網(wǎng)絡連接了4所大學)到現(xiàn)在，幾十年間出了很多的理論和解決方案，這些會在后續(xù)的文章中給大家一一做梳理。本部分先和大家具體剖析下什么是一致性。

4詳解一致性

什么叫達成一致了?說起來很簡單——在任意時間、任意位置看到的同一個事物是完全一致的。

比如一場足球賽，不管我們在現(xiàn)場還是在電視機前，看到足球從球員A傳給球員B，這個信息都是一樣的。但是嚴格意義上來說，這個并稱不上真正的一致，因為電視機接收到這個信息需要經(jīng)過衛(wèi)星信號、網(wǎng)絡等的傳輸，我們看到的時候相比現(xiàn)場的人肯定要晚。哪怕在現(xiàn)場的人，根據(jù)他所處的位置，理論上看到的信息也存在延遲差，只是因為光速非?？欤沟迷谙嗖顜装倜字畠?nèi)，這個延遲小到完全感受不到而已。

能得出的結(jié)論是：在考慮時間維度的情況下，不存在真正意義上的一致。

況且我們在分布式系統(tǒng)中，也沒有必要去達到真正的意義上的一致。因為越趨近于一致，系統(tǒng)相當于又歸一成一個單體了，在某一個時刻，只能做一件事，完全喪失了分布式系統(tǒng)的兩個目的之一“快”的優(yōu)勢。也因此衍生出多種一致性的變種，分別適用于不同的場景。為了便于理解，我們從嚴格程度的低到高來說。

大多數(shù)情況下，為了盡可能的“快”，系統(tǒng)中使用的大部分方案都是所謂的最終一致性，也就容忍一定條件下的不一致，優(yōu)先保證局部一致，然后再通過一系列復雜的狀態(tài)同步達到全局的一致。最終一致性很多可實現(xiàn)的分支，列出幾種常見的，拋磚引玉一下：

• 因果一致性：僅要求有因果關系的操作順序得到保證。比如朋友圈的回復功能。問“飯吃了嗎?”肯定得在回答“吃了”之前。
• 讀你所寫一致性：文字看著別扭，但很好解釋。比如你在朋友圈下面回復一句話，其它好友可以不用馬上看到你的回復，但是你自己必須得馬上看到，要不然回復到哪去了?
• 會話一致性：與人的一次聊天可以理解為一次會話。聊天雖然也有一定的因果關系，但是大部分場景下更多的是邏輯上的先后關系。比如你闡述一個事情，分為3條信息：首先...，然后...，最后...。如果這里的一致性得不到保證那么可能會變成：最后...，首先...，然后...。

比局部一致更嚴格一些的就是全局的順序一致性[1]，保證所有進程看到的全局執(zhí)行順序一致，并且每個進程自身的執(zhí)行順序和實際發(fā)生順序一致。

注：文中[1-6]標注皆可于文末找到對應參考資料

像上面提到的足球賽，比如實際發(fā)生的事情是①梅西把球傳給了C羅，②C羅又把球回傳給了梅西，那么每個人看到順序都應該是這樣。哪怕現(xiàn)場觀眾已經(jīng)看到②了，電視機前的我們還沒看到①，但是沒關系，這個事情發(fā)生的順序，對全世界來說都是一樣的。

再嚴格一些，就是在全局的順序一致性基礎上再增加一個相對時間的一致性要求，業(yè)界稱之為線性一致性[2]。還是用上面梅西和C羅相互傳球的例子來做個比喻，相當于梅西傳出球給C羅之后，整個球場“暫停”了，要等所有在觀看這場球賽的人都接收到這個傳球信息之后，C羅才能做下一個回傳。這里需要一個上帝(全局時鐘)來“暫停”。這是我們實際可以做到的極限了，滿足這類要求的系統(tǒng)中，名氣最大的就屬Google的Spanner了。

對不同級別的一致性匯總概述如下：

二、通過共識達成數(shù)據(jù)一致性

第一部分我們已經(jīng)對數(shù)據(jù)一致性問題做了一次剖析，那么怎么解決由于故障導致的不一致問題呢?通過共識來達成。所以，本部分會圍繞“共識”這個點展開。

1“共識”是什么?為什么會產(chǎn)生?

一致性問題其實是一個「結(jié)果」，本質(zhì)是由于數(shù)據(jù)冗余導致的，如果沒有冗余，也就不會有一致性問題了。

分布式系統(tǒng)里的各個子系統(tǒng)之間之所以能夠相互協(xié)作，就是因為其之間冗余了相同的數(shù)據(jù)作為“信物”。要不然我都不認識你的話，為什么要配合你干活呢?所以這個“信物”變了，你得通知我，要不然我又不認識你了。這個“信物”變更達成一致性的過程稱作達成「共識」。所以：

一致性問題是結(jié)果，共識是為達到這個結(jié)果所要經(jīng)過的過程，或者說一種手段。

在分布式系統(tǒng)中，冗余數(shù)據(jù)的場景不限于此，因為規(guī)模越大的系統(tǒng)，越不能容忍某一個子系統(tǒng)出問題后產(chǎn)生蝴蝶效應，所以往往會做高可用。小明1號倒下了還有千千萬萬個小明X號在堅守崗位，理想中的全天候24小時提供服務。

高可用的本質(zhì)是通過相同數(shù)據(jù)存儲多個副本，并都可對外提供服務。比如每個小明X號都有一本《按摩指法白皮書》，誰請假了都可以由其它小明X號提供相同的按摩服務。但是這個本《按摩指法白皮書》改了，就得通知到每個人，因為這是服務的全部和來源，所以在做了高可用的集群中數(shù)據(jù)冗余的問題更為突出。

實際上，如果分布式系統(tǒng)中各個節(jié)點都能保證瞬時響應、無故障運行，則達成共識很容易。就好像我們?nèi)艘粯樱谝欢ǚ秶鷥?nèi)只要吼一嗓子，通過穩(wěn)定的空氣傳播，相關人是否接收到這個消息，并且給出響應幾乎可以是“瞬時”的。

但是正如前文提到，這樣的系統(tǒng)只停留在想象中，響應請求往往存在延時，網(wǎng)絡會發(fā)生中斷，節(jié)點發(fā)生故障，甚至存在惡意節(jié)點故意要破壞系統(tǒng)。這就衍生出了經(jīng)典的「拜占庭將軍問題」[3]。

2拜占庭將軍問題

我們一般把「拜占庭將軍問題」分為2種情況來看待：

• 拜占庭錯誤。表示通過偽造信息進行惡意響應產(chǎn)生的錯誤。
• 非拜占庭錯誤。沒有進行響應產(chǎn)生的錯誤。

這個問題的核心在于：

如何解決某個變更在分布式網(wǎng)絡中得到一致的執(zhí)行結(jié)果是被參與多方都承認的，同時這個信息是被確定的，不可推翻的。

好比如何讓所有的小明X號收到的都是《按摩指法白皮書Ⅱ》，而不是其它的，并且把原來的那本銷毀掉。

這個問題衍生出了很多“共識”算法，解決「拜占庭錯誤」的稱作Byzantine Fault Tolerance(BFT)類算法，解決「非拜占庭錯誤」的稱作Crash Fault Tolerance(CFT)類算法。從這個2個名字中也可以看出，本質(zhì)的工作就是「容錯」。

有的小伙伴在平時的工作中可能對「容錯」的重要性感知沒那么強烈——不就產(chǎn)生一個BUG或者異常數(shù)據(jù)么?但是在航天領域，一個小錯誤可能導致整個發(fā)射的失敗，代價非常巨大。

對「拜占庭將軍問題」想深入的了解的，可以自行查閱相關資料，這里就不展開了，文末附上剛才我們標注的論文。

我們常見的軟件開發(fā)中一般不會考慮「拜占庭錯誤」，但它是區(qū)塊鏈項目的必需品。不過在主流的分布式數(shù)據(jù)庫中，皆能看到「非拜占庭錯誤」的身影，諸如TiDB的Paxos算法，CockroachDB的Raft算法。雖然我們大家在日常的coding中，對數(shù)據(jù)庫底層原理的了解并不是必須項。但是只要當我們涉及到應用程序級別的高可用時，那么至少「非拜占庭錯誤」是必須要面臨的一道坎。

BFT類算法

BFT類型算法又有2個分支?！富诖_定性的」和「基于概率的」。

先聊聊「基于確定性的」：

此類算法表示一旦對某個結(jié)果達成共識就不可逆轉(zhuǎn)，即共識是最終結(jié)果。它的代表作是PBFT(Practical Byzantine Fault Tolerance)算法[4]，自從有了央行背書(區(qū)塊鏈數(shù)字票據(jù)交易平臺)，名聲更大了。算法的原理，如下圖：

拿軍隊來比喻，這里的直線C可以認為是“總司令”，直線0是“軍長”，直線1、直線2、直線3都是“師長”，值得注意的是3號師長叛變了。整個過程這樣解釋：

• 「request」：總司令給軍長下了一個命令，“干!”。
• 「pre-prepare」：軍長把命令又廣播給3個師長。
• 「prepare」：每個師長收到并同意之后將發(fā)送“收到”給軍長和其他兩個師長。
• 「commit」：每個師長收到2f個師長(軍長不做prepare)的“收到”請求后發(fā)送“隨時開干”給軍長和其他兩個師長。(f為可容忍的拜占庭節(jié)點數(shù))
• 「reply」：每個師長收到2f+1條“隨時開干”消息之后，就能認為總司令的命令在相關的師長中都到達了“隨時開干”的狀態(tài)，那么他就直接開炮了!

真正想深入了解PBFT的話還有很多內(nèi)容，這里就不繼續(xù)展開了，有興趣的小伙伴可以在文末參考處自行查閱論文。

再聊聊「基于概率的」：

此類算法的共識結(jié)果則是臨時的，隨著時間推移或某種強化，共識結(jié)果被推翻的概率越來越小，成為事實上的最終結(jié)果。它的代表作是PoW(Proof of Work)算法，曾經(jīng)高達2W美元/個的比特幣就是基于這個算法來實現(xiàn)的。算法的原理拿“修仙”來做個簡單的比喻(實際比特中的算法比這更復雜)：

• 自己努力修煉，并讓神仙中大于一半的人認可你的修為，同意你成仙。
• 隨之你就成為了神仙。并且參與到評判后續(xù)其他人是否可以成為“神仙”的事情中去。
• 這個事情如果想通過賄賂來達到的話，隨著這個團隊的人數(shù)越多，賄賂的成本越大，就可以認為去做賄賂的人越少，那么導致被誤判的概率就越低，最終就越可信。

被誤判的概率公式是：0.5^個數(shù)，如果個數(shù)=6的話，誤判的概率是1.5625%。如果個數(shù)=10的話，就已經(jīng)是0.09765625%了，指數(shù)級下降。

值得注意的是，「基于確定性的」和「基于概率的」對于不合作節(jié)點的標準是不同的，前者至多能容忍1/3，后者是小于1/2。

4CFT類算法

正如上面所說CFT類算法解決的是分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點的場景(即可能消息丟失或重復，但無錯誤消息)下的共識達成問題。「拜占庭將軍問題」的提出者Leslie Lamport也在他另外的論文[5]中提出過「Paxos問題」，與這相似。在論文中通過一個故事類比了這個問題，如下：

• 希臘島嶼Paxon 上的「執(zhí)法者」在「議會大廳」中表決通過『法律』，并通過「服務員」傳遞紙條的方式交流信息，每個「執(zhí)法者」會將通過的『法律』記錄在自己的「賬目」上。問題在于「執(zhí)法者」和「服務員」都不可靠，他們隨時會因為各種事情離開「議會大廳」，并隨時可能有新的「執(zhí)法者」進入「議會大廳」進行法律表決。
• 使用何種方式能夠使得這個表決過程正常進行，且通過的『法律』不發(fā)生矛盾。

—— 百度百科

這里的關鍵對象在我們的系統(tǒng)中，可以類比為：

• 議會大廳=分布式系統(tǒng)
• 執(zhí)法者=某個程序
• 服務員=RPC通道
• 賬目=數(shù)據(jù)庫
• 法律=一次變更操作

Leslie Lamport自己也提出了解決這個問題的算法——Paxos算法[6]。這個算法的關鍵由以下3個定義來體現(xiàn)：

• 每次“變更”都有個唯一的序號，并且能夠通過它識別新舊;
• 「執(zhí)法者」只能接受比已知的“變更”更新的變更;
• 任意兩次“變更”必須有相同的「執(zhí)法者」參與。

這3點僅僅是保證一致性的最關鍵部分，全部內(nèi)容還有很多。有興趣的小伙伴可以在文末參考處自行查閱論文。

「Paxos」算法是一種無領導人(Leaderless)算法，實現(xiàn)比較復雜，所以產(chǎn)生了很多變種來簡化它，其中名氣最大的應該是「Raft」，2013年才問世。「Raft」算法是一種領導人(Leadership)的算法。由以下2個過程保證達成共識：

• 只會存在一個活著的領導人，領導人負責跟隨者的數(shù)據(jù)同步;
• 如果領導人“失聯(lián)”了，那么每個跟隨者都可成為候選人，最終比較誰的term最新，誰就是新的領導人。這個term是每個節(jié)點內(nèi)部維護的一個自增數(shù)。

雖然跟隨者的投票秉承先到先得，但是還是會遇到多個term相同的候選人獲得了相同票數(shù)(簡稱「分割投票問題」)，那么進行新一輪投票，直到?jīng)Q出勝負為止。由于Raft用隨機定時器來自增term，加上網(wǎng)絡是不穩(wěn)定的，所以再次遇到相同票數(shù)的概率就大大降低了。

完整的過程更復雜一些，有一個Raft算法的動畫推薦給大家，有興趣的可以了解一下：http://thesecretlivesofdata.com/raft/。

題外話，大家經(jīng)常用的Zookeeper里的「ZAB」(ZooKeeper Atomic Broadcast)算法也是CFT類算法，是以Fast Paxos算法為基礎實現(xiàn)的。

5結(jié)語

回過頭來看，我們發(fā)現(xiàn)，想要更嚴謹?shù)囊恢滦?，那么就需要增加相互通訊確認的次數(shù)，但是這會導致性能低下，正如PBFT和Paxos一樣。但是分布式系統(tǒng)就是這樣，到處都需要Balance，找到最適合的才是最重要的。

聊完了數(shù)據(jù)層面的「共識」問題，我們下回再聊聊「分布式事務」的問題，將會圍繞著常見的CAP、BASE理論展開。