• 這是一段關于一致性，事務以及兩階段提交的歷史的描述
• 閱讀關于一致性的文獻可能會有些困難，因為：
  • 各種用語在不斷的演化著(比如一致性<consensus>最初叫做協(xié)商<agreement>)；
  • 各種研究成果并不是以一種邏輯性的順序產(chǎn)生出來；
  • 同時描述整個分布式算法的框架與這些研究工作又是平行地演化著；
  • 此外除了Lynch的《分布式算法》外，很少有書籍涉及到這個主題
• 下面涉及的這些論文不是按照它們的發(fā)表順序來進行介紹，而是盡量以最容易理解的方式來組織
• 所知道的第一個一致性問題實例應該是Lamport的“Time, Clocks and the Ordering of Events in a Distributed System” (1978),盡管它并沒有明確的提出一致性(consensus)或者協(xié)商(agreement)的概念
• 在這篇論文里，Lamport討論了消息如何在有限的時間內(nèi)在不同處理器之間傳輸，同時還利用愛因斯坦的狹義相對論進行了有趣的比喻
• 早在1978年，Lamport就采用時空圖給出了一個完整的全方位的分析
• 關鍵問題在于，在一個分布式系統(tǒng)中，你無法判斷事件A是否發(fā)生在事件B之前，除非A和B存在某種依賴關系
• 每個觀察者都可能看到不同的事件發(fā)生序列，除非這些事件相互之間存在依賴關系，即分布式系統(tǒng)中的事件僅僅是部分有序的
• Lamport定義了一個稱為”發(fā)生在前”的關系和操作符，然后又給出了一個算法，用來確定分布式系統(tǒng)中的事件的全序關系，這樣所有的進程就可以看到與其他進程一樣的事件排序
• 同時，Lamport還提出了分布式狀態(tài)機的概念：
  • 讓一組確定性狀態(tài)機從相同的初始狀態(tài)開始，之后保證它們以相同的順序處理相同的消息
  • 這樣就可以保證每個狀態(tài)機都是其他狀態(tài)機的一個副本
  • 關鍵的問題就是讓每個狀態(tài)機在“哪個消息是下一個需要處理的消息”這個問題上達成一致，這就是一個一致性問題
  • 這就是一個創(chuàng)建事件排列的算法所需要做的，提供一個關于消息傳輸順序的統(tǒng)一約定
  • 然而，這個系統(tǒng)并不是容錯的，如果一個進程出錯，其他進程將無限等待下去直到它恢復
