黃守明

(銅陵學院 數(shù)學與計算機學院，安徽 銅陵 244061)

當今，許多大型科學系統(tǒng)、商業(yè)應用、圖像處理和數(shù)據(jù)挖掘等要處理TB甚至PB級的海量數(shù)據(jù)，需要超大的計算能力、網絡帶寬和存儲容量。把大量的存儲單元和計算資源(如CPU、內存和硬盤)集成起來生成一個網格，可以提供共享訪問計算和存儲資源[1-3]。數(shù)據(jù)網格是一種新型網格，提供了方便發(fā)現(xiàn)、調用和海量數(shù)據(jù)處理的服務及基礎設施，以及對這些數(shù)據(jù)集副本的創(chuàng)建和管理[4-6]。

在幾乎所有的數(shù)據(jù)復制(也稱為副本創(chuàng)建)算法中，涉及3個關鍵問題需要解決。

(1)副本選擇：在遍布整個網格的副本中挑選副本的過程。

(2)副本放置：選擇一個網格站點來放置副本的過程。

(3)副本管理：在數(shù)據(jù)網格中創(chuàng)建或刪除副本的過程。

通常，復制算法是靜態(tài)的或動態(tài)的。傳統(tǒng)的靜態(tài)復制算法的缺點是不能適應用戶行為的變化，而且不適合大量的數(shù)據(jù)和用戶。靜態(tài)復制算法也有一些優(yōu)點，如沒有動態(tài)算法的開銷，而且作業(yè)調度很快完成[7]；另一方面，動態(tài)復制策略創(chuàng)建和刪除副本是根據(jù)網格環(huán)境的變化，即用戶的文件訪問模式[8]。由于數(shù)據(jù)網格是動態(tài)環(huán)境，而且用戶的要求也是可變的，因此動態(tài)復制才更適合這些系統(tǒng)[9]。

文獻[10]提出了6種不同的副本創(chuàng)建策略：無副本、最好的客戶、級聯(lián)復制、普通緩存、緩存加級聯(lián)復制和多層數(shù)據(jù)網格的快速傳播，還介紹了3類局部性，即時間局部性、地理局部性和空間局部性。對這些策略的評價采用了不同的數(shù)據(jù)模式，文獻[11]對最新訪問最大權值(Latest Access Largest Weight,LALW)策略[12]進行了擴展。LALW算法給予最近被訪問的文件更高的權值，而且副本放置僅在集群級而不是站點級進行；文獻[13]提出了一種基于分類的復制策略(Replication Strategy based on Categorization,RSC)，通過使網絡級局部性最大化并避免網絡擁塞來減少數(shù)據(jù)訪問時間。但策略有2個不足：一是復制的文件被放在全部請求的站點而不是合適的站點；二是只有當存儲單元的容量小時，該策略才具有良好的性能。文獻[14]提出了一種動態(tài)層次復制(Dynamic Hierarchical Replication,DHR)策略，把副本存放在合適的站點，而不是許多站點，但它仍存在不足，如副本選擇和副本替換并不高效。文獻[15]提出的改進動態(tài)層次復制算法(Modified Dynamic Hierarchical Replication Algorithm,MDHRA)對DHR策略進行了改進，還提出了一種新的作業(yè)調度算法—聯(lián)合調度策略(Combined Scheduling Strategy,CSS)，采用分層調度來減少對于合適計算節(jié)點的搜索時間。文獻[16]針對多層數(shù)據(jù)網格提出了一種新的動態(tài)復制策略—預測分層快速傳播(Predictive Hierarchical Fast Spread,PHFS)，它是快速傳播動態(tài)復制方法的擴展形式。PHFS不僅在多層數(shù)據(jù)網格結構的不同層中按層次復制數(shù)據(jù)對象來得到更多的訪問位置，而且也使得存儲資源的利用最優(yōu)化。

總之，這些傳統(tǒng)的動態(tài)數(shù)據(jù)復制策略除了具備靈活性和更加適應動態(tài)變化的數(shù)據(jù)網格環(huán)境的優(yōu)點外，還存在副本選擇數(shù)量過大和副本放置站點過多等缺點，從而最終導致數(shù)據(jù)復制的作業(yè)時間延長，網絡開銷變大，嚴重時甚至導致文件的大量丟失等。

