【文章內(nèi)容簡介】 一致的 – 不考慮不同客戶之間的并發(fā)訪問 ?假設(shè) – 每個數(shù)據(jù)項 x有一個擁有者，只有擁有者可以修改x – 客戶的讀寫操作在本地副本上進行 – 更新最終將傳播給其他副本上。 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 38 客戶為中心的一致性 ?記號 – xi[t]: 數(shù)據(jù)項 x在局部場地 Li上在時刻 t的版本 – WS(xi[t]): 得出 xi[t]的寫操作集 – WS(xi[t1], xj[t2]): WS(xi[t])中的寫操作在 t2時刻在 Lj上執(zhí)行 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 39 單調(diào)讀一致性 ?當(dāng)一個進程讀了數(shù)據(jù)項 x的值后，所有后續(xù)的對 x的讀操作，都將返回相同的值，或者更新的值 – 例：讀 (舊金山 〉 紐約） ?示例： (a)：符合單調(diào)讀一致性 b): 不能保證單調(diào)讀一致性 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 40 單調(diào)寫一致性 ?一個進程對數(shù)據(jù)項 x的寫操作，必須在該進程對 x的所有后續(xù)寫操作之前完成。 – 例：軟件庫更新（版本 1,...,n) ?示例： (a)：符合單調(diào)寫一致性 (b): 不能保證單調(diào)寫一致性 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 41 讀自己寫一致性 ?一個進程對數(shù)據(jù)項 x的寫操作結(jié)果，總能被該進程對 x的后續(xù)讀操作讀到。 – 例 1： Web網(wǎng)頁更新、瀏覽 – 例 2：數(shù)字圖書館密碼更新 ?示例： (a)：符合讀自己寫一致性 (b): 不能保證自己寫一致性 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 42 寫跟隨讀一致性 ?一個進程在對數(shù)據(jù)項 x讀操作之后對 x的寫操作，必須在 x已讀出的相同值或者更近的值之上進行 – 例： BBS跟帖（讀文章 A,寫文章 B） ?示例： (a)：符合寫跟隨讀一致性 (b): 不能保證寫跟隨讀一致性 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 43 實現(xiàn)技術(shù)（ 1） ?基本方法 – 寫操作：全局唯一標(biāo)識符。 ? 服務(wù)器 ID:執(zhí)行位置 ? 序號 : 執(zhí)行順序 – 讀集合 Rset(c)：與客戶 c讀操作相關(guān)的寫操作標(biāo)識符 – 寫集合 Wset(c)：客戶 c執(zhí)行的寫操作的標(biāo)識符 S1 S2 Rset Wset Log Log 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 44 實現(xiàn)技術(shù)（ 2） ?單調(diào)讀一致性 – 當(dāng)客戶 c執(zhí)行讀操作 r； – c的服務(wù)器 s檢查 c的讀集合 Rset(c)，是否所有寫操作已在 c的本地更新； – 如果 c的本地沒有更新，則請求更新； – 執(zhí)行讀操作 r； – 將與 r有關(guān)的寫操作標(biāo)識符加入 Rset (c)。 S S‘ Rset Log Log 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 45 實現(xiàn)技術(shù)（ 3） ?單 調(diào)寫一致性 – 當(dāng)客戶 c執(zhí)行寫操作 w。 – 它的服務(wù)器 s檢查 c的寫集合 Wset (c)，是否所有寫操作已在 c的本地執(zhí)行； – 如果在 c的本地沒有執(zhí)行，則請求執(zhí)行； – 執(zhí)行寫操作 w。 – 將 w的標(biāo)識符加入 Wset (c)。 S S‘ Wset Log Log 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 46 實現(xiàn)技術(shù)（ 4） ?讀自己寫一致性 (寫后讀 ) – 當(dāng)客戶 c執(zhí)行讀操作 r； – c的服務(wù)器 s檢查 c的寫集合 Wset (c)，是否所有寫操作已在 c的本地執(zhí)行； – 如果在 c的本地沒有執(zhí)行，則請求執(zhí)行； – 執(zhí)行讀操作 r。 S Wset Log 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 47 實現(xiàn)技術(shù)（ 5） ?寫跟隨讀一致性（讀后寫） – 當(dāng)客戶 c執(zhí)行寫操作 w時， – c的服務(wù)器 s檢查 c的讀集合 Rset (c)，是否所有寫操作已在 c的本地執(zhí)行； – 如果在 c的本地沒有執(zhí)行，則請求執(zhí)行； – 將這些寫操作標(biāo)識符加入 Rset (c)。 S S‘ Rset Log Log 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 48 優(yōu)化方法（ 1） ? 性能問題 – Wset(c)和 Rset(c)將非常大，造成性能降低 ? 基于 session的優(yōu)化方法 – 減少寫集和讀集中的 元素個數(shù) – 定義 session: 打開，關(guān)閉 – WS(c)和 RS(c)在 session打開時建立，關(guān)閉時清除 。 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 49 優(yōu)化方法（ 2） ? 基于 時間戳向量的優(yōu)化方法 – 減小寫集和讀集 表示形式 的大小 – 對一個寫操作 WID,賦予時間戳 ts(WID) – 服務(wù)器 Si維持一個時間戳向量 RCVD(i)。 ? RCVD(i) [j]= Si收到的來自 Sj的最近寫操作的時間戳。 – 對寫集或讀集 A維持一個時間戳向量 VT(A)。VT(A)[i]為在 Si上的最大時間戳 – 并操作： VT(A+B)[i]=max{VT(A)[i], VT(B)[i]} – 包含關(guān)系： VT(A)≤VT(B)?VT(A)[i] ≤VT(B)[i] 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 50 優(yōu)化方法（ 3） ? 例：單調(diào)讀一致性 – 設(shè)客戶 c在服務(wù)器 Si上執(zhí)行讀操作 r。 – c的讀集為 VT(Rset) ， Si有 RCVD(i) – 如果 RCVD(i)[j] ≤VT(Rset)[j]，則在 Si進行更新 – 執(zhí)行后， VT(Rest)[j]=max{VT(Rest)[j], RCVD(i)[j]} 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 51 分布協(xié)議 ?分布式數(shù)據(jù)倉的設(shè)計 – 復(fù)制副本的類型：永久型、服務(wù)器型、客戶型 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 52 永久型副本 ?構(gòu)成分布式數(shù)據(jù)倉的初始集合 – 靜態(tài)的、固定的 – 副本數(shù)量較少 ?例 1： Web場地的分布類型 – 局域網(wǎng)：輪回策略型服務(wù)器 – Inter：鏡像服務(wù)器 ?例 2：分布式數(shù)據(jù)庫 – 工作站集群（ COW） – 聯(lián)邦數(shù)據(jù)庫 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 53 服務(wù)器發(fā)起型副本（ 1） ?推送式緩存（ push cache） – 動態(tài)設(shè)置新的副本 ?作用： – 當(dāng)負(fù)載發(fā)生變化時，如突然增加。 – 減少服務(wù)器負(fù)擔(dān) – 減少客戶的通信開銷 ?問題 – 在何時、何地發(fā)起復(fù)制 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 54 服務(wù)器發(fā)起型副本（ 2） ?實現(xiàn)方法 – 訪問計數(shù)： t(S,F)， S為服務(wù)器， F為文件 – 復(fù)制閾值： rep(S,F) – 刪除閾值： del(S,F) – 距離： dist(S,C),C為客戶。該信息來自路由數(shù)據(jù)庫 ?復(fù)制副本 – 復(fù)制副本條件： t(S,F) rep(S,F) ?刪除副本 – 刪除副本條件： t(S,F) del(S,F) ?遷移副本 – 遷移副本條件： del(S,F) t(S,F) rep(S,F) 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 55 服務(wù)器發(fā)起型副本（ 3） ?舉例：計數(shù)來自不同客戶的請求，將文件復(fù)制到離客戶附近的服務(wù)器上。 – 如果 tQ(P,F)〉 t(Q,F)/2，將 F從 Q遷移到 P 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 56 客戶端發(fā)起型副本 ?客戶緩存 (cache) – 客戶端的本地存儲 ?緩存命中率 (cache hit)： – 請求的數(shù)據(jù)可在緩存中取出的概率 – 提高命中率：緩 存可由多個客戶共享 ?客戶緩存的設(shè)置 – 與客戶相同的機器 – 局域網(wǎng)上多個客戶共享的機器上 – 廣域網(wǎng)上的代理服務(wù)器上 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 57 更新傳播（ 1） ? 當(dāng)客戶執(zhí)行一個更新操作后，該操作將傳播到所有副本 ? 傳播狀態(tài)與傳播操作 1. 傳播更新通告 2. 傳輸數(shù)據(jù)拷貝 3. 傳播更新操作 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 58 更新傳播（ 2） ? 通告無效協(xié)議（ invalidation） – 傳輸被修改的數(shù)據(jù)的位置 – 占用很少網(wǎng)絡(luò)帶寬 – 適用于讀 /寫比非常低的情況 ? 數(shù)據(jù)傳輸 (data shipping) – 傳輸被修改的數(shù)據(jù) – 占用較多網(wǎng)絡(luò)帶寬 – 適用于讀 /寫比非常高的情況 2022411 東北大學(xué)軟件所 于戈 第六章 分布式 一致性 59 更新傳播（ 3） ? 操作傳輸 (operation shipping) – 主動復(fù)制技術(shù) 每個副本有一個進程主動地進行更新 – 占用最少網(wǎng)絡(luò)帶寬 – 要求有較高處理能