復(fù)制定義和應(yīng)用

1、第6第6章 復(fù)制簡介 系統(tǒng)模型容錯服務(wù)高可用服務(wù)的實例研究：gossip體系結(jié)構(gòu)、Bayou和Coda小結(jié)簡介復(fù)制的概念 在多個計算機中進行數(shù)據(jù)副本的維護。復(fù)制的動機：增強服務(wù)增強性能 - 瀏覽器對Web資源的緩存 - 數(shù)據(jù)在多個服務(wù)器之間地透明復(fù)制提高可用性 - 服務(wù)器故障：1pn - 網(wǎng)絡(luò)分區(qū)和斷鏈操作：預(yù)先復(fù)制增強容錯能力 - 正確性：允許一定數(shù)量和類型的故障簡介復(fù)制的基本要求復(fù)制透明性 - 對客戶屏蔽多個物理拷貝的存在 - 客戶僅對一個邏輯對象進行操作一致性 - 在不同應(yīng)用中有不同強度的一致性需求 - 復(fù)制對象集合的操作必須滿足應(yīng)用需求第6章 復(fù)制簡介 系統(tǒng)模型容錯服務(wù)高可用服務(wù)的實例

2、研究：gossip體系結(jié)構(gòu)、Bayou和Coda小結(jié)系統(tǒng)模型基本模型FE請求和應(yīng)答C副本管理器C服務(wù)客戶前端RMRMFERM系統(tǒng)模型基本模型組件副本管理器 - 接收前端請求 - 對副本執(zhí)行原子性操作前端 - 接收客戶請求 - 通過消息傳遞與多個副本管理器進行通信系統(tǒng)模型副本對象的操作請求：前端將請求發(fā)送至一個或多個副本管理器協(xié)調(diào) - 保證執(zhí)行的一致性 - 對不同請求進行排序（FIFO，因果，全序）執(zhí)行：包括臨時請求的執(zhí)行協(xié)定：就提交請求的影響達成一致響應(yīng)：一個或多個副本管理器響應(yīng)前端第6章 復(fù)制簡介 系統(tǒng)模型容錯服務(wù)高可用服務(wù)的實例研究：gossip體系結(jié)構(gòu)、Bayou和Coda小結(jié)容錯服務(wù)復(fù)

3、制是提高系統(tǒng)容錯能力的有效手段之一為用戶提供一個單一的鏡像副本之間需要保持嚴(yán)格的一致性副本之間的不一致性將導(dǎo)致容錯能力失效銀行帳戶示例容錯服務(wù)1. 銀行帳戶x和y的兩個副本管理器位于計算機A、B上2. 客戶在本地的副本管理器上讀取和更新帳戶計算機AXY計算機 BXY同步客戶 2客戶 1容錯服務(wù)由于B在把帳戶x的更新傳送至A前出現(xiàn)故障，所以產(chǎn)生了不一致現(xiàn)象客戶1:setBalanceB(x,1)Server B failedsetBalanceA(y,2)客戶2:getBalanceA(y)=2getBalanceA(x)=0容錯服務(wù)被動(主備份)復(fù)制一個主副本管理器多個次副本管理器 - 若主副

4、本管理器出現(xiàn)故障，則某個備份副本管理器將提升為主副本管理器。模型FECFECRM主副本副本備份RMRM容錯服務(wù)被動復(fù)制時的事件次序請求 - 前端將請求發(fā)送給主副本管理器協(xié)調(diào) - 主副本管理器按接收次序?qū)φ埱笈判驁?zhí)行 - 主副本管理器執(zhí)行請求并存儲響應(yīng)容錯服務(wù)被動復(fù)制時的事件次序(續(xù))協(xié)定 - 若請求為更新操作，則主副本管理器向每個備份副本管理器發(fā)送更新后的狀態(tài)、響應(yīng)和唯一標(biāo)識符。 - 備份副本管理器返回確認(rèn)。響應(yīng) - 主副本管理器將響應(yīng)發(fā)送給前端 - 前端將響應(yīng)發(fā)送給客戶 容錯服務(wù)主動復(fù)制副本管理器地位對等，前端組播消息至副本管理器組模型FECFECRMRMRM容錯服務(wù)主動復(fù)制時的事件次序請求

