庫(kù)系統(tǒng)的故障原因和容錯(cuò)技術(shù)分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議網(wǎng)

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

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

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

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

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

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

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

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

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

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

11、方式） 鎖定-步進(jìn)方式 自動(dòng)檢查點(diǎn)設(shè)置方式 狀態(tài)檢查點(diǎn)設(shè)置方式 Delta檢查點(diǎn)設(shè)置方式 持久進(jìn)程對(duì)2.2 基本容錯(cuò)方法和技術(shù)基本容錯(cuò)方法和技術(shù)2 2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的故障原因和容錯(cuò)技術(shù)分布式數(shù)據(jù)庫(kù)系統(tǒng)的故障原因和容錯(cuò)技術(shù) 事務(wù)故障 系統(tǒng)故障 介質(zhì)故障 通信故障3.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)故障分布式數(shù)據(jù)庫(kù)系統(tǒng)故障3 3 分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議站點(diǎn)故障站點(diǎn)故障 局部恢復(fù)管理器 (LRM) 每個(gè)站點(diǎn)一個(gè) 維護(hù)局部事務(wù)的原子性和持久性 體系結(jié)構(gòu) 數(shù)據(jù)庫(kù)存儲(chǔ)在穩(wěn)定存儲(chǔ)器中 存儲(chǔ)和訪問(wèn)穩(wěn)定數(shù)據(jù)庫(kù)的單位是頁(yè)面 緩沖區(qū)中的數(shù)據(jù)庫(kù)稱作易失數(shù)據(jù)庫(kù) LRM僅僅在易失數(shù)據(jù)庫(kù)上執(zhí)行事務(wù)操作 對(duì)

12、數(shù)據(jù)庫(kù)的訪問(wèn)都要經(jīng)由數(shù)據(jù)庫(kù)緩沖區(qū)管理器 Flush(沖洗) 實(shí)現(xiàn)將數(shù)據(jù)庫(kù)緩沖區(qū)頁(yè)對(duì)穩(wěn)定DB的強(qiáng)迫寫3.2 局部可靠性協(xié)議局部可靠性協(xié)議3 3 分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議數(shù)據(jù)庫(kù)緩沖區(qū)(易變數(shù)據(jù)庫(kù))局部恢復(fù)管理器數(shù)據(jù)庫(kù)緩沖區(qū)管理器主存取出,沖洗讀/寫穩(wěn)定DB讀/寫LRM與緩沖區(qū)管理器的接口3.2 局部可靠性協(xié)議局部可靠性協(xié)議3 3 分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議 恢復(fù)信息 Log Undo Redo舊的穩(wěn)定DB狀態(tài)新的穩(wěn)定DB狀態(tài)Redo數(shù)據(jù)庫(kù)Log新的穩(wěn)定DB狀態(tài)舊的穩(wěn)定DB狀態(tài)Undo數(shù)據(jù)庫(kù)Log3.2 局部可靠性協(xié)議局部可靠性協(xié)議3 3 分布式數(shù)據(jù)庫(kù)的

13、可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議 目的 保證在DB上執(zhí)行的事務(wù)的原子性和持久性。 協(xié)議描述了原語(yǔ)的執(zhí)行過(guò)程 命令執(zhí)行過(guò)程 Begin-Transacrion：登錄 Read：LRM先在Trans的緩沖區(qū)中讀，若不在，則向緩沖區(qū)管理器發(fā)Fetch命令，讀出數(shù)據(jù)后，LRM將它交給調(diào)度程序 Write：若在Buffer中得到，則在那更新，否則對(duì)Buffer Manager發(fā)Fetch命令，讀出數(shù)據(jù)并修改，同時(shí)數(shù)據(jù)的前像和修改后的后像寫入Log Abort：通過(guò)Log做Undo Commit：將事務(wù)結(jié)束記錄入Log項(xiàng)3.2 局部可靠性協(xié)議局部可靠性協(xié)議3 3 分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可

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

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

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

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

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

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

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

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

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

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

24、“相鄰” 不存在不可提交狀態(tài)是與提交狀態(tài)“相鄰” 相鄰 從一個(gè)狀態(tài)直接轉(zhuǎn)換到另一個(gè)狀態(tài)3.8 三階段提交協(xié)議三階段提交協(xié)議3 3 分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可靠性協(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.8 三階段提交協(xié)議三階段提交協(xié)議3 3 分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議分布式數(shù)據(jù)庫(kù)的可靠性協(xié)議IWACc

25、ommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevote-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)者參與者開

