數(shù)據(jù)網(wǎng)格中一種高性能動(dòng)態(tài)數(shù)據(jù)復(fù)制策略

黃守明

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

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

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

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

(2)副本放置：選擇一個(gè)網(wǎng)格站點(diǎn)來(lái)放置副本的過(guò)程。

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

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

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

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

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

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

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

1.1 副本選擇

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

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

(1)

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

w1+w2+w3=1

(2)

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

1.2 副本放置

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

如果所請(qǐng)求的文件存在于存儲(chǔ)單元中，則不需要復(fù)制和拷貝它；如果所請(qǐng)求的文件不存在于存儲(chǔ)單元中，則將進(jìn)行復(fù)制。本文提出將副本放置在最佳的存儲(chǔ)單元(Best Storage Element,BSE)中。因此，為了找到BSE，算法必須計(jì)算出具有最小訪問時(shí)間Tmin的SE，即SETmin。在SETmin的Tmin計(jì)算中，必須考慮副本的請(qǐng)求頻率和最后請(qǐng)求副本的時(shí)間，這2個(gè)參數(shù)很重要，因?yàn)樗鼈儽砻髁嗽俅握?qǐng)求副本的概率。

(3)

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

圖1 尋找BSE的過(guò)程

1.3 副本管理

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

(4)

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

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

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

(5)

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

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

n(t)=n0×e-rt

(6)

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

(7)

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

(8)

全部時(shí)間間隔的平均增長(zhǎng)/衰減率為：

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

這樣，如果通過(guò)復(fù)制fi得到的可用性值大于從BSE中刪除候選文件損失的累計(jì)值，則要求在BSE中復(fù)制所請(qǐng)求的文件fi，即：

(15)

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

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

按CM值升序排序列表L；

Sum=0；

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

{

從列表L中選擇文件fi；

Sum=Sum+ΔAi×Ni；

}

end while

if(ΔAF×NF>Sum)

{

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

}

end if

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

{

存儲(chǔ)F的新副本；

}

end if

1.4 算法復(fù)雜度分析

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

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

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

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

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

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

表1 仿真參數(shù)值

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

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

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

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

(16)

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

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

(17)

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

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

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

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

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

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

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

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

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

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

顯然，從圖5可見，對(duì)于全部訪問模式來(lái)說(shuō)，本文提出的策略的性能要優(yōu)于其他的策略，這是因?yàn)楸疚奶岢龅牟呗詢H當(dāng)來(lái)自于復(fù)制文件的增益值大于復(fù)制文件的損失值時(shí)才決定創(chuàng)建副本。

結(jié)語(yǔ)

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