二階段提交

二階段提交(英語:Two-phase Commit)是指在電腦網絡以及資料庫領域內,為了使基於分散式系統架構下的所有節點在進行事務提交時保持一致性而設計的一種演算法。通常,二階段提交也被稱為是一種協定(Protocol)。在分散式系統中,每個節點雖然可以知曉自己的操作時成功或者失敗,卻無法知道其他節點的操作的成功或失敗。當一個事務跨越多個節點時,為了保持事務的ACID特性,需要引入一個作為協調者的組件來統一掌控所有節點(稱作參與者)的操作結果並最終指示這些節點是否要把操作結果進行真正的提交(比如將更新後的數據寫入磁碟等等)。因此,二階段提交的演算法思路可以概括為: 參與者將操作成敗通知協調者,再由協調者根據所有參與者的反饋情報決定各參與者是否要提交操作還是中止操作。

需要注意的是,二階段提交(英語:2PC)不應該與並行控制中的二階段鎖(英語:2PL)混淆。

前提

二階段提交演算法的成立基於以下假設:

  1. 該分散式系統中,存在一個節點作為協調者Coordinator),其他節點作為參與者Participants)。且節點之間可以進行網絡通訊。
  2. 所有節點都採用預寫式紀錄檔,且紀錄檔被寫入後即被保持在可靠的儲存裝置上,即使節點損壞不會導致紀錄檔數據的消失。
  3. 所有節點不會永久性損壞,即使損壞後仍然可以恢復。

基本演算法

以下對二階段提交演算法分階段進行說明。

第一階段(提交請求)

  1. 協調者節點向所有參與者節點詢問是否可以執行提交操作,並開始等待各參與者節點的響應。
  2. 參與者節點執行詢問發起為止的所有事務操作,並將Undo資訊Redo資訊英語redo log寫入紀錄檔。
  3. 各參與者節點響應協調者節點發起的詢問。如果參與者節點的事務操作實際執行成功,則它返回一個"同意"訊息;如果參與者節點的事務操作實際執行失敗,則它返回一個"中止"訊息。

有時候,第一階段也被稱作投票階段,即各參與者投票是否要繼續接下來的提交操作。

第二階段(提交執行階段)

成功

當協調者節點從所有參與者節點獲得的響應訊息都為"同意"時:

  1. 協調者節點向所有參與者節點發出"正式提交"的請求。
  2. 參與者節點正式完成操作,並釋放在整個事務期間內佔用的資源。
  3. 參與者節點向協調者節點傳送"完成"訊息。
  4. 協調者節點收到所有參與者節點反饋的"完成"訊息後,完成事務。

失敗

如果任一參與者節點在第一階段返回的響應訊息為"終止",或者協調者節點在第一階段的詢問逾時之前無法取得所有參與者節點的響應訊息時:

  1. 協調者節點向所有參與者節點發出"轉返操作"的請求。
  2. 參與者節點利用之前寫入的Undo資訊執行轉返,並釋放在整個事務期間內佔用的資源。
  3. 參與者節點向協調者節點傳送"轉返完成"訊息。
  4. 協調者節點收到所有參與者節點反饋的"轉返完成"訊息後,取消事務。

有時候,第二階段也被稱作完成階段,因為無論結果怎樣,協調者都必須在此階段結束當前事務。

演算法示意

下述流程圖簡單示意了二階段提交演算法中協調者和參與者之間的通訊流程

    協調者                                              參與者
                              QUERY TO COMMIT
                -------------------------------->
                              VOTE YES/NO           prepare*/abort*
                <-------------------------------
commit*/abort*                COMMIT/ROLLBACK
                -------------------------------->
                              ACKNOWLEDGMENT        commit*/abort*
                <--------------------------------  
end

"*" 所標記的操作意味着此類操作必須記錄在穩固儲存英語Stable storage上.[1]

缺點

二階段提交演算法的最大缺點就在於它的執行過程中間,節點都處於阻塞狀態。即節點之間在等待對方的響應訊息時,它將什麼也做不了。特別是,當一個節點在已經佔有了某項資源的情況下,為了等待其他節點的響應訊息而陷入阻塞狀態時,當第三個節點嘗試訪問該節點佔有的資源時,這個節點也將連帶陷入阻塞狀態。

另外,協調者節點指示參與者節點進行提交等操作時,如有參與者節點出現了崩潰等情況而導致協調者始終無法取得所有參與者的響應資訊,這時協調者將只能依賴協調者自身的逾時機制來生效。但往往逾時機制生效時,協調者都會指示參與者進行轉返操作。這樣的策略顯得比較保守。

二階段協定的實現

通用架構

一般情況下,2PC協定都應用在分散式電腦網絡中。通過實現多個相同的2PC組件,可以實現一個分散式的協定。該組件一般稱為事務處理器 (TMs,或者2PC代理以及事務處理監視器),該組件負責推進各事務節點執行協定(例如X/Open XA)。分散式事務內的涉及的所有資料庫,包括參與者、協調者均註冊到附近的TMs(一般和事務參與者處於相同的網絡節點中),從而可以通過2PC來完成相關事務。每一個分散式事務都屬於他們所註冊的TMs。每一個事務都有一個領導者,即協調者TM,用來管理2PC協定。基於效能和可靠性考慮,協調者角色可以轉移到其他的TM節點上。各參與者之間並不直接進行協定通訊,參與者只會和協調者進行訊息通訊,由協調者負責推進各參與者執行協定。通過這種架構,該協定完全是分散式的(因為不依賴任何中心節點或者數據結構),也可以根據業務規模橫向擴充。 這種通用架構對於除了2PC的其他分散式原子提交協定也是適用的,因為所有此類協定都使用相同的投票機制,並將結果廣播給協定的參與者。[2][3]

協定最佳化

通過假設一些特定的系統行為,可以實現一些方案來最佳化協定[2][3][4]。既能夠獲得兩階段提交協定的收益,同時能夠減少協定操作所消耗的時間。

假定轉返和假定提交

樹型二階段提交協定

關聯條目

參照

  1. ^ C. Mohan, Bruce Lindsay and R. Obermarck (1986): "Transaction management in the R* distributed database management system"頁面存檔備份,存於互聯網檔案館),ACM Transactions on Database Systems (TODS), Volume 11 Issue 4, Dec. 1986, Pages 378 - 396
  2. ^ 2.0 2.1 Hadzilacos, Vassos; Goodman, Nathan. Concurrency control and recovery in database systems. Reading, Mass.: Addison-Wesley Pub. Co. 1987. ISBN 0-201-10715-5. OCLC 13793504. 
  3. ^ 3.0 3.1 Vossen, Gottfried. "Transactional Information Systems". San Francisco: Morgan Kaufmann. 2002. ISBN 0-585-45682-8. OCLC 52610193. 
  4. ^ Philip A. Bernstein, Eric Newcomer (2009): Principles of Transaction Processing, 2nd Edition 互聯網檔案館存檔,存檔日期2010-08-07., Chapter 8, Morgan Kaufmann (Elsevier), ISBN 978-1-55860-623-4