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

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