第7章_分布式數(shù)據(jù)庫中的可靠性

1、分布式數(shù)據(jù)庫的可靠性的概念及其度量分布式數(shù)據(jù)庫的可靠性的概念及其度量分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議網(wǎng)絡(luò)分割和提交協(xié)議網(wǎng)絡(luò)分割和提交協(xié)議不一致性監(jiān)測和解決方法不一致性監(jiān)測和解決方法分布式數(shù)據(jù)庫中的可靠性分布式數(shù)據(jù)庫中的可靠性 第第7章章 可靠性 指數(shù)據(jù)庫在一給定時間間隔內(nèi)不產(chǎn)生任何失敗的概率。 它強調(diào)數(shù)據(jù)庫的正確性，要求數(shù)據(jù)庫正確運行，既符合某種規(guī)格化要求。 通常用來描述不可修復(fù)的系統(tǒng)。 可用性 強調(diào)的是當(dāng)需要訪問數(shù)據(jù)庫時，它是可用的。 指在給定的時間點系統(tǒng)可以正常運行的概率。 通常用于描述那些可以修復(fù)的系

2、統(tǒng)。 兩者關(guān)系 通常認(rèn)為構(gòu)建可用性的系統(tǒng)比可靠性的系統(tǒng)容易 兩者是統(tǒng)一的，可靠性高的系統(tǒng)可用性自然是好的 兩者又是矛盾的，增加錯誤風(fēng)險的情況下，可提高可用性;采用太謹(jǐn)慎的策略會降低可用性1.1 分布式數(shù)據(jù)庫可靠性概念分布式數(shù)據(jù)庫可靠性概念1 1 分布式數(shù)據(jù)庫可靠性概念及其度量分布式數(shù)據(jù)庫可靠性概念及其度量例: Site1 Site2 x1 x2 Lock x1 Lock x2 2PC Ready故障出現(xiàn)Site1也Ready故CommitSite 2 等待此時Site 2有兩種可能:a 以正確性為標(biāo)準(zhǔn)，x2則等待, 并Lock 2, 直到故障恢復(fù)。提高了可靠性，但犧牲了可用性。b 引入不一致性

3、的風(fēng)險下, 盡量提高可用性，解鎖x2, 其它事務(wù)可以使用它的值。Site 1 正常結(jié)束1.1 分布式數(shù)據(jù)庫可靠性概念分布式數(shù)據(jù)庫可靠性概念1 1 分布式數(shù)據(jù)庫可靠性概念及其度量分布式數(shù)據(jù)庫可靠性概念及其度量已知已知x1和和x2是是x的副本的副本事務(wù)事務(wù)T是更新是更新x的事務(wù)的事務(wù)Site 1是協(xié)調(diào)站點是協(xié)調(diào)站點Site 1是事務(wù)是事務(wù)T原發(fā)站點原發(fā)站點遵守兩階段提交協(xié)議遵守兩階段提交協(xié)議 平均故障間隔時間 指在可以自我修復(fù)的系統(tǒng)中相繼失敗之間的期望時間 通過可靠性函數(shù)來計算MTBF=0R(t)dt MTBF與系統(tǒng)失敗的概率有直接的關(guān)系 平均修復(fù)時間 是指修復(fù)一個系統(tǒng)所需要的期望時間，MTTR

4、它與失敗概率有關(guān) 指數(shù)型失敗和修復(fù)的概率的系統(tǒng)可用性 A=MTBF/(MTBF+MTTR) 可用性系統(tǒng) 5個9（99.999%）常用來描述可用性系統(tǒng) 但是可用性系統(tǒng)要求的成本比較高 具體設(shè)計時要綜合用戶兩方面的要求1.2 平均故障間隔時間和平均修復(fù)時間平均故障間隔時間和平均修復(fù)時間1 1 分布式數(shù)據(jù)庫可靠性概念及其度量分布式數(shù)據(jù)庫可靠性概念及其度量 系統(tǒng)（System） 是由一組組件構(gòu)成的一種機(jī)制，這些組件通過響應(yīng)來自某個環(huán)境的具有可識別行為模式的刺激而相互作用。component1component2component3環(huán)境系統(tǒng)刺激響應(yīng) 系統(tǒng)規(guī)范說明（Specification） 系統(tǒng)提供的

5、對所有可能的刺激將產(chǎn)生的響應(yīng)行為必須遵循的說明2.1 系統(tǒng)失敗的原因系統(tǒng)失敗的原因2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 故障 任何偏離規(guī)范說明的行為 軟故障和硬故障 軟故障包括間歇性（intermittent）和瞬變性（transient）故障，通過重啟動來修復(fù) 硬故障指永久性故障, 錯誤設(shè)計等 軟件和硬件故障2.1 系統(tǒng)失敗的原因系統(tǒng)失敗的原因2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 軟故障 占90%以上并且該比例穩(wěn)定 67年， 美空軍指出計算機(jī)中電子故障80%是間歇性的 67年，IBM 指出 90%故障是間

6、歇性的 80年，研究指出軟故障明顯高于硬故障 87年，Gray指出 大部分軟件故障是瞬變性故障2.1 系統(tǒng)失敗的原因系統(tǒng)失敗的原因2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 審查不同計算機(jī)系統(tǒng)中出錯的統(tǒng)計數(shù)據(jù) IBM/XA 的OS 可靠性報告 57%是硬件, 12% 軟件, 14%操作, 7% 環(huán)境（斯坦福 線性加速器SLAC） Tandem計算機(jī) 18%硬件 25% 軟件 25%維護(hù) 17%操作, 14%環(huán)境 AT&T 5ESS數(shù)字交換機(jī) 32.3%硬件, 44.3%軟件, 17.5%操作 軟件故障 通信或DB的原因是產(chǎn)生軟件故障的主要原因. 代

