教育資源網(wǎng)格中的一種動態(tài)數(shù)據(jù)復(fù)制技術(shù)

摘要：針對教育網(wǎng)格中數(shù)據(jù)資源共享的這個關(guān)鍵問題，主要在數(shù)據(jù)復(fù)制技術(shù)方面作了研究。在討論了一種合理的副本目錄管理模型后，提出了一種動態(tài)的副本創(chuàng)建策略，該策略提高了副本放置的效率，并能夠適應(yīng)用戶請求的動態(tài)變化。

關(guān)鍵詞：教育資源共享； 復(fù)制； 副本一致性； 副本放置

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)03－0869－03

網(wǎng)格是一種動態(tài)的、分布式的虛擬組織間的資源共享技術(shù)。這種共享強(qiáng)調(diào)對計算機(jī)、軟件、數(shù)據(jù)及其他資源的直接訪問，而不是簡單的文件交換。可以說網(wǎng)格就是通過把分布的資源集中整合起來，獲得任何單獨計算機(jī)無法達(dá)到的性能。

數(shù)據(jù)網(wǎng)格是網(wǎng)格技術(shù)的重要分支。在數(shù)據(jù)網(wǎng)格中，數(shù)據(jù)是最重要的資源。但是，由于資源在廣域上分布、本質(zhì)上異構(gòu)，并且由不同的個人或組織擁有，要進(jìn)行大規(guī)模的數(shù)據(jù)移動、跨域的數(shù)據(jù)共享就變得非常困難。

數(shù)據(jù)復(fù)制在數(shù)據(jù)網(wǎng)格中是一個關(guān)鍵的問題，其目標(biāo)是獲得對數(shù)據(jù)更好的訪問性能。目前，復(fù)制技術(shù)已經(jīng)廣泛地應(yīng)用到分布式系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中。在數(shù)據(jù)網(wǎng)格環(huán)境下，用戶要完成一項作業(yè)需要讀取大量的數(shù)據(jù)，通常這些數(shù)據(jù)又是以分布式的形式存放在網(wǎng)格的各個節(jié)點上。為了實現(xiàn)地理位置分散的多個虛擬組織之間的數(shù)據(jù)共享，可以采用在用戶附近緩存數(shù)據(jù)的方法來提高整個數(shù)據(jù)網(wǎng)格性能。復(fù)制技術(shù)就是在恰當(dāng)?shù)木W(wǎng)絡(luò)節(jié)點上放置數(shù)據(jù)副本，為用戶應(yīng)用提供一個能夠快速訪問和處理的遠(yuǎn)程數(shù)據(jù)的局部數(shù)據(jù)拷貝，避免大量數(shù)據(jù)遠(yuǎn)程的傳輸，從而大大減少訪問延遲和帶寬消耗，并有利于提高系統(tǒng)的可靠性[1]。

目前，關(guān)于教育資源共享網(wǎng)格的研究主要包括基于因特網(wǎng)的教育資源的研究探索、模型開發(fā)，以及如何使用網(wǎng)格的技術(shù)來實現(xiàn)。具體來說，就是如何將優(yōu)秀課件、優(yōu)秀教師的講課視頻、精品教程等通過因特網(wǎng)共享，并且能完成相應(yīng)的收費(fèi)、查詢、課件試用等功能。由于模型中涉及到了很多大量數(shù)據(jù)的遠(yuǎn)程傳輸問題，而復(fù)制技術(shù)又能在很大程度上減輕該問題中的訪問延遲和帶寬消耗，引入數(shù)據(jù)復(fù)制技術(shù)就成為必然。復(fù)制技術(shù)的使用主要包括：生成新的完整的或部分的數(shù)據(jù)副本；為了維護(hù)一致性和良好的副本定位功能，要把這些新的副本注冊到副本目錄中；用戶通過查詢目錄已發(fā)現(xiàn)所有現(xiàn)存的數(shù)據(jù)副本，并在其中選擇較好的一個或多個副本用于訪問。

1動態(tài)復(fù)制技術(shù)

副本的管理和分配方式可以分為靜態(tài)和動態(tài)兩種。靜態(tài)復(fù)制是指在系統(tǒng)設(shè)計時就將副本放置在一些節(jié)點上，當(dāng)系統(tǒng)開始工作后，即使系統(tǒng)環(huán)境有了顯著變化，或是用戶行為有了變化，這些節(jié)點上仍然存放著副本。整個系統(tǒng)的副本處于一個靜態(tài)不變的狀態(tài)，不能適應(yīng)系統(tǒng)的動態(tài)變化。

