分布式數據庫系統及其應用2021年11月——2021年1月分布式數據庫的可靠性的概念及其度量分布式數據庫系統的故障原因和容錯技術分布式數據庫的可靠性協議網絡分割和提交協議不一致性監測和解決方法分布式數據庫中的可靠性

第6章可靠性指數據庫在一給定時間間隔內不產生任何失敗的概率。它強調數據庫的正確性，要求數據庫正確運行，既符合某種規格化要求。通常用來描述不可修復的系統。可用性強調的是當需要訪問數據庫時，它是可用的。指在給定的時間t，數據庫按照說明能正常運行的概率。通常用于描述那些可以修復的系統。兩者關系通常認為構建可用性的系統比可靠性的系統容易；兩者是統一的，可靠性高的系統可用性自然是好的；兩者又是矛盾的，增加錯誤風險的情況下，可提高可用性；采用太謹慎的策略會降低可用性。1.1分布式數據庫可靠性概念1分布式數據庫可靠性概念及其度量例:Site1Site2x1x2Lockx1Lockx22PC

Ready故障出現Site1也Ready故CommitSite2等待此時站點2有兩種可能策略:策略一：以正確性為標準，x2保持在鎖定狀態,直到故障修復時為止。提高了可靠性，但犧牲了可用性。策略二：在數據庫中引入不一致性的風險下盡量提高可用性，解鎖x2,其它事務可以使用它的值。兩階段提交協議實現了第一個策略，犧牲可用性獲得高可靠性；如果要得到高可用性，就要考慮使用第二個策略。Site1正常結束1.1分布式數據庫可靠性概念1分布式數據庫可靠性概念及其度量：x1和x2是x的副本；事務T是更新x的事務；Site1是協調站點且是事務T原發站點；遵守兩階段提交協議。通常使用兩個參數的指標來度量一個分布式數據庫的可靠性程度：平均故障間隔時間MTBF和平均修復時間MTTR。平均故障間隔時間MTBF指在可以自我修復的系統中相繼失敗之間的期望時間；通過可靠性函數R(t)來計算MTBF=∫0∞R(t)dt可靠性函數R(t)與系統失敗的概率有直接的關系。平均修復時間MTTR是指修復一個失敗的系統所需要的期望時間。它與失敗概率有關指數型失敗和修復的概率的系統可用性可以描述為：

A=MTBF/(MTBF+MTTR)1.2平均故障間隔時間和平均修復時間1分布式數據庫可靠性概念及其度量可用性系統5個9〔99.999%〕常用來描述可用性系統；建立一個高可用性系統比建立一個通常要求的系統要花費更高的本錢(時間、人力、財力等)。具體設計時要仔細分析，與最終用戶商定，以確定用戶可以忍受多長的停機時間，以及停機可能造成的影響，并且明確說明高可用性系統的本錢。1.2平均故障間隔時間和平均修復時間1分布式數據庫可靠性概念及其度量故障任何偏離標準說明的行為稱為故障。軟故障和硬故障軟故障包括間歇性〔intermittent〕和瞬變性〔transient〕故障，通過重啟動來修復；硬故障指永久性故障,錯誤設計等。2.1系統失敗的原因2分布式數據庫系統的故障原因和容錯技術軟故障占90%以上并且該比例穩定67年，美空軍指出計算機中電子器件故障80%是間歇性的67年，IBM指出90%故障是間歇性的80年，研究指出軟故障的發生明顯高于硬故障87年，Gray指出大局部軟件故障是瞬變性故障軟件故障通信或數據庫的原因是產生軟件故障的主要原因。軟件故障的典型原因是代碼中的Bug,曾有報告指出,1000條指令中,0.25-10個BUG。軟件故障難以排除，一個典型的軟件工程在到達測試階段以前，要經過大量的設計審查和代碼檢驗。審查不同計算機系統中出錯的統計數據IBM/XA的OS可靠性報告57%是硬件,12%軟件,14%操作,7%環境〔斯坦福線性加速器SLAC〕Tandem計算機18%硬件25%軟件25%維護17%操作,14%環境AT&T5ESS數字交換機32.3%硬件,44.3%軟件,17.5%操作2.1系統失敗的原因2分布式數據庫系統的故障原因和容錯技術永久性故障錯誤的設計不穩定或者臨界的組件不穩定的外部環境操作者的過失系統失敗永久性錯誤間歇性錯誤瞬變的錯誤系統失敗的原因容錯設計出一種使系統識別出可能會發生的錯誤的方法。在系統中建立一種機制，使錯誤在造成系統故障之前就會被檢測出來，并能被去除或得到補償。錯誤預防技術保證所實現的系統不包含任何錯誤。錯誤預防有兩個方面：錯誤回避：保證系統不會帶入錯誤的技術〔詳細的設計方法學和質量控制〕錯誤去除：清查那些在使用了錯誤回避技術路線后還殘留在系統中的錯誤，并去除它們〔需要大量的測試和證實過程〕2.2基本容錯方法和技術2分布式數據庫系統的故障原因和容錯技術故障檢測潛伏的故障：故障發生一段時間后才被檢測出來；錯誤潛伏期：從故障發生到被檢測出來的時間；平均檢測時間(MTTD)：平均錯誤潛伏時間；平均修復時間(MTTR)：修復一個失敗的系統所需要的期望時間；平均故障間隔時間(MTBF)：在可以自我修復的系統中相繼的失敗之間的期望時間,由經驗或從可靠性函數計算。2.2基本容錯方法和技術2分布式數據庫系統的故障原因和容錯技術

