基于ｈｙｂｒｉｄ拓撲的數據網格副本創建策略

摘要：數據復制技術被廣泛應用于數據網格中，以縮短數據訪問時間和傳輸時間、降低網絡帶寬消耗。針對包含樹型拓撲和環型拓撲的混合式網格拓撲結構，提出了一種考慮網絡帶寬、網絡傳輸延遲、用戶請求頻率和站點可用存儲空間大小等因素的副本創建策略，并引入評估函數衡量各因素的影響大小，具有良好的可靠性、可擴展性和自適應性。模擬實驗的結果顯示此副本創建策略可以有效降低數據平均訪問時間。

關鍵詞：數據網格； 副本創建； 混合的； 拓撲

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

文章編號：1001-3695(2007)11-0286-03

數據復制技術被廣泛應用于分布式數據庫、移動數據庫和Internet等分布式環境中。在數據網格中，通過數據復制在多個站點為同一文件創建多個一致的副本，將數據移動到距離客戶更近的地方，可以顯著縮短數據訪問時間、傳輸時間，降低網絡帶寬消耗。多個副本站點分擔了初始副本站點的工作負載，有效地提高了系統整體性能，同時多個副本的存在也增強了系統的容錯性，避免了單點失效。

數據復制技術的一個關鍵問題是如何制訂有效的副本創建策略使系統平均響應時間最短、帶寬消耗最少，即選擇在什么時機、什么地方創建哪個文件的副本。副本創建策略考慮的因素主要包括網格系統的拓撲結構、系統運行負載、存儲終端效率、網絡狀況和數據副本大小等物理特性因素以及用戶訪問模式[1]。以往的副本創建策略多數依據在層次網格拓撲結構中用戶請求文件的頻率，本文提出了一種在混合式網絡拓撲結構中考慮數據傳輸時間、用戶請求頻率和站點存儲空間大小等因素的副本創建策略，具有良好的可靠性、可擴展性和自適應性。

1相關工作

數據復制策略包括靜態復制策略和動態復制策略。靜態復制策略是在系統運行之前就已經確定將在哪些站點上創建數據副本，這種方法無法適應網絡狀態和用戶訪問模式的變化，因而在數據網格環境下很少采用；動態復制策略則可以隨著網絡狀況和用戶行為的變化自動選擇創建和刪除文件副本，現有的研究都是圍繞動態復制策略進行的。

Ranganathan和Foster在文獻[2]中提出了六種應用于層次網絡結構中的復制策略：a)不進行復制和緩存，數據全部存儲在層次結構的根節點上；b)最佳客戶端策略，在請求文件次數最多的客戶站點上創建副本；c)瀑布策略，在從根站點到請求文件次數最多的客戶站點的路徑上依次創建副本；d)緩存策略，各個站點保存所請求文件的副本；e)瀑布策略結合緩存策略；f)快速傳播策略，在從根站點到最佳客戶站點的路徑上的每一個節點都創建副本。實驗顯示瀑布策略和快速傳播策略在用戶訪問模式具有一定時間相關性或地理相關性時能大大節省平均響應時間。這六種策略都只考慮了用戶請求文件的頻率而忽視了當前網絡帶寬的影響。文獻[3]提出了一種基于經濟模型的復制策略，按照反向拍賣協議確定副本創建位置及進行副本選擇，它將數據傳輸時間作為拍賣的價格指標；文獻[4]提出了兩種基于層次結構的副本創建算法SBU和ABU，其思想都是將文件復制到距離最佳客戶端經過網絡跳數最小的站點上，ABU算法更能準確計算出用戶請求文件的頻率，但這兩種算法也沒有考慮網絡帶寬的影響。

2Hybrid網格拓撲結構

數據網格中存儲的文件大小通常是GB級甚至是TB、PB級，這對網格系統的可靠性和可擴展性提出了更高的要求。為了增強系統的可擴展性，文獻[5]在層次式拓撲結構的基礎上提出了一種層次型和平面型拓撲相結合的混合式網格邏輯拓撲結構，在此拓撲結構中管理數據副本。平面型拓撲用環型結構表示，層次型拓撲用樹型結構表示，并且兩者可相互重疊在一起。其網格拓撲結構如圖1所示?？紤]到真實的廣域網連接，應允許一個子節點擁有多組父級節點，用圖1中的虛箭頭線連接表示。

環型結構最適合于存在多個副本服務器和P2P應用的情形，而樹型結構適合于C/S模式通信的情形。在環型結構中，多個高速連接站點可以采用P2P方式高效地傳輸數據；在樹型結構中，下級站點和父級站點采用C/S模式進行通信，有效利用了位置相關性和網絡帶寬，并且當有一個父級站點不可用時，子站點還可以與環型結構中的其他父級站點通信，避免了單點失效造成的影響。

