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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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