MTBF

MTTDMTTR在這段時間內，可能發生多起錯誤故障發生造成錯誤檢測到錯誤修復故障發生造成錯誤時間

相繼發生的事件2.2基本容錯方法和技術2分布式數據庫系統的故障原因和容錯技術冗余所有容錯系統設計中都采用的根本原那么是在系統的組件中提供冗余。對冗余的附加和補充的容錯原那么是設計的模塊化。模塊化系統的每個組件被設計為具有定義很好的輸入/輸出接口的模塊。模塊化可以把故障隔離在單一的組件中。容錯系統實現故障-停止模塊〔fail-stopmodule)進程對〔Processpairs)2.2基本容錯方法和技術2分布式數據庫系統的故障原因和容錯技術time正常 停止 恢復 正常易失存儲喪失穩定存儲ok故障-停止模塊不斷地對自身進行檢測，當檢測到一個故障時，就自動停止。優點是縮短了故障檢測的潛伏期。2.2基本容錯方法和技術2分布式數據庫系統的故障原因和容錯技術進程對〔Processpairs)通過軟件模塊的雙工來實現容錯。它的思想是通過兩個相互通信和合作的進程，完成系統的每一個效勞的方法來減少單個的故障點。這兩個進程中的一個叫做主進程，另外一個叫備份進程，它們同時提供同樣的效勞，主進程與備份進程都是基于故障-停止模塊實現。進程對機制要求進程之間進行通信，可以通過共享存儲區的手段來實現進程之間的通信。當設計一個可靠的軟件環境時，使用基于消息傳送的通信機制來實現一個操作系統是非常重要的。由于每個進程都在自己的地址區間內執行，一個進程可能發生的錯誤就不會傳播到另外一個進程，這種方法可以有效地進行錯誤隔離。2.2基本容錯方法和技術2分布式數據庫系統的故障原因和容錯技術目的分布式數據庫可靠性協議是為了保證在分布式數據庫上執行的分布式事務的原子性和持久性。這些協議描述了begin-transaction,read,write,abort,commit和recover原語的分布式執行過程。原語Begin_Transaction：該命令執行登記的功能；Read：該命令指定一個數據項；LRM先在Trans的緩沖區中讀，假設不在，那么向緩沖區管理器發Fetch命令，讀出數據后，LRM將它交給調度程序。Write：該命令指定了數據項和新值。假設在Buffer中得到，那么在那更新，否那么對BufferManager發Fetch命令，讀出數據并修改，同時數據的前像和修改后的后像寫入Log。Abort：該命令是異常終結事務處理失敗的一個信號。LTM讀取相應的事務處理日志，并且用數據項的前值取代在易變數據庫中的更新后的數據項的值。同時，調度程序被告知異常終結已經被成功地完成。Commit：該命令使LTM將一個事務處理結束記錄寫入日志中。3.1分布式數據庫可靠性協議的組成3分布式數據庫的可靠性協議分布式數據庫系統的可靠性協議組成包括提交協議、終結協議、恢復協議。提交和恢復協議詳細說明了提交命令和恢復命令是如何被執行的。終結協議是分布式系統特有的協議。在執行一個分布式事務時，假設一個站點有故障，希望其它站點也停止該事務。處理這種情況的技術就稱為終結協議。3.3分布式數據庫可靠性協議的組成3分布式數據庫的可靠性協議終結協議與恢復協議的比較假假設一個站點失效終結協議確定了未失效站點如何處理該失效事件；恢復協議確定失效站點重啟動后，進程〔協調者，參與者〕恢復它的狀態的過程。網絡分割時終結協議采取必要的措施終結在不同網絡區間執行的活動事務；當網絡重新連接后，恢復協議保證使各個冗余數據庫相互一致。3.1分布式數據庫可靠性協議的組成3分布式數據庫的可靠性協議兩階段提交協議的要點:將本地原子性提交行為的效果擴展到分布式事務,保證分布式事務提交的原子性,在不損壞日志情況下,實現快速故障恢復，提高DDB系統的可靠性。兩階段提交協議把事務的提交過程分為兩個階段：第一階段：表決階段，即形成一個共同的決定。第二階段：執行階段，目的是實現這個決定。允許參與者單方面撤銷事務，直到做出肯定性的建議；一旦參與者確定了提交或者撤銷提議，它不能再更改它的提議；當參與者處于就緒狀態，根據協調者發出的消息的種類，它可轉換為相應的提交或者撤銷狀態；協調者依據全局提交規那么作出全局終結決定；在發生故障的情況下，協調者和參與者可能會進入互相等待的狀態，一般采用定時器來解決這種問題。每個進程進入一個狀態時都要設置定時器。如果所期待的消息在定時器超時之前沒有到來，定時器向進程報警，進程于是調用它自己的超時協議。3.2兩階段提交協議的演變3分布式數據庫的可靠性協議初始寫begin_commit到日志等待有要求撤消的？寫commit到日志提交寫end_of_trans.到日志初始準備提交？寫ready到日志就緒消息類型？寫abort到日志寫commit到日志提交撤消撤消寫abort到日志寫abort到日志協調者參與者nonoabortcommit發送準備消息發送“建議撤消〞消息發送“建議提交〞消息發送“全局撤消〞消息發送“全局提交〞消息ACK發送〞應答ACK確認〞消息兩階段提交協議的活動yesyes假定撤銷2PC和假定提交2PC協議這兩種協議的根本思想是：只要當一個已就緒的參與者向協調者詢問事務的結果時，如果在協調者的日志中找不到該事務的任何信息，就認為該事務“被撤銷〞(對假定撤銷2PC協議)或“已經提交〞(對假定提交2PC協議)。目的是改善2PC的性能；假定撤銷2PC協議中，協調者不必等待參與者的ACK消息，減少了協調者與參與者之間傳遞消息的數量；當使用假定撤銷2PC協議時，可以看出協調者在決定撤銷后，可以立即忘記該事務。它可以寫入撤銷記錄，且不用等待參與者確認撤銷命令。寫入撤銷記錄后，協調者無需寫入事務結束記錄。3.2兩階段提交協議的演變3分布式數據庫的可靠性協議假定撤銷2PC和假定提交2PC協議假定提交2PC協議中，可以不將Prepare寫入Log，減少了Log寫入的次數；如果使用假定提交2PC協議，協調者在發送準備消息之前，強制性寫入一條收集記錄，它包含了參與執行事務的所有參與者的名字，此時協調者進入收集狀態。隨后協調者發送準備消息并進入等待狀態。當參與者收到準備消息后，以“建議撤銷〞或者以“建議提交〞消息響應。當協調者收到所有參與者的決定后，它就可以作出該事務是撤銷或提交的決定。如果斷定撤銷，協調者寫入撤銷記錄，進入撤銷狀態，并發送“全局撤銷〞命令，直到協調者收到參與者的撤銷確認，就寫入一條結束記錄，并忘記該事務。如果它決定提交該事務，就寫入提交記錄，發送“全局提交〞消息，然后忘記該事務。當參與者收到“全局提交〞消息后，它們寫入提交記錄，并更新數據庫。如果參與者收到“全局撤銷〞消息，它們寫入撤銷記錄并確認。3.2兩階段提交協議的演變3分布式數據庫的可靠性協議事務阻斷：某個站點上本來可以終結〔提交或撤銷〕的子事務，由于分布式數據庫系統的故障，它必須等到有故障的子事務修復后，取得必要的信息才能決定。故障的恢復是不可預料，所以它占有的資源也不能釋放，也沒法繼續執行，此時稱該事務處于事務阻斷狀態。阻斷協議：提交協議稱為阻斷協議是指發生某類故障時，使分布式事務可能處于阻斷狀態。在兩階段提交協議中，如果在提交階段協調者出故障，假設某個參與者與此同時宣布其已就緒提交，它必須等到協調者修復后，才能決定是否提交。在這種情況下，兩階段提交協議是阻斷協議。事務阻斷降低了系統的可用性，因為它們持有的鎖不能被釋放。3.3事務阻斷與終結協議3分布式數據庫的可靠性協議終結協議：允許一事務在有故障情況下仍能正確地結束。它提高系統的可用性。當正常的提交過程被故障中斷時，就調用終結協議，使無故障的站點正確地終結該事務。終結的可能類型(提交還是撤銷)依賴于當事務被故障中斷時提交協議使它處于什么狀態。終結協議僅對某些類型的故障起作用，而不是對所有故障都起作用。3.3事務阻斷與終結協議3分布式數據庫的可靠性協議判斷2PC協議是終結協議的條件至少有一個站點已收到結果命令。此時，可由該站點告訴其它參與者關于該事務的結果，并由它們來終結該事務。沒有一個參與者曾收到過結果命令，并且只有協調者站點出故障。此時，所有參與者站點都是可工作的，參與者可以選舉一個新的協調者，然后繼續。沒有一個可工作的參與者曾收到此命令，并且至少有一個參與者出故障時，終結就不可能。因為可工作的參與者無法知道出故障的參與者它已干過什么，仍無法獨立作出決定。3.3事務阻斷與終結協議3分布式數據庫的可靠性協議終結協議在協調者和參與者的定時器超時時發揮作用。超時發生在目的站點在期望的時間內沒有從發送站點得到所期望的消息時。處理超時的方法依賴于失效發生的時間和失效的類型。因此需要考慮在兩階段提交協議執行時的不同時間發生失效的情況。由于使用兩階段提交協議的狀態轉換圖而使討論變得容易。狀態圖中，圓形表示狀態，邊表示狀態轉換，終結狀態用同心圓表示。邊的標號按如下方式解釋：橫線上方表示狀態轉換的原因，即所收到的消息；橫線下方表示狀態轉換時所發出的消息。3.42PC協議的終結協議3分布式數據庫的可靠性協議超時處理技術協調者超時：協調者可以在三種狀態中發生超時故障：等待狀態、提交狀態和撤銷狀態。在等待狀態超時：在等待狀態，協調者正在等待參與者的局部決定。協調者不能單方面提交事務，因為不滿足全局提交規那么。協調者可以決定“全局撤銷〞事務，此時，協調者在日志中寫入撤銷記錄，并向所有參與者發送“全局撤銷〞消息。在提交狀態或撤銷狀態發生超時：在這種情況下，協調者不能確定是否在所有參與者站點上本地恢復管理程序都執行完提交或撤銷過程。因此協調者重復發出“全局提交〞命令或“全局撤銷〞命令給沒有響應的站點，并等待確認。3.42PC協議的終結協議3分布式數據庫的可靠性協議初始寫begin_commit到日志等待有要求撤消的？寫commit到日志提交寫end_of_trans.到日志初始準備提交？寫ready到日志就緒消息類型？寫abort到日志寫commit到日志提交撤消撤消寫abort到日志寫abort到日志協調者參與者nonoabortcommit發送準備消息發送“建議撤消〞消息發送“建議提交〞消息發送“全局撤消〞消息發送“全局提交〞消息ACK發送〞應答ACK確認〞消息兩階段提交協議的活動yesyes協調者超時IWCAFcommit-申請申請-prepare*ack*-ack*-_t_abortanyabortanycommit_t_commit_t_abort*noabort*prepared*commit*t=timeout超時處理技術參與者超時〔被阻斷時出現〕在初始狀態發生超時：參與者在該狀態下正在等待“準備〞消息，此時協調者必然在初始狀態發生失效。參與者在超時后可以單方面撤銷事務。在就緒狀態發生超時：參與者在該狀態下正提議提交事務，但不知道協調者的全局決定，參與者不能單方面作出決定。由于它處于就緒狀態，它必須提議事務。因此，它不能改變它的決定和單方面撤銷。另一方面，它不能單方面決定提交事務，因為其他參與者可能提議撤銷。在這種情況下，參與者將保持阻斷，直到它從其他站點處了解到事務的最終命運。3.42PC協議的終結協議3分布式數據庫的可靠性協議初始寫begin_commit到日志等待有要求撤消的？寫commit到日志提交寫end_of_trans.到日志初始準備提交？寫ready到日志就緒消息類型？寫abort到日志寫commit到日志提交撤消撤消寫abort到日志寫abort到日志協調者參與者nonoabortcommit發送準備消息發送“建議撤消〞消息發送“建議提交〞消息發送“全局撤消〞消息發送“全局提交〞消息ACK發送〞應答ACK確認〞消息兩階段提交協議的活動yesyes參與者超時IRCA申請-prepareprepared等價于結束狀態_t_ping申請-preparenocommitackabortackcommitackabortack設計終結協議如果參與者之間能夠互相通信，可以設計一個更加分布的終結協議。超時的參與者只需簡單地請求其他參與者來幫助它作出決定。考慮：假定Pi是超時的參與者〔詢問Pj〕，其它參與者Pj按如下響應：Pj處于初始狀態，于是單方面Abort，并回送“建議abort〞給Pi；Pj處于就緒狀態，此時不能幫助Pi終結；Pj處于提交或撤銷狀態，此時向Pi發送“建議提交〞或“建議撤銷〞消息。3.42PC協議的終結協議3分布式數據庫的可靠性協議協調者站點失效協調者在初始狀態失效發生在協調者初始化提交過程之前。因此，它將在恢復時啟動提交過程。協調者在等待狀態失效這時協調者已經發送了“準備〞命令。恢復時，協調者將從頭開始啟動提交過程，再次發送“準備〞消息。協調者在提交狀態或撤銷狀態失效這時，協調者已經把它的決定通知了參與者，并終結了事務。在恢復時，如果它已經收到了所有確實認消息，就不需要做任何事情。否那么，就要啟動終結協議。3.52PC協議的恢復協議3分布式數據庫的可靠性協議參與者站點失效一個參與者在初始狀態失效在恢復時，該參與者應該單方面撤銷事務。一個參與者在就緒狀態失效這時協調者已經收到失效站點在失效前發送的肯定決定。恢復時，失效站點的參與者認為是在就緒狀態發生了超時，于是啟動終結協議來處理該事務。一個參與者在提交狀態或撤銷狀態失效這些狀態表示了終結條件，所以在恢復時，參與者不需要采取任何專門的措施。3.52PC協議的恢復協議3分布式數據庫的可靠性協議提交協議是非阻斷的充要條件是在其狀態轉換圖中不包含兩種情形:沒有狀態是即與提交狀態又與撤銷狀態“相鄰〞；不存在不可提交狀態是與提交狀態“相鄰〞；相鄰指從一個狀態經過一次轉換就可以到達的另一個狀態。3.6三階段提交協議3分布式數據庫的可靠性協議2PC中的狀態如果任意一個進程處于提交狀態，就知道所有站點都已建議提交事務，這些狀態稱為可提交的。C(提交)狀態是可提交狀態,其它為不可提交狀態。就緒狀態是不可提交狀態，由于一個進程處于此狀態并不意味著所有進程都已建議提交事務，所以它是不可提交的。等待狀態是不可提交狀態。它們都侵犯了非阻斷協議的充要條件,從而考慮改變2PC,使其滿足非阻斷協議條件。在等待狀態和提交狀態之間,或者在就緒狀態和提交狀態之間增加另一種狀態作為緩沖狀態,用于在準備提交但還沒有提交的時候，從初始狀態到提交狀態之間有三次狀態轉換，從而有了3PC協議。3.6三階段提交協議3分布式數據庫的可靠性協議IWACcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort3PC中事務的狀態轉換圖PCPCready-to-commitglobal-commitglobal-commitACK(a)協調者(b)參與者協調者參與者初始寫begin_commit到日志等待有要求撤消的？寫Prepare-to-commit到日志準備提交寫end_of_trans.到日志初始準備提交？寫ready到日志就緒消息類型？寫abort到日志寫prepare-to-commit到日志準備提交撤消撤消寫abort到日志寫abort到日志準備撤消提交全局撤消準備提交ACKACK

