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

1、分布式系統(tǒng)之一致性與復(fù)制第一頁(yè)，共33頁(yè)。一、概述復(fù)制目標(biāo)可靠性性能難題數(shù)據(jù)的一致性兩種一致性模型以數(shù)據(jù)為中心的一致性模型以客戶為中心的一致性模型實(shí)現(xiàn)一致性的兩個(gè)問(wèn)題數(shù)據(jù)更新的實(shí)際分發(fā)問(wèn)題保持副本一致性的問(wèn)題第二頁(yè)，共33頁(yè)。一致性模型實(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)該返回該數(shù)據(jù)項(xiàng)最近一次寫(xiě)操作的結(jié)果在沒(méi)有全局時(shí)鐘的情況下，精確定義哪次寫(xiě)操作是最后一次寫(xiě)操作相當(dāng)困難基本目標(biāo)：有效限制在一個(gè)數(shù)據(jù)項(xiàng)執(zhí)行讀操作所應(yīng)該返回的值第三頁(yè)，共33頁(yè)。二、以數(shù)據(jù)為中心的一致性模型（a）不使用同步操作的一致性模

2、型 （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ù)的一致

3、性操作。(b)第四頁(yè)，共33頁(yè)。三、以客戶為中心的一致性模型第五頁(yè)，共33頁(yè)。1、最終一致性在許多分布式系統(tǒng)的數(shù)據(jù)存儲(chǔ)中不會(huì)出現(xiàn)同時(shí)發(fā)生的更新操作或者發(fā)生同時(shí)更新時(shí)，可以容易化解它們大部分操作是讀操作提供一種很弱的一致性模型，稱為最終一致性模型例：DNS系統(tǒng)中，各域由各自機(jī)構(gòu)管理，不會(huì)出現(xiàn)寫(xiě)寫(xiě)沖突，只需處理讀寫(xiě)沖突。在Web中，通常瀏覽器或者web代理在本地高速緩存保存一份已下載的頁(yè)面，但有可能過(guò)時(shí)，然而這種不一致性對(duì)客戶來(lái)說(shuō)是可以接受的。第六頁(yè)，共33頁(yè)。最終一致性特點(diǎn)：如果在一段很長(zhǎng)的時(shí)間內(nèi)沒(méi)有更新操作，那么所有副本將逐漸成為一致的這種形式的一致性就稱為最終一致性最終一致性實(shí)際上只要求更新

4、操作被保證傳播到所有副本上。最終一致性在客戶總是訪問(wèn)同一個(gè)副本時(shí)，沒(méi)有任何問(wèn)題如果客戶訪問(wèn)不同的副本時(shí)，就會(huì)出現(xiàn)問(wèn)題第七頁(yè)，共33頁(yè)。移動(dòng)用戶訪問(wèn)分布式數(shù)據(jù)庫(kù)的不同副本第八頁(yè)，共33頁(yè)。2、以客戶為中心的一致性以客戶為中心的一致性有效解決最終一致性模型中客戶對(duì)不同副本訪問(wèn)的問(wèn)題基本思想：為單一的客戶提供一致性保證，保證該客戶對(duì)數(shù)據(jù)存儲(chǔ)的訪問(wèn)一致不保證不同客戶并發(fā)訪問(wèn)的一致性四種模型單調(diào)讀單調(diào)寫(xiě)寫(xiě)后讀讀后寫(xiě)第九頁(yè)，共33頁(yè)。單調(diào)讀定義：如果一個(gè)進(jìn)程讀取數(shù)據(jù)項(xiàng)x的值，那么它對(duì)x執(zhí)行的任何后續(xù)讀操作總是得到第一次讀取的值或者更新的值。保證進(jìn)程不會(huì)讀到比以前讀的值更老的版本。第十頁(yè)，共33頁(yè)。單調(diào)寫(xiě)定

