歡迎光臨
每天分享高質量文章

分佈式系統關註點 :通過 “ 共識 ” 達成資料一致性

(點擊上方公眾號,可快速關註)


來源:Zachary

本文是本系列的第二篇。是前一篇《分佈式系統關註點——資料一致性》的後續內容。

前一篇可能講的過於通俗,逼格不高,不太受大家待見。。本篇會繼續堅持儘量講的通俗易懂,堅信讓更多的人看懂才有更大的價值。不過相對來說內容的專業度有所上升。

已經對資料一致性問題做了一次剖析,那麼怎麼解決由於故障導致的不一致問題呢?本文會圍繞“共識”這個點展開。

“共識”是什麼?為什麼會產生?

一致性問題其實是一個「結果」,本質是由於資料冗餘導致的,如果沒有冗餘,也就不會有一致性問題了。

分佈式系統里的各個子系統之間之所以能夠相互協作,就是因為其之間冗餘了相同的資料作為“信物”,要不然我都不認識你的話,為什麼要配合你幹活呢。所以這個“信物”變了,你得通知我,要不然我又不認識你了。這個“信物”變更達成一致性的過程稱作達成「共識」。所以:

一致性問題是結果,共識是為達到這個結果所要經過的過程,或者說一種手段。

在分佈式系統中,冗餘資料的場景不限於此,因為規模越大的系統,越不能容忍某一個子系統出問題後產生蝴蝶效應,所以往往會做高可用。小明1號倒下了還有千千萬萬個小明X號在堅守崗位,理想中的全天候24小時提供服務~。高可用的本質是通過相同資料儲存多個副本,並都可對外提供服務。比如每個小明X號都有一本《按摩指法白皮書》,誰請假了都可以由其它小明X號提供相同的按摩服務。但是這個本《按摩指法白皮書》改了,就得通知到每個人,因為這是服務的全部和來源,所以在做了高可用的集群中資料冗餘的問題更為突出。

實際上,如果分佈式系統中各個節點都能保證瞬時響應、無故障運行,則達成共識很容易。就好像我們人一樣,在一定範圍內只要吼一嗓子,通過穩定的空氣傳播,相關人是否接收到這個訊息,並且給出響應幾乎可以是“瞬時”的。但是正如上篇中提到,這樣的系統只停留在想象中,響應請求往往存在延時,網絡會發生中斷,節點發生故障,甚至存在惡意節點故意要破壞系統。這就衍生出了經典的「拜占庭將軍問題」[1]。

拜占庭將軍問題

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

  • 拜占庭錯誤。表示通過偽造信息進行惡意響應產生的錯誤。

  • 非拜占庭錯誤。沒有進行響應產生的錯誤。

這個問題的核心在於:

如何解決某個變更在分佈式網絡中得到一致的執行結果,是被參與多方都承認的,同時這個信息是被確定的,不可推翻的。

好比如何讓所有的小明X號收到的都是《按摩指法白皮書Ⅱ》,而不是其它的,並且把原來的那本銷毀掉。這個問題衍生出了很多“共識”演算法,解決「拜占庭錯誤」的稱作Byzantine Fault Tolerance(BFT)類演算法,解決「非拜占庭錯誤」的稱作Crash Fault Tolerance(CFT)類演算法。從這個2個名字中也可以看出,本質的工作就是「容錯」。有的小伙伴在平時的工作中可能對「容錯」的重要性感知沒那麼強烈,不就產生一個BUG或者異常資料麽,但是在航天領域,一個小錯誤可能導致整個發射的失敗,代價非常巨大。

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

我們常見的軟體開發中一般不會考慮「拜占庭錯誤」,但它是區塊鏈專案的必需品。不過在主流的分佈式資料庫中,皆能看到「非拜占庭錯誤」的身影,諸如Tidb的Raft 演算法,CockroachDB的Raft演算法。雖然我們大家在日常的coding中,對資料庫底層原理的瞭解並不是必須項。但是只要當我們涉及到應用程式級別的高可用時,那麼至少「非拜占庭錯誤」是必須要面臨的一道坎。

