分布式系統(tǒng)可靠性設(shè)計(jì)-資料下載頁
2025-01-07 04:00本頁面
【正文】 近的分布式快照，最近的一致性割集 ? 舉例 獨(dú)立檢查點(diǎn)（ 1） ? 獨(dú)立檢查點(diǎn) ? 每個(gè)進(jìn)程的檢查點(diǎn)是相互獨(dú)立的 ? 問題：多米諾效應(yīng) ? 局部狀態(tài)沒有形成分布式快照，導(dǎo)致級(jí)聯(lián)回滾（ cascaded rollback）過程 ? 舉例：只有 m,m39。的接受記錄，沒有發(fā)送記錄 獨(dú)立檢查點(diǎn)（ 2） ? 解決方法 ? 設(shè) CP[i](m)表示 Pi的第 m個(gè)檢查點(diǎn) ? 設(shè) INT[i](m)表示 CP[i](m)和 CP[i](m1)之間的間隔 ? 當(dāng) Pi在 INT[i](m)中發(fā)送消息 x時(shí)，帶上 (i,m) ? 當(dāng) Pj在 INT[j](n)收到 x后，記錄依賴關(guān)系INT[i](m)→ INT[j](n) ? Pj在 CP[j](n)中加入該依賴關(guān)系 ? 當(dāng) Pi需要回滾到 CP[i](m1)時(shí)，則 Pj需要回滾到 CP[j](n1) 協(xié)作式檢查點(diǎn)（ 2） ? 同步寫檢查點(diǎn) ? 所有進(jìn)程同步地在本地穩(wěn)存中寫檢查點(diǎn)，使保存的狀態(tài)自動(dòng)地保持全局一致。 ? 非阻塞式算法 ? 分布式快照算法 ? 兩階段阻塞式算法 ? CHECKPOINT_REQUEST： ? 協(xié)調(diào)者發(fā)送命令，所有進(jìn)程寫局部檢查點(diǎn)，將要發(fā)送消息插入隊(duì)列，向協(xié)調(diào)者返回 ACK消息。 ? CHECKPOINT_DONE： ? 當(dāng)協(xié)調(diào)者收到所有的 ACK后，發(fā)送命令，所有進(jìn)程繼續(xù) 協(xié)作式檢查點(diǎn)（ 2） ? 改進(jìn)算法 增量快照算法 ? 最近發(fā)送進(jìn)程： ? 進(jìn)程 P在上一個(gè)檢查點(diǎn)向其發(fā)送過請(qǐng)求的進(jìn)程。 ? 協(xié)調(diào)者恢復(fù)依賴進(jìn)程： ? 在上一個(gè)檢查點(diǎn)，直接或間接收到協(xié)調(diào)者消息的進(jìn)程。因此，由最近發(fā)送進(jìn)程的閉包集組成。 ? 協(xié)調(diào)者只向其最近發(fā)送進(jìn)程多播命令。 ? 當(dāng)進(jìn)程 P收到寫檢查點(diǎn)請(qǐng)求時(shí)，僅向 P的最近發(fā)送進(jìn)程，轉(zhuǎn)發(fā)該請(qǐng)求。每個(gè)進(jìn)程僅轉(zhuǎn)發(fā)該請(qǐng)求一次。 ? 當(dāng)所有進(jìn)程被確認(rèn)后，協(xié)調(diào)者發(fā)送第二個(gè)多播命令，開始實(shí)際寫檢查點(diǎn) 消息日志（ 1） ? 基本思想 ? 減少檢查點(diǎn)的個(gè)數(shù) ? 如果消息的傳送可以重放 (replay)，則可取得全局一致性狀態(tài)，而不必從穩(wěn)存恢復(fù)。 ? 分段確定性模型 (piecewise deterministic model)， 假定： ? 每個(gè)進(jìn)程在一序列的間隔中執(zhí)行，有先后次序，是確定性的。每個(gè)間隔是可重放的。 ? 每個(gè)間隔以一個(gè)非確定性事件開始，以下一個(gè)非確定形式件發(fā)生而結(jié)束。 ? 如果記錄所有非確定性事件，則全部執(zhí)行可重放。 消息日志（ 2） ? 孤兒進(jìn)程 ? 在進(jìn)程 P崩潰后，仍然存活的進(jìn)程。但在 P恢復(fù)后，其狀態(tài)與 P不一致 ? 舉例： ? 進(jìn)程 Q崩潰，消息 m2沒有寫日志 ? Q恢復(fù)后， m2,m3消息沒有重放，導(dǎo)致 R為孤兒進(jìn)程 消息日志（ 3） ? 消息 ? 消息頭：發(fā)送者、接受者、順序號(hào)、遞交號(hào) ? 穩(wěn)定消息：已記入穩(wěn)存，不會(huì)丟失 ? DEP(m)： ? 依賴于消息 m遞交的進(jìn)程集合。 ? 與 m有因果關(guān)系的進(jìn)程集合 ? COPY(m)： ? 擁有 m的副本，但未將 m寫入穩(wěn)存的進(jìn)程集合 . ? 孤兒進(jìn)程 ? Q存在于 DEP(m)，而 COPY(m)中的所有進(jìn)程崩潰 消息日志（ 4） ? 避免孤兒進(jìn)程 ? 如果 Q?DEP(m)，則保證 Q?COPY(m) ? 悲觀型 (pessimistic logging)日志協(xié)議 ? 保證每個(gè)不穩(wěn)定的消息 m最多提交到一個(gè)進(jìn)程 ? 不可能出現(xiàn)孤兒進(jìn)程 ? 樂觀型 (optimistic logging)日志協(xié)議 ? 在崩潰后處理，將 DEP(m)中的孤兒進(jìn)程都回滾到不再屬于 DEP(m)的狀態(tài) 小 結(jié) 1. 故障模型：故障類型、三模容錯(cuò) 2. 進(jìn)程容錯(cuò)技術(shù)：冗余容錯(cuò)、兩軍問題、拜占庭將軍問題 3. 客戶服務(wù)器容錯(cuò)問題 4. 組通信容錯(cuò)問題：原子多播、全局有序 5. 事務(wù)容錯(cuò)技術(shù)：兩段提交、三段提交 6. 恢復(fù)方法：分布式日志、消息日志 習(xí) 題 1. 在崩潰失敗的情況下，是什么使得 failstop模型難以實(shí)現(xiàn)？ 2. 如果一個(gè) Web瀏覽器返回一個(gè)過期的緩存的網(wǎng)頁，而不是服務(wù)器上的最新網(wǎng)頁。這是失敗嗎？如果是，屬于何種失??？ 3. 以下 TMR系統(tǒng)可應(yīng)付多少個(gè)故障元件（設(shè)備和表決器）？舉例說明可屏蔽掉的最壞的情況。 習(xí) 題 (續(xù) ) 4. 對(duì)以下應(yīng)用討論是最少一次語義還是最多一次語義合適： ① 從文件服務(wù)器讀寫文件 ② 編譯程序 ③ 遠(yuǎn)程銀行付款 5. 舉例說明不需要消息順序的分組通信 6. 虛擬同步性類似于分布式數(shù)據(jù)存儲(chǔ)器的弱一致性，它是以組視圖的變化作為同步點(diǎn)。那么，給出對(duì)應(yīng)于強(qiáng)一致性的同步性。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1