7、碼中的Bug, 曾有報告指出, 1000條指令中, 0.25-10個BUG2.1 系統(tǒng)失敗的原因系統(tǒng)失敗的原因2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)永久性故障錯誤的設(shè)計不穩(wěn)定或者臨界的組件不穩(wěn)定的外部環(huán)境操作者的過失系統(tǒng)失敗永久性錯誤間歇性錯誤瞬變的錯誤系統(tǒng)失敗的原因 容錯 設(shè)計一種使系統(tǒng)識別出可能會發(fā)生的錯誤的方法。在系統(tǒng)中建立一種機(jī)制，使錯誤在造成系統(tǒng)故障之前就會被檢測出來，并能被清除或得到補償。 錯誤預(yù)防 保證所實現(xiàn)的系統(tǒng)不包含任何錯誤 錯誤回避：保證系統(tǒng)不會帶入錯誤的技術(shù)（詳細(xì)的設(shè)計方法學(xué)和質(zhì)量控制） 錯誤清除：清查那些在使用了錯誤回避技術(shù)路線

8、后還殘留在系統(tǒng)中的錯誤，并清除它們（需要大量的測試和證實過程）2.2 基本容錯方法和技術(shù)基本容錯方法和技術(shù)2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 故障檢測 潛伏的故障：故障發(fā)生一段時間后才被檢測出來 錯誤潛伏期：從故障發(fā)生到被檢測出來的時間 平均檢測時間(MTTD)：平均錯誤潛伏時間 平均修復(fù)時間(MTTR)：修復(fù)一個失敗的系統(tǒng)所需要的期望時間 平均故障間隔時間(MTBF)：在可以自我修復(fù)的系統(tǒng)中相繼的失敗之間的期望時間, 由經(jīng)驗或從可靠性函數(shù)計算2.2 基本容錯方法和技術(shù)基本容錯方法和技術(shù)2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的

9、故障原因和容錯技術(shù) MTBF MTTDMTTR在這段時間內(nèi)，可能發(fā)生多起錯誤故障發(fā)生造成錯誤檢測到錯誤修復(fù)故障發(fā)生造成錯誤時間 相繼發(fā)生的事件2.2 基本容錯方法和技術(shù)基本容錯方法和技術(shù)2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 冗余 所有容錯系統(tǒng)設(shè)計中都采用的基本原則是在系統(tǒng)的組件中提供冗余 模塊化 系統(tǒng)的每個組件都設(shè)計為具有定義很好的輸入/輸出接口的模塊 模塊化可以把故障隔離在單一的組件中 系統(tǒng)實現(xiàn) 故障-停止模塊（fail-stop module) 進(jìn)程對（Process pairs)2.2 基本容錯方法和技術(shù)基本容錯方法和技術(shù)2 2 分布式數(shù)據(jù)庫系

10、統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)time正常 停止 恢復(fù) 正常易失存儲丟失穩(wěn)定存儲 ok 故障-停止模塊 不斷地對自身進(jìn)行檢測，當(dāng)檢測到一個故障時，就自動停止。 優(yōu)點是縮短了故障檢測的潛伏期。2.2 基本容錯方法和技術(shù)基本容錯方法和技術(shù)2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 進(jìn)程對（Process pairs) 通過軟件模塊的雙工來實現(xiàn)容錯。兩個進(jìn)程，一個是主進(jìn)程，一個是備份，它們同時提供同樣的服務(wù)，主進(jìn)程與備份進(jìn)程都是基于故障-停止模塊實現(xiàn)。 分類方式（根據(jù)主進(jìn)程和備份進(jìn)程之間的通信方式） 鎖定-步進(jìn)方式 自動檢查點設(shè)置方式

11、 狀態(tài)檢查點設(shè)置方式 Delta檢查點設(shè)置方式 持久進(jìn)程對2.2 基本容錯方法和技術(shù)基本容錯方法和技術(shù)2 2 分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù)分布式數(shù)據(jù)庫系統(tǒng)的故障原因和容錯技術(shù) 分布式數(shù)據(jù)庫的可靠性協(xié)議是為了保證在分布式數(shù)據(jù)庫上執(zhí)行的分布式事務(wù)的原子性和持久性。 這些協(xié)議描述了Begin_Transaction、Read、Write、Abort、 Commit和Recover原語的分布式執(zhí)行過程。3.1 分布式可靠性協(xié)議分布式可靠性協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 分布式數(shù)據(jù)庫系統(tǒng)的可靠性協(xié)議包括提交協(xié)議、終結(jié)協(xié)議和恢復(fù)協(xié)議 提交協(xié)議和恢復(fù)協(xié)議詳細(xì)說明了提交命

