標籤：

一致性, 兩階段提交和事務提交的發展史(譯)

01-28

原文地址: betathoughts.blogspot.com [注: 初次翻譯, 這裡面提到的論文可能理解不夠, 有錯誤的地方感謝幫忙指出]

這是關於一致性, 事務和兩階段提交的歷史, 因為用詞的變化導致閱讀一致性相關的文章非常的麻煩(consensus 在較早以前都叫做agreement), 這些分散式相關的論文並沒有按照邏輯的順序產出, 並且整體的分散式演算法是在並行發展的. 目前只有Lynch 的 Distributed Algorithm 這本書有這些主題

接下來描述的Paper主要按他們的關聯性排序, 並沒有根據他們的出版時間進行排序.

第一個我知道的關於一致性問題的實例是Lamports "Time, Clocks and the Ordering of Events in a Distributed System" (1978), 雖然這篇文章沒有嚴格的定義了一個一致性的問題. 在這個文章裡面 Lamport 討論了在有限的時間內消息是怎麼在進程之間進行傳輸, 並且將進程之間傳遞消息和愛因斯坦的相對論進行的對比. 最近在博客上討論分散式系統和愛因斯坦的相對論的關聯非常的熱門,但是在1978年的時候 Lamport就已經給出了一個完整的時空圖的分析. 這個結論是在一個分散式系統裡面, 只有A事件能夠觸發B事件的發生, 你才能夠說明A事件發生在B事件前面, 否則是不行的. 不同的進程看到的事件的順序是不一致的, 也就是在一個分散式系統裡面, 只存在一個偏序關係, 不存在一個全序關係. Lamport 定義了"happens before" 關係和操作, 並且給出了一個在分散式系統裡面全局的定義事件順序關係的演算法, 這樣所有的進程看到的事件的順序關係就是一致的

Lamport還介紹了一個分散式的狀態機: 所有的狀態機以一個相同的初始狀態啟動, 並且保證所有的狀態機處理的消息是一模一樣的. 那麼每一個狀態機就是其他狀態機的副本. 那麼, 關鍵的問題是保證每一個副本約定好下一條要處理的消息: 一個一致性問題. 這個用上面給出的全局的定義事件順序關係的演算法可以做到的. 但是這個系統容錯能力是不行的, 假如有一個進程失敗了, 那麼其他的進程必須等待他恢復.

大約在這邊論文發布的相同的時間, Gray 發布了兩階段提交協議的演算法 "Notes on Database Operating Systems" (1979). 兩階段提交協議存在的問題是, 如果TM(Transaction Manager)在某些時刻如果失敗了, 整個Transaction 就會阻塞. Skeen又發布了"NonBlocking Commit Protocols" (1981)這篇論文. 論文指出在一個分散式的事務裡面, 需要一個三階段的提交協議來避免在兩階段提交中存在的阻塞問題. 但是問題是這個一個完美三階段提交協議需要將近25年的時間來完成一次提交!

Fischer, Lynch and Paterson 在論文 "Impossibility of distributed consensus with one faulty process" (1985)證明, 在一個非同步系統裡面, 只要有一個錯誤的進程, 一致性就不可能達成. 這個也就是著名的"FLP"結論. 在這個時間"一致性" 代表的是一堆進程同意同一個值的問題. 一個非同步系統(非同步系統指的是進程運行的速度不一定, 並且進程之間傳遞消息所需要的時間也不一定, 有可能無限長)在最完美的網路環境(這裡的環境指的是所有的消息都會被送達, 消息送達的順序和消息被發送的順序是一致的, 並且消息是不會被多次的發送)下, 只要有一個進程出錯, 這個一致性就無法達成. 這個問題的難點在於你不能判斷一個進程是停止了還是跑的非常的慢. 處理一個在非同步系統裡面的錯誤幾乎是不可能的. 這篇論文是非常重要的, 因為它告訴了我們什麼事情是不可能的, 就像能量守恆定律對於永動機一樣. 這篇文章證明過程是所有想要解決非同步系統的一致性問題的演算法必須有某些屬性, 然後他們通過反證法證明了這些屬性是不可能存在的.

在這個階段, 人們認為分散式系統分成同步的(進程運行在已知的速度, 並且在進程之間消息的傳遞在規定的時間到達) 和 非同步的(進程運行在任意的速度, 並且進程間消息的傳遞時間不能保證). 非同步的系統是一個更為常見的系統. 一個演算法能夠解決非同步系統的一致性問題, 肯定也能夠解決同步系統的一致性問題, 但是反過來不行.你可以把一個同步系統看成一個非同步系統的特例, 同步系統是進程運行在規定速度, 進程之間傳遞消息有時間上線的一個非同步系統.

