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

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

3、制是提高系統(tǒng)容錯(cuò)能力的有效手段之一為用戶提供一個(gè)單一的鏡像副本之間需要保持嚴(yán)格的一致性副本之間的不一致性將導(dǎo)致容錯(cuò)能力失效銀行帳戶示例容錯(cuò)服務(wù)1. 銀行帳戶x和y的兩個(gè)副本管理器位于計(jì)算機(jī)A、B上2. 客戶在本地的副本管理器上讀取和更新帳戶計(jì)算機(jī)AXY計(jì)算機(jī) BXY同步客戶 2客戶 1容錯(cuò)服務(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容錯(cuò)服務(wù)被動(dòng)(主備份)復(fù)制一個(gè)主副本管理器多個(gè)次副本管理器 - 若主副

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

5、 - 前端使用全序、可靠的組播原語將請求組播到副本管理器組協(xié)調(diào) - 組通信系統(tǒng)以同樣的次序(全序)將請求傳遞到每個(gè)副本管理器執(zhí)行 - 每個(gè)副本管理器以相同的方式執(zhí)行請求響應(yīng) - 每個(gè)副本管理器將響應(yīng)發(fā)送給前端 - 前端將響應(yīng)發(fā)送給客戶第6章 復(fù)制簡介 系統(tǒng)模型容錯(cuò)服務(wù)高可用服務(wù)的實(shí)例研究：gossip體系結(jié)構(gòu)、Bayou和Coda小結(jié)高可用服務(wù)的實(shí)例研究高可用性和容錯(cuò)能力容錯(cuò)能力 - 只要可能，所有正確的副本管理器都能夠及時(shí)收到更新，并在將控制傳遞回客戶以前達(dá)成一致。高可用性 - 采用較弱程度的一致性，提高共享數(shù)據(jù)的可用性。 - 實(shí)例：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)的兩個(gè)保證 - 隨著時(shí)間的推移，每個(gè)用戶總能獲得一致服務(wù)副本管理器提供的數(shù)據(jù)能反映迄今為止客戶已經(jīng)觀測到的更新 - 副本之間松弛的一致性所有副本管理器最終將收到所有更新兩個(gè)客戶可能會(huì)觀察到不同的副本客戶可能觀察到過時(shí)數(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消息進(jìn)行相互更新gossip消息的交換是偶爾的發(fā)現(xiàn)消息丟失后，才和特定的副本管理器交換消息gossip體系結(jié)構(gòu)前端的版本時(shí)間戳客戶交換數(shù)據(jù) -通過訪問相同的gossip服務(wù) - 相互直接通信FE客戶FE服務(wù)時(shí)間戳向量RMRMRMgossip為了控制操作處理次序，每個(gè)前端維持了一個(gè)向量時(shí)間戳goss

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

9、ssip體系結(jié)構(gòu)副本管理器狀態(tài)(續(xù))已執(zhí)行操作表 - 記錄已經(jīng)執(zhí)行的更新的唯一標(biāo)識(shí)符，防止重復(fù)執(zhí)行時(shí)間戳表 - 確定何時(shí)一個(gè)更新已經(jīng)應(yīng)用于所有的副本管理器gossip體系結(jié)構(gòu)查詢操作副本管理器收到查詢 - q.prevalueTS立即響應(yīng)返回消息中的時(shí)間戳為valueTS - 否則將消息保存到保留隊(duì)列如：q.pre(2,4,6),valueTS(2,5,5)前端收到查詢響應(yīng) - 合并時(shí)間戳：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)強(qiáng)制的和即時(shí)的更新操作強(qiáng)制更新和即時(shí)更新需要特殊處理，強(qiáng)制更新是全序加因果序，

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

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

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

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

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

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

17、da文件系統(tǒng)復(fù)制策略(續(xù).)文件關(guān)閉 - Venus進(jìn)程發(fā)送更新消息（包括CVV和文件的新內(nèi)容）到AVSG - AVSG中的每個(gè)服務(wù)器更新文件，并返回確認(rèn)。 - Venus計(jì)算新的CVV，增加相應(yīng)服務(wù)器的修改記數(shù)，并分發(fā)新的CVV。CRMRMRM2, 2, 12, 2, 12, 2, 13, 3, 22, 2, 1Coda文件系統(tǒng)構(gòu)建CVV示例一文件F在三個(gè)服務(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個(gè)服務(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