• 大概在這篇論文發(fā)表的同一時間，JimGray在“Notes on Database Operating Systems” (1979)中描述了兩階段提交(2PC)
• 不幸的是，如果事務管理器在某個錯誤的時間點失敗的話，2PC就會被阻塞
• Dale Skeen在“NonBlocking Commit Protocols” (1981)中指出，對于一個分布式系統(tǒng)，需要3階段的提交算法來避免2PC中的阻塞問題
• 問題關鍵在于找到一個好的3PC算法，這已花費了將近25年
• Fischer, Lynch 和 Paterson在“Impossibility of distributed consensus with one faulty process” (1985)中指出對于一個異步系統(tǒng)來說即使只有一個進程出錯，分布式一致性也是不可能達到的，這就是著名的FLP結(jié)論
• 直到此時，consensus才成為“讓一系列處理器在一個value上達成共識的”這一問題的叫法
• 在一個具有完美網(wǎng)絡(所有的消息都會被傳輸，按序到達，不會重復)的異步系統(tǒng)(處理器以任意的速率運行，處理器間的消息傳輸可能花費任意時長)中，只要有一個出錯進程(即使只有一次故障)分布式一致性就是不可能的
• 問題的核心在于，你無法區(qū)分一個進程到底是終止了還是正在以極低的速度執(zhí)行，這使得在異步系統(tǒng)中的錯誤處理幾乎是不可能的
• 此外這篇論文的重要性還在于它展示了如何證明某些事情是不可能的：首先證明解決該問題的算法都必須滿足一些屬性，然后證明滿足這些屬性是不可能的，比如通過反證法證明(這種方法曾經(jīng)被圖靈用于停機問題的證明中)
• 此時，人們意識到一個分布式算法具有兩個屬性：安全性(safety)和活性(liveness)
• 安全性意味著壞的事情不會發(fā)生，而活性意味著某些好的事情最終一定會發(fā)生
• 2PC作為一個一致性算法，用來保證所有的進程在“事務要么提交要么失敗退出”上達成一致
• 2PC是安全的，不會有壞的數(shù)據(jù)被寫入到數(shù)據(jù)庫，但是它的活性并不好：如果事務管理器在一個錯誤的點上失敗，那么系統(tǒng)會阻塞
• 也是在此時，人們意識到可以將一個分布式系統(tǒng)分為同步的(進程以已知的速率運行，消息會在限制的時間內(nèi)傳輸)和異步的(進程以未知的任意的速率運行，消息的傳輸時間沒有上界)
• 異步與同步相比，是一種更通用的情況
• 一個適用于異步系統(tǒng)的算法，也能被用于同步系統(tǒng)，但是反過來并不成立
• 你可以將同步系統(tǒng)看做是異步系統(tǒng)的一個特殊情況，只是消息傳輸時間恰好有個上界
• 在FLP之前，還有這樣一篇論文“The Byzantine Generals Problem” (1982)
• 在這種形式的一致性問題中，進程還可能會說謊，而且它們還會盡力地去欺騙其他進程
• 這個問題看起來比FLP更難，但是對于同步的情況它確實存在一個解(盡管當這篇論文發(fā)表的時候，同步和異步系統(tǒng)的區(qū)分還沒有明確提出)
• 但是這個解代價很高，需要大量多輪的消息傳遞
• 這個問題最初來源于航天工業(yè)：如果飛機上的傳感器給出錯誤的信息會怎么樣呢？(很明顯，這個系統(tǒng)被認為是同步的)
• 在1986年，分布式系統(tǒng)領域關注一致性和事務的人們聚在了一起
• 在那個時候，最好的一致性算法就是Byzantine Generals，但是這個算法代價太高而無法用于事務處理
• 關于這場會議JimGray寫了一篇文章“A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem.” (1987)，這篇論文的導引里有如下的語句：
• “在這次會議之前，人們普遍認為分布式系統(tǒng)中的事務提交問題是拜占庭將軍問題的一個退化版本；或許這次會議的最大意義在于指出二者很少有共同點”
• 最終，分布式事務被認為是一個新的一致性問題，稱為uniform consensus (參見“Uniform consensus is harder than consensus” (2000))
• 在uniform consensus中，所有的進程都必須在一個value上達成一致，即使是那些出錯的進程
• 一個事務當且僅當所有的RM都準備好提交時才會被提交
• 而大多數(shù)的一致性問題只關注那些沒有出錯的進程可以達到一致
• 因此，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)中重新提到這個算法
• 這篇論文對如何構(gòu)建容錯系統(tǒng)和Paxos進行了很好的介紹
• 后來Lamport又發(fā)表了“Paxos Made Simple (2001)
• Paxos的核心是：給定固定數(shù)目的進程，任何一個多數(shù)者集合與其他的多數(shù)者集合必然至少存在一個公共元素
• 比如給定三個元素A，B和C
• 那么可能的多數(shù)者集合是AB, AC, 或者 BC
• 當一個決定由其中一個多數(shù)者集合比如AB通過時，那么在以后的任何時刻其他的多數(shù)者集合中至少有一個元素能夠記住之前的多數(shù)者集合做出的決定
• 比如對于多數(shù)者集合AB，那么A，B會記住決定，對于AC，A會記得，對于BC，B還記得
• Paxos可以容忍消息的丟失，延遲，重傳和亂序
• 只要存在一個leader可以跟進程中的一個多數(shù)者集合會話兩次，就能達到一致性
• 任何進程，包括leader在內(nèi)，都可以失敗或重啟，實際上所有的進程可以在同一時間失敗掉，而算法仍然是安全的
• 同一時間，可能有不止一個leader
• Paxos是一個異步算法，沒有顯式的超時設置
• 然而只有當系統(tǒng)表現(xiàn)出同步的方式時，它才能達到一致性
• 比如消息要在一定的時間內(nèi)傳輸
• 根據(jù)FLP結(jié)論，存在一種病態(tài)的情況，Paxos在這種情況下無法達到一致性，但是在實際中避免出現(xiàn)這種情況相對容易些
• 將一個系統(tǒng)簡單的劃分為同步異步有些寬泛
• Dwork, Lynch 和 Stockmeyer在“Consensus in the presence of partial synchrony” (1988)中定義了部分同步系統(tǒng)
• 存在兩種類型的部分同步系統(tǒng)：其中一種情況是進程以給定邊界內(nèi)的速率運行，消息傳輸時間是有界的，但是邊界的實際取值事先無法得知；
• 另一種情況是處理速度的邊界以及消息傳輸上界事先已知，但是只在未來的某個未知時間才開始成立
• 對于現(xiàn)實世界來說，部分同步模型是一個比同步異步模型更好的模型
• 大部分時間網(wǎng)絡行為都是以一種可預測的方式發(fā)生，但是可能突然會變得很瘋狂
• 在“Consensus on Transaction Commit” (2005)中，Lamport和Jim Gray將Paxos應用在分布式事務提交問題中
• 他們使用Paxos來對2PC中的事務管理器進行高效的備份
• 對于事務中涉及的每個RM使用一個Paxos的實例來決定該RM(resource manager,實際上就是該事務涉及的進程)是否提交該事務
• 在這里面，為每個RM使用一個Paxos實例看起來很昂貴，但是實際證明情況并不是這樣
• 對于沒有錯誤發(fā)生的情況下，Paxos提交可以通過兩個階段完成，與2PC相比盡管有更多的消息需要傳輸?shù)哂邢嗤南⒀舆t
• 只有當錯誤發(fā)生時，才需要第3個階段
• 給定2n+1個事務管理器，當錯誤副本數(shù)小于等于n時，Paxos提交都可以完成
• Paxos提交并沒有使用Paxos算法來直接解決事務提交問題，它并不是用來解決uniform consensus，而是用來讓系統(tǒng)容錯
• 有一種觀點認為分布式事務不應該被使用，因為2PC是阻塞失效的
• Paxos提交就是用來解決阻塞的問題
• 有一些關于CAP(Consistency(一致性), Availability(可用性) 和 Partition tolerance(分區(qū)容錯性))猜想的討論
• 這個猜想指出，在分布式系統(tǒng)中，無法同時滿足上述三個屬性(即在分布式系統(tǒng)的設計中，無法同時滿足對數(shù)據(jù)的實時一致性要求、完全無故障的可用性以及分區(qū)容錯性)
• 我們可以將Consistency等同于consensus(共識)來檢驗下CAP
• 根據(jù)FLP結(jié)論，在一個異步系統(tǒng)中，當出現(xiàn)一個出錯進程時，無法達到consensus
• 所以對于一個異步系統(tǒng)來說，我們無法同時得到Consistency和Availability(在網(wǎng)絡分區(qū)(網(wǎng)絡故障)的情況下，系統(tǒng)需要在可用性和一致性之間作出選擇，即是選擇保持可用性而降低一致性，還是放棄一些可用性以維持一致性)
• 假設現(xiàn)在有一個包含三個節(jié)點A，B和C的Paxos系統(tǒng)
• 如果有2個節(jié)點在工作，我們就能達到一致性，即我們可以得到consistency 和 availability
• 現(xiàn)在如果C被分割，而且有查詢請求，它就會因無法與其他節(jié)點通信而無法響應{!這樣就不具有可用性了}
• 它無法判斷到底是自己被分割了，還是其他兩個節(jié)點down掉了，又或者是網(wǎng)速很慢
• 其他兩個節(jié)點可以正常進行，因為它們相互可以通信并形成一個多數(shù)者集合
• 所以對于CAP猜想，Paxos無法處理網(wǎng)絡分割，因為C無法對查詢做出響應
• 然而在工程上，我們可以繞過這個問題
• 假設我們處在一個數(shù)據(jù)中心內(nèi)部，可以使用兩套獨立網(wǎng)絡(Paxos并不介意出現(xiàn)重復消息)
• 如果我們是在因特網(wǎng)上，我們可以讓客戶端查詢所有的節(jié)點A，B，C
• 如果C被分割了，它可以查詢A或者B，除非它跟C一樣被分割了
• 對于一個同步網(wǎng)絡，如果C被分割了，如果它在一定的時間內(nèi)收不到消息就可以知道自己被分割了，因此能夠向客戶端聲明自己down掉了

文章來源地址http://www.zghlxwxcb.cn/news/detail-732857.html

到了這里，關于論文-分布式-共識，事務以及兩階段提交的歷史描述的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！