對此，本文提出了一種新的動態(tài)數(shù)據(jù)復制策略，提出的動態(tài)數(shù)據(jù)復制策略主要在副本選擇、副本放置和副本管理3方面進行了改進和提高。首先為了選擇最佳副本，采用了一個考慮影響數(shù)據(jù)傳輸時間的鏈路帶寬和影響數(shù)據(jù)傳輸性能的CPU及I/O的評分函數(shù)；其次計算出具有最小訪問時間的存儲單元(Storage Element,SE)，將副本放置在最佳的存儲單元(Best Storage Element,BSE)中；最后采用一個基于將來文件的訪問次數(shù)n(它基于指數(shù)增長/衰減模型得到)、特定副本的大小S、當前時間CT、特定副本的最后請求時間LT和數(shù)據(jù)的可用性A計算得到的CM值作為副本替換階段對BSE中的可用副本進行刪除判決。仿真結果表明，本文提出的動態(tài)數(shù)據(jù)復制策略相比于其他算法，在平均總作業(yè)執(zhí)行時間、有效網絡利用和系統(tǒng)文件丟失率方面都有明顯的改進。

1 本文提出的動態(tài)復制策略

本文提出的動態(tài)復制策略由3部分構成。

1.1 副本選擇

當不同的站點存有數(shù)據(jù)集的副本時，通過選擇最佳副本可以有效利用鏈路的帶寬并減少延遲，從而直接影響數(shù)據(jù)傳輸時間，同時，CPU和I/O對數(shù)據(jù)傳輸性能也有影響。因此，提出評分函數(shù)如下：

Score=PBW×w1+PCPU×w2+PI/O×w3

(1)

式中PBW表示從選擇的站點到請求文件駐留站點的可用帶寬百分比，PCPU為請求文件駐留站點的CPU空閑狀態(tài)的百分比，PI/O為請求文件駐留站點的可用存儲空間的百分比，wi(i=1,2,3)為權值，且：

w1+w2+w3=1

(2)

這些權值可以由數(shù)據(jù)網格機構的管理員根據(jù)數(shù)據(jù)網格節(jié)點中存儲系統(tǒng)的不同屬性來設置。因此，如果幾個站點有副本f，則選擇一個有最大Score值的站點。

1.2 副本放置

為了提高系統(tǒng)的可靠性和性能，每個文件在網格中可以有一些副本，每個副本必須保存在不同的存儲單元中。

如果所請求的文件存在于存儲單元中，則不需要復制和拷貝它；如果所請求的文件不存在于存儲單元中，則將進行復制。本文提出將副本放置在最佳的存儲單元(Best Storage Element,BSE)中。因此，為了找到BSE，算法必須計算出具有最小訪問時間Tmin的SE，即SETmin。在SETmin的Tmin計算中，必須考慮副本的請求頻率和最后請求副本的時間，這2個參數(shù)很重要，因為它們表明了再次請求副本的概率。

(3)

式中CT是當前時間，LTi是副本i的最后請求時間，F(xiàn)Ri是副本i的請求頻率，圖1所示詳細描述了尋找最佳存儲單元這一實現(xiàn)過程。

圖1 尋找BSE的過程

1.3 副本管理

如果沒有足夠的復制空間，則1個或多個文件必須作為替換階段的候選文件，采用下列計算公式確定替換：

(4)

式中n是將來文件的訪問次數(shù)，它基于指數(shù)增長/衰減，S是特定副本的大小，CT是當前時間，LT是特定副本的最后請求時間，A是數(shù)據(jù)的可用性(Availability，A)。對BSE中的可用副本基于CM值的升序進行排序作為刪除。

下面對式(4)中的2個重要參數(shù)的確定進行分析。

(1)可用性(A)：每個存儲單元都有數(shù)據(jù)可用性，它表明了一個文件存在的概率。假設存儲單元中保存的全部文件有相同的可用性，存儲單元j中的文件可用性用ASEj來表示。由于可能存在一個文件的多個副本，因此每個文件fi的可用性用Ai表示，計算如下：

(5)

式中N為文件fi的副本數(shù)量。顯然，對于訪問一個文件的每次操作來說，不可用性的概率為1-Ai，假設文件的訪問操作是各自單獨完成的。

