高級操作系統(tǒng)-第七章-一致性和復(fù)制

第七章一樣性和復(fù)制概述以數(shù)據(jù)為中心的一樣性模型以客戶為中心的一樣性模型復(fù)制管理一樣性協(xié)議概述：復(fù)制的目的牢靠性性能服務(wù)器數(shù)量擴(kuò)展地理區(qū)域擴(kuò)展代價(jià)：一樣性網(wǎng)絡(luò)通信開銷強(qiáng)一樣性要求的原子操作很難快速完成解決方法：放寬一樣性方面的限制，放寬程度取決于復(fù)制數(shù)據(jù)的訪問和更新模式以及數(shù)據(jù)的用途以數(shù)據(jù)為中心的一樣性模型邏輯數(shù)據(jù)存儲(chǔ)的一般組織，物理上是分布的，并被復(fù)制到各個(gè)進(jìn)程探討共享數(shù)據(jù)讀操作和寫操作時(shí)的一樣性問題一樣性模型實(shí)質(zhì)上是進(jìn)程和數(shù)據(jù)存儲(chǔ)間的約定：假如進(jìn)程同意遵守某些規(guī)則，數(shù)據(jù)存儲(chǔ)將正常進(jìn)行。正常狀況下，進(jìn)程的讀操作應(yīng)當(dāng)返回最終一次寫操作的結(jié)果沒有全局時(shí)鐘，精確定義哪次寫操作是最終一次寫操作是困難的作為全局時(shí)鐘的替代，產(chǎn)生了一系列一樣性模型，每種模型都有效地限制了一個(gè)數(shù)據(jù)項(xiàng)上執(zhí)行一次讀操作所應(yīng)返回的值嚴(yán)格一樣性

（StrictConsistency）a)嚴(yán)格的一樣性存儲(chǔ)b)非嚴(yán)格的一樣性存儲(chǔ)任何對數(shù)據(jù)項(xiàng)X的讀操作將返回最近一次對X進(jìn)行寫操作的值對全部進(jìn)程來說，全部寫操作都是瞬間可見的，系統(tǒng)維護(hù)著一個(gè)確定的全局時(shí)間依次線性化和依次一樣性

LinearizabilityandSequentialConsistency(1)a)依次一樣的數(shù)據(jù)存儲(chǔ)b)非依次一樣的數(shù)據(jù)存儲(chǔ)依次一樣性對存儲(chǔ)器的限制比嚴(yán)格一樣性要弱一些，要滿足以下的條件：（1）

每個(gè)進(jìn)程的內(nèi)部操作依次是確定不變的；（2）

假如全部的進(jìn)程都對某一個(gè)存儲(chǔ)單元執(zhí)行操作，那么，它們的操作依次是確定的，即任一進(jìn)程都可以感知到這些進(jìn)程同樣的操作依次。線性化和依次一樣性(2)依次一樣性可與事務(wù)串行化相比串行化：假如一個(gè)并發(fā)執(zhí)行的事務(wù)處理集合的結(jié)果可以依據(jù)某種依次逐個(gè)執(zhí)行事務(wù)獲得，該事務(wù)處理集合是可串行化的區(qū)分：粒度的不同依次一樣性：讀寫操作串行化：事務(wù)（一系列讀寫操作的集合）盡管依次一樣性是一個(gè)對程序員友好的模型，但其存在嚴(yán)峻的性能問題：假如執(zhí)行讀操作的時(shí)間是r,執(zhí)行寫操作的時(shí)間是w，結(jié)點(diǎn)間最小的數(shù)據(jù)包傳送時(shí)間是t,那么存在r+w>t。線性化：弱于嚴(yán)格一樣性而強(qiáng)于依次一樣性依據(jù)一系列時(shí)鐘同步確定序列依次（利用時(shí)間戳）依次一樣性和線性化供應(yīng)了程序開發(fā)人員在并發(fā)程序設(shè)計(jì)中期望的語義：全部寫操作都以相同的依次被每個(gè)進(jìn)程看到因果一樣性