動態(tài)復(fù)制則不同，它是在系統(tǒng)工作中根據(jù)具體用戶行為的變化和系統(tǒng)的動態(tài)變化來放置和管理副本。用戶作業(yè)要調(diào)用某個數(shù)據(jù)文件時，有可能直接在已有的副本中選擇一個或多個副本進(jìn)行傳輸，當(dāng)個別節(jié)點負(fù)載過重時也有可能在合適的位置創(chuàng)建新的副本。這樣，系統(tǒng)中的副本管理具有高度的動態(tài)性，可以適應(yīng)用戶請求的變化或系統(tǒng)中副本存儲節(jié)點的變化。

定位副本都是通過副本目錄來完成的，而動態(tài)復(fù)制技術(shù)會引起副本一致性問題。如何保證副本在創(chuàng)建、更改或刪除以后，副本目錄信息能夠及時地更新[2]，是目前一個較難解決的問題。本文把重點放在教育網(wǎng)格中如何建立合適的副本目錄和如何動態(tài)地進(jìn)行副本放置上。

2副本目錄

2．1目錄模型的設(shè)計

借鑒文獻(xiàn)[3]中所提出的樹和環(huán)相結(jié)合的混合拓?fù)浣Y(jié)構(gòu)，建立一個如圖1所示的目錄模型。由于中心目錄能夠大大簡化副本的一致性問題，模型中依然保留了中心目錄節(jié)點。同時，采用中心目錄和中間目錄結(jié)合的雙層目錄結(jié)構(gòu)可以在很大程度上減輕中心目錄節(jié)點的負(fù)擔(dān)，有利于系統(tǒng)的穩(wěn)定性。

將教育資源共享網(wǎng)格中的節(jié)點按照地區(qū)劃分為子網(wǎng)，如地區(qū)A、B（地區(qū)A同樣可以劃分更多的子網(wǎng)地區(qū)A1、A2等）。中間目錄節(jié)點就是這么一些地區(qū)級的網(wǎng)格節(jié)點，負(fù)責(zé)中間目錄的管理。最底層的節(jié)點是資源存放的節(jié)點，這些節(jié)點保存了其自身數(shù)據(jù)元的目錄信息，如圖1中的S1、S2節(jié)點。對同一層上的目錄節(jié)點用環(huán)形結(jié)構(gòu)將它們相互連接起來，方便了同層節(jié)點之間相互查詢，提高了它們之間數(shù)據(jù)傳輸讀取的效率，同時減輕了中央目錄節(jié)點的傳輸負(fù)擔(dān)和查詢負(fù)擔(dān)。

通過簡化并改進(jìn)文獻(xiàn)[4]中的目錄策略，以適用上述的目錄模型，具體的設(shè)置如下：為了實現(xiàn)數(shù)據(jù)的統(tǒng)一訪問和管理，將系統(tǒng)中各類型的數(shù)據(jù)都抽象為數(shù)據(jù)元，每個數(shù)據(jù)元都設(shè)置一個在整個系統(tǒng)中惟一的邏輯數(shù)據(jù)名(logical data name，LDN)；為了區(qū)分對同一數(shù)據(jù)元產(chǎn)生的不同副本，給每個副本設(shè)置不同的物理副本名(physics replica name，PRN)，PRN中主要包括副本所在的物理位置信息。

中間目錄節(jié)點上要維持的目錄信息是地區(qū)到PRN的一個映射，如一個地區(qū)的一個節(jié)點上有某一個副本，它就只需維持一個(地區(qū)，PRN)的映射信息。這樣，這個地區(qū)的副本目錄就提供本地副本的查詢能力。在中心目錄節(jié)點上，由于各中間目錄節(jié)點的存在，減小了副本存儲和更新的開銷，即如果某個地區(qū)上存在一個邏輯數(shù)據(jù)名為LDN的數(shù)據(jù)元副本，僅需要維持一個(LDN，地區(qū))的映射。

例如，地區(qū)A的一個網(wǎng)格節(jié)點上有數(shù)據(jù)元LDN1的一個副本，其物理副本名為PRN1，那么地區(qū)A上維持一個(地區(qū)A，PRN1)的映射，中心目錄維持一個(LDN1，地區(qū)A)的映射。

2．2副本的查詢定位