5、 - 前端使用全序、可靠的組播原語將請求組播到副本管理器組協(xié)調(diào) - 組通信系統(tǒng)以同樣的次序(全序)將請求傳遞到每個副本管理器執(zhí)行 - 每個副本管理器以相同的方式執(zhí)行請求響應(yīng) - 每個副本管理器將響應(yīng)發(fā)送給前端 - 前端將響應(yīng)發(fā)送給客戶第6章 復(fù)制簡介 系統(tǒng)模型容錯服務(wù)高可用服務(wù)的實例研究：gossip體系結(jié)構(gòu)、Bayou和Coda小結(jié)高可用服務(wù)的實例研究高可用性和容錯能力容錯能力 - 只要可能，所有正確的副本管理器都能夠及時收到更新，并在將控制傳遞回客戶以前達成一致。高可用性 - 采用較弱程度的一致性，提高共享數(shù)據(jù)的可用性。 - 實例：gossip、Bayou和Codagossip體系結(jié)構(gòu)體系

6、結(jié)構(gòu)前端可以選擇任意副本管理器提供兩種基本操作：查詢更新副本管理器定期通過gossip消息來傳遞客戶的更新QueryValFERMRMRMQuery, prevVal, newUpdateFEUpdate id服務(wù)客戶Update,prev(2,2,3)gossip體系結(jié)構(gòu)體系結(jié)構(gòu)(續(xù))系統(tǒng)的兩個保證 - 隨著時間的推移，每個用戶總能獲得一致服務(wù)副本管理器提供的數(shù)據(jù)能反映迄今為止客戶已經(jīng)觀測到的更新 - 副本之間松弛的一致性所有副本管理器最終將收到所有更新兩個客戶可能會觀察到不同的副本客戶可能觀察到過時數(shù)據(jù)gossip體系結(jié)構(gòu)查詢和更新操作流程請求 - 前端將請求發(fā)送至副本管理器查詢：客戶可能

7、阻塞更新：無阻塞更新響應(yīng) - 副本管理器立即應(yīng)答收到的更新請求協(xié)調(diào) - 收到請求的副本管理器并不處理操作，直到它能根據(jù)所要求的次序約束處理請求為止。gossip體系結(jié)構(gòu)查詢和更新操作流程(續(xù))執(zhí)行 - 副本管理器執(zhí)行請求查詢響應(yīng) - 副本管理器對查詢請求作出應(yīng)答協(xié)定 - 副本管理器通過交換gossip消息進行相互更新gossip消息的交換是偶爾的發(fā)現(xiàn)消息丟失后，才和特定的副本管理器交換消息gossip體系結(jié)構(gòu)前端的版本時間戳客戶交換數(shù)據(jù) -通過訪問相同的gossip服務(wù) - 相互直接通信FE客戶FE服務(wù)時間戳向量RMRMRMgossip為了控制操作處理次序，每個前端維持了一個向量時間戳goss

8、ip體系結(jié)構(gòu)前端的版本時間戳(續(xù))每個前端維護一個向量時間戳 - 每個副本管理器有一條對應(yīng)的記錄 - 更新或查詢信息中包含時間戳 -合并操作返回的時間戳與前端時間戳向量時間戳的作用 - 反映前端訪問的最新數(shù)據(jù)值gossip體系結(jié)構(gòu)副本管理器狀態(tài)副本時間戳更新日志值時間戳值執(zhí)行操作表穩(wěn)定的更新更新gossip消息FE副本時間戳副本日志OperationIDUpdate PrevFE副本管理器其它的副本管理器時間戳表gossip體系結(jié)構(gòu)副本管理器狀態(tài)(續(xù))值 - 副本管理器維護的應(yīng)用狀態(tài)的值值的時間戳 - 更新的向量時間戳更新日志 - 記錄更新操作副本的時間戳 - 已經(jīng)被副本服務(wù)器接收到的更新go