5、義：一個(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更新，殺毒軟件的更新第十一頁(yè)，共33頁(yè)。寫(xiě)后讀定義：一個(gè)進(jìn)程對(duì)數(shù)據(jù)項(xiàng)x的寫(xiě)操作的結(jié)果總是被它對(duì)x的后續(xù)讀操作看見(jiàn)。寫(xiě)后讀要求當(dāng)進(jìn)程在某個(gè)副本上執(zhí)行了寫(xiě)操作后，如果在其他副本上對(duì)該數(shù)據(jù)執(zhí)行后續(xù)的讀操作的話，必須先執(zhí)行這個(gè)寫(xiě)操作更新，保證寫(xiě)的結(jié)果對(duì)后續(xù)讀操作可見(jiàn)。例子：分布式web站點(diǎn)的頁(yè)面更新問(wèn)題第十二頁(yè)，共33頁(yè)。讀后寫(xiě)定義：進(jìn)程對(duì)x的讀操作得到

6、的值，不能比它后續(xù)寫(xiě)操作所基于的x的值更新。也就是說(shuō)，讀后寫(xiě)一致性要求如果后續(xù)的寫(xiě)操作需要x的值的話，它們（指這些后續(xù)寫(xiě)）得到的x的值必須與前面讀操作的值相同或者更新。例如：分布式bbs系統(tǒng)的回帖問(wèn)題第十三頁(yè)，共33頁(yè)。四、分發(fā)協(xié)議第十四頁(yè)，共33頁(yè)。1、副本類(lèi)型一致性模型只從理論上解決一致性問(wèn)題從實(shí)現(xiàn)的角度研究數(shù)據(jù)更新發(fā)送給各個(gè)副本的方法，即分發(fā)協(xié)議一致性協(xié)議副本的設(shè)計(jì)問(wèn)題位置時(shí)間誰(shuí)來(lái)放置這些拷貝三種類(lèi)型的副本永久副本服務(wù)器啟動(dòng)的副本客戶啟動(dòng)的副本第十五頁(yè)，共33頁(yè)。三種副本第十六頁(yè)，共33頁(yè)。2、永久副本永久副本是分布式數(shù)據(jù)存儲(chǔ)的初始集合數(shù)量一般比較少靜態(tài)配置例1：分布式web站點(diǎn)，兩種分

7、布方式：在局域網(wǎng)內(nèi)多臺(tái)服務(wù)器上復(fù)制web頁(yè)面文件，請(qǐng)求被轉(zhuǎn)發(fā)到其中一臺(tái)上鏡像形式。站點(diǎn)被復(fù)制到散布于因特網(wǎng)上多個(gè)服務(wù)器，客戶訪問(wèn)時(shí)選擇鏡像例2：分布式數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)被復(fù)制在多臺(tái)服務(wù)器上，形成工作站集群，不共享磁盤(pán)和內(nèi)存。第十七頁(yè)，共33頁(yè)。3、服務(wù)器啟動(dòng)的副本目標(biāo)提高系統(tǒng)性能而由服務(wù)器動(dòng)態(tài)創(chuàng)建的副本原理由服務(wù)器根據(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)服務(wù)器的負(fù)載一臺(tái)服務(wù)器的某些文件可能被轉(zhuǎn)移或復(fù)制到對(duì)這些文件訪問(wèn)頻繁的客戶附近的服務(wù)器第十八頁(yè)，共33頁(yè)。服務(wù)器啟動(dòng)的

