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

1、第七章第七章 一致性和復(fù)制一致性和復(fù)制 概述概述 以數(shù)據(jù)為中心的一致性模型以數(shù)據(jù)為中心的一致性模型 以客戶為中心的一致性模型以客戶為中心的一致性模型 復(fù)制管理復(fù)制管理 一致性協(xié)議一致性協(xié)議 可靠性可靠性 性能性能 服務(wù)器數(shù)量擴展服務(wù)器數(shù)量擴展 地理區(qū)域擴展地理區(qū)域擴展 代價：一致性代價：一致性 網(wǎng)絡(luò)通信開銷網(wǎng)絡(luò)通信開銷 強一致性要求的原子操作很難快速完成強一致性要求的原子操作很難快速完成 解決辦法：解決辦法： 放寬一致性方面的限制，放寬程度取決于復(fù)制數(shù)據(jù)的放寬一致性方面的限制，放寬程度取決于復(fù)制數(shù)據(jù)的訪問和更新模式以及數(shù)據(jù)的用途訪問和更新模式以及數(shù)據(jù)的用途以數(shù)據(jù)為中心的一致性模型以數(shù)據(jù)為中心的

2、一致性模型邏輯數(shù)據(jù)存儲的一般組織，物理上是分布的，并被復(fù)制到各個進程邏輯數(shù)據(jù)存儲的一般組織，物理上是分布的，并被復(fù)制到各個進程討論討論共享數(shù)據(jù)共享數(shù)據(jù)讀操作和寫操作時的一致性問題讀操作和寫操作時的一致性問題一致性模型實質(zhì)上是進程和數(shù)據(jù)存儲間的約定：如果進程同意遵守某些規(guī)則，數(shù)一致性模型實質(zhì)上是進程和數(shù)據(jù)存儲間的約定：如果進程同意遵守某些規(guī)則，數(shù)據(jù)存儲將正常進行。正常情況下，進程的讀操作應(yīng)該返回最后一次寫操作的結(jié)果據(jù)存儲將正常進行。正常情況下，進程的讀操作應(yīng)該返回最后一次寫操作的結(jié)果沒有全局時鐘，精確定義哪次寫操作是最后一次寫操作是困難的沒有全局時鐘，精確定義哪次寫操作是最后一次寫操作是困難的作

3、為全局時鐘的替代，產(chǎn)生了一系列一致性模型，每種模型都有效地限制了一個作為全局時鐘的替代，產(chǎn)生了一系列一致性模型，每種模型都有效地限制了一個數(shù)據(jù)項上執(zhí)行一次讀操作所應(yīng)返回的值數(shù)據(jù)項上執(zhí)行一次讀操作所應(yīng)返回的值嚴格一致性嚴格一致性（Strict Consistency）a) 嚴格的一致性存儲嚴格的一致性存儲b) 非嚴格的一致性存儲非嚴格的一致性存儲任何對數(shù)據(jù)項任何對數(shù)據(jù)項X的讀操作將返回最近一次對的讀操作將返回最近一次對X進行寫操作的值進行寫操作的值對所有進程來說，所有寫操作都是瞬間可見的，系統(tǒng)維護著一對所有進程來說，所有寫操作都是瞬間可見的，系統(tǒng)維護著一個絕對的全局時間順序個絕對的全局時間順序a

4、) 順序一致的數(shù)據(jù)存儲順序一致的數(shù)據(jù)存儲b) 非順序一致的數(shù)據(jù)存儲非順序一致的數(shù)據(jù)存儲順序一致性對存儲器的限制比嚴格一致性要弱一些，要滿足以下的條件：順序一致性對存儲器的限制比嚴格一致性要弱一些，要滿足以下的條件： （1） 每個進程的內(nèi)部操作順序是確定不變的；每個進程的內(nèi)部操作順序是確定不變的； （2） 假如所有的進程都對某一個存儲單元執(zhí)行操作，那么，它們的操作順序是確假如所有的進程都對某一個存儲單元執(zhí)行操作，那么，它們的操作順序是確定的，即任一進程都可以感知到這些進程同樣的操作順序。定的，即任一進程都可以感知到這些進程同樣的操作順序。 順序一致性可與事務(wù)串行化相比順序一致性可與事務(wù)串行化相比

