教育資源網格中的一種動態數據復制技術

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

關鍵詞：教育資源共享； 復制； 副本一致性； 副本放置

中圖分類號：TP393文獻標志碼：A

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

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

數據網格是網格技術的重要分支。在數據網格中，數據是最重要的資源。但是，由于資源在廣域上分布、本質上異構，并且由不同的個人或組織擁有，要進行大規模的數據移動、跨域的數據共享就變得非常困難。

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

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

1動態復制技術

副本的管理和分配方式可以分為靜態和動態兩種。靜態復制是指在系統設計時就將副本放置在一些節點上，當系統開始工作后，即使系統環境有了顯著變化，或是用戶行為有了變化，這些節點上仍然存放著副本。整個系統的副本處于一個靜態不變的狀態，不能適應系統的動態變化。

動態復制則不同，它是在系統工作中根據具體用戶行為的變化和系統的動態變化來放置和管理副本。用戶作業要調用某個數據文件時，有可能直接在已有的副本中選擇一個或多個副本進行傳輸，當個別節點負載過重時也有可能在合適的位置創建新的副本。這樣，系統中的副本管理具有高度的動態性，可以適應用戶請求的變化或系統中副本存儲節點的變化。

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

2副本目錄

2．1目錄模型的設計

借鑒文獻[3]中所提出的樹和環相結合的混合拓撲結構，建立一個如圖1所示的目錄模型。由于中心目錄能夠大大簡化副本的一致性問題，模型中依然保留了中心目錄節點。同時，采用中心目錄和中間目錄結合的雙層目錄結構可以在很大程度上減輕中心目錄節點的負擔，有利于系統的穩定性。

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

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

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

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

2．2副本的查詢定位

網格用戶對應的中間目錄節點是副本查詢定位的起始點。當底層網格用戶節點請求要得到某一個數據時，首先要向其對應的地區節點發出查詢請求。當一個地區節點收到網格用戶對數據元LDN的查詢請求后，會首先查詢本地是否有該LDN的副本，具體過程如下：

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

b)如果本地沒有該數據元的副本或副本數目不能滿足用戶請求，則查找中央目錄節點。在中央目錄節點上可以方便地查詢到哪個地區有該數據元的相關副本；然后再到那些地區查詢副本具體的PRN信息，并通過同層目錄節點之間的環形連接來傳遞這些信息，這樣可以有效地提高信息傳輸的效率；最后網格用戶通過PRN信息定位到目標副本。

2．3副本的一致性維護

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

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

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

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

在目錄模型中，采用了樹和環相結合的混合拓撲結構。采用樹的結構是目錄模型中多層目錄策略的前提；在整個查詢定位的過程中，同一層節點上采用的環形連接可以提高目錄信息的傳輸效率，并且同層之間的信息傳遞也減輕了中央節點的負擔。

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

3一種動態的副本放置策略

3．1副本放置問題

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

文獻[5]提出了一種副本放置策略，但這種策略并沒有討論如何在一個用戶請求動態變化的環境里進行副本的動態管理，以盡可能保證上述復制技術的優勢得到體現。

本文的動態副本放置算法不僅完成了對副本放置位置的優化選擇，而且考慮了對副本數目的控制。另外，算法具有高度的動態性，從網格用戶作業調用某個數據的角度，用戶請求有可能直接在已有的副本中選擇一個或多個副本進行傳輸，當相關副本節點負載過重時也有可能在合適的位置創建新的副本。

3．2數學模型

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

圖1目錄模型圖2數據網格樹

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

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

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

副本節點集R的負載為R中每個節點的負載以及中心節點a的負載的和。

3．3動態副本放置算法

3．3．1算法目標

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

3．3．2算法描述

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

a)設t0為起始時刻，此時運行系統，計算整個系統每個節點的負載。

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

c)IfI

{

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

在中心節點a到副本放置節點的路徑上，把所有節點的負載都減去副本放置節點的負載（注意，經過這一步，可能會使副本放置節點的一個或多個祖先節點由heavy節點變為light節點)，并將副本數目I加上1；

更新副本目錄信息；

執行步驟d)；

}

IfI≥k

{

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

按深度優先的順序，把R中所有的節點按負載由小到大的順序排列，負載相同的節點按照創建時間由早到晚排列，然后將它們依次加入置換隊列L；

選取置換隊列L中最早進入隊列的節點，刪除放在其上的副本節點，并將副本數目I減小1；

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

重新執行步驟c)；

}

d)重復執行c)，要保證副本放置或置換的次數小于等于k次，直至隊列P中沒有節點，這時系統中也就沒有了heavy節點。

e)放置好副本后，各網格用戶節點訪問數據副本，具體的步驟如下：

先在本地查找數據副本；

若找不到，查找其父節點；

如果本地節點到中心節點a的路徑上都找不到副本，中心節點響應請求。

f)時間間隔T后，重新計算系統中各個節點的負載。

重復執行b)~f)，直至系統停止。

3．4算法舉例

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

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

3．5算法復雜度分析

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

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

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

4結束語

本文所述的目錄結構模型和定位策略在教育資源網格中能較好地實現副本目錄的更新，并有效地提高了副本定位的效率。

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

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

參考文獻：

[1]陳梅，都志輝.網格cache若干問題分析[J].計算機科學，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.

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