在FLP之前, 就有"The Byzantine Generals Problem" (1982)這篇論文. 在這個一致性問題裡面, 進程可以傳遞錯誤信息, 並且他們積極的將這個錯誤信息傳遞給其他進程. 這個問題看起來比FLP結論更難, 但是在同步系統下, 還是有方法能夠達成一致的(雖然在這篇文章發布的時候, 同步系統和非同步系統的定義還沒那麼的明確). 但是這個方法在消息的傳遞的總量, 以及消息傳遞的輪數都非常的多, 因此性能不行. 這裡Byzantine 將軍問題最早的想法來自於航空業: 當一個飛機上的感測器捕獲一個錯誤信息的時候該怎麼辦(這裡的系統可以看成是同步系統).

在1986年, 關注一致性的問題和事務的問題的人們聚集起來. 在那個時候, 最好的一致性演算法就是上面提出的Byzantine Generals, 但是這個演算法用來處理事務時間開銷又太大. Jim Graw 在會議上發布了一篇文章 "A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem." (1987).

這篇論文包含了這樣一段話在開頭 :-)

"在這個會議之前, 大量的研究認為在分散式系統裡面的事務提交是一個退化版本的Byzantine 將軍問題. 可能這個會議最有用的結論是這兩個問題沒有任何的相關性"

最終分散式事務被看成了一個新版的一致性問題, 叫 uniform consensus ("Uniform consensus is harder than consensus" (2000)). 在uniform consensus 裡面, 所有的進程必須同意一個值, 包括哪些出錯的進程. 一個事務在當且僅當所有的RMs(資源管理者)已經準備好要提交的時候, 才能夠提交. 大部分的一致性只考慮到不出錯的進程達成一致. Uniform consensus考慮的是所有的進程都達成一致, 所以Uniform consensus 是更難實現的

最後 Lamport 在論文"The Part-Time Parliament" (submitted in 1990, published 1998).提出了Paxos一致性演算法. 不幸的是這篇論文用希臘明主投票做類比的寫法讓人們很難看懂, 所以這篇文章一直被忽略. 直到被Butler Lampson 在他的論文"How to Build a Highly Availability System using Consensus" (1996) 提起. 這篇論文介紹了如何使用Paxos來建立一個容錯的系統. 後來Lamport 才又發布了"Paxos Made Simple (2001)", 寫的讓大家都看的明白.

Paxos最核心的問題是, 給定一個固定數目的進程, 這些進程的大部分定義為至少和其他的這個進程的大部分有一個相同的進程. 比如: 有A, B, C三個進程. 那麼可能的這些進程大部分是AB, AC, BC. 如果有一個決定被某一個大部分通過, 比如AB. 那麼任意一個時刻一個大部分的集合包含A或者B. 這樣這些大部分的集合其它元素就可以從A, B那邊獲得這個決定的值.

Paxos能夠容忍信息丟失, 消息的延遲, 消息的重複發送以及消息的亂序到達. 如存在一個唯一一個在足夠長的時間內能夠對某一個大部分集合進行兩次訪問的Leader, 那麼這個系統就能達到一致. 任何進程, 包括Leader都可以失敗或者重啟. 實際上所有的進程允許在同一個時刻同時失敗, 這個時候這個演算法仍然是安全. 並且這個演算法容忍在某一個時候有多個主存在.

Paxos是一個解決非同步系統一致的演算法; 這裡並沒有嚴格的超時限定. 然而只有當這個非同步的系統表現出在同步的狀態的情況下, 這個系統才能夠達到一致. 在這個系統表現出在非同步的狀態的時候, 這個系統無法達成一致, 但是這個時候是安全的, 不會返回錯誤的結果. 有一個特殊的情形下Paxos是無法達成一致的, 這也是符合"FLP"的結論. 但是在實現的時候很容易避免這個情形.

明確的將系統分成同步和非同步有點太過寬泛. Dwork, Lynch 和 Stockmeyer定義了一個偏序的同步系統 "Consensus in the presence of partial synchrony" (1988). 存在兩個版本的偏序同步系統: 一種是進程運行在某一個固定的速度並且消息在某一個規定的時間內傳達, 但是這個某一個值是多少事先是不知道的. 另一種是進程運行的速度範圍以及消息送達的時間是事先可以知道的, 但是他們保持這種狀態僅僅是在未來的一段時間內, 這個時間有多長, 我們不知道. 比起同步系統和非同步系統, 這個偏序的同步系統更接近現實世界.網路在絕大部分的情況下應該是可預測的, 但是偶然還是會變的不可預測.