5、串行化串行化：如果一個并發(fā)執(zhí)行的事務(wù)處理集合的結(jié)果可：如果一個并發(fā)執(zhí)行的事務(wù)處理集合的結(jié)果可以按照某種順序逐個執(zhí)行事務(wù)獲得，該事務(wù)處理集合以按照某種順序逐個執(zhí)行事務(wù)獲得，該事務(wù)處理集合是可串行化的是可串行化的區(qū)別：粒度的不同區(qū)別：粒度的不同 順序一致性：讀寫操作順序一致性：讀寫操作 串行化：事務(wù)（一系列讀寫操作的集合）串行化：事務(wù)（一系列讀寫操作的集合）線性化線性化： 弱于嚴格一致性而強于順序一致性弱于嚴格一致性而強于順序一致性 根據(jù)一系列時鐘同步確定序列順序（利用時間戳）根據(jù)一系列時鐘同步確定序列順序（利用時間戳）順序一致性和線性化提供了程序開發(fā)人員在并發(fā)程序順序一致性和線性化提供了程序開發(fā)

6、人員在并發(fā)程序設(shè)計中期望的語義：設(shè)計中期望的語義：所有寫操作都以相同的順序被每所有寫操作都以相同的順序被每個進程看到個進程看到因果一致性因果一致性Casual Consistency (1) 所有進程必須以相同的順序看到具有所有進程必須以相同的順序看到具有潛在因果關(guān)系潛在因果關(guān)系的寫操作的寫操作 不同機器上的進程可以以不同的順序看到并發(fā)的寫不同機器上的進程可以以不同的順序看到并發(fā)的寫操作操作因果一致性因果一致性 (2)因果一致性存儲允許的，但順序和嚴格一致性存儲不允許的順序因果一致性存儲允許的，但順序和嚴格一致性存儲不允許的順序a)違背因果一致性的時間存儲順序違背因果一致性的時間存儲順序b)符

7、合因果一致性的時間存儲順序符合因果一致性的時間存儲順序FIFO 一致性一致性FIFO Consistency (1) FIFO一致性模型是在因果一致性模型上的進一一致性模型是在因果一致性模型上的進一步弱化，它滿足下面的條件：步弱化，它滿足下面的條件： 由由某一個進程完成的寫操作某一個進程完成的寫操作可以被其他所有的進程可以被其他所有的進程按照順序感知到，而從不同進程中來的寫操作對不按照順序感知到，而從不同進程中來的寫操作對不同的進程可以有不同的順序。同的進程可以有不同的順序。 FIFO 一致性一致性 (2)符合符合FIFO 一致性的時間存儲順序一致性的時間存儲順序與順序一致性的區(qū)別與順序一致性

8、的區(qū)別:順序一致性：盡管語句的執(zhí)行順序是非確定的，順序一致性：盡管語句的執(zhí)行順序是非確定的，但所有的進程對順序達成一致但所有的進程對順序達成一致FIFO 一致性：各個進程不需要達成一致，不同一致性：各個進程不需要達成一致，不同進程可以以不同的順序看到進程可以以不同的順序看到引入同步的一致性引入同步的一致性 引入顯示的同步變量引入顯示的同步變量 當(dāng)一個進程對數(shù)據(jù)進行操作時，不保證其他進程當(dāng)一個進程對數(shù)據(jù)進行操作時，不保證其他進程何時看到這一操作，只是在執(zhí)行一次同步時，數(shù)何時看到這一操作，只是在執(zhí)行一次同步時，數(shù)據(jù)的改變才被傳播據(jù)的改變才被傳播 弱一致性弱一致性 釋放一致性釋放一致性 入口一致性入

9、口一致性 同步變量同步變量S僅有一個關(guān)聯(lián)操作僅有一個關(guān)聯(lián)操作synchronization(S),該操作同步數(shù)據(jù)存儲的所有本地拷貝該操作同步數(shù)據(jù)存儲的所有本地拷貝 弱一致性模型必須滿足的條件有下面幾點弱一致性模型必須滿足的條件有下面幾點: 對同步變量的訪問滿足一致性的要求對同步變量的訪問滿足一致性的要求 說明所有進程都以相同的順序看到同步變量進行的所說明所有進程都以相同的順序看到同步變量進行的所有操作有操作 對同步變量的訪問，只有在以前的寫操作在各處都完成對同步變量的訪問，只有在以前的寫操作在各處都完成之后才能進行。之后才能進行。 強迫在所有備份上完成所有的寫操作強迫在所有備份上完成所有的寫操