12、令和恢復(fù)命令是如何執(zhí)行的。 終結(jié)協(xié)議是分布式系統(tǒng)特有的。設(shè)想在執(zhí)行一個分布式事務(wù)時，其中一個站點失效了，我們希望其它站點也停止該事務(wù)，處理這種情況的技術(shù)就稱為終結(jié)協(xié)議。 終結(jié)協(xié)議和恢復(fù)協(xié)議是恢復(fù)問題的兩個相反的方面：假定一個站點失效了，終結(jié)協(xié)議確定了未失效站點如何處理該失效事件； 而恢復(fù)協(xié)議確定失效站點重新啟動后，其進(jìn)程（協(xié)調(diào)者或參與者）恢復(fù)它的狀態(tài)的過程。在網(wǎng)絡(luò)分割的情況下，終結(jié)協(xié)議采取必要的措施來終結(jié)在不同的網(wǎng)絡(luò)區(qū)間執(zhí)行的活動事務(wù)；在網(wǎng)絡(luò)重新連接后，恢復(fù)協(xié)議保證使各個冗余數(shù)據(jù)庫相互一致。3.1 分布式可靠性協(xié)議分布式可靠性協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 目的

13、維持在多個數(shù)據(jù)庫上執(zhí)行的事務(wù)的原子性和持久性 原語 Begin_Transaction read, write, Abort, commit 命令執(zhí)行與局部協(xié)議類似3.1 分布式可靠性協(xié)議分布式可靠性協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 可靠性協(xié)議組成 包括提交、終結(jié)、恢復(fù)協(xié)議 提交和恢復(fù)協(xié)議詳細(xì)說明提交命令和恢復(fù)命令是如何執(zhí)行的 終結(jié)協(xié)議是分布式系統(tǒng)特有的協(xié)議。在執(zhí)行一個分布式事務(wù)時，若一個Site故障，希望其它Site也停止該事務(wù)。處理這種情況的技術(shù)就稱為終止協(xié)議。3.1 分布式可靠性協(xié)議分布式可靠性協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 終結(jié)

14、協(xié)議與恢復(fù)協(xié)議的比較 假若一個Site失效 終結(jié)協(xié)議確定了未失效Site如何處理該失效事件 恢復(fù)協(xié)議確定失效Site重啟動后，進(jìn)程（協(xié)調(diào)者，參與者）恢復(fù)它的狀態(tài)的過程 網(wǎng)絡(luò)分割時 終結(jié)協(xié)議采取必要的措施來終結(jié)在不同網(wǎng)絡(luò)區(qū)間執(zhí)行的活動事務(wù) 當(dāng)網(wǎng)絡(luò)重新連接后，恢復(fù)協(xié)議保證使各個冗余DB相互一致3.1 分布式可靠性協(xié)議分布式可靠性協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 兩階段提交協(xié)議的要點 允許參與者單方面撤銷事務(wù)，直到做出肯定性的建議 一旦參與者確定了提交或者撤銷提議，它不能再更改 當(dāng)參與者處于就緒狀態(tài)，它可根據(jù)協(xié)調(diào)者發(fā)出的消息的種類，轉(zhuǎn)換為相應(yīng)的提交或者撤銷狀態(tài) 協(xié)調(diào)者依據(jù)

15、全局提交規(guī)則作出全局終結(jié)決定 在發(fā)生故障的情況下，協(xié)調(diào)者和參與者可能會進(jìn)入互相等待的狀態(tài)，一般采用定時器來解決這種問題3.2 兩階段提交協(xié)議的演變兩階段提交協(xié)議的演變3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議協(xié)調(diào)者參與者PREPAREPREPAREDCOMMITACK2PC-提交協(xié) 調(diào) 者參 與 者PREPARENOABORTACK2PC-夭折集中式2PC協(xié)調(diào)者 參與者IWCAIRCAcommit-申請 申請-prepare* no abort* prepared* commit commit ACK 申請-prepare prepared 申請-prepare no abort

16、 ACKF ACK* ACK* 標(biāo)記: 輸入消息 輸出消息* = 每一個3.2 兩階段提交協(xié)議的演變兩階段提交協(xié)議的演變3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 當(dāng)參與者進(jìn)入“R”狀態(tài): 它必定已獲得所有資源 它只能根據(jù)協(xié)調(diào)者指令提交或夭折 當(dāng)所有參與者是在“R”時, 協(xié)調(diào)者才能進(jìn)入“C” 狀態(tài), 即, 它一定最終能提交3.2 兩階段提交協(xié)議的演變兩階段提交協(xié)議的演變3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 假定撤銷2PC和假定提交2PC協(xié)議 目的是改善2PC的性能 假定撤銷協(xié)議中，協(xié)調(diào)者不必等待參與者的ACK消息，減少了協(xié)調(diào)者與參與者之間傳遞消息的數(shù)量 假定提

17、交協(xié)議中，可以不將Prepare寫入Log，減少了Log寫入的次數(shù)3.2 兩階段提交協(xié)議的演變兩階段提交協(xié)議的演變3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 事務(wù)阻斷：某個Site上本來可以終結(jié)（提交或撤銷）的子事務(wù)，由于DDBS故障，必須等待到故障恢復(fù)（其占有的資源不釋放） 阻斷協(xié)議：提交協(xié)議稱為阻斷協(xié)議是指發(fā)生某類故障時，使分布式事務(wù)可能處于阻斷狀態(tài) 終結(jié)協(xié)議：允許事務(wù)在有故障情況下仍能正確結(jié)束3.3 事務(wù)阻斷與終結(jié)協(xié)議事務(wù)阻斷與終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 判斷2PC協(xié)議是終結(jié)協(xié)議的條件 至少有一個Site已收到結(jié)果命令（該Site可以告