(2)將來文件的訪問次數(shù)(n)：我們采用指數(shù)增長/衰減的概念來預測文件的下一個訪問次數(shù)。現(xiàn)實世界的許多現(xiàn)象如細菌繁殖、放射性同位素衰減和信用支付等都可以采用這個概念來建模，這種模型也適用于數(shù)據(jù)網格訪問。設n0是時刻t文件f的訪問次數(shù)，則時刻t+1該文件的訪問次數(shù)是n(t)，其指數(shù)增長/衰減模型為：

n(t)=n0×e-rt

(6)

因此，根據(jù)指數(shù)增長/衰減模型，可得到：

(7)

式中α為增長/衰減率，求解式(7)有：

(8)

全部時間間隔的平均增長/衰減率為：

(9)

于是，可以得到下一個時間間隔的訪問數(shù)為：

(10)

例如，我們可以用指數(shù)模型找到文件f的下一個訪問數(shù)。如23、20、12、10分別為文件f在4個時間間隔的訪問數(shù)，則首先要計算出文件f的平均增長/衰減率：

(11)

最后，估計出文件f的下一個訪問數(shù)：

(12)

替換僅在保存新副本的可用性值大于刪除現(xiàn)有文件的可用性值情況下進行?，F(xiàn)在，復制文件fi的可用性值可通過下式得到：

(13)

刪除候選文件的可用性值將由下式得到：

(14)

這樣，如果通過復制fi得到的可用性值大于從BSE中刪除候選文件損失的累計值，則要求在BSE中復制所請求的文件fi，即：

(15)

式中Ni是文件fi的副本數(shù)量。實現(xiàn)替換策略的偽代碼如下。

從BSE中的文件生成列表L且對于每個文件按式(4)計算CM值；

按CM值升序排序列表L；

Sum=0；

while(L不為空&&對于新副本沒有足夠的空間)

{

從列表L中選擇文件fi；

Sum=Sum+ΔAi×Ni；

}

end while

if(ΔAF×NF>Sum)

{

刪除BSE的L中的候選文件；

}

end if

if(對于BSE中F的新副本有足夠的空間)

{

存儲F的新副本；

}

end if

1.4 算法復雜度分析

從前面分析可知，本文算法實現(xiàn)主要由3個階段構成，即副本選擇、副本放置和副本管理。在副本選擇階段，如果副本數(shù)量為f，則選擇一個有最大Score值的站點的復雜度為O(f)；在副本放置階段，為了將副本放置在最佳的存儲單元，副本列表大小為L，副本i的請求頻率為FRi，則完成該階段的復雜度為O(LFRi)；在副本管理階段，復雜度主要由替換算法決定，要完成副本數(shù)量為f、列表大小為L的副本管理，其復雜度為O(nfL)-O(Nj)，其中n為訪問次數(shù)，Nj為候選文件數(shù)量；故本文算法總的實現(xiàn)復雜度為O(nfL)+O(LFRi)-O(Nj)。

2 算法仿真結果及分析

2.1 網格仿真單元及配置

我們采用OptorSim數(shù)據(jù)網格仿真器來仿真所提出的動態(tài)復制策略。OptorSim為用戶提供了數(shù)據(jù)網格體系結構和編程接口，OptorSim中包括了許多組件，如計算單元(Computing Element,CE)，存儲單元(Storage Elements,SE)、資源代理(Resource Broker,RB)，副本管理器(Replica Manager,RM)和副本優(yōu)化器(Replica Optimizer,RO)。每個站點由0或多個CEs和0或多個SEs構成，圖2所示為算法仿真所采用的OptorSim數(shù)據(jù)網格仿真器的體系結構示意圖。

圖2 OptorSim體系結構

一個作業(yè)通常會請求數(shù)據(jù)訪問的一組邏輯文件名，被請求的文件順序由訪問模式規(guī)定。仿真中考慮3種不同的訪問模式：順序式，即文件按在作業(yè)配置文件中規(guī)定的順序被訪問；單一隨機式，即文件請求與先前文件請求是一個單元，但方向是隨機的；隨機Zipf訪問式，這里Pi=K/iS，Pi是第i項排名的頻率，K是最被頻繁訪問的數(shù)據(jù)項的受歡迎程度，S決定分布的形狀；數(shù)據(jù)復制策略通常假設數(shù)據(jù)在數(shù)據(jù)網格中是只讀的；表1所示為仿真中設置的參數(shù)值。

表1 仿真參數(shù)值

3.2 仿真結果及分析

為了評價不同復制策略實施的有效性，采用以下性能指標。