9、ssip體系結(jié)構(gòu)副本管理器狀態(tài)(續(xù))已執(zhí)行操作表 - 記錄已經(jīng)執(zhí)行的更新的唯一標(biāo)識符，防止重復(fù)執(zhí)行時間戳表 - 確定何時一個更新已經(jīng)應(yīng)用于所有的副本管理器gossip體系結(jié)構(gòu)查詢操作副本管理器收到查詢 - q.prevalueTS立即響應(yīng)返回消息中的時間戳為valueTS - 否則將消息保存到保留隊列如：q.pre(2,4,6),valueTS(2,5,5)前端收到查詢響應(yīng) - 合并時間戳：frontEndTS:=merge(frontEndTS,new)(2,5,6)gossip體系結(jié)構(gòu)按因果次序處理更新前端發(fā)送更新請求：(u.op, u.prev, u.id)副本管理器i接收請求 - 丟棄

10、：操作已經(jīng)處理過 - 否則，將更新記錄日志ts =u.prev, tsi=tsi+1logRecord= - 副本管理器將ts返回給前端frontEndTS=merge(frontEndTS, ts)gossip體系結(jié)構(gòu)按因果次序處理更新(續(xù))更新請求u的穩(wěn)定性條件u.prevvalueTS副本管理器的更新操作 - value := apply(value, r.u.op) - valueTS := merge(valueTS, r.ts) - executed := executedr.u.idgossip體系結(jié)構(gòu)強制的和即時的更新操作強制更新和即時更新需要特殊處理，強制更新是全序加因果序，

11、保證更新的強制次序的基本方法是在相現(xiàn)象的時間戳后加入一個唯一的序號，并以這個序號的次序來處理它們。gossip消息 副本管理器通過gossip消息來更新自身的狀態(tài)。通過時間戳表里的記錄來估計其它副本管理器還沒有收到哪些更新。gossip消息m的格式：日志和副本時間戳gossip體系結(jié)構(gòu)收到gossip消息后執(zhí)行的操作日志合并 - 若r.ts replicsTS，則丟棄 - 將記錄加入到日志，合并時間戳replicaTS := merge(replicaTS, m.ts)執(zhí)行任何以前沒有執(zhí)行并已經(jīng)穩(wěn)定了的更新 - 根據(jù)向量時間戳的偏序“”對更新進行排序，并依次執(zhí)行更新。當(dāng)知道更新已執(zhí)行并沒有重復(fù)

12、執(zhí)行的危險時，刪除日志和已執(zhí)行操作表中的記錄 - 若tableTSic r.tsc，則丟棄r。gossip體系結(jié)構(gòu)更新傳播gossip體系結(jié)構(gòu)未規(guī)定具體的更新傳播策略如何選擇合適的gossip消息的發(fā)送頻率？ - 分鐘、小時或天？由具體應(yīng)用需求決定如何選擇合適的合作者(副本管理器) - 隨機策略使用加權(quán)概率來選擇更合適的合作者 - 確定策略使用副本管理器狀態(tài)的函數(shù)來選擇合作者 - 拓?fù)洳呗跃W(wǎng)格、環(huán)、樹gossip體系結(jié)構(gòu)目標(biāo)：保證服務(wù)的高可用性存在問題：不適合接近實時的更新復(fù)制可擴展性問題Bayou系統(tǒng)和操作變換方法Bayou系統(tǒng)簡介與gossisp體系結(jié)構(gòu)和基于時間戳的反熵協(xié)議類似提供的一致

13、性保證弱于順序一致性能夠進行沖突檢測和沖突解決 - 操作變換：一個或多個相沖突的操作被取消或改變以解決沖突的過程。 - 例子行政主管和秘書同時預(yù)約 ，其中行政主管為離線更新行政主管上線后，Bayou系統(tǒng)檢測到?jīng)_突，然后批準(zhǔn)行政主管的預(yù)約而取消秘書的預(yù)約。Bayou系統(tǒng)和操作變換方法提交的更新和臨時更新臨時的更新更新首次應(yīng)用于數(shù)據(jù)庫時，被標(biāo)記為臨時的。提交的更新Bayou將臨時的更新以規(guī)范次序放置，并添加提交標(biāo)識。數(shù)據(jù)庫副本狀態(tài)提交的更新序列臨時的更新序列更新重排序 新更新到達或某個臨時更新被修改為提交的更新Bayou系統(tǒng)和操作變換方法提交更新和臨時更新示例t2t1t0cNc2c1c0Ti+1t

