煩人的數(shù)據(jù)不一致問題到底怎么解決？——通過“共識”達成數(shù)據(jù)一致性

這次準備開啟一個新的系列來寫了，聊聊分布式系統(tǒng)中的關(guān)注點。節(jié)奏不會排的太緊湊，計劃兩周一更吧。

       本文是本系列的第二篇。是前一篇《不知道是不是最通俗易懂的《數(shù)據(jù)一致性》剖析了》的后續(xù)內(nèi)容。

　　前一篇可能講的過于通俗，逼格不高，不太受大家待見。。本篇會繼續(xù)堅持盡量講的通俗易懂，堅信讓更多的人看懂才有更大的價值。不過相對來說內(nèi)容的專業(yè)度有所上升。

　　已經(jīng)對數(shù)據(jù)一致性問題做了一次剖析，那么怎么解決由于故障導(dǎo)致的不一致問題呢？本文會圍繞“共識”這個點展開。

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

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

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

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

        在分布式系統(tǒng)中，冗余數(shù)據(jù)的場景不限于此，因為規(guī)模越大的系統(tǒng)，越不能容忍某一個子系統(tǒng)出問題后產(chǎn)生蝴蝶效應(yīng)，所以往往會做高可用。小明1號倒下了還有千千萬萬個小明X號在堅守崗位，理想中的全天候24小時提供服務(wù)~。高可用的本質(zhì)是通過相同數(shù)據(jù)存儲多個副本，并都可對外提供服務(wù)。比如每個小明X號都有一本《×××指法白皮書》，誰請假了都可以由其它小明X號提供相同的×××服務(wù)。但是這個本《×××指法白皮書》改了，就得通知到每個人，因為這是服務(wù)的全部和來源，所以在做了高可用的集群中數(shù)據(jù)冗余的問題更為突出。

        實際上，如果分布式系統(tǒng)中各個節(jié)點都能保證瞬時響應(yīng)、無故障運行，則達成共識很容易。就好像我們?nèi)艘粯?，在一定范圍?nèi)只要吼一嗓子，通過穩(wěn)定的空氣傳播，相關(guān)人是否接收到這個消息，并且給出響應(yīng)幾乎可以是“瞬時”的。但是正如〖上篇，←點我〗文中提到，這樣的系統(tǒng)只停留在想象中，響應(yīng)請求往往存在延時，網(wǎng)絡(luò)會發(fā)生中斷，節(jié)點發(fā)生故障，甚至存在惡意節(jié)點故意要破壞系統(tǒng)。這就衍生出了經(jīng)典的「拜占庭將軍問題」[1]。

02  拜占庭將軍問題

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

        ■ 拜占庭錯誤。表示通過偽造信息進行惡意響應(yīng)產(chǎn)生的錯誤。

        ■ 非拜占庭錯誤。沒有進行響應(yīng)產(chǎn)生的錯誤。

        這個問題的核心在于：

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

        好比如何讓所有的小明X號收到的都是《×××指法白皮書Ⅱ》，而不是其它的，并且把原來的那本銷毀掉。這個問題衍生出了很多“共識”算法，解決「拜占庭錯誤」的稱作Byzantine Fault Tolerance（BFT）類算法，解決「非拜占庭錯誤」的稱作Crash Fault Tolerance（CFT）類算法。從這個2個名字中也可以看出，本質(zhì)的工作就是「容錯」。有的小伙伴在平時的工作中可能對「容錯」的重要性感知沒那么強烈，不就產(chǎn)生一個BUG或者異常數(shù)據(jù)么，但是在航天領(lǐng)域，一個小錯誤可能導(dǎo)致整個發(fā)射的失敗，代價非常巨大。

        對「拜占庭將軍問題」想深入的了解的，可以自行查閱相關(guān)資料，這里就不展開了，文末附上提出時的論文。

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

03  BFT類算法

        BFT類型算法又有2個分支?！?span >基于確定性的」和「基于概率的」。

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

