Byzantine Generals Problem
昨天那篇文章提到的Two General Paradox實(shí)際上是一個弱化的Byzantine Generals Problem. 1982年, Leslie Lamport和另外兩位科學(xué)家年發(fā)表了一篇論文闡述 [The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems,Volume 4 Issue 3, July 1982 Pages 382-401] 描述了更一般化的情況, 這種情況下不僅是網(wǎng)絡(luò)會有故障, 節(jié)點(diǎn)本身也會有不按照邏輯執(zhí)行的問題. 比如一個叛徒將軍亂發(fā)消息或者不按照程序邏輯執(zhí)行. 完整的拜占庭將軍問題更加復(fù)雜, 必須加以特定場景的假設(shè)才能解決, 比如同步網(wǎng)絡(luò). 這個問題比較復(fù)雜, 本文只是簡要介紹一下.
在同步網(wǎng)絡(luò)中, 有3f+1個節(jié)點(diǎn), 如果故障節(jié)點(diǎn)不超過f個, 那么這個問題是可以解決的. 我們這里不做嚴(yán)格證明, 但是可以簡單解釋一下原因岛宦。
我們考慮最基礎(chǔ)的一種情況, 假設(shè)有三個將軍, 只有一個叛徒. 如果A是叛徒, 那么A可能會給B發(fā)出進(jìn)攻(1), 然后給C發(fā)出撤退(0)的命令. 當(dāng)B和C互相同步信息的時候他們會發(fā)現(xiàn)兩個不一致的信息. 但是B和C誰也無法判斷誰是叛徒, 比如從B的角度來看, 他無法判斷A是叛徒或者C是叛徒. 所以三個將軍里有一個叛徒是無法解決的. 如果消息可以防止偽造, 那么在同步網(wǎng)絡(luò)中叛徒達(dá)到1/3也是可以解決的. 下圖右邊從C的角度來看, 因?yàn)橄⑹钦鎸?shí)無法偽造的, 那么很明顯A是叛徒. 由此可以推導(dǎo)到3f+1的情況.
但是同步網(wǎng)絡(luò)現(xiàn)實(shí)生活中太少, 如果要考慮在異步網(wǎng)絡(luò)之中, 拜占庭將軍問題是非常難解決的, 實(shí)際上根據(jù)FLP定理, 異步網(wǎng)絡(luò)中是沒有完全同時保證safety和liveness的一致性算法的. 但是在實(shí)際工程中我們?nèi)绻潘蒷iveness的要求, 是有實(shí)際可用的算法的, 這個算法進(jìn)入無限循環(huán)的概率非常非常低. 1999年Miguel Castro和Barbara Liskov提出了PBFT算法(Practical Byzantine Fault Tolerance), 這個算法可以在異步網(wǎng)絡(luò)中不保證liveness的情況下解決拜占庭將軍問題. 雖然不保證Liveness但是這個算法進(jìn)入無限循環(huán)的概率非常低, 在工程中是完全可用的. 實(shí)際上他們實(shí)現(xiàn)了一個PBFT的分布式NFS文件服務(wù)器, 最壞的時候性能只下降了24%! 為此BarbaraLiskov獲得了2008年代圖靈獎. 有興趣的同學(xué)可以自己去看 Practical Byzantine Fault Tolerance and Proactive Recovery. (ACM Transactions on Computer Systems, Vol. 20, No. 4, November 2002, Pages 398–461).
順便提一句, 面向?qū)ο笾械腖iskov替換原則也是她提出的.
FLP Impossibility
分布式事務(wù)作為Consensus類型問題, 在異步網(wǎng)絡(luò)中非常難實(shí)現(xiàn). 很多科學(xué)家們做了很多偉大的嘗試, 包括2PC, 3PC, 等等, 但是1985年的時候, 一個重要的論文告訴了我們答案, 這就是著名的FLP Impossibility:
No completely asynchronous consensus protocol can tolerate even a single unannounced process death. [ Impossibility of Distributed Consensus with One Faulty Process,Journal of the Association for Computing Machinery, Vol. 32, No. 2, April 1985]
在異步網(wǎng)絡(luò)環(huán)境中只要有一個故障節(jié)點(diǎn), 任何Consensus算法都無法保證正確結(jié)束. (這里unannounced process death是指一個進(jìn)程停止工作了但是其它節(jié)點(diǎn)不知道, 其它節(jié)點(diǎn)認(rèn)為是消息延遲或者這個進(jìn)程特別慢. FLP假設(shè)沒有拜占庭的故障節(jié)點(diǎn), 那種情況過于困難, 故障在這里的定義是指進(jìn)程停止嘗試讀取消息, 相當(dāng)于crash-stop).
FLP中設(shè)計的模型是一個比現(xiàn)實(shí)情況要更可靠的模型, 當(dāng)然了, 如果連更可靠的模型下一致性問題失效那么現(xiàn)實(shí)中更寬松的環(huán)境當(dāng)然也是失效的. FLP還假設(shè)異步網(wǎng)絡(luò)是可靠的, 盡管有延遲但是所有的消息都會投遞一次且僅一次, 每個進(jìn)程只會寫入一次狀態(tài), 然后就進(jìn)入了decision state, 這是一個很強(qiáng)的保證, 幾乎沒有任何網(wǎng)絡(luò)能達(dá)到這樣的可靠性. FLP并不要求所有非故障節(jié)點(diǎn)都達(dá)成一致, 只要有一個進(jìn)程進(jìn)入decision state就算達(dá)成一致了, 而且一致結(jié)果只能是屬于{0, 1}, 這也是非常”容易”的agreement約束. 加上前面還提到最多只有一個進(jìn)程發(fā)生故障, 相對于現(xiàn)實(shí)情況這已經(jīng)是一個極端可靠的環(huán)境了, 但是在這樣可靠的環(huán)境中仍然無法有一個一致性算法存在! 更不用說真實(shí)世界中的網(wǎng)絡(luò)分區(qū)問題和拜占庭式問題了. FLP的證明告訴我們一致性算法的liveness是無法保證的, 如果你要safety那么就會可能進(jìn)入無限循環(huán), 每次狀態(tài)變化都會可能保持當(dāng)前的狀態(tài)是可分支的(bivalent). FLP的嚴(yán)格證明很有趣, 但限于篇幅這里就不做介紹了. 有興趣的同學(xué)可以去看原論文, 如果你覺得里面的數(shù)學(xué)語言比較晦澀, 可以看我寫的一篇白話文的證明過程描述(鏈接：http://danielw.cn/FLP-proof/).
所有consensus問題最終在異步網(wǎng)絡(luò)上只要有一個故障節(jié)點(diǎn)就都無法達(dá)成完全一致并結(jié)束. 這個理論的證明非常重要, 它終止了多年的爭論, 現(xiàn)在你可以省省力氣了, 不要再浪費(fèi)精力去試圖設(shè)計一個能在異步網(wǎng)絡(luò)上能夠容忍各種故障并保持一致的系統(tǒng)了. 比如分布式事務(wù)是永遠(yuǎn)無法實(shí)現(xiàn)單體應(yīng)用級別的一致性的.
無論是Paxos還是Raft算法, 理論上都可能會進(jìn)入無法表決通過的死循環(huán)(但是這個概率其實(shí)是非常非常低的), 但是他們都是滿足safety的, 只是放松了liveness的要求, Barbara Liskov的PBFT也是這樣. 在實(shí)際應(yīng)用中, 上下游系統(tǒng)之間的一致性除了通過2PC或者Paxos Commit來實(shí)現(xiàn), 我們也可以通過其他方式來實(shí)現(xiàn)最終的一致, 來避免2PC的缺點(diǎn). 現(xiàn)實(shí)中你不得不接受短時間的不一致在分布式系統(tǒng)中是一種常態(tài)的事實(shí). CAP理論的提出者Eric Brewer曾經(jīng)這樣說過:
So the general answer is you allow things to be inconsistent and thenyou find ways to compensate for mistakes, versus trying to prevent mistakes altogether. In fact, the financial system is actually not based on consistency, it's based on auditing and compensation. They didn't know any thing about the CAP theorem, that was just the decision they made in figuring out what they wanted, and that's actually, I think, the right decision.
舉個例子,實(shí)際上你從A銀行往B銀行轉(zhuǎn)賬實(shí)際上是沒有兩階段提交或者分布式事務(wù)的, 金融行業(yè)是一個古老的行業(yè), 在計算機(jī)出現(xiàn)之前銀行就已經(jīng)出現(xiàn)了, 金融行業(yè)有一點(diǎn)非常值得我們借鑒, 那就是WORM(write once read many). 金融行業(yè)把不一致當(dāng)做常態(tài)而非異常.舉個例子, 會計記賬的時候, 如果發(fā)現(xiàn)前面有一筆預(yù)付記錄或者錯誤記錄, 會計不會用橡皮抹掉那條記錄再改成正確的, 會計只會在最后面加一筆記錄來抵消前面的錯誤, 或者按照差額加一筆抵沖的記錄. 任何記錄只能寫入一次, 然后再也不會改變. 我們假設(shè)沒有人民銀行作為中間節(jié)點(diǎn), 把轉(zhuǎn)賬簡化為A銀行直接給B銀行轉(zhuǎn)賬, 在轉(zhuǎn)賬過程中如果A已經(jīng)扣款并通知了B,但是B發(fā)現(xiàn)這個賬號由于洗錢被鎖定了, 不能入款, 那么B返回拒絕消息給A, 這時候A可以再追加一筆補(bǔ)償交易, 把剛才扣掉的錢補(bǔ)償回來. 整個過程可能是幾秒鐘, 也可能是幾分鐘, 也有可能是第二天(比如網(wǎng)絡(luò)故障, 重試多次后放棄, 對賬時發(fā)現(xiàn)). 在任何一個步驟發(fā)生故障, 用戶都會經(jīng)歷一定時間的不一致, 從前面的討論我們知道2PC如果允許超時回滾, 2PC也無法消除這個不一致的時間窗口, 但是只要有歷史記錄我們就可以通過自動補(bǔ)償或者每日對賬去補(bǔ)償, 讓數(shù)據(jù)重新一致. 這種事務(wù)可以很好地忍耐各種故障, 包括網(wǎng)絡(luò)分區(qū), 只要每個消息都有全局唯一的id或者消息是冪等的即可. 當(dāng)網(wǎng)絡(luò)恢復(fù)時任何一個節(jié)點(diǎn)都可以根據(jù)消息id輕松地去掉重復(fù)的消息, 當(dāng)消息丟失時, 可以稍后重試或者每天對賬.
如果事務(wù)包含特別復(fù)雜的計算, 或者涉及了線下的物流或者多方交易, 那么這樣的事務(wù)可能需要幾天才能完成, 這種長事務(wù)(Long Lived Transaction) 在2PC中更是無法處理, 我們總不能去鎖定這些數(shù)據(jù)幾天吧? 1987年普林斯頓大學(xué)的Garcia-Molina和Salem發(fā)表了一篇論文提出了saga的概念. 一個長事務(wù)T中的操作可以拆分為彼此獨(dú)立的本地事務(wù)T1, T2, T3, 那么就可以稱之為saga. 其中的每一個Ti都有一個相應(yīng)的補(bǔ)償事務(wù)Ci. 如果部分Ti失敗了需要Ci來修復(fù)回原始狀態(tài),Ci不會直接把數(shù)據(jù)庫改回原先的狀態(tài), Ci通常是像前面說的會計的做法追加修正內(nèi)容去抹平Ti帶來的變化. 下圖中事務(wù)參與者有A,B, C, 每次發(fā)起的事務(wù)都有一個全局唯一的id, 參與者之間的消息在網(wǎng)絡(luò)故障時可以重發(fā) (可以通過id去重復(fù)消息, 或者保證冪等操作). 假如T3在C中執(zhí)行時失敗了, 如果T3已經(jīng)提交了或者這個系統(tǒng)不支持回滾, 那么必須使用C3來補(bǔ)償T3帶來的變化. 然后發(fā)消息給B, B會執(zhí)行C2去補(bǔ)償T2, 然后B可以選擇繼續(xù)通知A去回滾, 或者稍后等外部條件發(fā)生變化再執(zhí)行T2, 然后讓C去重試. 這樣整個系統(tǒng)變成了一個狀態(tài)機(jī),參與者之間雖然有可能不一致,一個訂單或者一筆交易一定會處于狀態(tài)機(jī)的某一個狀態(tài), 整個事務(wù)的過程仍然是整體可以追溯的.
Saga這種方法并不適合所有的情況, 它也不是銀彈, 但是它是比2PC/3PC更適合來解決分布式事務(wù). 2PC/3PC的思路是想在源頭上阻止分布式事務(wù)不一致的產(chǎn)生, 但這是不可能實(shí)現(xiàn)的. 不一致是常態(tài), 不是異常, 異步網(wǎng)絡(luò)中能容忍節(jié)點(diǎn)故障的total correct的consensus算法不存在简卧。
本文作者：Daniel吳強(qiáng)（點(diǎn)融黑幫）扣墩，現(xiàn)任點(diǎn)融網(wǎng)首席社交平臺架構(gòu)師，前盛大架構(gòu)師, 專注分布式系統(tǒng)和移動應(yīng)用, 有十三年的開發(fā)經(jīng)驗(yàn), 目前在點(diǎn)融做最愛的兩件事情: 寫代碼和重構(gòu)代碼鞍爱。
