【正文】 每個(gè)站點(diǎn)獨(dú)立于其它站點(diǎn)記錄其本地檢查點(diǎn) , 所以建立一致全局狀態(tài)由冷啟動(dòng)過程實(shí)現(xiàn) – 改進(jìn) 2PC, 使屬于兩個(gè)分布事務(wù) T和 T’的所有子事務(wù)的檢查點(diǎn)在執(zhí)行這兩個(gè)事務(wù)的所有站點(diǎn)中都以同樣的次序記錄 檢查點(diǎn)和冷啟動(dòng) 5 不一致性檢測和解決方法 總 結(jié) ?分布式數(shù)據(jù)庫可靠性的概念 ?分布式數(shù)據(jù)庫系統(tǒng)故障原因和容錯(cuò)技術(shù) ?分布式數(shù)據(jù)庫的可靠性協(xié)議 ?網(wǎng)絡(luò)分割與提交協(xié)議 ?不一致性的檢測和解決方法 。 – 如果一事務(wù) T被包含在 C中 , 則按串行化次序 , 在 T前面的全部沖突事務(wù)也包含在 C中 ? 重構(gòu)全局一致狀態(tài)的最簡單辦法是使用 – 本地轉(zhuǎn)儲(chǔ) – 本地的運(yùn)行紀(jì)錄 – 全局的檢查點(diǎn) 檢查點(diǎn)和冷啟動(dòng) 5 不一致性檢測和解決方法 ? 如果有全局檢查點(diǎn) , 則重構(gòu)就相對容易 . – 首先在故障站點(diǎn)處決定認(rèn)為是安全的最近的一個(gè)本地檢查點(diǎn) ,這就確定了必須重構(gòu)的較早的全局狀態(tài) – 然后請求所有其它站點(diǎn)重新建立相對應(yīng)的本地檢查點(diǎn)的本地狀態(tài) ? 存在的問題 – 只有一個(gè)站點(diǎn)把一“寫檢查點(diǎn)”報(bào)文廣播給所有其它站點(diǎn)是不夠的 , 因?yàn)榭赡艹霈F(xiàn)如下頁圖所述的情況 檢查點(diǎn)和冷啟動(dòng) 5 不一致性檢測和解決方法 站點(diǎn) 1 站點(diǎn) 2 站點(diǎn) 3 C1 時(shí)間 T2 C2 C3 T3 R C 其中： T2和 T3是事務(wù) T的子事務(wù)， T3是兩階段提交的協(xié)調(diào)者。 三階段提交協(xié)議的超時(shí)處理 3 分布式數(shù)據(jù)庫的可靠性協(xié)議 協(xié)調(diào)者 參與者 PREPARE PREPARED COMMIT PRECOMMIT ACK 1. 超時(shí) : Abort 3. 超時(shí) : 忽略 1. 超時(shí) : abort 2. 超時(shí) :終結(jié)協(xié)議 :終結(jié)協(xié)議 2. 超時(shí) : 把參與者 移入 PC ? 競選新的協(xié)調(diào)者 – 使用競選協(xié)議 ? 新協(xié)調(diào)者送出 REQUEST狀態(tài)給參與者 ? 使用終結(jié)規(guī)則做出決定 ? 與參與者通信 三階段提交協(xié)議的終結(jié)協(xié)議 3 分布式數(shù)據(jù)庫的可靠性協(xié)議 競選協(xié)議 ? 進(jìn)程全序 – 協(xié)調(diào)者 = 0, 參與者 1,…,n ? 任何時(shí)候 , 選擇 “最小的” 工作進(jìn)程為協(xié)調(diào)者 三階段提交協(xié)議的終結(jié)協(xié)議 3 分布式數(shù)據(jù)庫的可靠性協(xié)議 ? 終結(jié)規(guī)則 – 新協(xié)調(diào)者在 Wait狀態(tài)：將全局 Abort. 此時(shí)參與者可以在任何狀態(tài) , 若參與者是在 PC狀態(tài) , 即它是期望有“ GCommit” , 但是得到了“ GAbort”. 3PC中缺少從 PC到 Abort的轉(zhuǎn)換 , 這對終結(jié)協(xié)議很有用 . – 新協(xié)調(diào)者在 PC狀態(tài)：此時(shí)沒有參與者是在Abort狀態(tài) , 協(xié)調(diào)者可以全局提交 , 發(fā)送“ GCommit”命令 . – 新協(xié)調(diào)者在 Abort狀態(tài)：收到第一個(gè)消息后，所有參與者進(jìn)入 Abort狀態(tài) 三階段提交協(xié)議的終結(jié)協(xié)議 3 分布式數(shù)據(jù)庫的可靠性協(xié)議 ? 3PC與 2PC恢復(fù)協(xié)議的差別很小 – 協(xié)調(diào)者在 Wait狀態(tài)故障 , 按照終結(jié)協(xié)議，參與者已終結(jié)事務(wù) , 因此 , 協(xié)調(diào)者在恢復(fù)時(shí)必須查詢以決定事務(wù)的命運(yùn) – 協(xié)調(diào)者在 PC狀態(tài)故障 , 終結(jié)協(xié)議已使工作的參與者終結(jié) , 因此 , 協(xié)調(diào)者需詢問 – 一個(gè)參與者在 PC狀態(tài)故障 , 必須詢問以確定其它參與者如何終結(jié)事務(wù) 三階段提交協(xié)議的恢復(fù)協(xié)議 3 分布式數(shù)據(jù)庫的可靠性協(xié)議 ? 網(wǎng)絡(luò)分割是由通信線路故障引起的 – 簡單分割，僅僅是網(wǎng)絡(luò)分裂成兩部分 – 多重分割，更復(fù)雜 ? 網(wǎng)絡(luò)分割非阻斷協(xié)議的存在性 – 即在發(fā)生網(wǎng)絡(luò)分割時(shí) , 是否存在允許獨(dú)立恢復(fù)的協(xié)議 – 獨(dú)立恢復(fù)是指站點(diǎn)重啟動(dòng)時(shí) , 無需遠(yuǎn)程訪問 ? 若存在處理分割的非阻斷協(xié)議 , 那么 , 該協(xié)議可使某個(gè)分割中的站點(diǎn)到達(dá)終結(jié)決定 , 而且這個(gè)決定與另一分割中的決定一致 ? 一般結(jié)論 – 獨(dú)立恢復(fù)協(xié)議只存在于單站點(diǎn)故障的情形 – 若發(fā)生網(wǎng)絡(luò)分割的時(shí)候 , 丟了報(bào)文的話 , 則不存在任何非阻斷的協(xié)議能從網(wǎng)絡(luò)分割故障中恢復(fù) 網(wǎng)絡(luò)分割概述 4 網(wǎng)絡(luò)分割與提交協(xié)議 ? 非冗余數(shù)據(jù)庫 – 任何需要訪問存儲(chǔ)在另一網(wǎng)絡(luò)區(qū)域里的數(shù)據(jù)項(xiàng)的新事務(wù)都被阻斷 , 等待網(wǎng)絡(luò)修復(fù) – 位于同一區(qū)域里的數(shù)據(jù)項(xiàng)的并發(fā)訪問由并發(fā)控制算法處理 – 網(wǎng)絡(luò)分割時(shí)由 提交協(xié)議 處理 ? 冗余數(shù)據(jù)庫 – 分割時(shí) , 副本可能位于不同的區(qū)域 – 由 復(fù)制協(xié)議 處理 網(wǎng)絡(luò)分割概述 4 網(wǎng)絡(luò)分割與提交協(xié)議 ? 網(wǎng)絡(luò)分割處理策略 – 一致性與可用性的選擇 – 非冗余數(shù)據(jù)庫處理網(wǎng)絡(luò)分割的終結(jié)協(xié)議 ? 集中式協(xié)議，基于集中式并發(fā)控制算法 (主站點(diǎn)法和主副本法 ) ? 基于表決的協(xié)議 – 冗余數(shù)據(jù)庫處理網(wǎng)絡(luò)分割的終結(jié)協(xié)議 ? 復(fù)制控制協(xié)議 網(wǎng)絡(luò)分割概述 4 網(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+Vc≤V, 當(dāng) 0 ≤Va, Vc ≤V n i=1 基于表決的協(xié)議 4 網(wǎng)絡(luò)分割與提交協(xié)議 ? 網(wǎng)絡(luò)分割時(shí) , 在每個(gè)分割部分選擇一個(gè)新的協(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) PreAbort, 該狀態(tài)在 Ready和 Abort之間 基于表決的協(xié)議 4 網(wǎng)絡(luò)分割與提交協(xié)議 I W A C mit prepare voteabort globalabort votemit preparetomit I R A C prepare votemit globalabort ACK preparetomit readytomit prepare voteabort 基于法定人數(shù) 3PC中事務(wù)的狀態(tài)轉(zhuǎn)換圖 PC PC readytomit globalmit globalmit ACK (a) 協(xié)調(diào)者 (b) 參與者 PA readytoabort globalabort PA readytoabort globalabort ? 基于法定人數(shù)的 3PC集中式協(xié)議 – 選擇一個(gè)新的協(xié)調(diào)者 – 協(xié)調(diào)者收集狀態(tài)信息 , 并按如下規(guī)則執(zhí)行 1) 若至少一個(gè)站點(diǎn)已 Commit(Abort), 則協(xié)調(diào)者對其它站點(diǎn)發(fā)送 Commit(Abort)命令 2) 若處于 PC狀態(tài)站點(diǎn)的票數(shù) =Vc, 則發(fā)送 Commit 3) 若 PA狀態(tài)站點(diǎn)的票數(shù) =Va, 則發(fā)送 Abort 4) 若 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ù) 基于表決的協(xié)議 4 網(wǎng)絡(luò)分割與提交協(xié)議 ? 數(shù)據(jù)復(fù)制的目的 – 高吞吐量 – 較好的響應(yīng)時(shí)間 – 高可用性 ? 復(fù)制作為可選擇的提交協(xié)議 – 數(shù)據(jù)在多站點(diǎn)獨(dú)立更新 , 使用“惰性復(fù)制協(xié)議”減少數(shù)據(jù)不一致問題 . 復(fù)制控制協(xié)議 4 網(wǎng)絡(luò)分割與提交協(xié)議 ? 基本方法： – 每個(gè)副本看作一個(gè)獨(dú)立的數(shù)據(jù)項(xiàng) X1 X2 X3 Lock mgr X3 Lock mgr X2 Lock mgr X1 Txi Tx