26、始-3PC 記錄寫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 abo

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

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

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

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

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

32、論 獨(dú)立恢復(fù)協(xié)議只存在于單站點(diǎn)故障的情形 若發(fā)生網(wǎng)絡(luò)分割的時(shí)候, 丟了報(bào)文的話, 則不存在任何非阻斷的協(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ù)庫(kù) 任何需要訪問(wèn)存儲(chǔ)在另一網(wǎng)絡(luò)區(qū)域里的數(shù)據(jù)項(xiàng)的新事務(wù)都被阻斷, 等待網(wǎng)絡(luò)修復(fù) 位于同一區(qū)域里的數(shù)據(jù)項(xiàng)的并發(fā)訪問(wèn)由并發(fā)控制算法處理 網(wǎng)絡(luò)分割時(shí)由提交協(xié)議處理 冗余數(shù)據(jù)庫(kù) 分割時(shí), 副本可能位于不同的區(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ù)庫(kù)處理網(wǎng)絡(luò)分割的終結(jié)協(xié)議 集中式協(xié)議，基

33、于集中式并發(fā)控制算法(主站點(diǎn)法和主副本法) 基于表決的協(xié)議 冗余數(shù)據(jù)庫(kù)處理網(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é)議 多數(shù)法和基于法定人數(shù)法 在事務(wù)中止或提交前, 大多數(shù)站點(diǎn)必須一致同意中止或提交 基于法定人數(shù)的規(guī)則 每個(gè)站點(diǎn)i有選票數(shù)Vi, Vi是正整數(shù) V= Vi 事務(wù)在提交前，它必須獲得提交法定票數(shù)Vc 事務(wù)在Abort前，它必須獲得Abort法定票數(shù)Va Va+VcV, 當(dāng)0 Va, Vc Vni=14.2 基于表決的協(xié)議基于表決的協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 網(wǎng)絡(luò)分割時(shí), 在每個(gè)分割部分選擇一個(gè)新的

34、協(xié)調(diào)者 3PC中加入PA狀態(tài), 從而不允許從Wait /Ready到Abort 狀態(tài)的轉(zhuǎn)換 原因 有多個(gè)協(xié)調(diào)者阻止事務(wù)終結(jié), 不允許多個(gè)協(xié)調(diào)者得出不同的結(jié)論, 因此希望協(xié)調(diào)者獲得撤銷的決定 如果新協(xié)調(diào)者故障, 它不知道是否達(dá)到提交或撤銷的法定票數(shù), 這樣參與者必須明確做出提交或撤銷的決定 Ready(或Wait)都不滿足該需求, 預(yù)示引入另一個(gè)狀態(tài)Pre-Abort, 該狀態(tài)在Ready和Abort之間4.2 基于表決的協(xié)議基于表決的協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議IWACcommitpreparevote-abortglobal-abortvote-commitprepare

35、-to-commitIRACpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort基于法定人數(shù)3PC中事務(wù)的狀態(tài)轉(zhuǎn)換圖PCPCready-to-commitglobal-commit global-commitACK(a) 協(xié)調(diào)者(b) 參與者PAready-to-abortglobal-abortPAready-to-abortglobal-abort 基于法定人數(shù)的3PC集中式協(xié)議 選擇一個(gè)新的協(xié)調(diào)者 協(xié)調(diào)者收集狀態(tài)信息, 并按如下規(guī)則執(zhí)行1) 若至少一個(gè)站點(diǎn)已Commit(Abo

36、rt), 則協(xié)調(diào)者對(duì)其它站點(diǎn)發(fā)送Commit(Abort)命令2) 若處于PC狀態(tài)站點(diǎn)的票數(shù)=Vc, 則發(fā)送Commit3) 若PA狀態(tài)站點(diǎn)的票數(shù)=Va, 則發(fā)送Abort4) 若PC狀態(tài)站點(diǎn)的票數(shù)+Ready狀態(tài)站點(diǎn)的票數(shù)=Vc, 則發(fā)送PC命令給不確定站點(diǎn), 等待2)狀態(tài)出現(xiàn)5) 若PA狀態(tài)站點(diǎn)的票數(shù)+Ready狀態(tài)站點(diǎn)的票數(shù)=Va, 則發(fā)送PA命令給不確定站點(diǎn), 等待3)狀態(tài)出現(xiàn)6) 否則, 等待故障修復(fù)4.2 基于表決的協(xié)議基于表決的協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 數(shù)據(jù)復(fù)制的目的 高吞吐量 較好的響應(yīng)時(shí)間 高可用性 復(fù)制作為可選擇的提交協(xié)議 數(shù)據(jù)在多站點(diǎn)獨(dú)立更新, 使