網(wǎng)格用戶對應(yīng)的中間目錄節(jié)點是副本查詢定位的起始點。當(dāng)?shù)讓泳W(wǎng)格用戶節(jié)點請求要得到某一個數(shù)據(jù)時，首先要向其對應(yīng)的地區(qū)節(jié)點發(fā)出查詢請求。當(dāng)一個地區(qū)節(jié)點收到網(wǎng)格用戶對數(shù)據(jù)元LDN的查詢請求后，會首先查詢本地是否有該LDN的副本，具體過程如下：

a)如果有該數(shù)據(jù)元的副本并且副本數(shù)目能滿足網(wǎng)格用戶的請求，就直接返回這些副本PRN信息，用戶就可以通過這些PRN方便地定位到目標(biāo)副本。

b)如果本地沒有該數(shù)據(jù)元的副本或副本數(shù)目不能滿足用戶請求，則查找中央目錄節(jié)點。在中央目錄節(jié)點上可以方便地查詢到哪個地區(qū)有該數(shù)據(jù)元的相關(guān)副本；然后再到那些地區(qū)查詢副本具體的PRN信息，并通過同層目錄節(jié)點之間的環(huán)形連接來傳遞這些信息，這樣可以有效地提高信息傳輸?shù)男剩蛔詈缶W(wǎng)格用戶通過PRN信息定位到目標(biāo)副本。

2．3副本的一致性維護(hù)

為了使整個系統(tǒng)可以正常工作，并保證查詢信息的準(zhǔn)確可靠，維護(hù)副本信息的一致性必須采用合適的更新策略。

對于上述副本目錄模型，副本信息的更新主要包括兩個方面，即中央和地區(qū)目錄的更新。也就是說，當(dāng)副本被創(chuàng)建或刪除后，要分別對(地區(qū)，PRN)(LDN，地區(qū))這兩組映射進(jìn)行檢查和更新。

例如，如圖1所示，刪除地區(qū)A上一個數(shù)據(jù)元LDN1的副本，其物理副本名為PRN1，并且刪除后地區(qū)A上就沒有任何LDN1的副本。具體的更新是：刪除地區(qū)A上(地區(qū)A，PRN1)的映射，并從中心目錄刪除(LDN1，地區(qū)A)的映射。

2．4目錄模型和目錄策略的分析

在目錄模型中，采用了樹和環(huán)相結(jié)合的混合拓?fù)浣Y(jié)構(gòu)。采用樹的結(jié)構(gòu)是目錄模型中多層目錄策略的前提；在整個查詢定位的過程中，同一層節(jié)點上采用的環(huán)形連接可以提高目錄信息的傳輸效率，并且同層之間的信息傳遞也減輕了中央節(jié)點的負(fù)擔(dān)。

改進(jìn)后的副本目錄策略不僅能很好地應(yīng)用于系統(tǒng)，而且可以有效地支持對副本的本地查詢，使本地數(shù)據(jù)請求可以更快地滿足。同時，由于中心目錄節(jié)點的負(fù)載較輕，可以在一定程度上支持更多的副本信息查詢。在這種副本策略下，單個地區(qū)節(jié)點的失效并不影響其他節(jié)點的功能，具有較好的可靠性。

3一種動態(tài)的副本放置策略

3．1副本放置問題

復(fù)制技術(shù)是數(shù)據(jù)網(wǎng)格中加快數(shù)據(jù)訪問的一種重要技術(shù)。在用戶附近放置數(shù)據(jù)副本不僅可以減少訪問開銷，而且在很多應(yīng)用中可以增加數(shù)據(jù)的可靠性[5]。副本的放置策略必須討論以下兩個問題：a)副本應(yīng)放置在合適的位置，以保證各個服務(wù)器的負(fù)載均衡。b)選擇最佳副本數(shù)量。副本過多，則副本節(jié)點維護(hù)副本的費(fèi)用會非常昂貴；副本過少，又無法保證數(shù)據(jù)訪問的效率。

文獻(xiàn)[5]提出了一種副本放置策略，但這種策略并沒有討論如何在一個用戶請求動態(tài)變化的環(huán)境里進(jìn)行副本的動態(tài)管理，以盡可能保證上述復(fù)制技術(shù)的優(yōu)勢得到體現(xiàn)。

本文的動態(tài)副本放置算法不僅完成了對副本放置位置的優(yōu)化選擇，而且考慮了對副本數(shù)目的控制。另外，算法具有高度的動態(tài)性，從網(wǎng)格用戶作業(yè)調(diào)用某個數(shù)據(jù)的角度，用戶請求有可能直接在已有的副本中選擇一個或多個副本進(jìn)行傳輸，當(dāng)相關(guān)副本節(jié)點負(fù)載過重時也有可能在合適的位置創(chuàng)建新的副本。