18、知其它參與者關(guān)于該事務(wù)的結(jié)果，并由它們來終結(jié)該事務(wù)） 沒有一個參與者收到命令，并且只有協(xié)調(diào)者Site故障（此時，所有參與者站點都是可工作的，參與者可以選舉一個新的協(xié)調(diào)者，然后繼續(xù)）3.3 事務(wù)阻斷與終結(jié)協(xié)議事務(wù)阻斷與終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 終結(jié)協(xié)議在協(xié)調(diào)者和參與者的定時器超時時發(fā)揮作用 超時處理技術(shù) 協(xié)調(diào)者超時 在等待狀態(tài)超時，可以決定“全局撤銷” 在撤銷狀態(tài)超時，重發(fā)“G-abort” 在提交狀態(tài)超時，重發(fā)“G-commit” 參與者超時（被阻斷時出現(xiàn)） 在初始狀態(tài)超時，單方面Abort 在Ready狀態(tài)超時，被阻斷，等待事務(wù)最終處理結(jié)果3.4 2P

19、C協(xié)議的終結(jié)協(xié)議協(xié)議的終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議協(xié)調(diào)者超時IWCAFcommit-申請申請-prepare*ack*-ack*-_t_abortanyabortanycommit_t_commit_t_abort*noabort*prepared*commit*t=timeout參與者超時IRCA申請-prepareprepared等價于結(jié)束狀態(tài)_t_ ping申請-preparenocommitackabortackcommitackabortack 設(shè)計終結(jié)協(xié)議 假定Pi是超時的參與者（詢問Pj），其它Pj按如下響應(yīng) Pj處于初始狀態(tài)，于是單方面Abo

20、rt，并回送“建議abort”給Pi Pj處于Ready狀態(tài)，此時不能幫助Pi終結(jié) Pj處于Commit或Abort狀態(tài)，此時向Pi發(fā)送“建議提交”或“建議Abort”3.4 2PC協(xié)議的終結(jié)協(xié)議協(xié)議的終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 Pi超時，可能有的解釋 Pi收到Pj的“建議撤銷”回答，此時Pi夭折 Pi收到Pj“建議撤銷”回答，但是其它Pj處于Ready狀態(tài)，此時Pi仍然Abort Pi收到Pj處于Ready狀態(tài)，此時沒有一個參與者有足夠的信息恰當(dāng)?shù)亟K結(jié)事務(wù) Pi收到其他所有的Pj”全局提交”或”全局夭折”消息，Pi可以根據(jù)消息終結(jié) Pi收到某些Pj的“全

21、局提交”，而另一些Pj處于Ready狀態(tài)，Pi可以提交3.4 2PC協(xié)議的終結(jié)協(xié)議協(xié)議的終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 協(xié)調(diào)者站點失效 協(xié)調(diào)者在初始狀態(tài)失效 發(fā)生在協(xié)調(diào)者初始化提交過程之前 因此，它將在恢復(fù)時啟動提交過程 協(xié)調(diào)者在等待狀態(tài)失效 這時協(xié)調(diào)者已經(jīng)發(fā)送了“準(zhǔn)備”命令 恢復(fù)時，協(xié)調(diào)者將從頭開始啟動提交過程，再次發(fā)送“準(zhǔn)備”消息 協(xié)調(diào)者在提交狀態(tài)或撤銷狀態(tài)失效 這時，協(xié)調(diào)者已經(jīng)把它的決定通知了參與者，并終結(jié)了事務(wù) 在恢復(fù)時，如果它已經(jīng)收到了所有的確認(rèn)消息，就不需要做任何事情 否則，就要啟動終結(jié)協(xié)議3.5 2PC協(xié)議的恢復(fù)協(xié)議協(xié)議的恢復(fù)協(xié)議3 3 分布式數(shù)

22、據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 參與者站點失效 一個參與者在初始狀態(tài)失效 在恢復(fù)時，該參與者應(yīng)該單方面撤銷事務(wù) 一個參與者在就緒狀態(tài)失效 這時協(xié)調(diào)者已經(jīng)收到失效站點在失效前發(fā)送的肯定決定 恢復(fù)時，失效站點的參與者認(rèn)為是在就緒狀態(tài)發(fā)生了超時，于是啟動終結(jié)協(xié)議來處理該事務(wù) 一個參與者在提交狀態(tài)或撤銷狀態(tài)失效 這些狀態(tài)表示了終結(jié)條件，所以在恢復(fù)時，參與者不需要采取任何專門的措施 附加情形（略）3.5 2PC協(xié)議的恢復(fù)協(xié)議協(xié)議的恢復(fù)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 提交協(xié)議是非阻斷的充要條件是, 在其狀態(tài)轉(zhuǎn)換圖中不存在: 沒有狀態(tài)是即與提交又與撤銷狀態(tài)“相鄰” 不

23、存在不可提交狀態(tài)是與提交狀態(tài)“相鄰” 相鄰 從一個狀態(tài)直接轉(zhuǎn)換到另一個狀態(tài)3.6 三階段提交協(xié)議三階段提交協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 2PC中的狀態(tài) C(提交)狀態(tài)是可提交狀態(tài), 其它為不可提交狀態(tài) Ready 狀態(tài)是不可提交狀態(tài) Wait狀態(tài)是不可提交狀態(tài) 它們都侵犯了非阻斷協(xié)議的充要條件, 從而考慮改變2PC, 使其滿足非阻斷協(xié)議條件 在Wait 和 Commit 之間, 或者在Ready和Commit之間加入另一種狀態(tài)作為緩沖狀態(tài), 從而有了3PC協(xié)議3.6 三階段提交協(xié)議三階段提交協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議IWcomm