10、作 對數(shù)據(jù)的操作（讀或?qū)懀挥性谝郧暗膶ν阶兞康膶?shù)據(jù)的操作（讀或?qū)懀?，只有在以前的對同步變量的操作完成之后才能進行。操作完成之后才能進行。 保證所得到的數(shù)值是最新值保證所得到的數(shù)值是最新值a)對弱一致性有效的時間順序?qū)θ跻恢滦杂行У臅r間順序b)對弱一致性無效的時間順序?qū)θ跻恢滦詿o效的時間順序釋放一致性釋放一致性Release Consistency (1)對釋放一致性有效的時間順序?qū)︶尫乓恢滦杂行У臅r間順序釋放一致性使用兩種類型的同步變量來代替原來的一種同步釋放一致性使用兩種類型的同步變量來代替原來的一種同步變量變量獲取獲取Acquire操作用于表明進程進入臨界區(qū)操作用于表明進程進入臨界

11、區(qū)釋放釋放Release操作用于表明進程退出臨界區(qū)操作用于表明進程退出臨界區(qū)釋放一致性釋放一致性 (2) 通常，如果一個分布式共享存儲系統(tǒng)滿足釋放一致通常，如果一個分布式共享存儲系統(tǒng)滿足釋放一致性，則它必須遵守以下的規(guī)則：性，則它必須遵守以下的規(guī)則： 某進程只有在成功完成某進程只有在成功完成Acquire操作之后，才能對共享數(shù)據(jù)進操作之后，才能對共享數(shù)據(jù)進行讀寫操作。行讀寫操作。 某進程只有在完成對共享數(shù)據(jù)的讀寫操作之后，某進程只有在完成對共享數(shù)據(jù)的讀寫操作之后，Release操作操作才能完成。才能完成。 Acquire和和Release操作必須滿足操作必須滿足FIFO一致性要求。一致性要求。

12、 進程執(zhí)行獲取操作時要保證數(shù)據(jù)更新，與遠程數(shù)據(jù)保持一致，進程執(zhí)行獲取操作時要保證數(shù)據(jù)更新，與遠程數(shù)據(jù)保持一致，但不保證本地數(shù)據(jù)改變被立即傳播到其他拷貝但不保證本地數(shù)據(jù)改變被立即傳播到其他拷貝 進程執(zhí)行釋放操作時已改變的數(shù)據(jù)被立即傳播到其他拷貝，進程執(zhí)行釋放操作時已改變的數(shù)據(jù)被立即傳播到其他拷貝，不保證一定從其他拷貝引入改變不保證一定從其他拷貝引入改變要求每個普通的共享數(shù)據(jù)都要與某種同步變量（如鎖）關(guān)聯(lián)要求每個普通的共享數(shù)據(jù)都要與某種同步變量（如鎖）關(guān)聯(lián)思想：使得多個包含不同共享數(shù)據(jù)的臨界區(qū)可以同時執(zhí)行，從而思想：使得多個包含不同共享數(shù)據(jù)的臨界區(qū)可以同時執(zhí)行，從而增加系統(tǒng)的并行度，付出的代價是每

13、個共享數(shù)據(jù)與某種同步變量增加系統(tǒng)的并行度，付出的代價是每個共享數(shù)據(jù)與某種同步變量關(guān)聯(lián)的額外開銷和復(fù)雜性關(guān)聯(lián)的額外開銷和復(fù)雜性滿足入口一致性的條件是：滿足入口一致性的條件是： 在一個進程可以獲取一個同步變量前，所有由該同步變量保在一個進程可以獲取一個同步變量前，所有由該同步變量保護的共享數(shù)據(jù)相對與該進程已經(jīng)護的共享數(shù)據(jù)相對與該進程已經(jīng)更新更新完畢完畢 在一個進程被允許以在一個進程被允許以獨占獨占模式訪問某同步變量之前，任何別模式訪問某同步變量之前，任何別的進程不可以擁有該同步變量，即使以非獨占模式擁有。的進程不可以擁有該同步變量，即使以非獨占模式擁有。 在一個進程以獨占模式訪問一個同步變量之后，