3．2數(shù)學(xué)模型

采用一棵樹來表示一個數(shù)據(jù)網(wǎng)格系統(tǒng)。如圖2所示，T為數(shù)據(jù)網(wǎng)格系統(tǒng)樹，根節(jié)點為A，副本可能放在除a外的任何節(jié)點上。假設(shè)所有的數(shù)據(jù)請求都來自于葉子節(jié)點，且對于葉節(jié)點m，w(m)表示m請求數(shù)據(jù)的數(shù)量。

圖1目錄模型圖2數(shù)據(jù)網(wǎng)格樹

其中：N為樹中節(jié)點的集合；R是樹中所有放置了副本的節(jié)點集合。n是樹中的一個節(jié)點，n的負(fù)載f(n)可以嵌套地定義為

fR(n)=w(n)如果n是葉子節(jié)點

∑cfR(c)如果c是n的子節(jié)點，且cR

副本節(jié)點集R的負(fù)載為R中每個節(jié)點的負(fù)載以及中心節(jié)點a的負(fù)載的和。

3．3動態(tài)副本放置算法

3．3．1算法目標(biāo)

給定一個數(shù)據(jù)網(wǎng)格樹，在網(wǎng)格用戶的數(shù)據(jù)請求動態(tài)變化的情況下，副本節(jié)點創(chuàng)建和刪除必須可以適應(yīng)這種動態(tài)變化。對于副本的創(chuàng)建，本文主要考慮兩個限制因素：保證副本集R中R的基數(shù)(R中節(jié)點個數(shù))不超過k；保證系統(tǒng)中每個節(jié)點的負(fù)載都不大于D。如果一個樹節(jié)點的負(fù)載大于D，則稱之為heavy節(jié)點；否則稱為light節(jié)點。如果一個heavy節(jié)點所有的子節(jié)點都是light節(jié)點，則稱該heavy節(jié)點為critical節(jié)點。

3．3．2算法描述

由于系統(tǒng)內(nèi)用戶的請求是動態(tài)變化的，設(shè)置時間間隔T，每間隔T時刻，重新查看各用戶節(jié)點的請求，并根據(jù)新的請求計算出系統(tǒng)各節(jié)點的負(fù)載；同時必須保證時間T內(nèi)，副本放置或置換的次數(shù)不大于k。設(shè)I為當(dāng)前時刻系統(tǒng)中的副本數(shù)目；L為置換隊列，當(dāng)放置的副本過多時，可以被新副本替換的副本節(jié)點。具體的算法描述如下：

a)設(shè)t0為起始時刻，此時運(yùn)行系統(tǒng)，計算整個系統(tǒng)每個節(jié)點的負(fù)載。

b)找出每一個critical節(jié)點的子節(jié)點中負(fù)載最大的節(jié)點，將這些節(jié)點按其負(fù)載由大到小排列成一個隊列P。

c)IfI

{

選取P中的第一個節(jié)點，放置一個副本，然后從P中刪除該節(jié)點；

在中心節(jié)點a到副本放置節(jié)點的路徑上，把所有節(jié)點的負(fù)載都減去副本放置節(jié)點的負(fù)載（注意，經(jīng)過這一步，可能會使副本放置節(jié)點的一個或多個祖先節(jié)點由heavy節(jié)點變?yōu)閘ight節(jié)點)，并將副本數(shù)目I加上1；

更新副本目錄信息；

執(zhí)行步驟d)；

}

IfI≥k

{

采用LRU(最近最少使用)置換策略來完成副本的置換，具體描述如下：

按深度優(yōu)先的順序，把R中所有的節(jié)點按負(fù)載由小到大的順序排列，負(fù)載相同的節(jié)點按照創(chuàng)建時間由早到晚排列，然后將它們依次加入置換隊列L；

選取置換隊列L中最早進(jìn)入隊列的節(jié)點，刪除放在其上的副本節(jié)點，并將副本數(shù)目I減小1；

在中心節(jié)點a到刪除副本節(jié)點的路徑上，重新計算每個節(jié)點的負(fù)載；

重新執(zhí)行步驟c)；

}

d)重復(fù)執(zhí)行c)，要保證副本放置或置換的次數(shù)小于等于k次，直至隊列P中沒有節(jié)點，這時系統(tǒng)中也就沒有了heavy節(jié)點。