(1)總作業(yè)執(zhí)行時間，包括數(shù)據(jù)傳輸和作業(yè)執(zhí)行時間，這是網格用戶評價其算法執(zhí)行的一個最重要的指標。

(2)有效網絡利用(Effective Network Usage,ENU)，用于估計網絡資源的使用效率，計算公式如下：

(16)

式中Nrfa是CE從遠程站點讀取一個文件的訪問次數(shù)，Nfa是文件復制操作的總次數(shù)，Nlfa是CE讀取一個本地文件的次數(shù)，ENU的值在0～1之間，ENU值越低，表示網絡帶寬的利用越有效。

(3)系統(tǒng)文件丟失率(System File Missing Rate,SFMR)，SFMR表示潛在的不可用文件數(shù)量與全部作業(yè)請求的文件數(shù)量之比，它用于測量數(shù)據(jù)的可用性，定義為：

(17)

式中n表示作業(yè)的總數(shù)量，mj表示每個作業(yè)的文件訪問操作數(shù)，Ai為式(5)定義的文件fi的可用性概率。越小的SFMR值表現(xiàn)出越好的系統(tǒng)數(shù)據(jù)可用性。

圖3所示為在3種不同訪問模式時采用包括本文提出的動態(tài)復制策略在內共6種動態(tài)復制策略得到的平均總作業(yè)執(zhí)行時間。

圖3 3種訪問模式時不同復制策略的平均總作業(yè)執(zhí)行時間

從圖3可以看出，RSC策略的平均總作業(yè)執(zhí)行時間最大，是因為RSC策略將副本存儲在有高帶寬的站點，并復制那些在區(qū)域內可能會很快被訪問的文件。由于在每個站點的SE的大小不足以存儲全部數(shù)據(jù)的大部分，故采用站點級替換策略對性能沒有太多的改進；LALW的平均總作業(yè)執(zhí)行時間比RSC快大約9%，因為LALW選擇一個受歡迎的文件作為復制，通過分配不同的權值給每個歷史數(shù)據(jù)訪問記錄，對每個記錄的重要性進行區(qū)分；DHR的平均總作業(yè)執(zhí)行時間相比于采用順序訪問模式的RSC算法降低了12%，是由于它選擇最佳副本位置作為執(zhí)行作業(yè)，考慮存儲中等待的請求數(shù)量和數(shù)據(jù)傳輸時間；MDHRA比RSC的平均總作業(yè)執(zhí)行時間約快25%，比采用Zipf分布的DHR快11%；在全部算法和全部文件訪問模式中，本文提出的策略有最小的平均總作業(yè)執(zhí)行時間。

由于采用隨機訪問模式，一組特定的文件更容易被網格站點請求，請求文件的大部分在之前已被復制。因此，全部復制策略在隨機文件訪問模式(包括單一隨機式和隨機Zipf訪問式)下相比于順序訪問模式的平均總作業(yè)執(zhí)行時間要小。

圖4所示為在隨機Zipf訪問模式時6種動態(tài)復制策略得到的有效網絡利用。

圖4 隨機Zipf訪問模式時不同復制策略的有效網絡利用

從圖4可見，PHFS的ENU相比于RSC約低37%，主要原因是對于PHFS，網格站點在需要時才會有他們需要的文件，因此副本總數(shù)將減少，而本地訪問總數(shù)增加；本文提出的策略是最佳的，帶寬消耗最小，從而也減少了網絡流量。

圖5所示為在3種訪問模式時得到的6種方案的SFMR。

圖5 3種訪問模式時不同復制策略的SFMR

顯然，從圖5可見，對于全部訪問模式來說，本文提出的策略的性能要優(yōu)于其他的策略，這是因為本文提出的策略僅當來自于復制文件的增益值大于復制文件的損失值時才決定創(chuàng)建副本。

結語

數(shù)據(jù)復制策略已廣泛應用于數(shù)據(jù)網格中復制被頻繁訪問的數(shù)據(jù)到合適的站點。本文提出了一種動態(tài)數(shù)據(jù)復制策略，選擇最佳副本位置作為執(zhí)行作業(yè)，還同時考慮了CPU和I/O等因素。算法還將副本存儲到最佳站點，而不是很多站點，從而使得文件大部分時間可被訪問，使得數(shù)據(jù)丟失率最小化和文件的可用性最大化，從而減少響應時間、訪問延遲和帶寬消耗，提高了系統(tǒng)的性能。