CasualConsistency(1)全部進(jìn)程必需以相同的依次看到具有潛在因果關(guān)系的寫操作不同機(jī)器上的進(jìn)程可以以不同的依次看到并發(fā)的寫操作因果一樣性(2)因果一樣性存儲(chǔ)允許的，但依次和嚴(yán)格一樣性存儲(chǔ)不允許的依次因果一樣性(3)違反因果一樣性的時(shí)間存儲(chǔ)依次符合因果一樣性的時(shí)間存儲(chǔ)依次FIFO一樣性

FIFOConsistency(1)FIFO一樣性模型是在因果一樣性模型上的進(jìn)一步弱化，它滿足下面的條件：由某一個(gè)進(jìn)程完成的寫操作可以被其他全部的進(jìn)程依據(jù)依次感知到，而從不同進(jìn)程中來的寫操作對不同的進(jìn)程可以有不同的依次。FIFO一樣性(2)符合FIFO一樣性的時(shí)間存儲(chǔ)依次FIFO一樣性(3)與依次一樣性的區(qū)分:依次一樣性：盡管語句的執(zhí)行依次是非確定的，但全部的進(jìn)程對依次達(dá)成一樣FIFO一樣性：各個(gè)進(jìn)程不須要達(dá)成一樣，不同進(jìn)程可以以不同的依次看到引入同步的一樣性引入顯示的同步變量當(dāng)一個(gè)進(jìn)程對數(shù)據(jù)進(jìn)行操作時(shí)，不保證其他進(jìn)程何時(shí)看到這一操作，只是在執(zhí)行一次同步時(shí)，數(shù)據(jù)的變更才被傳播弱一樣性釋放一樣性入口一樣性弱一樣性

WeakConsistency(1)同步變量S僅有一個(gè)關(guān)聯(lián)操作synchronization(S),該操作同步數(shù)據(jù)存儲(chǔ)的全部本地拷貝弱一樣性模型必需滿足的條件有下面幾點(diǎn):

對同步變量的訪問滿足一樣性的要求說明全部進(jìn)程都以相同的依次看到同步變量進(jìn)行的全部操作對同步變量的訪問，只有在以前的寫操作在各處都完成之后才能進(jìn)行。強(qiáng)迫在全部備份上完成全部的寫操作對數(shù)據(jù)的操作（讀或?qū)懀?，只有在以前的對同步變量的操作完成之后才能進(jìn)行。保證所得到的數(shù)值是最新值弱一樣性(2)對弱一樣性有效的時(shí)間依次對弱一樣性無效的時(shí)間依次釋放一樣性

ReleaseConsistency(1)對釋放一樣性有效的時(shí)間依次弱一樣性存在的問題：當(dāng)同步變量被訪問時(shí)，數(shù)據(jù)存儲(chǔ)不知道此次訪問是因?yàn)檫M(jìn)程結(jié)束對共享數(shù)據(jù)的寫操作，還是因?yàn)檫M(jìn)程將起先讀數(shù)據(jù)而進(jìn)行的釋放一樣性運(yùn)用兩種類型的同步變量來代替原來的一種同步變量獲得Acquire操作用于表明進(jìn)程進(jìn)入臨界區(qū)釋放Release操作用于表明進(jìn)程退出臨界區(qū)釋放一樣性(2)通常，假如一個(gè)分布式共享存儲(chǔ)系統(tǒng)滿足釋放一樣性，則它必需遵守以下的規(guī)則：某進(jìn)程只有在成功完成Acquire操作之后，才能對共享數(shù)據(jù)進(jìn)行讀寫操作。某進(jìn)程只有在完成對共享數(shù)據(jù)的讀寫操作之后，Release操作才能完成。Acquire和Release操作必需滿足FIFO一樣性要求。進(jìn)程執(zhí)行獲得操作時(shí)要保證數(shù)據(jù)更新，與遠(yuǎn)程數(shù)據(jù)保持一樣，但不保證本地?cái)?shù)據(jù)變更被馬上傳播到其他拷貝進(jìn)程執(zhí)行釋放操作時(shí)已變更的數(shù)據(jù)被馬上傳播到其他拷貝，不保證確定從其他拷貝引入變更入口一樣性