14、在對該同步在一個進程以獨占模式訪問一個同步變量之后，在對該同步變量的所有者變量的所有者檢查檢查之前，任何其他進程都不能執(zhí)行下一個非之前，任何其他進程都不能執(zhí)行下一個非獨占訪問。獨占訪問。對入口一致性有效的時間順序?qū)θ肟谝恢滦杂行У臅r間順序一致性總結(jié)一致性總結(jié)a)不使用同步操作的一致性模型不使用同步操作的一致性模型b)使用同步操作的一致性模型使用同步操作的一致性模型ConsistencyDescription嚴格嚴格所有共享訪問按絕對時間排序所有共享訪問按絕對時間排序線性化線性化所有進程以相同順序看到所有的共享訪問。而且，訪問是根據(jù)全局時間戳排序的所有進程以相同順序看到所有的共享訪問。而且，訪問

15、是根據(jù)全局時間戳排序的順序順序所有進程以相同順序看到所有的共享訪問。訪問不是根據(jù)時間排序的所有進程以相同順序看到所有的共享訪問。訪問不是根據(jù)時間排序的因果因果所有進程以相同順序看到因果相關(guān)的共享訪問。所有進程以相同順序看到因果相關(guān)的共享訪問。FIFO所有進程以不同進程提出寫操作的順序相互看到寫操作。來自不同進程的寫操作可以不所有進程以不同進程提出寫操作的順序相互看到寫操作。來自不同進程的寫操作可以不必總是以相同的順序出現(xiàn)。必總是以相同的順序出現(xiàn)。(a)ConsistencyDescription弱弱只有在執(zhí)行一次同步后，共享數(shù)據(jù)才被認為是一致的只有在執(zhí)行一次同步后，共享數(shù)據(jù)才被認為是一致的釋放

16、釋放退出臨界區(qū)時，使共享數(shù)據(jù)成為一致的退出臨界區(qū)時，使共享數(shù)據(jù)成為一致的入口入口進入臨界區(qū)時，使屬于一個臨界區(qū)的共享數(shù)據(jù)成為一致的進入臨界區(qū)時，使屬于一個臨界區(qū)的共享數(shù)據(jù)成為一致的(b) 最終一致性最終一致性：很多情況下系統(tǒng)能容忍相對較高程度的：很多情況下系統(tǒng)能容忍相對較高程度的不一致性，共同之處在于：只有一個或少數(shù)幾個進程不一致性，共同之處在于：只有一個或少數(shù)幾個進程執(zhí)行更新操作，如果較長時間內(nèi)沒有更新操作，那么執(zhí)行更新操作，如果較長時間內(nèi)沒有更新操作，那么副本將逐漸成為一致的副本將逐漸成為一致的 數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng) DNS WWW 特點：特點： 只有少數(shù)幾個進程執(zhí)行更新操作，只需要處理讀

17、寫沖突只有少數(shù)幾個進程執(zhí)行更新操作，只需要處理讀寫沖突 能容忍相對較高程度的不一致性能容忍相對較高程度的不一致性 實現(xiàn)開銷小實現(xiàn)開銷小 如果客戶總是訪問同一副本，最終一致性能工作得很如果客戶總是訪問同一副本，最終一致性能工作得很好好移動用戶訪問分布式數(shù)據(jù)庫不同副本的原理移動用戶訪問分布式數(shù)據(jù)庫不同副本的原理如果一個進程讀取數(shù)據(jù)項如果一個進程讀取數(shù)據(jù)項x的值，那么該進程對的值，那么該進程對x執(zhí)行的任何后續(xù)讀操作執(zhí)行的任何后續(xù)讀操作將總是得到第一次讀取的那個值或更新的值將總是得到第一次讀取的那個值或更新的值進程進程 P 對同一數(shù)據(jù)存儲的兩個不同本地備份執(zhí)行的讀操作對同一數(shù)據(jù)存儲的兩個不同本地備份執(zhí)

