黃守明

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

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

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

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

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

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

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

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

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

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

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

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

1.1 副本選擇

當(dāng)不同的站點存有數(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)為權(quán)值，且：

w1+w2+w3=1

(2)

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

1.2 副本放置

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

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

(3)

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

圖1 尋找BSE的過程

1.3 副本管理

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

(4)

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

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

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

(5)

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

(2)將來文件的訪問次數(shù)(n)：我們采用指數(shù)增長/衰減的概念來預(yù)測文件的下一個訪問次數(shù)。現(xiàn)實世界的許多現(xiàn)象如細菌繁殖、放射性同位素衰減和信用支付等都可以采用這個概念來建模，這種模型也適用于數(shù)據(jù)網(wǎng)格訪問。設(shè)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)有文件的可用性值情況下進行。現(xiàn)在，復(fù)制文件fi的可用性值可通過下式得到：

(13)

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

(14)

這樣，如果通過復(fù)制fi得到的可用性值大于從BSE中刪除候選文件損失的累計值，則要求在BSE中復(fù)制所請求的文件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 算法復(fù)雜度分析

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

2 算法仿真結(jié)果及分析

2.1 網(wǎng)格仿真單元及配置

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

圖2 OptorSim體系結(jié)構(gòu)

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

表1 仿真參數(shù)值

3.2 仿真結(jié)果及分析

為了評價不同復(fù)制策略實施的有效性，采用以下性能指標(biāo)。

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

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

(16)

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

(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)復(fù)制策略在內(nèi)共6種動態(tài)復(fù)制策略得到的平均總作業(yè)執(zhí)行時間。

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

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

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

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

圖4 隨機Zipf訪問模式時不同復(fù)制策略的有效網(wǎng)絡(luò)利用

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

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

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

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

結(jié)語

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