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