Lamport 和 Gray 在論文"Consensus on Transaction Commit" (2005)里繼續嘗試將Paxos應用到分散式事務系統里, 他們使用Paxos替換掉了兩階段提交裡面的Transtraction Manager, 並且對每一個Resource Manager使用一個Paxos實例用來判斷是否同意這個Resource Manager提交這個事務.表面上, 每一個Resource Manager 使用一個Paxos看過去成本特別高, 但是事實上不是的. 在沒有錯誤的情況下, Paxos提交在兩個階段就會完成. 它和兩階段提交有著相同的消息延遲, 雖然可能會多傳送一部分消息. 在有錯誤的情況下, Paxos的第三個階段是需要的, 這個和Skeen 的結論也是一致的. 給定2n + 1個TM副本, Paxos的提交可以容忍n個錯誤的副本. Paxos提交不需要用Paxos直接解決事務提交的問題. Paxos 沒有用來解決uniform consensus, 而是用來使這個系統容災能力更強.

因為兩階段提交是阻塞的是無效的, Paxos 提交忙於解決阻塞這個問題. 所以有些人認為分散式事務不應該被使用.

最近有一些關於CAP(Consistency, Availability, Partition)猜想的討論.這個猜想斷言你不可能在一個分散式系統裡面同時滿足這三個屬性, 也就是不存在一個系統, 它是一致的, 在有錯誤的進程存在並且有可能出現網路分區的情況下.

我們通過把Consistency 看成Consensus來檢查一下這個CAP猜想, 對於一個非同步系統, 根據FLP理論, 只要存在一個進程錯誤的情況下, 這個系統就無法達成一致. 所以對於一個非同步的系統我們不能同時有一致性和可用性.

現在我們再看一下一個有三個節點的Paxos系統:A, B, C. 加入有兩個節點在工作, 我們就能夠達到一致. 那麼我們就能實現一致性和可用性. 現在假如C被單獨隔離了, 而這個時候有請求訪問到C, 這個時候C是無法返回的, 因為必須有超過兩個節點才能夠返回結果, 而這個時候C無法和A, B節點通信的. C此刻是不知道是它自己被分區隔離了還是另外的兩個節點都掛掉了, 還是說這個時候的網路特別慢的問題. 另外的兩個節點能夠繼續的工作, 因為她們兩個能夠通信, 就可以超過半數的返回結果了. 所以對於CAP理論而言, Paxos並沒有分區容錯性, 因為這個時候C是無法對用戶的請求回應的. 然而我們在工程上繞過這個問題. 假如在同一個數據中心裏面, 我們可以使用兩個獨立的網路連接不同的節點, 因為Paxos可以容忍數據的重複發送.

對於一個同步的網路,假如C被分區了, 假如C在規定的周期內沒有收到信息, 那麼C能夠知道它自己被分區了. 然後C就能夠從客戶端的訪問中摘除掉了.

Paxos, Paxos Commit 和 HTTP/REST 已經被合併起來建立一個高可用的同配置網格計算系統. 詳細的信息可以從這裡獲得HARC, 以及更多的在這個文章裡面的討論"Co-Allocation, Fault Tolerance and Grid Computing" (2006).

[1] research.microsoft.com/

[2] research.microsoft.com/

[3] cs.cornell.edu/courses/

[4] theory.lcs.mit.edu/tds/

[5] research.microsoft.com/

[6] research.microsoft.com/

[7] infoscience.epfl.ch/get

[8] research.microsoft.com/

[9] research.microsoft.com/

[10] research.microsoft.com/

[11] theory.lcs.mit.edu/tds/

[12] research.microsoft.com/

[13] cct.lsu.edu/%7Emaclaren

[14] allhands.org.uk/2006/pr


推薦閱讀：

※關於一致性協議的一些對比和總結
※Atlas: Baidu分散式存儲系統
※CockroachDB和TiDB中的Multi Raft Group是如何實現的?
※raft協議疑問？
※分散式一致性演算法是如何解決少數派節點的寫順序一致性問題的?

TAG:分布式一致性 | 分布式系统 | 分布式存储 |