e)放置好副本后，各網(wǎng)格用戶節(jié)點訪問數(shù)據(jù)副本，具體的步驟如下：

先在本地查找數(shù)據(jù)副本；

若找不到，查找其父節(jié)點；

如果本地節(jié)點到中心節(jié)點a的路徑上都找不到副本，中心節(jié)點響應(yīng)請求。

f)時間間隔T后，重新計算系統(tǒng)中各個節(jié)點的負(fù)載。

重復(fù)執(zhí)行b)~f)，直至系統(tǒng)停止。

3．4算法舉例

對算法中步驟c）放置副本的過程舉例見圖2。

假設(shè)節(jié)點e是隊列P中的第一個節(jié)點，且e的負(fù)載為f(e)。在節(jié)點e上放置一個副本，并將e從隊列P中刪除；然后找到a到e路徑上的所有節(jié)點（也就是a、b、c三個節(jié)點），把這三個節(jié)點的負(fù)載都減去f(e)；最后再將I的值減1，并更新副本目錄。

3．5算法復(fù)雜度分析

在一個時間T內(nèi)，如果樹的節(jié)點數(shù)目一共為n，當(dāng)沒有副本時，需要O(n)的時間來計算每個節(jié)點的負(fù)載，然后就可以確定出每個節(jié)點的種類。

同樣，在這個時間T內(nèi)，由于放置副本的次數(shù)不能大于k，本文選擇critical節(jié)點一定不大于k，而且要對所有critical節(jié)點的子節(jié)點中負(fù)載最大的節(jié)點進(jìn)行排序， k個數(shù)據(jù)排序的復(fù)雜度為O(log k)，算法步驟b）的綜合復(fù)雜度為O(k log k)。

但在放置副本后，更新其祖先節(jié)點負(fù)載的費(fèi)用是比較昂貴的，最壞的情況下可能達(dá)到Ω(kn)。

4結(jié)束語

本文所述的目錄結(jié)構(gòu)模型和定位策略在教育資源網(wǎng)格中能較好地實現(xiàn)副本目錄的更新，并有效地提高了副本定位的效率。

文獻(xiàn)[6]提出了一些副本放置方法，包括最佳客戶、層疊復(fù)制、平緩存、快速擴(kuò)展等方法。本文的副本放置策略與這幾種放置方法相比，可以精確地將副本放置在可以解決負(fù)載過重問題的節(jié)點上，并且對副本的數(shù)目有嚴(yán)格的限制，可以大大減少系統(tǒng)維護(hù)副本的開銷。而且，本策略具有很強(qiáng)的動態(tài)性，能夠適應(yīng)數(shù)據(jù)請求的動態(tài)變化。

為了提高副本放置策略的性能，對于放置副本后的各節(jié)點負(fù)載的更新工作必須進(jìn)行改進(jìn)。同時，如何確定副本的數(shù)目，如何控制副本放置的過程以及副本過多后的副本置換策略的改進(jìn)，這些都是接下來需要研究的重點問題。

參考文獻(xiàn)：

[1]陳梅，都志輝.網(wǎng)格cache若干問題分析[J].計算機(jī)科學(xué)，2004，31(5):1517.

[2]DULLMANN D， HOSCHEK W， JAENMARTINEZ J，et al. Models for replica synchronisation and consistency in a data grid[C]//Proc of the 10th IEEE Symposium on High Performance and Distributed Computing (HPDC10).[S.l.]:IEEE， 2001: 7－9.

[3]LAMEHAMEDI H， SHENTU Z， SZYMANSKI B，et al. Simulation of dynamic data replication strategies in data grids[C]//Proc of the 12th Heterogeneous Computing Workshop.2003:22－26.

[4]LI Dongsheng，XIAO Nong，LU Xicheng. Dynamic selfadaptive replica location method in data grids[C]//Proc of Cluster Computing IEEE International Conference.[S.l.]:IEEE Computer Society Press， 2003: 442－445.

[5]LIU Pangfeng，WU Janjan.Optimal replica placement strategy for hierarchical data grid systems[C]//Proc of the 6th IEEE Internatio￣nal Symposium on Cluster Computing and the Grid(CCGRID’06). Wa￣shington DC:IEEE Computer Society， 2006:417－420.

[6]KAVITHA R， IAMNITCHI A， FOSTER I.Design and evaluation of replication strategies for a high performance data grids[C]//Proc of International Conference on Computing in High Energy and Nuclear Physics. 2001:106118.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”