18、行的讀操作a)提供單調(diào)讀一致性的數(shù)據(jù)存儲提供單調(diào)讀一致性的數(shù)據(jù)存儲b)不提供單調(diào)讀一致性的數(shù)據(jù)存儲不提供單調(diào)讀一致性的數(shù)據(jù)存儲.WS(x1;x2)表示表示W(wǎng)S(x1)的操作已的操作已在在L2更新完畢更新完畢 一個進程對數(shù)據(jù)項一個進程對數(shù)據(jù)項x執(zhí)行的寫操作必須在該進程對執(zhí)行的寫操作必須在該進程對x執(zhí)行的任何后續(xù)寫操作之前執(zhí)行的任何后續(xù)寫操作之前完成完成 進程進程 P 對同一數(shù)據(jù)存儲的兩個不同本地備份執(zhí)行的寫操作對同一數(shù)據(jù)存儲的兩個不同本地備份執(zhí)行的寫操作提供單調(diào)寫一致性的數(shù)據(jù)存儲提供單調(diào)寫一致性的數(shù)據(jù)存儲不提供單調(diào)寫一致性的數(shù)據(jù)存儲不提供單調(diào)寫一致性的數(shù)據(jù)存儲 類似以數(shù)據(jù)為中心的類似以數(shù)據(jù)為中心

19、的FIFO一致性一致性一個進程對數(shù)據(jù)項一個進程對數(shù)據(jù)項x執(zhí)行的寫操作結(jié)果總會被該進程對執(zhí)行的寫操作結(jié)果總會被該進程對x執(zhí)行的任何后續(xù)讀執(zhí)行的任何后續(xù)讀操作看見操作看見提供寫后讀一致性的數(shù)據(jù)存儲提供寫后讀一致性的數(shù)據(jù)存儲不提供寫后讀一致性的數(shù)據(jù)存儲不提供寫后讀一致性的數(shù)據(jù)存儲同一個進程對數(shù)據(jù)項同一個進程對數(shù)據(jù)項x執(zhí)行的讀操作之后的寫操作，保證發(fā)生在執(zhí)行的讀操作之后的寫操作，保證發(fā)生在與與x讀取之相同或更新的值上讀取之相同或更新的值上提供讀后寫一致性的數(shù)據(jù)存儲提供讀后寫一致性的數(shù)據(jù)存儲不提供讀后寫一致性的數(shù)據(jù)存儲不提供讀后寫一致性的數(shù)據(jù)存儲數(shù)據(jù)存儲的不同類型備份數(shù)據(jù)存儲的不同類型備份分發(fā)協(xié)議分發(fā)協(xié)

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

21、型來自不同客戶的訪問請求計數(shù)來自不同客戶的訪問請求計數(shù)更新傳播更新傳播更新傳播更新傳播：更新從一個拷貝傳播到其他拷貝更新從一個拷貝傳播到其他拷貝相關(guān)設(shè)計問題：相關(guān)設(shè)計問題：狀態(tài)與操作狀態(tài)與操作拉協(xié)議與推協(xié)議拉協(xié)議與推協(xié)議單播與多播單播與多播實際傳播的信息實際傳播的信息 只傳播只傳播更新的通知更新的通知：無效化協(xié)議：無效化協(xié)議 可以指定數(shù)據(jù)存儲的哪些部分被更新了可以指定數(shù)據(jù)存儲的哪些部分被更新了 請求在無效的拷貝上操作時，先更新該拷貝請求在無效的拷貝上操作時，先更新該拷貝 幾乎不占帶寬，適合更新操作比讀寫操作多的場合（兩次更新間可能幾乎不占帶寬，適合更新操作比讀寫操作多的場合（兩次更新間可能沒有

22、讀操作）沒有讀操作） 把把數(shù)據(jù)數(shù)據(jù)從一個拷貝傳送到另一個拷貝從一個拷貝傳送到另一個拷貝 適合讀對寫的比率相對高的場合：被修改的數(shù)據(jù)可能在下一個更新前適合讀對寫的比率相對高的場合：被修改的數(shù)據(jù)可能在下一個更新前被讀取，即更新是有效的可能性較高被讀取，即更新是有效的可能性較高 可以只傳送修改的日志可以只傳送修改的日志 通過將多個修改壓縮到一個消息里來減少通信開銷通過將多個修改壓縮到一個消息里來減少通信開銷 把把更新操作更新操作傳送到其他拷貝：主動復(fù)制傳送到其他拷貝：主動復(fù)制 假設(shè)每個副本由一個進程代表，該進程通過執(zhí)行操作主動地更新數(shù)據(jù)：假設(shè)每個副本由一個進程代表，該進程通過執(zhí)行操作主動地更新數(shù)據(jù)：