nonoabortPrepare-to-commit寫commit到日志提交提交寫commit到日志撤消提交準備提交

在中事務執行的過程3PC協調者超時在等待狀態超時：與2PC中協調者在等待超時相同,協調者單方面決定撤銷事務，然后它在日志中寫入撤銷記錄，向所有建議提交事務的參與者發送“全局撤銷〞消息。在預備提交狀態超時：此時協調者不知道未響應的參與者是否已經轉換到預備提交狀態。但它知道它們至少處于就緒狀態，這意味著它們一定已經建議提交事務。因此協調者可以發送“預備提交〞消息使所有參與者轉換到預備提交狀態，再將提交記錄寫入日志，并發送“全局提交〞消息給所有可操作的參與者。在提交/撤銷狀態超時：協調者不知參與者是否已確實執行了提交(撤銷)命令，但是它們至少處于預備提交狀態。因此協調者不需要做專門的處理。3.7三階段提交協議的超時處理3分布式數據庫的可靠性協議參與者超時在初始狀態超時：與2PC中的情況相同。在就緒狀態超時：參與者已經建議提交事務，但不知道協調者的全局決定。由于與協調者失去聯系，終結協議將選舉一個新的協調者，新協調者根據三階段提交協議的終結協議終結事務。在預備提交狀態超時：參與者已收到“預備提交Prepare-to-commit〞消息,正在等待來自協調者的“全局提交〞消息,處理同第二條。3.7三階段提交協議的超時處理3分布式數據庫的可靠性協議協調者參與者PREPAREPREPAREDCOMMITPRECOMMITACK1.等待超時:撤銷事務3.提交/撤銷超時:

忽略1.初始超時:

撤銷事務2.就緒超時:

終結協議3.預備提交超時:

終結協議2.預備提交超時:把參與者移入預備提交終結協議規那么新協調者在等待狀態：將全局撤銷事務。此時參與者可能處于初始狀態、就緒狀態、撤銷狀態或預備提交狀態等任何狀態。假設參與者處于預備提交狀態，正在等待“全局提交〞消息，但它們卻收到“全局撤銷〞消息。它們的狀態轉換圖不存在從預備提交狀態到撤銷狀態的轉換，而這種轉換對于終結協議是必需的，所以該轉換應當是執行終結協議時的一種合法轉換。新協調者處于預備提交狀態：此時參與者可以處于就緒狀態、預備提交狀態或提交狀態。沒有參與者可能處于撤銷狀態。協調者因此將全局提交事務,并發送“全局提交〞消息。新協調者處于撤銷狀態：收到第一個消息后，參與者也都轉換到撤銷狀態。3.8三階段提交協議的終結協議3分布式數據庫的可靠性協議3PC與2PC恢復協議的差異很小協調者在等待狀態失效按照終結協議，參與者已終結事務,因此,協調者在恢復時必須向它們詢問以確定如何終結事務。協調者在預備提交狀態失效終結協議再一次指導可操作參與者終結事務。由于此過程可從預備提交狀態轉換到撤銷狀態，協調者必須詢問以確定如何終結事務。一個參與者在預備提交狀態失效它必須詢問以確定其它參與者如何終結事務。3.9三階段提交協議的恢復協議3分布式數據庫的可靠性協議三階段提交協議的一個特性：使用三階段提交協議，能夠無阻斷地終結事務。網絡分割是由通信線路故障引起的簡單分割，僅僅是網絡分裂成兩局部多重分割，更復雜網絡分割非阻斷協議的存在性即在發生網絡分割時,是否存在允許獨立恢復的協議獨立恢復是指站點重啟動時,無需遠程訪問假設存在處理分割的非阻斷協議,那么,該協議可使某個分割中的站點到達終結決定,而且這個決定與另一分割中的決定一致一般結論獨立恢復協議只存在于單站點故障的情形假設發生網絡分割的時候,丟了報文的話,那么不存在任何非阻斷的協議能從網絡分割故障中恢復4.1網絡分割概述4網絡分割與提交協議非冗余數據庫任何需要訪問存儲在另一網絡區域里的數據項的新事務都被阻斷,等待網絡修復位于同一區域里的數據項的并發訪問由并發控制算法處理網絡分割時由提交協議處理冗余數據庫分割時,副本可能位于不同的區域由復制協議處理4.1網絡分割概述4網絡分割與提交協議網絡分割處理策略一致性與可用性的選擇非冗余數據庫處理網絡分割的終結協議集中式協議，基于集中式并發控制算法(主站點法和主副本法)基于表決的協議冗余數據庫處理網絡分割的終結協議復制控制協議4.1網絡分割概述4網絡分割與提交協議多數法和基于法定人數法在事務中止或提交前,大多數站點必須一致同意中止或提交基于法定人數的規那么每個站點i有選票數Vi,Vi是正整數V=Vi事務在提交前，它必須獲得提交法定票數Vc事務在Abort前，它必須獲得Abort法定票數VaVa+Vc≤V,當0≤Va,Vc≤Vni=14.2基于表決的協議4網絡分割與提交協議網絡分割時,在每個分割局部選擇一個新的協調者3PC中參加PA狀態,從而不允許從Wait/Ready到Abort狀態的轉換原因有多個協調者阻止事務終結,不允許多個協調者得出不同的結論,因此希望協調者獲得撤銷的決定如果新協調者故障,它不知道是否到達提交或撤銷的法定票數,這樣參與者必須明確做出提交或撤銷的決定Ready(或Wait)都不滿足該需求,預示引入另一個狀態Pre-Abort,該狀態在Ready和Abort之間4.2基于表決的協議4網絡分割與提交協議IWACcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort基于法定人數3PC中事務的狀態轉換圖PCPCready-to-commitglobal-commitglobal-commitACK(a)協調者(b)參與者PAready-to-abortglobal-abortPAready-to-abortglobal-abort基于法定人數的3PC集中式協議選擇一個新的協調者協調者收集狀態信息,并按如下規那么執行1)假設至少一個站點已Commit(Abort),那么協調者對其它站點發送Commit(Abort)命令2)假設處于PC狀態站點的票數>=Vc,那么發送Commit3)假設PA狀態站點的票數>=Va,那么發送Abort4)假設PC狀態站點的票數+Ready狀態站點的票數>=Vc,那么發送PC命令給不確定站點,等待2)狀態出現5)假設PA狀態站點的票數+Ready狀態站點的票數>=Va,那么發送PA命令給不確定站點,等待3)狀態出現6)否那么,等待故障修復4.2基于表決的協議4網絡分割與提交協議數據復制的目的高吞吐量較好的響應時間高可用性復制作為可選擇的提交協議數據在多站點獨立更新,使用“惰性復制協議〞減少數據不一致問題.4.3復制控制協議4網絡分割與提交協議根本方法：每個副本看作一個獨立的數據項X1X2X3LockmgrX3LockmgrX2LockmgrX1TxiTxjTxk對象X有副本X1,X2,X34.3復制控制協議4網絡分割與提交協議Read(X):獲取X1共享鎖獲取X2共享鎖獲取X3共享鎖分別讀X1,X2,X3事務結束時,釋放X1,X2,X3鎖X1lockmgrX3lockmgrX2lockmgrreadWrite(X):獲取X1互斥鎖獲取X2互斥鎖獲取X3互斥鎖寫新值到X1,X2,X3事務結束時,釋放X1,X2,X3鎖X1X3X2locklocklockwritewritewrite讀鎖和訪問只對一個副本寫鎖全部,并且更新全部副本讀可用性高寫可用性低，只要有一個副本不可獲得，更新事務就不能終結ROWA方法X1X2X3讀者加鎖寫者發現沖突!4.3復制控制協議4網絡分割與提交協議ROWA的改進(ROWA-A)ROWA-A“讀一個寫所有可獲得協議〞根本思想是寫命令在所有可獲得的副本上執行，然后事務終結，當時不可獲得的副本將在它們重新可獲得時被捕獲更新事務T的協調者向所有包含x副本的站點發送WT(x),并等待執行(或拒絕)確實認.當不可獲得站點恢復時,也將更新自己的數據庫.但如果站點在T開始之前就不可獲得,它們就可能沒有注意到T的存在,以及T對x的更新.問題協調者認為不可獲得的參與者仍然工作,并且更新了x,但是其確認沒有到達協調者站點在事務啟動時不可獲得,隨后恢復并開始執行事務4.3復制控制協議4網絡分割與提交協議于是,協調者在提交前要進行有效性驗證檢查所有不可獲得的站點是否仍然不可獲得,如果協調者收到一個響應,它就撤銷T.假設都是不可獲得,那么檢查在WT(x)執行是可獲得的站點仍然可獲得,是那么提交事務ROWA-A比ROWA協議能更好地適應失效,包括網絡分割.ROWA的改進(ROWA-A)4.3復制控制協議4網絡分割與提交協議基于法定人數的復制控制Gifford算法讀法定人數Vr,寫法定人數Vw規那么1：Vr+Vw>V，可防止讀-寫沖突規那么2：Vw>V/2，防止寫-寫沖突該算法確保了在兩個不同網絡區域上啟動且訪問同一數據的事務不會同時終結4.3復制控制協議4網絡分割與提交協議惰性復制協議思想只在一個或多個副本上執行更新,以后再將更新傳播到所有副本上特點所有權參數：定義更新副本的權限,副本可以更新就稱為主Copy(主站點),否那么稱輔Copy(輔站點)傳播參數：定義何時把對一個副本的更新傳播到包含該對象的其它副本刷新參數：定義了刷新事務的調度策略配置參數：描述站點和網絡的特點4.3復制控制協議4網絡分割與提交協議兩類所有副本都可更新,存在副本的組所有權,常用延遲立即方式更新只有一個被更新的主站點(惰性主站點法)幾種刷新方案:按需刷新,每次提交執行查詢時,執行所有收到的刷新事務來刷新被查詢讀取的輔Copy,造成查詢響應延遲成組刷新,根據應用刷新要求,成組執行刷新事務定期刷新,在固定時間間隔內觸發刷新惰性復制協議4.3復制控制協議4網絡分割與提交協議網絡的一致視圖可靠性算法是假定:全部能工作的站點對網絡的所有站點(包括其本身)的狀態(即工作或故障)具有一致的視圖決定網絡的一致視圖監視網絡的狀態，當站點狀態發生轉換時,能及時發現新的信息一致地傳播給全部站點5.1決定網絡的狀態5不一致性檢測和解決方法假設建于廣義的網絡范圍內每個站點有一狀態表,每個站點一個表項,記錄其工作/不工作，程序可查詢狀態表得到狀態信息任何程序能夠在任一站點設置一個“看守〞,當該站點變化狀態時它就收到一個中斷分割時,狀態表和一致視圖的意義站點只認為那些能和它通信的站點是工作的一致視圖的數目與別離的站點組數目一樣多5.1決定網絡的狀態5不一致性檢測和解決方法監視網絡的狀態決定一站點是否工作時向它請求一個報文,然后等待到超時控制站點(請求站點)受控站點在一廣義監視算法中，受控站點周期性地發送I-am-up〔我在工作〕報文5.1決定網絡的狀態5不一致性檢測和解決方法網絡站點K-3UP站點K-2DOWN站點K-1站點KUPDOWN(狀態)網絡上站點的狀態站點K控制站點K-3,即它檢查來自K-3的I-am-up報文是否到達，站點K負責發現站點K-1和K-2從不工作到工作的恢復，上圖中K-1和K-2不一定是有故障,它們可能在分割的另一組中，圖反映了站點K和K-3的網絡視圖播送新的狀態監視功能每次檢測出一個狀態變化,就激活此播送功能此功能的目的是播送新的狀態表，使同一組的全部站點具有相同的狀態表此功能可由假設干站點并行激活,需要某種機構來控制沖突狀態表的每個新的版本附加一全局唯一的時間戳在I-am-up報文中包含當前狀態表的版本號啟動新狀態表播送的站點首先執行一次同步以獲得一時間戳，然后發送狀態表給已答復的所有站點5.1決定網絡的狀態5不一致性檢測和解決方法需求處理故障的策略有可能犧牲正確性來提高可用性，因此接受了不一致性的風險在這種情況下，監測這些不一致性，并盡可能地加以解決是很有用的概念需要首先發現哪些數據局部已經不一致〔不一致性檢測〕然后根據發生的情況，給這些局部賦予一個最合理的值〔不一致性的解法〕5.2不一致性的檢測和解決方法概念5不一致性檢測和解決方法提出問題假設網絡分割期間,在兩個或多個站點組中已執行了假設干事務,可能對同一數據片斷的不同副本進行了獨立更新檢測方法一種比較自然的方法比較各副本的內容,檢查其是否相同，但是這種方法不僅效率低，一般也是不正確的。5.3不一致性的檢測5不一致性檢測和解決方法檢測方法采用版本號允許對數據項操作的站點的副本是主副本,其它是孤立或隔離的副本正常工作期間,全部副本都是主副本,并且互相一致,每份副本維持一個原版號和一個當前版本號網絡分割時,每個孤立副本的原版本號被置為當前版本號值,并且,直到分割修復為止,此原版號不會改變5.3不一致性的檢測5不一致性檢測和解決方法例子前提數據項x的副本x1,x2,x3存儲在三個不同站點V1,V2,V3分別是x1,x2,x3的版本號初始時,三份副本一致,所以有:V1=(0,2)，V2=(0,2)，V3=(0,2)，假設經過了兩次更新〔原版本號，當前版本號〕發生一次分割,把x3從其它兩個副本分開,多數法選擇x2和x1為主副本,版本號變為V1=(0,2)，V2=(0,2)，V3=(2,2)網絡分割期間,假設只更新主副本,版本號為V1=(0,3)，V2=(0,3)，V3=(2,2)修