24、itpreparevote-abortglobal-abortvote-commitprepare-to-commitIRpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort3PC中事務(wù)的狀態(tài)轉(zhuǎn)換圖PCPCready-to-commitglobal-commit global-commitACK(a) 協(xié)調(diào)者(b) 參與者協(xié)調(diào)者參與者 PREPAREPREPAREDCOMMITDONE PRECOMMITACK協(xié)調(diào)者參與者 PREPARENOABORTDONE協(xié)調(diào)者參與者開始-3PC

25、 記錄寫Log (參與者列表)commit記錄寫Log (狀態(tài)C)prepared記錄寫Log (狀態(tài) W)committed 記錄寫Log (狀態(tài) C) PREPAREPREPAREDCOMMIT PRECOMMITACK協(xié)調(diào)者參與者初始寫begin_commit到日志等待有要求撤消的？寫Prepare-to-commit到日志準(zhǔn)備提交寫end_of_trans.到日志初始準(zhǔn)備提交？寫ready到日志就緒消息類型？寫abort到日志寫prepare-to-commit到日志準(zhǔn)備提交撤消撤消寫abort到日志寫abort到日志準(zhǔn)備撤消提交全局撤消準(zhǔn)備提交ACKACK nono abortPre

26、pare-to-commit寫commit到日志提交提交 在 中事務(wù)執(zhí)行的過程 寫commit到日志撤消提交準(zhǔn)備提交3PC 協(xié)調(diào)者 在Wait狀態(tài)超時：與2PC中協(xié)調(diào)者在Wait超時相同, 協(xié)調(diào)者單方面Abort 在PC狀態(tài)超時：此時協(xié)調(diào)者不知道未響應(yīng)的參與者是否到達(dá)PC. 但是知道每個參與者至少在Ready狀態(tài), 因此協(xié)調(diào)者可以將所有參與者移入PC狀態(tài) 在Commit/Abort狀態(tài)超時 協(xié)調(diào)者不知參與者是否已執(zhí)行命令,但是對Commit而言, 知道參與者至少在PC狀態(tài)。因此，協(xié)調(diào)者不需要做專門的處理3.7 三階段提交協(xié)議的超時處理三階段提交協(xié)議的超時處理3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布

27、式數(shù)據(jù)庫的可靠性協(xié)議 參與者超時 在Initial狀態(tài)超時：與2PC中的情況相同 在Ready狀態(tài)超時：參與者準(zhǔn)備Commit. 由于與協(xié)調(diào)者的通信丟失, 終結(jié)協(xié)議將選舉一個新的協(xié)調(diào)者，新協(xié)調(diào)者根據(jù)下面所述終結(jié)協(xié)議終結(jié)事務(wù) 在PC狀態(tài)超時：參與者已收到“Prepare-to-commit”, 正在等待來自協(xié)調(diào)者的“全局提交”消息, 處理同第二條。3.7 三階段提交協(xié)議的超時處理三階段提交協(xié)議的超時處理3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議協(xié)調(diào)者參與者 PREPAREPREPAREDCOMMIT PRECOMMITACK1. 超時: Abort3. 超時: 忽略1. 超時: a

28、bort2. 超時:終結(jié)協(xié)議3.超時:終結(jié)協(xié)議2. 超時: 把參與者移入PC 競選新的協(xié)調(diào)者 使用競選協(xié)議 新協(xié)調(diào)者送出 REQUEST狀態(tài)給參與者 使用終結(jié)規(guī)則做出決定 與參與者通信3.8 三階段提交協(xié)議的終結(jié)協(xié)議三階段提交協(xié)議的終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議競選協(xié)議 進(jìn)程全序 協(xié)調(diào)者 = 0, 參與者 1,n 任何時候, 選擇 “最小的” 工作進(jìn)程為協(xié)調(diào)者3.8 三階段提交協(xié)議的終結(jié)協(xié)議三階段提交協(xié)議的終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 終結(jié)規(guī)則 新協(xié)調(diào)者在Wait狀態(tài)：將全局Abort. 此時參與者可以在任何狀態(tài), 若參與者

29、是在PC狀態(tài), 即它是期望有“G-Commit” , 但是得到了“G-Abort”. 3PC中缺少從PC到Abort的轉(zhuǎn)換, 這對終結(jié)協(xié)議很有用. 新協(xié)調(diào)者在PC狀態(tài)：此時沒有參與者是在Abort狀態(tài), 協(xié)調(diào)者可以全局提交, 發(fā)送“G-Commit”命令. 新協(xié)調(diào)者在Abort狀態(tài)：收到第一個消息后，所有參與者進(jìn)入Abort狀態(tài)3.8 三階段提交協(xié)議的終結(jié)協(xié)議三階段提交協(xié)議的終結(jié)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 3PC與2PC恢復(fù)協(xié)議的差別很小 協(xié)調(diào)者在Wait狀態(tài)故障, 按照終結(jié)協(xié)議，參與者已終結(jié)事務(wù), 因此, 協(xié)調(diào)者在恢復(fù)時必須查詢以決定事務(wù)的命運 協(xié)調(diào)者在PC