▲圖片來源于網(wǎng)絡(luò)，版權(quán)歸原作者所有

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

        ■ 「request」：總司令給軍長下了一個命令，“干！”。

        ■ 「pre-prepare」：軍長把命令又廣播給3個師長。

        ■ 「prepare」：每個師長收到并同意之后將發(fā)送“收到”給軍長和其他兩個師長。

        ■ 「commit」：每個師長收到2f個師長（軍長不做prepare）的“收到”請求后發(fā)送“隨時開干”給軍長和其他兩個師長。（f為可容忍的拜占庭節(jié)點數(shù)）

        ■ 「reply」：每個師長收到2f+1條“隨時開干”消息之后，就能認為總司令的命令在相關(guān)的師長中都到達了“隨時開干”的狀態(tài)，那么他就直接開炮了!

        真正深入了解PBFT的話還有很多內(nèi)容，這里就不繼續(xù)展開了，有興趣的小伙伴自行查閱文末論文地址或者關(guān)注公眾號后直接后臺回復(fù)“一致性”打包下載。

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

        ■ 自己努力修煉，并讓神仙中大于一半的人認可你的修為，同意你成仙。

        ■ 隨之你就成為了神仙。并且參與到評判后續(xù)其他人是否可以成為“神仙”的事情中去。

        ■ 這個事情如果想通過賄賂來達到的話，隨著這個團隊的人數(shù)越多，賄賂的成本越大，就可以認為去做賄賂的人越少，那么導(dǎo)致被誤判的概率就越低，最終就越可信。

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

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

04  CFT類算法

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

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

使用何種方式能夠使得這個表決過程正常進行，且通過的『法律』不發(fā)生矛盾。

        —— 百度百科

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

        ■ 議會大廳 = 分布式系統(tǒng)

        ■ 執(zhí)法者 = 某個程序

        ■ 服務(wù)員 = RPC通道

        ■ 賬目 = 數(shù)據(jù)庫

        ■ 法律 = 一次變更操作

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

        ■ 每次“變更”都有個唯一的序號，并且能夠通過它識別新舊

        ■ 「執(zhí)法者」只能接受比已知的“變更”更新的變更

        ■ 任意兩次“變更”必須有相同的「執(zhí)法者」參與

        這3點僅僅是保證一致性的最關(guān)鍵部分，全部內(nèi)容還有很多。有興趣的小伙伴自行查閱文末論文地址或者關(guān)注公眾號后直接后臺回復(fù)“一致性”打包下載。

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

        ■ 只會存在一個活著的領(lǐng)導(dǎo)人，領(lǐng)導(dǎo)人負責跟隨者的數(shù)據(jù)同步。

        ■ 如果領(lǐng)導(dǎo)人“失聯(lián)”了，那么每個跟隨者都可成為候選人，最終比較誰的term最新，誰就是新的領(lǐng)導(dǎo)人。這個term是每個節(jié)點內(nèi)部維護的一個自增數(shù)。

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

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

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

05  結(jié)語

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

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

        最后如果說想成為數(shù)據(jù)一致性專家，問有沒有捷徑的話。去閱讀老爺子Leslie Lamport的論文就是捷徑，他的個人主頁：http://www.lamport.org/ 。

? 微信后臺回復(fù)“一致性”關(guān)鍵字，可打包下載喲~

[1]《The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems》,Leslie Lamport,1982。

鏈接：https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Byzantine-Generals-Problem.pdf

[2]《Practical Byzantine Fault Tolerance》，Miguel Castro&Barbara Liskov，1999。

鏈接：http://101.96.10.63/pmg.csail.mit.edu/papers/osdi99.pdf

[3]《The Part-Time Parliament》,Leslie Lamport,1998。

鏈接：https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Part-Time-Parliament.pdf

[4]《In Search of an Understandable Consensus Algorithm》，Diego Ongaro&John Ousterhout，2013

鏈接：https://raft.github.io/raft.pdf

作者：Zachary（個人微信號：Zachary-ZF）

微信公眾號（首發(fā)）：跨界架構(gòu)師。<-- 點擊查閱近期熱門文章

定期發(fā)表原創(chuàng)內(nèi)容：架構(gòu)設(shè)計丨分布式系統(tǒng)丨產(chǎn)品丨運營丨一些深度思考。

掃碼加入小圈子 ↓