分布式數(shù)據(jù)庫及相關(guān)問題(參考版)
2025-05-14 08:00本頁面
【正文】 。 2. 總結(jié)基本時標(biāo)法和保守時標(biāo)法控制并發(fā)事務(wù)的過程。 //說明兩者之間沒有發(fā)生過其他更新操作！ 否則，該站點(diǎn)投否定票。 3. 寫階段：如果驗(yàn)證獲得通過，則提交該事務(wù)，否則重新啟動事務(wù)。 2）各站點(diǎn)進(jìn)行表決，并把表決結(jié)果回送源站點(diǎn)。 2. 驗(yàn)證階段：檢測事務(wù)對數(shù)據(jù)庫的更新是否會導(dǎo)致破壞數(shù)據(jù)庫的一致性。更新表的內(nèi)容： 1）所有讀數(shù)據(jù)對象及其時標(biāo) 2）所有寫數(shù)據(jù)對象的新值。 例站點(diǎn) i上緩沖區(qū)隊(duì)列情況如下： 站點(diǎn) 1 站點(diǎn) 2 ? 站點(diǎn) n R11 R12 R13 W11 R21 R22 R23 R24 W21 W22 … Rn1 Rn2 Wn2 讀隊(duì)列 寫隊(duì)列 站點(diǎn) i 上處理緩沖區(qū)隊(duì)列上的操作算法： 重復(fù)執(zhí)行如下步驟，直到?jīng)]有滿足執(zhí)行條件的 Rij 和 Wij ，或者至少出現(xiàn)一個讀 /寫隊(duì)列為空， 此時 RT/WT=0： 1）令： RT = min(Rij), WT = min(Wij) i：站點(diǎn)序號； j：讀 /寫操作的序號 2）按下列原則處理緩沖區(qū)內(nèi)各個站點(diǎn)讀 /寫隊(duì)列： * 掃描讀隊(duì)列若各隊(duì)列存在若干個 Rij WT,則，按時標(biāo)順序 逐一執(zhí)行 Rij，并使 Rij出隊(duì)列 * 掃描寫隊(duì)列若各隊(duì)列存在若干個 Wij RT,則，按時標(biāo)順序 逐一執(zhí)行 Wij，并使 Wij出隊(duì)列 五 并發(fā)控制的樂觀方法 驗(yàn)證 讀 /計(jì)算 寫 /提交 悲觀法事務(wù)的執(zhí)行過程 讀 /計(jì)算 驗(yàn)證 寫 /提交 樂觀法事務(wù)的執(zhí)行過程 樂觀方法的特點(diǎn)： 1） 任何事務(wù)在寫一個數(shù)據(jù)項(xiàng)之前，必須首先讀該數(shù)據(jù)項(xiàng)。 （ 3）每個站點(diǎn)都開辟一個緩沖區(qū)，用于保存其它站點(diǎn)發(fā)來的讀 / 寫操作。 （ 2）每個站點(diǎn)必須按照時標(biāo)時間的順序發(fā)送讀 / 寫數(shù)據(jù)的請求。 規(guī)則： （ 1）每個事務(wù)只在一個站點(diǎn)執(zhí)行。 若 TS WTM(x)， 則， 拒絕該操作；并使發(fā)出該操作的事務(wù)用新時標(biāo)重新啟動； 否則， 執(zhí)行讀操作，且使： RTM(x) = max（ RTM(x), TS） 2）設(shè) TS是對數(shù)據(jù)對象 x進(jìn)行寫操作的當(dāng)前時標(biāo)。 4）在事務(wù)結(jié)束之前，不對數(shù)據(jù)庫進(jìn)行物理操作。 3）事務(wù)的每個讀或?qū)懖僮鞫加性撌聞?wù)的時標(biāo)。 若 ts(Ti) ts(Tj) , 則 Qi在 Qj之前執(zhí)行。 四 并發(fā)控制的時標(biāo)技術(shù) 1. 時標(biāo) :唯一識別一個事務(wù)，并用于對事務(wù)進(jìn)行排序的標(biāo)識符。 ● 撤消并恢復(fù)占用資源較少的事務(wù)。 4）死鎖的解決 原則：撤消并恢復(fù)代價最小的事務(wù)。 站點(diǎn) A 站點(diǎn) B 事務(wù) T1持有 對 X的鎖 事務(wù) T2持有 對 Y的鎖 事務(wù) T2請求 對 X的鎖 事務(wù) T1請求 對 Y的鎖 T2等待 T1 完成釋放 對 X的鎖 T1等待 T2 完成釋放 對 Y的鎖 2）全局等待圖（ GWFG） 站點(diǎn) A:擁有 x 、 y的副本； T1: read(x), write(y) 站點(diǎn) B:擁有 y 、 z的副本； T2: read(y), write(z) 站點(diǎn) C:擁有 z 的副本； T3: read(z), write(x) T1 T2 T3 X y z 3）死鎖的檢測 A 集中式死鎖檢測法 ● 指定某站點(diǎn)上的鎖管理器作為全局死鎖檢測器 ● 其余站點(diǎn)周期地向全局死鎖檢測器發(fā)送 LWFG ● 全局死鎖檢測器產(chǎn)生 GWFG，并檢測有無回路 B 分布式死鎖檢測法 ● 每個站點(diǎn)都有死鎖檢測器，負(fù)責(zé)檢測本地可能的死鎖。 ● 遵守鎖的相容性規(guī)則 ● 遵守兩段鎖協(xié)議（ Two Phase Locking2PL) ● 持有 X鎖的事務(wù)，必須到結(jié)束事務(wù)才能開鎖。 算法：對主副本加鎖；執(zhí)行更新操作；開鎖 3）分布式加鎖算法：鎖的管理由各個站點(diǎn)調(diào)度器參與、協(xié)調(diào)，本地調(diào)度器負(fù)責(zé)本站數(shù)據(jù)加鎖。 2) 任意兩個沖突操作在它們同時出現(xiàn)的各個局部調(diào)度中，必須有相同的執(zhí)行順序。 站點(diǎn) 1 調(diào)度 S1 = { R1, W1, C1, R2, W2, C2 } 站點(diǎn) 2 調(diào)度 S2 = { R2, W2, C2 , R1, W1, C1 } 設(shè)：站點(diǎn) 1， 站點(diǎn) 2上都有 y的副本，且 都執(zhí)行事務(wù) T1, T2。 Write(y)。 T2: Read(y)。 Write(y)。 T1: Read(y)。 2 局部調(diào)度：每個站點(diǎn)上的調(diào)度稱為局部調(diào)度 3 全局調(diào)度：數(shù)據(jù)庫系統(tǒng)全局事務(wù)的調(diào)度。 本節(jié)重點(diǎn) 167。 1. 試比較集中式、分布式事務(wù)的特點(diǎn)。 ● 處于“就緒”狀態(tài)的參與者可能進(jìn)入提交狀態(tài)，或撤消狀態(tài)。 兩階段提交協(xié)議的特點(diǎn)： ● 參與者有權(quán)單方面撤消事務(wù)。 ● 參與者進(jìn)入“撤消”或“提交”狀態(tài)。 ●協(xié)調(diào)者寫撤消日志； ●協(xié)調(diào)者發(fā)出“全局撤消”消息； ●協(xié)調(diào)者進(jìn)入“撤消”狀態(tài)。 ●協(xié)調(diào)者寫提交日志； ●協(xié)調(diào)者發(fā)出“全局提交”消息； ●協(xié)調(diào)者進(jìn)入“提交”狀態(tài)。 Case2:不可以提交子事務(wù)： ※ 參與者寫 “ 撤消 ” 日志； ※ 向協(xié)調(diào)者發(fā) “ 建議撤消 ” 消息； ※ 參與者進(jìn)入 “ 撤消 ” 狀態(tài)。 ① 協(xié)調(diào)者： ●寫 “ 開始事務(wù) ” 日志； ●向各個參與者發(fā)出 “ 準(zhǔn)備 ” 命令； ●進(jìn)入等待狀態(tài)。 send to ROOT_AGENT(‘ SUCCESS’ / ‘ FAIL’ ) waitting mit / abort 二 . 分布式事務(wù)的兩階段提交協(xié)議 2PC:TwoPhase Commitment Protocal 協(xié)調(diào)者 日志 參與者 。 waitting mit / abort end AGENT（子代理） : begin transaction receive from ROOT_AGENT( AMOUNT,TO_ACC )。 create AGENT。 begin transaction select BALANCE into FROM_AMOUNT from ACCOUNT_TABLE where ACCOUNT_NO = FROM_ACC。 mit end 設(shè)：轉(zhuǎn)出帳戶在源站點(diǎn)上。 if FROM_AMOUNT AMOUNT 0 then abort else begin update ACCOUNT_TABLE set BALANCE = BALANCE AMOUNT where ACCOUNT_NO = FROM_ACC。 全局應(yīng)用事務(wù)： read(AMOUNT, FROM_ACC, TO_ACC)。 一個全局事務(wù)在執(zhí)行時分解為由若干與相應(yīng)站點(diǎn)有關(guān)的操作序列組成的“子事務(wù)”。在什么條件下可以利用半連接算法實(shí)現(xiàn)直接連接運(yùn)算？ 167。 本節(jié)重點(diǎn) 1. 總結(jié)分
高考資料相關(guān)推薦
鄂ICP備17016276號-1