EntryConsistency(1)要求每個(gè)一般的共享數(shù)據(jù)都要與某種同步變量（如鎖）關(guān)聯(lián)思想：使得多個(gè)包含不同共享數(shù)據(jù)的臨界區(qū)可以同時(shí)執(zhí)行，從而增加系統(tǒng)的并行度，付出的代價(jià)是每個(gè)共享數(shù)據(jù)與某種同步變量關(guān)聯(lián)的額外開銷和困難性滿足入口一樣性的條件是：在一個(gè)進(jìn)程可以獲得一個(gè)同步變量前，全部由該同步變量愛護(hù)的共享數(shù)據(jù)相對與該進(jìn)程已經(jīng)更新完畢在一個(gè)進(jìn)程被允許以獨(dú)占模式訪問某同步變量之前，任何別的進(jìn)程不行以擁有該同步變量，即使以非獨(dú)占模式擁有。在一個(gè)進(jìn)程以獨(dú)占模式訪問一個(gè)同步變量之后，在對該同步變量的全部者檢查之前，任何其他進(jìn)程都不能執(zhí)行下一個(gè)非獨(dú)占訪問。入口一樣性(2)對入口一樣性有效的時(shí)間依次一樣性總結(jié)不運(yùn)用同步操作的一樣性模型運(yùn)用同步操作的一樣性模型ConsistencyDescription嚴(yán)格所有共享訪問按絕對時(shí)間排序線性化所有進(jìn)程以相同順序看到所有的共享訪問。而且，訪問是根據(jù)全局時(shí)間戳排序的順序所有進(jìn)程以相同順序看到所有的共享訪問。訪問不是根據(jù)時(shí)間排序的因果所有進(jìn)程以相同順序看到因果相關(guān)的共享訪問。FIFO所有進(jìn)程以不同進(jìn)程提出寫操作的順序相互看到寫操作。來自不同進(jìn)程的寫操作可以不必總是以相同的順序出現(xiàn)。(a)ConsistencyDescription弱只有在執(zhí)行一次同步后，共享數(shù)據(jù)才被認(rèn)為是一致的釋放退出臨界區(qū)時(shí)，使共享數(shù)據(jù)成為一致的入口進(jìn)入臨界區(qū)時(shí)，使屬于一個(gè)臨界區(qū)的共享數(shù)據(jù)成為一致的(b)以客戶為中心的一樣性模型

最終一樣性（EventualConsistency）最終一樣性：很多狀況下系統(tǒng)能容忍相對較高程度的不一樣性，共同之處在于：只有一個(gè)或少數(shù)幾個(gè)進(jìn)程執(zhí)行更新操作，假如較長時(shí)間內(nèi)沒有更新操作，那么副本將漸漸成為一樣的數(shù)據(jù)庫系統(tǒng)DNSWWW特點(diǎn)：只有少數(shù)幾個(gè)進(jìn)程執(zhí)行更新操作，只須要處理讀寫沖突能容忍相對較高程度的不一樣性實(shí)現(xiàn)開銷小假如客戶總是訪問同一副本，最終一樣性能工作得很好以客戶為中心的一樣性模型移動(dòng)用戶訪問分布式數(shù)據(jù)庫不同副本的原理以客戶為中心的一樣性模型不考慮數(shù)據(jù)可能被多個(gè)用戶共享的問題，而是集中考慮一個(gè)單獨(dú)用戶應(yīng)被供應(yīng)的一樣性。單調(diào)讀（MonotonicReads）假如一個(gè)進(jìn)程讀取數(shù)據(jù)項(xiàng)x的值，那么該進(jìn)程對x執(zhí)行的任何后續(xù)讀操作將總是得到第一次讀取的那個(gè)值或更新的值進(jìn)程P對同一數(shù)據(jù)存儲(chǔ)的兩個(gè)不同本地備份執(zhí)行的讀操作供應(yīng)單調(diào)讀一樣性的數(shù)據(jù)存儲(chǔ)不供應(yīng)單調(diào)讀一樣性的數(shù)據(jù)存儲(chǔ).WS(x1;x2)表示W(wǎng)S(x1)的操作已在L2更新完畢單調(diào)寫（MonotonicWrites）一個(gè)進(jìn)程對數(shù)據(jù)項(xiàng)x執(zhí)行的寫操作必需在該進(jìn)程對x執(zhí)行的任何后續(xù)寫操作之前完成進(jìn)程P對同一數(shù)據(jù)存儲(chǔ)的兩個(gè)不同本地備份執(zhí)行的寫操作供應(yīng)單調(diào)寫一樣性的數(shù)據(jù)存儲(chǔ)不供應(yīng)單調(diào)寫一樣性的數(shù)據(jù)存儲(chǔ)類似以數(shù)據(jù)為中心的FIFO一樣性寫后讀（ReadYourWrites）一個(gè)進(jìn)程對數(shù)據(jù)項(xiàng)x執(zhí)行的寫操作結(jié)果總會(huì)被該進(jìn)程對x執(zhí)行的任何后續(xù)讀操作望見供應(yīng)寫后讀一樣性的數(shù)據(jù)存儲(chǔ)不供應(yīng)寫后讀一樣性的數(shù)據(jù)存儲(chǔ)讀后寫(WritesFollowReads)同一個(gè)進(jìn)程對數(shù)據(jù)項(xiàng)x執(zhí)行的讀操作之后的寫操作，保證發(fā)生在與x讀取之相同或更新的值上供應(yīng)讀后寫一樣性的數(shù)據(jù)存儲(chǔ)不供應(yīng)讀后寫一樣性的數(shù)據(jù)存儲(chǔ)復(fù)制管理