30、狀態(tài)故障, 終結(jié)協(xié)議已使工作的參與者終結(jié), 因此, 協(xié)調(diào)者需詢問 一個參與者在PC狀態(tài)故障, 必須詢問以確定其它參與者如何終結(jié)事務(wù)3.9 三階段提交協(xié)議的恢復(fù)協(xié)議三階段提交協(xié)議的恢復(fù)協(xié)議3 3 分布式數(shù)據(jù)庫的可靠性協(xié)議分布式數(shù)據(jù)庫的可靠性協(xié)議 網(wǎng)絡(luò)分割是由通信線路故障引起的 簡單分割，僅僅是網(wǎng)絡(luò)分裂成兩部分 多重分割，更復(fù)雜 網(wǎng)絡(luò)分割非阻斷協(xié)議的存在性 即在發(fā)生網(wǎng)絡(luò)分割時, 是否存在允許獨立恢復(fù)的協(xié)議 獨立恢復(fù)是指站點重啟動時, 無需遠(yuǎn)程訪問 若存在處理分割的非阻斷協(xié)議, 那么, 該協(xié)議可使某個分割中的站點到達(dá)終結(jié)決定, 而且這個決定與另一分割中的決定一致 一般結(jié)論 獨立恢復(fù)協(xié)議只存在于單站點

31、故障的情形 若發(fā)生網(wǎng)絡(luò)分割的時候, 丟了報文的話, 則不存在任何非阻斷的協(xié)議能從網(wǎng)絡(luò)分割故障中恢復(fù)4.1 網(wǎng)絡(luò)分割概述網(wǎng)絡(luò)分割概述4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 非冗余數(shù)據(jù)庫 任何需要訪問存儲在另一網(wǎng)絡(luò)區(qū)域里的數(shù)據(jù)項的新事務(wù)都被阻斷, 等待網(wǎng)絡(luò)修復(fù) 位于同一區(qū)域里的數(shù)據(jù)項的并發(fā)訪問由并發(fā)控制算法處理 網(wǎng)絡(luò)分割時由提交協(xié)議處理 冗余數(shù)據(jù)庫 分割時, 副本可能位于不同的區(qū)域 由復(fù)制協(xié)議處理4.1 網(wǎng)絡(luò)分割概述網(wǎng)絡(luò)分割概述4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 網(wǎng)絡(luò)分割處理策略 一致性與可用性的選擇 非冗余數(shù)據(jù)庫處理網(wǎng)絡(luò)分割的終結(jié)協(xié)議 集中式協(xié)議，基于集中式并發(fā)控制算法(主站點法

32、和主副本法) 基于表決的協(xié)議 冗余數(shù)據(jù)庫處理網(wǎng)絡(luò)分割的終結(jié)協(xié)議 復(fù)制控制協(xié)議4.1 網(wǎng)絡(luò)分割概述網(wǎng)絡(luò)分割概述4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 集中式終結(jié)協(xié)議基于集中式并發(fā)控制算法。 由于主站點管理著封鎖表，所以主站點并發(fā)控制算法允許在包含主站點的區(qū)域繼續(xù)進(jìn)行正常的操作。 主副本并發(fā)控制算法允許在多個區(qū)域執(zhí)行不同的查詢。 對任意給定的查詢，只有包含事務(wù)寫集中的數(shù)據(jù)項的主副本區(qū)域可以繼續(xù)執(zhí)行該事務(wù)。4.2 集中式終結(jié)協(xié)議集中式終結(jié)協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 多數(shù)法和基于法定人數(shù)法 在事務(wù)中止或提交前, 大多數(shù)站點必須一致同意中止或提交 基于法定人數(shù)的規(guī)則 每個站點

33、i有選票數(shù)Vi, Vi是正整數(shù) V= Vi 事務(wù)在提交前，它必須獲得提交法定票數(shù)Vc 事務(wù)在Abort前，它必須獲得Abort法定票數(shù)Va Va+VcV, 當(dāng)0 Va, Vc Vni=14.3 基于表決的協(xié)議基于表決的協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 網(wǎng)絡(luò)分割時, 在每個分割部分選擇一個新的協(xié)調(diào)者 3PC中加入PA狀態(tài), 從而不允許從Wait /Ready到Abort 狀態(tài)的轉(zhuǎn)換 原因 有多個協(xié)調(diào)者阻止事務(wù)終結(jié), 不允許多個協(xié)調(diào)者得出不同的結(jié)論, 因此希望協(xié)調(diào)者獲得撤銷的決定 如果新協(xié)調(diào)者故障, 它不知道是否達(dá)到提交或撤銷的法定票數(shù), 這樣參與者必須明確做出提交或撤銷的決定 R

34、eady(或Wait)都不滿足該需求, 預(yù)示引入另一個狀態(tài)Pre-Abort, 該狀態(tài)在Ready和Abort之間4.3 基于表決的協(xié)議基于表決的協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議IWcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort基于法定人數(shù)3PC中事務(wù)的狀態(tài)轉(zhuǎn)換圖PCPCready-to-commitglobal-commit glo

35、bal-commitACK(a) 協(xié)調(diào)者(b) 參與者PAready-to-abortglobal-abortPAready-to-abortglobal-abort 基于法定人數(shù)的3PC集中式協(xié)議 選擇一個新的協(xié)調(diào)者 協(xié)調(diào)者收集狀態(tài)信息, 并按如下規(guī)則執(zhí)行1) 若至少一個站點已Commit(Abort), 則協(xié)調(diào)者對其它站點發(fā)送Commit(Abort)命令2) 若處于PC狀態(tài)站點的票數(shù)=Vc, 則發(fā)送Commit3) 若PA狀態(tài)站點的票數(shù)=Va, 則發(fā)送Abort4) 若PC狀態(tài)站點的票數(shù)+Ready狀態(tài)站點的票數(shù)=Vc, 則發(fā)送PC命令給不確定站點, 等待2)狀態(tài)出現(xiàn)5) 若PA狀態(tài)站點

