分布式系統(tǒng)之9、一致性與復(fù)制

第六章 全都性與復(fù)制一、概述復(fù)制目標(biāo)牢靠性性能難題數(shù)據(jù)的全都性兩種全都性模型以數(shù)據(jù)為中心的全都性模型以客戶為中心的全都性模型實(shí)現(xiàn)全都性的兩個(gè)問(wèn)題數(shù)據(jù)更新的實(shí)際分發(fā)問(wèn)題保持副本全都性的問(wèn)題全都性模型實(shí)質(zhì)上是進(jìn)程和數(shù)據(jù)存儲(chǔ)之間的一個(gè)商定，進(jìn)程只有遵守商定，數(shù)據(jù)存儲(chǔ)才能正常運(yùn)行根本原則：正常狀況下，一個(gè)進(jìn)程執(zhí)行對(duì)某項(xiàng)數(shù)據(jù)的讀操作時(shí)，應(yīng)當(dāng)返回該數(shù)據(jù)項(xiàng)最近一次寫(xiě)操作的結(jié)果在沒(méi)有全局時(shí)鐘的狀況下，準(zhǔn)確定義哪次寫(xiě)操作是最終一次寫(xiě)操作相當(dāng)困難根本目標(biāo)：有效限制在一個(gè)數(shù)據(jù)項(xiàng)執(zhí)行讀操作所應(yīng)當(dāng)返回的值二、以數(shù)據(jù)為中心的全都性模型〔a〕不使用同步操作的全都性模型〔b〕使用同步操作的全都性模型一致性描述嚴(yán)格一致性所有共享訪問(wèn)事件必須按絕對(duì)時(shí)間嚴(yán)格排序線性一致性所有進(jìn)程看到的共享訪問(wèn)必須是同一順序。訪問(wèn)則是按照全局時(shí)間戳排序。順序一致性所有進(jìn)程看到的共享訪問(wèn)必須是同一順序。訪問(wèn)不是按時(shí)間戳排序。因果一致性所有進(jìn)程以相同順序看到的有因果關(guān)系的共享訪問(wèn)FIFO各進(jìn)程按自己的隊(duì)列方式對(duì)寫(xiě)操作排序，這個(gè)順序?qū)λ羞M(jìn)程可見(jiàn)，但來(lái)自不同進(jìn)程的對(duì)共享寫(xiě)操作的排序有可能不一樣。(a)一致性描述弱一致性至少執(zhí)行一次同步后，共享數(shù)據(jù)才被認(rèn)為是一致的。釋放一致性退出臨界區(qū)后，執(zhí)行共享數(shù)據(jù)一致性操作入口一致性進(jìn)入臨界區(qū)時(shí)，執(zhí)行屬于該臨界區(qū)的共享數(shù)據(jù)的一致性操作。(b)三、以客戶為中心的全都性模型1、最終全都性在很多分布式系統(tǒng)的數(shù)據(jù)存儲(chǔ)中不會(huì)消失同時(shí)發(fā)生的更新操作或者發(fā)生同時(shí)更新時(shí)，可以簡(jiǎn)潔化解它們大局部操作是讀操作供給一種很弱的全都性模型，稱為最終全都性模型例：DNS系統(tǒng)中，各域由各自機(jī)構(gòu)治理，不會(huì)消失寫(xiě)－寫(xiě)沖突，只需處理讀－寫(xiě)沖突。在Web中，通常掃瞄器或者web代理在本地高速緩存保存一份已下載的頁(yè)面，但有可能過(guò)時(shí)，然而這種不全都性對(duì)客戶來(lái)說(shuō)是可以承受的。最終全都性特點(diǎn)：假設(shè)在一段很長(zhǎng)的時(shí)間內(nèi)沒(méi)有更新操作，那么全部副本將漸漸成為全都的這種形式的全都性就稱為最終全都性最終全都性實(shí)際上只要求更新操作被保證傳播到全部副本上。最終全都性在客戶總是訪問(wèn)同一個(gè)副本時(shí)，沒(méi)有任何問(wèn)題假設(shè)客戶訪問(wèn)不同的副本時(shí)，就會(huì)消失問(wèn)題移動(dòng)用戶訪問(wèn)分布式數(shù)據(jù)庫(kù)的不同副本2、以客戶為中心的全都性以客戶為中心的全都性有效解決最終全都性模型中客戶對(duì)不同副本訪問(wèn)的問(wèn)題根本思想：為單一的客戶供給全都性保證，保證該客戶對(duì)數(shù)據(jù)存儲(chǔ)的訪問(wèn)全都不保證不同客戶并發(fā)訪問(wèn)的全都性四種模型單調(diào)讀單調(diào)寫(xiě)寫(xiě)后讀讀后寫(xiě)單調(diào)讀定義：假設(shè)一個(gè)進(jìn)程讀取數(shù)據(jù)項(xiàng)x的值，那么它對(duì)x執(zhí)行的任何后續(xù)讀操作總是得到第一次讀取的值或者更新的值。保證進(jìn)程不會(huì)讀到比以前讀的值更老的版本。單調(diào)寫(xiě)定義：一個(gè)進(jìn)程對(duì)數(shù)據(jù)項(xiàng)x執(zhí)行的寫(xiě)操作必需在它對(duì)x執(zhí)行任何后續(xù)寫(xiě)操作之前完成。單調(diào)寫(xiě)操作規(guī)定，對(duì)x的拷貝上執(zhí)行寫(xiě)操作只有該拷貝已經(jīng)完全通過(guò)了從前的全部寫(xiě)操作之后才能被進(jìn)展，而這些從前執(zhí)行的寫(xiě)操作可能發(fā)生在x的其他拷貝上。例子：軟件的更新，比方windows更新，殺毒軟件的更新寫(xiě)后讀定義：一個(gè)進(jìn)程對(duì)數(shù)據(jù)項(xiàng)x的寫(xiě)操作的結(jié)果總是被它對(duì)x的后續(xù)讀操作觀察。寫(xiě)后讀要求當(dāng)進(jìn)程在某個(gè)副本上執(zhí)行了寫(xiě)操作后，假設(shè)在其他副本上對(duì)該數(shù)據(jù)執(zhí)行后續(xù)的讀操作的話，必需先執(zhí)行這個(gè)寫(xiě)操作更新，保證寫(xiě)的結(jié)果對(duì)后續(xù)讀操作可見(jiàn)。例子：分布式web站點(diǎn)的頁(yè)面更新問(wèn)題讀后寫(xiě)定義：進(jìn)程對(duì)x的讀操作得到的值，不能比它后續(xù)寫(xiě)操作所基于的x的值更新。也就是說(shuō)，讀后寫(xiě)全都性要求假設(shè)后續(xù)的寫(xiě)操作需要x的值的話，它們〔指這些后續(xù)寫(xiě)〕得到的x的值必需與前面讀操作的值一樣或者更新。例如：分布式bbs系統(tǒng)的回帖問(wèn)題四、分發(fā)協(xié)議1、副本類(lèi)型全都性模型只從理論上解決全都性問(wèn)題從實(shí)現(xiàn)的角度爭(zhēng)論數(shù)據(jù)更新發(fā)送給各個(gè)副本的方法，即分發(fā)協(xié)議全都性協(xié)議副本的設(shè)計(jì)問(wèn)題位置時(shí)間誰(shuí)來(lái)放置這些拷貝三種類(lèi)型的副本永久副本效勞器啟動(dòng)的副本客戶啟動(dòng)的副本三種副本2、永久副本永久副本是分布式數(shù)據(jù)存儲(chǔ)的初始集合數(shù)量一般比較少靜態(tài)配置例1：分布式web站點(diǎn)，兩種分布方式：在局域網(wǎng)內(nèi)多臺(tái)效勞器上復(fù)制web頁(yè)面文件，懇求被轉(zhuǎn)發(fā)到其中一臺(tái)上鏡像形式。站點(diǎn)被復(fù)制到散布于因特網(wǎng)上多個(gè)效勞器，客戶訪問(wèn)時(shí)選擇鏡像例2：分布式數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)被復(fù)制在多臺(tái)效勞器上，形成工作站集群，不共享磁盤(pán)和內(nèi)存。3、效勞器啟動(dòng)的副本目標(biāo)提高系統(tǒng)性能而由效勞器動(dòng)態(tài)創(chuàng)立的副本原理由效勞器依據(jù)系統(tǒng)運(yùn)行狀況動(dòng)態(tài)創(chuàng)立、銷(xiāo)毀副本例如對(duì)于突發(fā)的大流量web訪問(wèn)，就有可能需要?jiǎng)?chuàng)立這種副本。一個(gè)重要問(wèn)題：何時(shí)、何地創(chuàng)立或刪除副本動(dòng)態(tài)復(fù)制算法原則：復(fù)制可能是為了減輕一臺(tái)效勞器的負(fù)載一臺(tái)效勞器的某些文件可能被轉(zhuǎn)移或復(fù)制到對(duì)這些文件訪問(wèn)頻繁的客戶四周的效勞器效勞器啟動(dòng)的副本動(dòng)態(tài)復(fù)制算法：每臺(tái)效勞器跟蹤每個(gè)文件的訪問(wèn)計(jì)數(shù)以及這些訪問(wèn)客戶的位置。對(duì)效勞器S上的文件F的訪問(wèn)數(shù)下降到低于刪除閾值del(S,F)時(shí)，S可以刪除F。但必需保證系統(tǒng)中至少有一個(gè)F拷貝。反之，假設(shè)對(duì)F的懇求高于復(fù)制閾值rep(S,F)時(shí)，則發(fā)生復(fù)制。假設(shè)訪問(wèn)數(shù)在二者之間，則允許F的轉(zhuǎn)移。4、客戶啟動(dòng)的副本定義：實(shí)際上就是客戶高速緩存客戶使用它臨時(shí)存儲(chǔ)剛懇求過(guò)的數(shù)據(jù)的拷貝。高速緩存完全由客戶治理，所以原則上效勞器不負(fù)責(zé)緩存內(nèi)容是否過(guò)時(shí)高速緩存形式位于客戶機(jī)本機(jī)位于局域網(wǎng)中一臺(tái)特殊的主機(jī)，如代理效勞器。部署在廣域網(wǎng)中的幾個(gè)特定的特地高速緩存效勞器上。5、更新傳播為保證數(shù)據(jù)的全都性，數(shù)據(jù)的更新最終要被傳播到其他拷貝上更新傳播的三種類(lèi)型只傳播更新通知數(shù)據(jù)從一個(gè)副本傳送到另一個(gè)副本更新操作被傳播到其他副本更新傳播無(wú)效化協(xié)議是一種典型的更新通知通知其他拷貝已經(jīng)發(fā)生了更新，這些拷貝包含的指定數(shù)據(jù)項(xiàng)不再有效更新操作遠(yuǎn)遠(yuǎn)多于讀操作時(shí)特別適宜。當(dāng)讀的頻率遠(yuǎn)高于寫(xiě)頻率時(shí)，就需要在多個(gè)副本之間傳送被修改的數(shù)據(jù)更新操作傳播不傳送任何數(shù)據(jù)修改信息，而是告知其他副本它應(yīng)當(dāng)執(zhí)行什么操作也稱為主動(dòng)復(fù)制更新傳播更新傳播的另一個(gè)問(wèn)題是實(shí)行什么方式傳播更新兩種方式“推”式的方法〔基于效勞器的協(xié)議或推協(xié)議〕：更新由發(fā)生的原始點(diǎn)主動(dòng)傳播到其他副本上。應(yīng)用于需要維持較高程度全都性的系統(tǒng)，永久副本和效勞器啟動(dòng)的副本就一般承受這種方式?！袄笔降姆椒ā不诳蛻舻膮f(xié)議或拉協(xié)議〕：客戶或者非更新原始點(diǎn)副本懇求其他效勞器發(fā)送更新集合。適用于客戶高速緩存。五、全都性協(xié)議全都性協(xié)議：全都性模型的實(shí)際實(shí)現(xiàn)的工作原理。兩種全都性協(xié)議類(lèi)型基于主備份的協(xié)議復(fù)制的寫(xiě)協(xié)議區(qū)分在于是否具有主拷貝。1、基于主備份的協(xié)議數(shù)據(jù)存儲(chǔ)的任一數(shù)據(jù)項(xiàng)x都有一個(gè)主備份對(duì)x的全部寫(xiě)操作都必需經(jīng)過(guò)主備份來(lái)協(xié)調(diào)遠(yuǎn)程寫(xiě)協(xié)議最簡(jiǎn)潔的基于主備份的協(xié)議原理讀和寫(xiě)操作都在遠(yuǎn)程主備份效勞器上執(zhí)行數(shù)據(jù)實(shí)際上根本沒(méi)有被復(fù)制，而且也不允許移動(dòng)。缺點(diǎn)？基于主備份的遠(yuǎn)程寫(xiě)協(xié)議主機(jī)備份協(xié)議遠(yuǎn)程寫(xiě)協(xié)議的一種改進(jìn)方式原理允許進(jìn)程在本地可用副本上執(zhí)行讀操作但必需向主拷貝上轉(zhuǎn)發(fā)寫(xiě)操作潛在性能問(wèn)題：更新是堵塞的。因而啟動(dòng)更新的進(jìn)程要等待很長(zhǎng)時(shí)間。也可以在主機(jī)備份協(xié)議中使用非堵塞的工作方式，只要主備份效勞器更新了x的主拷貝，就返回確認(rèn)消息。這種方式的主要問(wèn)題是容錯(cuò)力量問(wèn)題。主機(jī)備份協(xié)議本地寫(xiě)協(xié)議本地寫(xiě)協(xié)議也有兩種第一種每個(gè)數(shù)據(jù)項(xiàng)只有一個(gè)拷貝進(jìn)程要對(duì)其執(zhí)行操作時(shí)，先將數(shù)據(jù)的唯一主拷貝傳送到進(jìn)程本地，再執(zhí)行操作這種完全遷移的方法的主要問(wèn)題是它需要跟蹤每個(gè)數(shù)據(jù)項(xiàng)的當(dāng)前位置其次種在主機(jī)備份協(xié)議中，主拷貝允許在多個(gè)執(zhí)行寫(xiě)操作的進(jìn)程〔效勞器〕之間遷移。 這種方法的主要優(yōu)點(diǎn)是系列寫(xiě)操作可以在本地執(zhí)行。基于主備份的本地寫(xiě)協(xié)議主機(jī)備份協(xié)議中移