37、用“惰性復(fù)制協(xié)議”減少數(shù)據(jù)不一致問(wèn)題. 4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 基本方法： 每個(gè)副本看作一個(gè)獨(dú)立的數(shù)據(jù)項(xiàng)X1X2X3Lockmgr X3Lockmgr X2Lockmgr X1TxiTxjTxk對(duì)象 X 有副本 X1, X2, X34.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 Read(X): 獲取 X1 共享鎖 獲取 X2 共享鎖 獲取 X3 共享鎖 分別讀 X1, X2, X3 事務(wù)結(jié)束時(shí), 釋放 X1, X2, X3 鎖X1lockmgrX3lockmgrX2lockmgrread Write(X):

38、獲取 X1 互斥鎖 獲取 X2 互斥鎖 獲取 X3 互斥鎖 寫新值到 X1, X2, X3 事務(wù)結(jié)束時(shí), 釋放 X1, X2, X3 鎖X1X3X2locklocklockwritewritewrite 讀鎖和訪問(wèn)只對(duì)一個(gè)副本 寫鎖全部, 并且更新全部副本 讀可用性高 寫可用性低，只要有一個(gè)副本不可獲得，更新事務(wù)就不能終結(jié)ROWA方法X1X2X3讀者加鎖寫者發(fā)現(xiàn)沖突!4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議ROWA的改進(jìn)(ROWA-A) ROWA-A “讀一個(gè)寫所有可獲得協(xié)議” 基本思想是寫命令在所有可獲得的副本上執(zhí)行，然后事務(wù)終結(jié)，當(dāng)時(shí)不可獲得的副本將在它

39、們重新可獲得時(shí)被捕獲 更新事務(wù)T的協(xié)調(diào)者向所有包含x副本的站點(diǎn)發(fā)送WT(x), 并等待執(zhí)行(或拒絕)的確認(rèn). 當(dāng)不可獲得站點(diǎn)恢復(fù)時(shí), 也將更新自己的數(shù)據(jù)庫(kù). 但如果站點(diǎn)在T開始之前就不可獲得, 它們就可能沒(méi)有注意到T的存在, 以及T對(duì)x的更新. 問(wèn)題 協(xié)調(diào)者認(rèn)為不可獲得的參與者仍然工作, 并且更新了x , 但是其確認(rèn)沒(méi)有到達(dá)協(xié)調(diào)者 站點(diǎn)在事務(wù)啟動(dòng)時(shí)不可獲得, 隨后恢復(fù)并開始執(zhí)行事務(wù)4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 于是, 協(xié)調(diào)者在提交前要進(jìn)行有效性驗(yàn)證 檢查所有不可獲得的站點(diǎn)是否仍然不可獲得, 如果協(xié)調(diào)者收到一個(gè)響應(yīng), 它就撤銷T. 若都是不可獲得,

40、 則檢查在WT(x)執(zhí)行是可獲得的站點(diǎn)仍然可獲得, 是則提交事務(wù) ROWA-A比ROWA協(xié)議能更好地適應(yīng)失效, 包括網(wǎng)絡(luò)分割.ROWA的改進(jìn)(ROWA-A)4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議基于法定人數(shù)的復(fù)制控制 Gifford算法 讀法定人數(shù)Vr, 寫法定人數(shù)Vw 規(guī)則1：Vr + Vw V，可避免讀-寫沖突 規(guī)則2：Vw V/2，避免寫-寫沖突 該算法確保了在兩個(gè)不同網(wǎng)絡(luò)區(qū)域上啟動(dòng)且訪問(wèn)同一數(shù)據(jù)的事務(wù)不會(huì)同時(shí)終結(jié)4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議惰性復(fù)制協(xié)議 思想 只在一個(gè)或多個(gè)副本上執(zhí)行更新, 以后再將更