36、的票數(shù)+Ready狀態(tài)站點的票數(shù)=Va, 則發(fā)送PA命令給不確定站點, 等待3)狀態(tài)出現(xiàn)6) 否則, 等待故障修復(fù)4.3 基于表決的協(xié)議基于表決的協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 數(shù)據(jù)復(fù)制的目的 高吞吐量 較好的響應(yīng)時間 高可用性 復(fù)制作為可選擇的提交協(xié)議 數(shù)據(jù)在多站點獨立更新, 使用“惰性復(fù)制協(xié)議”減少數(shù)據(jù)不一致問題. 4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 基本方法： 每個副本看作一個獨立的數(shù)據(jù)項X1X2X3Lockmgr X3Lockmgr X2Lockmgr X1TxiTxjTxk對象 X 有副本 X1, X2, X34.4 復(fù)制控

37、制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 Read(X): 獲取 X1 共享鎖 獲取 X2 共享鎖 獲取 X3 共享鎖 分別讀 X1, X2, X3 事務(wù)結(jié)束時, 釋放 X1, X2, X3 鎖X1lockmgrX3lockmgrX2lockmgrread Write(X): 獲取 X1 互斥鎖 獲取 X2 互斥鎖 獲取 X3 互斥鎖 寫新值到 X1, X2, X3 事務(wù)結(jié)束時, 釋放 X1, X2, X3 鎖X1X3X2locklocklockwritewritewrite 讀鎖和訪問只對一個副本 寫鎖全部, 并且更新全部副本 讀可用性高 寫可用性低，只要有一個副本不可

38、獲得，更新事務(wù)就不能終結(jié)ROWA方法X1X2X3讀者加鎖寫者發(fā)現(xiàn)沖突!4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議ROWA的改進(jìn)(ROWA-A) ROWA-A “讀一個寫所有可獲得協(xié)議” 基本思想是寫命令在所有可獲得的副本上執(zhí)行，然后事務(wù)終結(jié)，當(dāng)時不可獲得的副本將在它們重新可獲得時被捕獲 更新事務(wù)T的協(xié)調(diào)者向所有包含x副本的站點發(fā)送WT(x), 并等待執(zhí)行(或拒絕)的確認(rèn). 當(dāng)不可獲得站點恢復(fù)時, 也將更新自己的數(shù)據(jù)庫. 但如果站點在T開始之前就不可獲得, 它們就可能沒有注意到T的存在, 以及T對x的更新. 問題 協(xié)調(diào)者認(rèn)為不可獲得的參與者仍然工作, 并且更新了

39、x , 但是其確認(rèn)沒有到達(dá)協(xié)調(diào)者 站點在事務(wù)啟動時不可獲得, 隨后恢復(fù)并開始執(zhí)行事務(wù)4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 于是, 協(xié)調(diào)者在提交前要進(jìn)行有效性驗證 檢查所有不可獲得的站點是否仍然不可獲得, 如果協(xié)調(diào)者收到一個響應(yīng), 它就撤銷T. 若都是不可獲得, 則檢查在WT(x)執(zhí)行是可獲得的站點仍然可獲得, 是則提交事務(wù) ROWA-A比ROWA協(xié)議能更好地適應(yīng)失效, 包括網(wǎng)絡(luò)分割.ROWA的改進(jìn)(ROWA-A)4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議基于法定人數(shù)的復(fù)制控制 Gifford算法 讀法定人數(shù)Vr, 寫法定

40、人數(shù)Vw 規(guī)則1：Vr + Vw V，可避免讀-寫沖突 規(guī)則2：Vw V/2，避免寫-寫沖突 該算法確保了在兩個不同網(wǎng)絡(luò)區(qū)域上啟動且訪問同一數(shù)據(jù)的事務(wù)不會同時終結(jié)4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議惰性復(fù)制協(xié)議 思想 只在一個或多個副本上執(zhí)行更新, 以后再將更新傳播到所有副本上 特點 所有權(quán)參數(shù)：定義更新副本的權(quán)限, 副本可以更新就稱為主Copy(主站點), 否則稱輔Copy(輔站點) 傳播參數(shù)：定義何時把對一個副本的更新傳播到包含該對象的其它副本 刷新參數(shù)：定義了刷新事務(wù)的調(diào)度策略 配置參數(shù)：描述站點和網(wǎng)絡(luò)的特點4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4

41、網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 兩類 所有副本都可更新, 存在副本的組所有權(quán), 常用延遲立即方式更新 只有一個被更新的主站點(惰性主站點法) 幾種刷新方案: 按需刷新, 每次提交執(zhí)行查詢時, 執(zhí)行所有收到的刷新事務(wù)來刷新被查詢讀取的輔Copy, 造成查詢響應(yīng)延遲 成組刷新, 根據(jù)應(yīng)用刷新要求, 成組執(zhí)行刷新事務(wù) 定期刷新, 在固定時間間隔內(nèi)觸發(fā)刷新惰性復(fù)制協(xié)議4.4 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 網(wǎng)絡(luò)的一致視圖 可靠性算法是假定: 全部能工作的站點對網(wǎng)絡(luò)的所有站點(包括其本身)的狀態(tài)(即工作或故障)具有一致的視圖 決定網(wǎng)絡(luò)的一致視圖 監(jiān)視網(wǎng)絡(luò)的狀態(tài)