14、i.已提交臨時臨時更新ti成為下一個提交更新，并被插入到最新提交更新cN之后Bayou系統(tǒng)和操作變換方法依賴檢查和合并過程依賴檢查 - 一個更新執(zhí)行時是否會產(chǎn)生沖突 - 例子：寫寫沖突、讀寫沖突檢測合并過程 - 改變將要執(zhí)行的操作，避免沖突，并獲得相似效果 - 無法合并系統(tǒng)報錯Bayou系統(tǒng)討論復(fù)制對于應(yīng)用而言是不透明的復(fù)雜度高Coda文件系統(tǒng)AFS的主要缺陷只提供有限復(fù)制，規(guī)模受限，不適用于大規(guī)模共享的文件訪問。Coda目標(biāo)提供一個共享的文件存儲。Coda對AFS的擴展采用文件卷復(fù)制技術(shù)提高吞吐率和容錯性在客戶計算機上緩存文件副本斷鏈處理Coda文件系統(tǒng)Coda體系結(jié)構(gòu)Venus/Vice進

15、程 - Venus：前端和副本管理器的混合體 - Vice：副本管理器卷存儲組(VSG) 持有一個文件卷副本的服務(wù)器集合可用的卷存儲組(AVSG) 打開一個文件的客戶能訪問的VSG的某個子集Coda文件系統(tǒng)Coda體系結(jié)構(gòu)(續(xù))文件訪問過程 - 當(dāng)前AVSG中的任何一個服務(wù)器提供文件服務(wù)，并緩存在客戶計算機上。 - 對每個副本管理器進行更新分布。關(guān)閉文件 - 修改過的拷貝并行廣播到AVSG中的所有服務(wù)器。Coda文件系統(tǒng)Coda體系結(jié)構(gòu)(續(xù))斷鏈操作 - AVSG為空時，客戶緩存文件 - 手工干預(yù)解決沖突設(shè)計原則 - 服務(wù)器上的拷貝比客戶計算機緩存中的拷貝更可靠Coda文件系統(tǒng)復(fù)制策略樂觀策略

16、 - 在網(wǎng)絡(luò)分區(qū)和斷鏈操作期間，仍然可以進行文件修改實現(xiàn) - Coda版本向量(CVV)作為時間戳附加在每個版本的文件上CVV中的每個元素是一個估計值，表示服務(wù)器上文件修改次數(shù)的估計目的提供足夠的關(guān)于每個文件副本的更新歷史，以檢測出潛在的沖突，進行手工干預(yù)和自動更新。Coda文件系統(tǒng)復(fù)制策略(續(xù))例如：CVV=（2，2，1） - 文件在服務(wù)器1上收到2個更新 -文件在服務(wù)器2上收到2個更新 -文件在服務(wù)器3上收到1個更新沖突檢測 - 若一個站點的CVV大于或等于所有其它站點相應(yīng)的CVV，則不存在沖突。自動更新 - 若對于兩個CVV而言，v1v2與v2v1均不成立，則存在一個沖突。 手工干預(yù)Co

17、da文件系統(tǒng)復(fù)制策略(續(xù).)文件關(guān)閉 - Venus進程發(fā)送更新消息（包括CVV和文件的新內(nèi)容）到AVSG - AVSG中的每個服務(wù)器更新文件，并返回確認(rèn)。 - Venus計算新的CVV，增加相應(yīng)服務(wù)器的修改記數(shù)，并分發(fā)新的CVV。CRMRMRM2, 2, 12, 2, 12, 2, 13, 3, 22, 2, 1Coda文件系統(tǒng)構(gòu)建CVV示例一文件F在三個服務(wù)器S1、S2和S3上有副本 - VSG = S1, S2, S3 - F被C1,C2修改 - 由于網(wǎng)絡(luò)分區(qū)的原因C1: S1, S2； C2: S3Coda文件系統(tǒng)構(gòu)建CVV示例一(續(xù))最初，F(xiàn)的CVV在3個服務(wù)器上是相同的，比如1, 1, 1C1修改F，然后關(guān)閉 - S1和S2上的CVV更新為：2, 2, 1Coda文件系統(tǒng)構(gòu)建CVV示例一(續(xù).)網(wǎng)絡(luò)故障修復(fù)后 - S1和S2上的CVV為2, 2, 1，S3上的CVV為1, 1, 1 - S1或S2上的文件版本替代S3上的文件版本Coda文件系統(tǒng)構(gòu)建CVV示例二文件F