41、新傳播到所有副本上 特點(diǎn) 所有權(quán)參數(shù)：定義更新副本的權(quán)限, 副本可以更新就稱為主Copy(主站點(diǎn)), 否則稱輔Copy(輔站點(diǎn)) 傳播參數(shù)：定義何時(shí)把對(duì)一個(gè)副本的更新傳播到包含該對(duì)象的其它副本 刷新參數(shù)：定義了刷新事務(wù)的調(diào)度策略 配置參數(shù)：描述站點(diǎn)和網(wǎng)絡(luò)的特點(diǎn)4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 兩類 所有副本都可更新, 存在副本的組所有權(quán), 常用延遲立即方式更新 只有一個(gè)被更新的主站點(diǎn)(惰性主站點(diǎn)法) 幾種刷新方案: 按需刷新, 每次提交執(zhí)行查詢時(shí), 執(zhí)行所有收到的刷新事務(wù)來(lái)刷新被查詢讀取的輔Copy, 造成查詢響應(yīng)延遲 成組刷新, 根據(jù)應(yīng)用刷新要求,

42、 成組執(zhí)行刷新事務(wù) 定期刷新, 在固定時(shí)間間隔內(nèi)觸發(fā)刷新惰性復(fù)制協(xié)議4.3 復(fù)制控制協(xié)議復(fù)制控制協(xié)議4 4 網(wǎng)絡(luò)分割與提交協(xié)議網(wǎng)絡(luò)分割與提交協(xié)議 網(wǎng)絡(luò)的一致視圖 可靠性算法是假定: 全部能工作的站點(diǎn)對(duì)網(wǎng)絡(luò)的所有站點(diǎn)(包括其本身)的狀態(tài)(即工作或故障)具有一致的視圖 決定網(wǎng)絡(luò)的一致視圖 監(jiān)視網(wǎng)絡(luò)的狀態(tài)，當(dāng)站點(diǎn)狀態(tài)發(fā)生轉(zhuǎn)換時(shí), 能及時(shí)發(fā)現(xiàn) 新的信息一致地傳播給全部站點(diǎn)5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 假設(shè) 建于廣義的網(wǎng)絡(luò)范圍內(nèi) 每個(gè)站點(diǎn)有一狀態(tài)表, 每個(gè)站點(diǎn)一個(gè)表項(xiàng), 記錄其工作/不工作，程序可查詢狀態(tài)表得到狀態(tài)信息 任何程序能夠在任一站點(diǎn)設(shè)

43、置一個(gè)“看守”, 當(dāng)該站點(diǎn)變化狀態(tài)時(shí)它就收到一個(gè)中斷 分割時(shí), 狀態(tài)表和一致視圖的意義 站點(diǎn)只認(rèn)為那些能和它通信的站點(diǎn)是工作的 一致視圖的數(shù)目與分離的站點(diǎn)組數(shù)目一樣多5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 監(jiān)視網(wǎng)絡(luò)的狀態(tài) 決定一站點(diǎn)是否工作時(shí)向它請(qǐng)求一個(gè)報(bào)文, 然后等待到超時(shí) 控制站點(diǎn) (請(qǐng)求站點(diǎn)) 受控站點(diǎn) 在一廣義監(jiān)視算法中，受控站點(diǎn)周期性地發(fā)送I-am-up（我在工作）報(bào)文5.1 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法網(wǎng)絡(luò)站點(diǎn)K-3UP站點(diǎn)K-2DOWN站點(diǎn)K-1站點(diǎn)KUPDOWN(狀態(tài))網(wǎng)絡(luò)上站