BFT類演算法

BFT型別演算法又有2個分支。「基於確定性的」和「基於概率的」。

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

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

  1. 「request」:總司令給軍長下了一個命令,“乾!”。

  2. 「pre-prepare」:軍長把命令又廣播給3個師長。

  3. 「prepare」:每個師長收到並同意之後將發送“收到”給軍長和其他兩個師長。

  4. 「commit」:每個師長收到2f個師長(軍長不做prepare)的“收到”請求後發送“隨時開乾”給軍長和其他兩個師長。(f為可容忍的拜占庭節點數)

  5. 「reply」:每個師長收到2f+1條“隨時開乾”訊息之後,就能認為總司令的命令在相關的師長中都到達了“隨時開乾”的狀態,那麼他就直接開炮了!

真正深入瞭解PBFT的話還有很多內容,這裡就不繼續展開了,有興趣的小伙伴自行查閱文末論文地址。

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

  • 自己努力修煉,並讓神仙中大於一半的人認可你的修為,同意你成仙。

  • 隨之你就成為了神仙。並且參與到評判後續其他人是否可以成為“神仙”的事情中去。

  • 這個事情如果想通過賄賂來達到的話,隨著這個團隊的人數越多,賄賂的成本越大,就可以認為去做賄賂的人越少,那麼導致被誤判的概率就越低,最終就越可信。

被誤判的概率公式是: 0.5 ^ 個數,如果個數=6的話,誤判的概率是1.5625%。如果個數=10的話,就已經是0.09765625%了,指數級下降。

值得註意的是,「基於確定性的」和「基於概率的」對於不合作節點的標準是不同的,前者至多能容忍1/3,後者是小於1/2。

CFT類演算法

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

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

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

        —— 百度百科

這裡的關鍵物件在我們的系統中,可以類比為:

  • 議會大廳 = 分佈式系統

  • 執法者 = 某個程式

  • 服務員 = RPC通道

  • 賬目 = 資料庫

  • 法律 = 一次變更操作

Leslie Lamport自己也提出瞭解決這個問題的演算法,「Paxos」演算法[4]。這個演算法的關鍵由以下3個定義來體現:

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

  • 「執法者」只能接受比已知的“變更”更新的變更

  • 任意兩次“變更”必須有相同的「執法者」參與

這3點僅僅是保證一致性的最關鍵部分,全部內容還有很多。有興趣的小伙伴自行查閱文末論文地址或者直接後臺回覆“一致性”打包下載。

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

  • 只會存在一個活著的領導人,領導人負責跟隨者的資料同步。

  • 如果領導人“失聯”了,那麼每個跟隨者都可成為候選人,最終比較誰的term最新,誰就是新的領導人。這個term是每個節點內部維護的一個自增數。

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

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

題外話,大家經常用的Zookeeper里的「ZAB」(ZooKeeper Atomic Broadcast)演算法也是CFT類演算法,是以Fast Paxos演算法為基礎實現的。

結語

回過頭來看,我們發現,想要更嚴謹的一致性,那麼就需要增加相互通訊確認的次數,但是這會導致性能低下,正如PBFT和Paxos一樣。但是分佈式系統就是這樣,到處都需要Balance,找到最適合的才是最重要的。

聊完了資料層面的「共識」問題,我們下回再聊聊「分佈式事務」的問題,圍繞著常見的CAP、BASE理論展開。

最後如果說想成為資料一致性專家,問有沒有捷徑的話。去閱讀老爺子Leslie Lamport的論文就是捷徑,他的個人主頁:http://www.lamport.org/ 。

參考文獻

[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),7年電商行業經驗,5年開發團隊管理經驗,4年互聯網架構經驗,目前任職於上海可得網絡科技(集團)首席架構師。專註大型系統架構、分佈式系統。個人微信公眾號:跨界架構師(ID:Zachary_ZF)。



【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~



看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

赞(0)

分享創造快樂