23、假設(shè)操作關(guān)聯(lián)的參數(shù)少，傳播更新的帶寬代價小假設(shè)操作關(guān)聯(lián)的參數(shù)少，傳播更新的帶寬代價小在多客戶、單一服務(wù)器系統(tǒng)中，基于推式協(xié)議與基于拉式協(xié)議比較在多客戶、單一服務(wù)器系統(tǒng)中，基于推式協(xié)議與基于拉式協(xié)議比較問題問題基于推式基于推式基于拉式基于拉式服務(wù)器的狀態(tài)服務(wù)器的狀態(tài)客戶副本和高速緩存的列表客戶副本和高速緩存的列表無無發(fā)送的消息發(fā)送的消息更新（以及以后可能獲取的更新）更新（以及以后可能獲取的更新）輪詢和更新輪詢和更新客戶響應(yīng)時間客戶響應(yīng)時間立即（或獲取更新的時間）立即（或獲取更新的時間）獲取更新的時間獲取更新的時間基于推式協(xié)議：基于服務(wù)器的協(xié)議基于推式協(xié)議：基于服務(wù)器的協(xié)議 永久副本和服務(wù)器啟動的

24、副本更新永久副本和服務(wù)器啟動的副本更新 用于副本需要完全相同的時候用于副本需要完全相同的時候 適合讀對寫的比率相對高的場合（更新對讀操作有效），高效適合讀對寫的比率相對高的場合（更新對讀操作有效），高效基于拉式協(xié)議：基于客戶的協(xié)議基于拉式協(xié)議：基于客戶的協(xié)議 一臺服務(wù)器或客戶請求其他服務(wù)器向它發(fā)送持有的更新一臺服務(wù)器或客戶請求其他服務(wù)器向它發(fā)送持有的更新 用于客戶高速緩存：用于客戶高速緩存：Web高速緩存，客戶輪詢服務(wù)器高速緩存，客戶輪詢服務(wù)器基于租用的更新傳播基于租用的更新傳播 更新傳播的混合形式更新傳播的混合形式 租用是服務(wù)器的承諾，它將在指定的時間內(nèi)將更新推給客戶。租用是服務(wù)器的承諾，它

25、將在指定的時間內(nèi)將更新推給客戶。 租用到期后：租用到期后： 客戶被迫輪詢服務(wù)器以實現(xiàn)更新客戶被迫輪詢服務(wù)器以實現(xiàn)更新 客戶請求一個新的租期客戶請求一個新的租期 三種類型的租用三種類型的租用 根據(jù)數(shù)據(jù)項的年齡：為預(yù)期保持不變的數(shù)據(jù)授予一個長期根據(jù)數(shù)據(jù)項的年齡：為預(yù)期保持不變的數(shù)據(jù)授予一個長期的租用，可以減少更新消息的數(shù)量的租用，可以減少更新消息的數(shù)量 根據(jù)客戶請求高速緩存副本的頻率：頻率高的客戶授予長根據(jù)客戶請求高速緩存副本的頻率：頻率高的客戶授予長期的租用，只跟蹤對數(shù)據(jù)感興趣的客戶期的租用，只跟蹤對數(shù)據(jù)感興趣的客戶 基于服務(wù)器的狀態(tài)空間開銷：將要過載時，縮短新租用的基于服務(wù)器的狀態(tài)空間開銷：將