該混合式的拓撲結構增強了網格系統中的數據可用性，并且對層次型結構進行了很好的擴展，同時它能夠自動適應因副本的創建和刪除而引起的拓撲結構的變化。每當在站點上創建一個數據副本時，系統會在本地副本目錄上增加一條物理名稱到邏輯名稱的映射記錄，副本目錄信息的改變將傳播給兄弟節點和父節點，最終傳播至根節點。刪除副本也會進行相同的同步更新。新的副本站點加入hybrid拓撲結構中有兩種選擇，即成為原副本站點的子節點或兄弟節點。一般來說，地理位置相距較近、擁有高帶寬連接的副本站點應組織在同一個環型結構或樹型結構中，而傳輸延遲較大的站點則不應該直接連接在一起。

3副本創建算法

針對hybrid網格拓撲結構，副本創建算法有最小化傳輸時間算法(minimize transfer time，MTT)與增強的最小化傳輸時間算法(advanced MTT，AMTT)。MTT算法以網絡帶寬和傳輸延遲作為衡量文件傳輸時間的標準?？紤]到用戶訪問模式具有一定的時間相關性，AMTT算法將用戶請求文件的頻率也作為衡量標準之一，并且考慮到站點可用存儲空間大小對創建副本的影響。

假定某個網格包括九個站點，分別用S1，S2，…，S9表示，如圖2所示。相鄰站點間的文件傳輸代價用傳輸時間表示，即圖2中每條邊上的數字。

所有數據文件副本最初放置在根節點S1上，每個站點將從距離最近的包含文件副本的站點獲取所需要的文件。使用Dijkstra算法生成各站點間的最短路徑，得到如圖3所示的網絡路由表。

3．1最小化傳輸時間算法

MTT計算出在某個站點創建文件副本后其他站點獲取此文件所需時間的總和，得到最小的傳輸時間總和的站點即是要創建文件副本的站點。假設在站點S2創建文件副本F，則對應的傳輸時間總和ST計算如下：

4模擬實驗

本文使用網格模擬器在模擬環境中比較AMTT算法和Cascading算法[2]的性能。假定網格中共有九個站點，網格拓撲結構如圖2所示。設S1是一級站點，其他站點是普通站點，模擬環境的參數如表1所示。共有1 000個任務分配給所有普通站點執行，用戶訪問模式服從均勻分布。

設定AMTT算法的式(1)中兩個參數的取值分別為λ1=1、λ2=0。隨著普通站點之間的帶寬發生變化，所有站點執行完1 000個讀取文件任務所花費的總時間如圖4所示。結果顯示，AMTT算法比Cascading算法節省約50%的執行時間，且當網絡帶寬降低時，前者任務執行時間變化幅度比后者小得多。

設定AMTT算法的式(1)中兩個參數的取值分別為λ1=1，λ2=40，網絡帶寬為1 000 Mbps。隨著普通站點存儲空間的大小發生變化，所有站點執行完1 000個讀取文件任務所花費的總時間如圖5所示?？梢钥闯觯军c存儲空間越大，所花費的執行時間越小，并AMTT算法比Cascading算法所花費的執行時間要少得多，并且當存儲空間大小變化時，前者的任務執行時間變化的幅度也比后者小得多。

可以看出，AMTT算法較Cascading算法具有很好的自適應性，并能大幅度減少文件傳輸時間。

5結束語

本文描述了一種結合樹型拓撲和環型拓撲的混合式網格拓撲結構。這種混合拓撲結構充分利用了樹型結構和環形結構的優點，具有良好的可擴展性、可靠性和自適應性。在此混合拓撲結構的基礎上詳細描述了一種考慮到數據傳輸時間、用戶請求頻率和站點存儲空間大小等因素的副本創建策略，并引入評估函數衡量各個因素的影響大小，通過算法分析和模擬實驗可知，AMTT算法能有效地適應網絡環境的變化、減少大量的文件傳輸時間。今后將對算法和評估函數作進一步改進，尋找更佳的副本創建策略，并對混合網格拓撲結構中的副本定位技術進行深入研究。

參考文獻：

[1]孫海燕，王曉東，肖儂，等.數據網格中的數據復制技術研究[J].計算機科學，2005，32(7):13－16.

[2]RANGANATHAN K， FOSTER I. Design and evaluation of dynamic replication strategies for a high－performance data grid[C]//Proc of International Conference on Computing in High Energy and Nuclear Physics.Beijing:[s.n.]，2001.

[3]BELL W H， CAMERON D G， CARVAJAL－SCHIAFFINO R， et al. Evaluation of an economy－based file replication strategy for a data grid[C]//Proc of the 3rd Int Symposium on Cluster Computing and the Grid.Tokyo:IEEE Computer Society，2003:698-714.

[4]TANG Ming， LEE B S，YEO C K， et al. Dynamic replication algorithms for the multi－tier data grid[J]. Future Generation Computer Systems， 2005(4):775-790.

[5]LAMEHAMEDI H， SHENTU Z， SZYMANSKI B， et al. Simulation of dynamic data replication strategies in data grids[C]//Proc of International Parallel and Distributed Processing Symposium.Nice，France:[s.n.]，2003:22-26.

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