副本放置（ReplicaPlacement）數(shù)據(jù)存儲(chǔ)的不同類型備份分發(fā)協(xié)議:將數(shù)據(jù)更新發(fā)送給各個(gè)副本的方法副本放置：位置、時(shí)間和由誰來放置永久副本：副本的初始集合，數(shù)量很少，用作允許被修改以保證一樣性的唯一副本服務(wù)器啟動(dòng)的副本:用于在客戶旁邊放置只讀備份，從而提高性能客戶啟動(dòng)的副本：客戶高速緩存，改善數(shù)據(jù)的訪問時(shí)間；對只讀數(shù)據(jù)高效；可以讓多個(gè)客戶共享緩存；效率取決于數(shù)據(jù)類型服務(wù)器啟動(dòng)的副本

Server-InitiatedReplicas來自不同客戶的訪問懇求計(jì)數(shù)服務(wù)器啟動(dòng)的副本是為提高性能而存在的數(shù)據(jù)存儲(chǔ)的備份創(chuàng)建或刪除副本的準(zhǔn)確位置和時(shí)間:每臺(tái)服務(wù)器跟蹤每個(gè)文件的訪問計(jì)數(shù)以及提出這些訪問的懇求刪除閾值復(fù)制閾值懇求的數(shù)量位于兩者之間時(shí)，當(dāng)來自P的對F的懇求總量超過Q上對F的懇求總量的一半時(shí)，轉(zhuǎn)移數(shù)據(jù)到P更新傳播更新傳播：更新從一個(gè)拷貝傳播到其他拷貝相關(guān)設(shè)計(jì)問題：狀態(tài)與操作拉協(xié)議與推協(xié)議單播與多播狀態(tài)與操作實(shí)際傳播的信息只傳播更新的通知：無效化協(xié)議可以指定數(shù)據(jù)存儲(chǔ)的哪些部分被更新了懇求在無效的拷貝上操作時(shí)，先更新該拷貝幾乎不占帶寬，適合更新操作比讀寫操作多的場合（兩次更新間可能沒有讀操作）把數(shù)據(jù)從一個(gè)拷貝傳送到另一個(gè)拷貝適合讀對寫的比率相對高的場合：被修改的數(shù)據(jù)可能在下一個(gè)更新前被讀取，即更新是有效的可能性較高可以只傳送修改的日志通過將多個(gè)修改壓縮到一個(gè)消息里來削減通信開銷把更新操作傳送到其他拷貝：主動(dòng)復(fù)制假設(shè)每個(gè)副本由一個(gè)進(jìn)程代表，該進(jìn)程通過執(zhí)行操作主動(dòng)地更新數(shù)據(jù)：假設(shè)操作關(guān)聯(lián)的參數(shù)少，傳播更新的帶寬代價(jià)小拉協(xié)議與推協(xié)議