26、要過載時，縮短新租用的期限期限單播與多播單播與多播 多播：服務(wù)器向其他多播：服務(wù)器向其他N臺服務(wù)器發(fā)送更新時，底層臺服務(wù)器發(fā)送更新時，底層的網(wǎng)絡(luò)負責(zé)向多個接收者發(fā)送一個消息，高效的網(wǎng)絡(luò)負責(zé)向多個接收者發(fā)送一個消息，高效 與推式更新結(jié)合更高效與推式更新結(jié)合更高效 單播：服務(wù)器向其他單播：服務(wù)器向其他N臺服務(wù)器發(fā)送更新時，要發(fā)臺服務(wù)器發(fā)送更新時，要發(fā)送送N個單獨的消息個單獨的消息 與拉式更新結(jié)合更高效：只有一個客戶請求更新與拉式更新結(jié)合更高效：只有一個客戶請求更新Epidemic協(xié)議協(xié)議 提供提供最終一致性最終一致性：保證所有的副本最終是一致的：保證所有的副本最終是一致的不解決更新沖突，只關(guān)心使用

27、最少的消息將更新傳播到所有副本不解決更新沖突，只關(guān)心使用最少的消息將更新傳播到所有副本一個服務(wù)器可以是：一個服務(wù)器可以是： 傳染性的：持有愿意向其他服務(wù)器散布的更新傳染性的：持有愿意向其他服務(wù)器散布的更新 易感的：尚未更新的服務(wù)器易感的：尚未更新的服務(wù)器 隔離的：已更新的服務(wù)器如果不愿意或不能擴散其更新隔離的：已更新的服務(wù)器如果不愿意或不能擴散其更新反熵反熵傳播模型：服務(wù)器傳播模型：服務(wù)器P周期的隨機選取一臺服務(wù)器周期的隨機選取一臺服務(wù)器Q交換更新，方式包括：交換更新，方式包括： P只把自己的更新推入只把自己的更新推入Q：較差的選擇：較差的選擇 P只從只從Q拉出新的更新拉出新的更新 P和和Q相

28、互發(fā)送更新相互發(fā)送更新 可以證明：如果初始只有一臺服務(wù)器具有傳染性，無論采用哪種形式，可以證明：如果初始只有一臺服務(wù)器具有傳染性，無論采用哪種形式，更新最終將被傳播到所有服務(wù)器上更新最終將被傳播到所有服務(wù)器上 思想：思想： 如果服務(wù)器如果服務(wù)器P剛剛因為數(shù)據(jù)項剛剛因為數(shù)據(jù)項x而被更新，那么它聯(lián)系任而被更新，那么它聯(lián)系任意一個其他服務(wù)器意一個其他服務(wù)器Q，并試圖將更新推入，并試圖將更新推入Q。 如果如果Q已經(jīng)被其他服務(wù)器更新了，已經(jīng)被其他服務(wù)器更新了， P可能會失去繼續(xù)擴散可能會失去繼續(xù)擴散的興趣，變成隔離的（這種可能性是的興趣，變成隔離的（這種可能性是1/k） 快速傳播更新的方法快速傳播更新的

29、方法 但不能保證所有的服務(wù)器都被更新了但不能保證所有的服務(wù)器都被更新了 s=e-(k+1)(1-s) ,k=3時，時，s小于小于2% 可以將可以將gossiping和反熵結(jié)合和反熵結(jié)合一致性協(xié)議一致性協(xié)議 一致性協(xié)議描述特定的一致性模型的實現(xiàn)一致性協(xié)議描述特定的一致性模型的實現(xiàn) 基于主備份的協(xié)議基于主備份的協(xié)議：每個數(shù)據(jù)：每個數(shù)據(jù)x都有一個關(guān)聯(lián)的主備都有一個關(guān)聯(lián)的主備份，負責(zé)協(xié)調(diào)份，負責(zé)協(xié)調(diào)x的寫操作，根據(jù)主備份的位置分為：的寫操作，根據(jù)主備份的位置分為： 遠程寫協(xié)議遠程寫協(xié)議 本地寫協(xié)議本地寫協(xié)議 復(fù)制的寫協(xié)議復(fù)制的寫協(xié)議：寫操作可以在多個副本上執(zhí)行：寫操作可以在多個副本上執(zhí)行 主動復(fù)制主動復(fù)制 基于法定數(shù)目的協(xié)議基于法定數(shù)目的協(xié)議 基于主備份的遠程寫協(xié)議，所有讀操作和寫操作都被轉(zhuǎn)發(fā)到基于主備份的遠程寫協(xié)議，所有讀操作和寫操作都被轉(zhuǎn)發(fā)到一個固定的服務(wù)器