44、點(diǎn)的狀態(tài)站點(diǎn)K控制站點(diǎn)K-3, 即它檢查來(lái)自K-3的I-am-up報(bào)文是否到達(dá)，站點(diǎn)K負(fù)責(zé)發(fā)現(xiàn)站點(diǎn)K-1和K-2從不工作到工作的恢復(fù)，上圖中K-1和K-2不一定是有故障, 它們可能在分割的另一組中，圖反映了站點(diǎn)K和K-3的網(wǎng)絡(luò)視圖 廣播新的狀態(tài) 監(jiān)視功能每次檢測(cè)出一個(gè)狀態(tài)變化, 就激活此廣播功能 此功能的目的是廣播新的狀態(tài)表，使同一組的全部站點(diǎn)具有相同的狀態(tài)表 此功能可由若干站點(diǎn)并行激活, 需要某種機(jī)構(gòu)來(lái)控制沖突 狀態(tài)表的每個(gè)新的版本附加一全局唯一的時(shí)間戳 在I-am-up報(bào)文中包含當(dāng)前狀態(tài)表的版本號(hào) 啟動(dòng)新狀態(tài)表廣播的站點(diǎn)首先執(zhí)行一次同步以獲得一時(shí)間戳，然后發(fā)送狀態(tài)表給已回答的所有站點(diǎn)5.1

45、 決定網(wǎng)絡(luò)的狀態(tài)決定網(wǎng)絡(luò)的狀態(tài)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 需求 處理故障的策略有可能犧牲正確性來(lái)提高可用性，因此接受了不一致性的風(fēng)險(xiǎn) 在這種情況下，監(jiān)測(cè)這些不一致性，并盡可能地加以解決是很有用的 概念 需要首先發(fā)現(xiàn)哪些數(shù)據(jù)部分已經(jīng)不一致（不一致性檢測(cè)） 然后根據(jù)發(fā)生的情況，給這些部分賦予一個(gè)最合理的值（不一致性的解法）5.2 不一致性的檢測(cè)和解決方法概念不一致性的檢測(cè)和解決方法概念5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 提出問(wèn)題 假設(shè)網(wǎng)絡(luò)分割期間, 在兩個(gè)或多個(gè)站點(diǎn)組中已執(zhí)行了若干事務(wù), 可能對(duì)同一數(shù)據(jù)片斷的不同副本進(jìn)行了獨(dú)立更新 檢測(cè)方法 一種比較自然

46、的方法 比較各副本的內(nèi)容, 檢查其是否相同，但是這種方法不僅效率低，一般也是不正確的。5.3 不一致性的檢測(cè)不一致性的檢測(cè)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 檢測(cè)方法 采用版本號(hào) 允許對(duì)數(shù)據(jù)項(xiàng)操作的站點(diǎn)的副本是主副本, 其它是孤立或隔離的副本 正常工作期間, 全部副本都是主副本, 并且互相一致, 每份副本維持一個(gè)原版號(hào)和一個(gè)當(dāng)前版本號(hào) 網(wǎng)絡(luò)分割時(shí), 每個(gè)孤立副本的原版本號(hào)被置為當(dāng)前版本號(hào)值, 并且, 直到分割修復(fù)為止, 此原版號(hào)不會(huì)改變5.3 不一致性的檢測(cè)不一致性的檢測(cè)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 例子 已知前提 數(shù)據(jù)項(xiàng)x的副本x1, x2, x3

47、存儲(chǔ)在三個(gè)不同站點(diǎn) V1, V2, V3分別是x1, x2, x3的版本號(hào) 初始時(shí), 三份副本一致, 所以有: V1=(0, 2)，V2 =(0, 2)，V3=(0, 2)，假設(shè)經(jīng)過(guò)了兩次更新 （原版本號(hào)，當(dāng)前版本號(hào)） 發(fā)生一次分割, 把x3從其它兩個(gè)副本分開, 多數(shù)法選擇x2和x1為主副本, 版本號(hào)變?yōu)?V1=(0, 2)，V2 =(0, 2)， V3=(2, 2) 網(wǎng)絡(luò)分割期間, 假設(shè)只更新主副本, 版本號(hào)為 V1=(0, 3)，V2 =(0, 3) ，V3=(2, 2) 修復(fù)后, 可以看出x3未曾修改5.3 不一致性的檢測(cè)不一致性的檢測(cè)5 5 不一致性檢測(cè)和解決方法不一致性檢測(cè)和解決方法 假設(shè)分割時(shí), 只更新x3, 版本號(hào)為 V1=(0, 2) V2 =(0, 2) V3=(2, 3) 此時(shí)若沒(méi)有其它孤立副本, 則可以用x3的更新施加到主副本, 但若還有x4，V4=(2,3)， 則即使x3與x4版本號(hào)相同也不能說(shuō)其是一致的 若主副本與孤立副本都更新過(guò), 版本號(hào)為 V1=(0, 3) V2 =(0, 3) V3=