42、，當(dāng)站點狀態(tài)發(fā)生轉(zhuǎn)換時, 能及時發(fā)現(xiàn) 新的信息一致地傳播給全部站點5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測和解決方法不一致性檢測和解決方法 假設(shè) 建于廣義的網(wǎng)絡(luò)范圍內(nèi) 每個站點有一狀態(tài)表, 每個站點一個表項, 記錄其工作/不工作，程序可查詢狀態(tài)表得到狀態(tài)信息 任何程序能夠在任一站點設(shè)置一個“看守”, 當(dāng)該站點變化狀態(tài)時它就收到一個中斷 分割時, 狀態(tài)表和一致視圖的意義 站點只認(rèn)為那些能和它通信的站點是工作的 一致視圖的數(shù)目與分離的站點組數(shù)目一樣多5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測和解決方法不一致性檢測和解決方法 監(jiān)視網(wǎng)絡(luò)的狀態(tài) 決定一站點是否工作時向它請求

43、一個報文, 然后等待到超時 控制站點 (請求站點) 受控站點 在一廣義監(jiān)視算法中，受控站點周期性地發(fā)送I-am-up（我在工作）報文5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測和解決方法不一致性檢測和解決方法站點K-3UP站點K-2DOWN站點K-1站點KUPDOWN(狀態(tài))網(wǎng)絡(luò)上站點的狀態(tài)站點K控制站點K-3, 即它檢查來自K-3的I-am-up報文是否到達(dá)，站點K負(fù)責(zé)發(fā)現(xiàn)站點K-1和K-2從不工作到工作的恢復(fù)，上圖中K-1和K-2不一定是有故障, 它們可能在分割的另一組中，圖反映了站點K和K-3的網(wǎng)絡(luò)視圖 廣播新的狀態(tài) 監(jiān)視功能每次檢測出一個狀態(tài)變化, 就激活此廣播功能 此功能

44、的目的是廣播新的狀態(tài)表，使同一組的全部站點具有相同的狀態(tài)表 此功能可由若干站點并行激活, 需要某種機(jī)構(gòu)來控制沖突 狀態(tài)表的每個新的版本附加一全局唯一的時間戳 在I-am-up報文中包含當(dāng)前狀態(tài)表的版本號 啟動新狀態(tài)表廣播的站點首先執(zhí)行一次同步以獲得一時間戳，然后發(fā)送狀態(tài)表給已回答的所有站點5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測和解決方法不一致性檢測和解決方法 需求 處理故障的策略有可能犧牲正確性來提高可用性，因此接受了不一致性的風(fēng)險 在這種情況下，監(jiān)測這些不一致性，并盡可能地加以解決是很有用的 概念 需要首先發(fā)現(xiàn)哪些數(shù)據(jù)部分已經(jīng)不一致（不一致性檢測） 然后根據(jù)發(fā)生的情況，給這

45、些部分賦予一個最合理的值（不一致性的解法）5.2 不一致性的檢測和解決方法概念不一致性的檢測和解決方法概念5 5 不一致性檢測和解決方法不一致性檢測和解決方法 提出問題 假設(shè)網(wǎng)絡(luò)分割期間, 在兩個或多個站點組中已執(zhí)行了若干事務(wù), 可能對同一數(shù)據(jù)片斷的不同副本進(jìn)行了獨立更新 檢測方法 一種比較自然的方法 比較各副本的內(nèi)容, 檢查其是否相同，但是這種方法不僅效率低，一般也是不正確的。5.3 不一致性的檢測不一致性的檢測5 5 不一致性檢測和解決方法不一致性檢測和解決方法 檢測方法 采用版本號 允許對數(shù)據(jù)項操作的站點的副本是主副本, 其它是孤立或隔離的副本 正常工作期間, 全部副本都是主副本, 并且

46、互相一致, 每份副本維持一個原版號和一個當(dāng)前版本號 網(wǎng)絡(luò)分割時, 每個孤立副本的原版本號被置為當(dāng)前版本號值, 并且, 直到分割修復(fù)為止, 此原版號不會改變5.3 不一致性的檢測不一致性的檢測5 5 不一致性檢測和解決方法不一致性檢測和解決方法 例子 已知前提 數(shù)據(jù)項x的副本x1, x2, x3 存儲在三個不同站點 V1, V2, V3分別是x1, x2, x3的版本號 初始時, 三份副本一致, 所以有: V1=(0, 2)，V2 =(0, 2)，V3=(0, 2)，假設(shè)經(jīng)過了兩次更新 （原版本號，當(dāng)前版本號） 發(fā)生一次分割, 把x3從其它兩個副本分開, 多數(shù)法選擇x2和x1為主副本, 版本號變

47、為 V1=(0, 2)，V2 =(0, 2)， V3=(2, 2) 網(wǎng)絡(luò)分割期間, 假設(shè)只更新主副本, 版本號為 V1=(0, 3)，V2 =(0, 3) ，V3=(2, 2) 修復(fù)后, 可以看出x3未曾修改5.3 不一致性的檢測不一致性的檢測5 5 不一致性檢測和解決方法不一致性檢測和解決方法 假設(shè)分割時, 只更新x3, 版本號為 V1=(0, 2) V2 =(0, 2) V3=(2, 3) 此時若沒有其它孤立副本, 則可以用x3的更新施加到主副本, 但若還有x4，V4=(2,3)， 則即使x3與x4版本號相同也不能說其是一致的 若主副本與孤立副本都更新過, 版本號為 V1=(0, 3) V2 =(0, 3) V3=(2, 3) 那么，此孤立副本