PullversusPushProtocols在多客戶、單一服務(wù)器系統(tǒng)中，基于推式協(xié)議與基于拉式協(xié)議比較問題基于推式基于拉式服務(wù)器的狀態(tài)客戶副本和高速緩存的列表無發(fā)送的消息更新（以及以后可能獲取的更新）輪詢和更新客戶響應(yīng)時(shí)間立即（或獲取更新的時(shí)間）獲取更新的時(shí)間基于推式協(xié)議：基于服務(wù)器的協(xié)議永久副本和服務(wù)器啟動(dòng)的副本更新用于副本須要完全相同的時(shí)候適合讀對寫的比率相對高的場合（更新對讀操作有效），高效基于拉式協(xié)議：基于客戶的協(xié)議一臺(tái)服務(wù)器或客戶懇求其他服務(wù)器向它發(fā)送持有的更新用于客戶高速緩存：Web高速緩存，客戶輪詢服務(wù)器基于租用的更新傳播更新傳播的混合形式租用是服務(wù)器的承諾，它將在指定的時(shí)間內(nèi)將更新推給客戶。租用到期后：客戶被迫輪詢服務(wù)器以實(shí)現(xiàn)更新客戶懇求一個(gè)新的租期三種類型的租用依據(jù)數(shù)據(jù)項(xiàng)的年齡：為預(yù)期保持不變的數(shù)據(jù)授予一個(gè)長期的租用，可以削減更新消息的數(shù)量依據(jù)客戶懇求高速緩存副本的頻率：頻率高的客戶授予長期的租用，只跟蹤對數(shù)據(jù)感愛好的客戶基于服務(wù)器的狀態(tài)空間開銷：將要過載時(shí)，縮短新租用的期限單播與多播多播：服務(wù)器向其他N臺(tái)服務(wù)器發(fā)送更新時(shí)，底層的網(wǎng)絡(luò)負(fù)責(zé)向多個(gè)接收者發(fā)送一個(gè)消息，高效與推式更新結(jié)合更高效單播：服務(wù)器向其他N臺(tái)服務(wù)器發(fā)送更新時(shí)，要發(fā)送N個(gè)單獨(dú)的消息與拉式更新結(jié)合更高效：只有一個(gè)客戶懇求更新Epidemic協(xié)議供應(yīng)最終一樣性：保證全部的副本最終是一樣的不解決更新沖突，只關(guān)切運(yùn)用最少的消息將更新傳播到全部副本一個(gè)服務(wù)器可以是：傳染性的：持有情愿向其他服務(wù)器散布的更新易感的：尚未更新的服務(wù)器隔離的：已更新的服務(wù)器假如不情愿或不能擴(kuò)散其更新反熵傳播模型：服務(wù)器P周期的隨機(jī)選取一臺(tái)服務(wù)器Q交換更新，方式包括：P只把自己的更新推入Q：較差的選擇P只從Q拉出新的更新P和Q相互發(fā)送更新可以證明：假如初始只有一臺(tái)服務(wù)器具有傳染性，無論接受哪種形式，更新最終將被傳播到全部服務(wù)器上gossiping思想：假如服務(wù)器P剛剛因?yàn)閿?shù)據(jù)項(xiàng)x而被更新，那么它聯(lián)系隨意一個(gè)其他服務(wù)器Q，并試圖將更新推入Q。假如Q已經(jīng)被其他服務(wù)器更新了，P可能會(huì)失去接著擴(kuò)散的愛好，變成隔離的（這種可能性是1/k）快速傳播更新的方法但不能保證全部的服務(wù)器都被更新了s=e-(k+1)(1-s),k=3時(shí)，s小于2%可以將gossiping和反熵結(jié)合一樣性協(xié)議一樣性協(xié)議描述特定的一樣性模型的實(shí)現(xiàn)基于主備份的協(xié)議：每個(gè)數(shù)據(jù)x都有一個(gè)關(guān)聯(lián)的主備份，負(fù)責(zé)協(xié)調(diào)x的寫操作，依據(jù)主備份的位置分為：遠(yuǎn)程寫協(xié)議本地寫協(xié)議復(fù)制的寫協(xié)議：寫操作可以在多個(gè)副本上執(zhí)行主動(dòng)復(fù)制基于法定數(shù)目的協(xié)議遠(yuǎn)程寫協(xié)議

Remote-WriteProtocols(1)基于主備份的遠(yuǎn)程寫協(xié)議，全部讀操作和寫操作都被轉(zhuǎn)發(fā)到一個(gè)固定的服務(wù)器上遠(yuǎn)程寫協(xié)議

Remote-WriteProtocols(2)主機(jī)備份協(xié)議的原理主機(jī)備份協(xié)