8、副本動(dòng)態(tài)復(fù)制算法：每臺(tái)服務(wù)器跟蹤每個(gè)文件的訪問(wèn)計(jì)數(shù)以及這些訪問(wèn)客戶的位置。對(duì)服務(wù)器S上的文件F的訪問(wèn)數(shù)下降到低于刪除閾值del(S, F)時(shí)，S可以刪除F。但必須保證系統(tǒng)中至少有一個(gè)F拷貝。反之，如果對(duì)F的請(qǐng)求高于復(fù)制閾值rep(S, F)時(shí)，則發(fā)生復(fù)制。如果訪問(wèn)數(shù)在二者之間，則允許F的轉(zhuǎn)移。第十九頁(yè)，共33頁(yè)。4、客戶啟動(dòng)的副本定義：實(shí)際上就是客戶高速緩存客戶使用它暫時(shí)存儲(chǔ)剛請(qǐng)求過(guò)的數(shù)據(jù)的拷貝。高速緩存完全由客戶管理，所以原則上服務(wù)器不負(fù)責(zé)緩存內(nèi)容是否過(guò)時(shí)高速緩存形式位于客戶機(jī)本機(jī)位于局域網(wǎng)中一臺(tái)特殊的主機(jī)，如代理服務(wù)器。部署在廣域網(wǎng)中的幾個(gè)特定的專門(mén)高速緩存服務(wù)器上。第二十頁(yè)，共33頁(yè)。5

9、、更新傳播為保證數(shù)據(jù)的一致性，數(shù)據(jù)的更新最終要被傳播到其他拷貝上更新傳播的三種類(lèi)型只傳播更新通知數(shù)據(jù)從一個(gè)副本傳送到另一個(gè)副本更新操作被傳播到其他副本第二十一頁(yè)，共33頁(yè)。更新傳播無(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)該執(zhí)行什么操作也稱為主動(dòng)復(fù)制第二十二頁(yè)，共33頁(yè)。更新傳播更新傳播的另一個(gè)問(wèn)題是采取什么方式傳播更新兩種方式“推”式的方法（基于服務(wù)器的協(xié)議或推協(xié)議）：更新由發(fā)生的原始點(diǎn)主動(dòng)傳播

10、到其他副本上。應(yīng)用于需要維持較高程度一致性的系統(tǒng)，永久副本和服務(wù)器啟動(dòng)的副本就一般采用這種方式。“拉”式的方法（基于客戶的協(xié)議或拉協(xié)議）：客戶或者非更新原始點(diǎn)副本請(qǐng)求其他服務(wù)器發(fā)送更新集合。適用于客戶高速緩存。第二十三頁(yè)，共33頁(yè)。五、一致性協(xié)議第二十四頁(yè)，共33頁(yè)。一致性協(xié)議：一致性模型的實(shí)際實(shí)現(xiàn)的工作原理。兩種一致性協(xié)議類(lèi)型基于主備份的協(xié)議復(fù)制的寫(xiě)協(xié)議區(qū)別在于是否具有主拷貝。第二十五頁(yè)，共33頁(yè)。1、基于主備份的協(xié)議數(shù)據(jù)存儲(chǔ)的任一數(shù)據(jù)項(xiàng)x都有一個(gè)主備份對(duì)x的所有寫(xiě)操作都必須經(jīng)過(guò)主備份來(lái)協(xié)調(diào)第二十六頁(yè)，共33頁(yè)。遠(yuǎn)程寫(xiě)協(xié)議最簡(jiǎn)單的基于主備份的協(xié)議原理讀和寫(xiě)操作都在遠(yuǎn)程主備份服務(wù)器上執(zhí)行數(shù)據(jù)實(shí)際上根本沒(méi)有被復(fù)制，而且也不允許移動(dòng)。缺點(diǎn)？第二十七頁(yè)，共33頁(yè)?；谥鱾浞莸倪h(yuǎn)程寫(xiě)協(xié)議第二十八頁(yè)，共33頁(yè)。主機(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é)議中使用非阻塞的工作方式，只要主備份服務(wù)器更新了x的主拷貝，就返回確認(rèn)消息。這種方式的主要問(wèn)題是容錯(cuò)能力問(wèn)題。第二十九頁(yè)，共33頁(yè)。主機(jī)備份協(xié)議第三十頁(yè)，共33頁(yè)。本地寫(xiě)協(xié)議本地寫(xiě)協(xié)議也有兩種第一種每個(gè)數(shù)據(jù)項(xiàng)只有一個(gè)拷貝進(jìn)程要對(duì)其執(zhí)行操作時(shí)