間隔執(zhí)行的異步副本放置策略*

謝紀(jì)東，武繼剛

廣東工業(yè)大學(xué) 計算機學(xué)院，廣州 510006

1 引言

數(shù)據(jù)網(wǎng)格已經(jīng)廣泛應(yīng)用在科學(xué)研究中，其目的是將許多分布遙遠(yuǎn)的存儲資源連接起來，以方便網(wǎng)格用戶分享數(shù)據(jù)[1]，這種數(shù)據(jù)一般需要消耗大量存儲以至于無法集中存儲在一個節(jié)點中[2]。

一般而言，計算密集型的應(yīng)用需要用到大量數(shù)據(jù)，尤其在科學(xué)計算型應(yīng)用[3-4]，比如高能物理[5]、天氣模擬以及衛(wèi)星圖像處理等[6-7]。而且隨著最近一段時間數(shù)據(jù)挖掘和機器學(xué)習(xí)的發(fā)展，越來越多的數(shù)據(jù)需要進(jìn)行復(fù)雜的實驗和分析。

然而，由于硬件成本的限制，在本地存儲和維護(hù)大量數(shù)據(jù)的代價有時是難以接受的，而如果將數(shù)據(jù)全部放置在遠(yuǎn)程服務(wù)器中，比如云端[8-9]，由于網(wǎng)絡(luò)帶寬的限制，取回數(shù)據(jù)的時間代價又太大，因此副本放置技術(shù)應(yīng)運而生，副本技術(shù)利用用戶對文件請求的歷史數(shù)據(jù)，利用有限的本地存儲資源只存儲用戶最需要文件的副本，而所有文件的原本存儲在云端，這樣不僅能有效利用本地存儲資源，也能充分利用云端的資源，同時方便共享數(shù)據(jù)資源。

本文通過改進(jìn)文獻(xiàn)[10]中對文件熱度的定義，利用間隔執(zhí)行機制以及異步策略來設(shè)計算法，算法由兩部分組成，一部分是全局算法，負(fù)責(zé)收集各個集群的用戶文件請求計算候選副本，另一部分為局部（本地）算法，由集群中心控制，局部算法負(fù)責(zé)放置副本到合適位置以適應(yīng)集群網(wǎng)絡(luò)環(huán)境。本文主要有3點貢獻(xiàn)：

（1）通過邊際分析方法改進(jìn)了文獻(xiàn)[10]中對文件流行度的定義從而能選擇更合適的候選副本。

（2）通過異步機制，分而治之的思想重構(gòu)文獻(xiàn)[10]中的算法。

（3）通過高斯分布、冪律分布來模擬用戶行為進(jìn)行模擬實驗，實驗結(jié)果表明本文提出的策略有效改善了網(wǎng)絡(luò)傳輸環(huán)境。

2 相關(guān)工作

副本技術(shù)的兩個主要挑戰(zhàn)：副本的選擇和副本放置。副本選擇主要負(fù)責(zé)選擇用戶最需要的副本，而一般用流行度表示用戶需要的迫切程度。副本放置主要負(fù)責(zé)將副本放置到網(wǎng)絡(luò)中最合適的節(jié)點以使用戶在請求文件時能擁有較小的網(wǎng)絡(luò)延遲和帶寬消耗[11]。

文件流行度的概念主要用來描述文件被需要的程度，大部分方法[1,10,12-19]都利用文件的請求頻率來定義文件流行度。

文獻(xiàn)[12]提出了最近請求文件最大權(quán)重算法（latest access largest weight，LALW）。該算法對不同的文件請求計算不同的權(quán)重，時間越近的請求擁有越大的權(quán)重，這樣能使用戶最近的偏好得以凸顯。文獻(xiàn)[15]提出了基于主動刪除技術(shù)的最近請求最大權(quán)算法（closest access greatest weight with proactive deletion，CAGWPD），該算法基于歷史請求記錄以及主動刪除技術(shù)，通過設(shè)置閾值來控制副本數(shù)量，選擇文件流行度大于平均流行度的文件作為副本。這種方式能更加有效地利用資源節(jié)點的存儲容量。文獻(xiàn)[18]提出了公平分享算法（fair-share replication，F(xiàn)SR），該方法通過平衡資源節(jié)點的工作量和存儲容量來更有效地放置副本到合適的節(jié)點。這幾種方法都沒有考慮到用戶的行為變化對系統(tǒng)的影響，在定義文件熱度時，其偏向于將小文件作為副本進(jìn)行放置，而忽略了大文件的傳輸能顯著影響網(wǎng)絡(luò)傳輸條件的事實。

流行文件優(yōu)先復(fù)制算法（popular file replicate first，PFRF）由文獻(xiàn)[1]提出，該算法基于星型拓?fù)渚W(wǎng)絡(luò)，在節(jié)點存儲資源有限的情況下通過歷史文件請求判斷文件熱度并進(jìn)行副本放置，其采用間隔執(zhí)行的算法運行機制充分考慮了用戶行為變化，并進(jìn)行了復(fù)雜的實驗來評測PFRF算法。但是其文件熱度定義和之前的工作一樣，偏向于選擇小文件，同樣忽略了大文件請求對網(wǎng)絡(luò)造成的影響。

改進(jìn)的流行文件優(yōu)先復(fù)制算法（improved popular file replicate first，IPFRF）由文獻(xiàn)[10]提出，該算法同樣基于間隔執(zhí)行的運行機制，所謂間隔執(zhí)行，即將時間劃分為等間隔時間段，算法會在一個時間段結(jié)束時運行。這種機制有利于動態(tài)調(diào)整副本選擇和放置。IPFRF改進(jìn)了PFRF中沒有考慮節(jié)點地理位置而進(jìn)行副本放置的缺點。IPFRF通過調(diào)節(jié)文件請求權(quán)重，對集群進(jìn)行個性化推薦，增加副本刪除機制更加有效利用了本地存儲資源，提高了副本命中率，有效減少了網(wǎng)絡(luò)平均延遲和消耗帶寬。但是由于IPFRF的算法需要等待收集所有集群的信息才能進(jìn)行計算，一旦有集群離線，系統(tǒng)會發(fā)生不可預(yù)知錯誤，缺乏健壯性，同樣由于和PFRF采用了相似的文件熱度定義，對大文件的請求不敏感。

基于以上缺點，本文提出了一種改進(jìn)流行度的基于間隔執(zhí)行機制的異步文件副本放置策略。本文從三方面對IPFRF進(jìn)行了改進(jìn)。第一，通過對文件請求產(chǎn)生的邊際延遲分析，大文件在一定條件下需要進(jìn)行優(yōu)先放置，而不是一味地用文件請求密度來進(jìn)行定義造成在選擇副本時偏好小文件的問題。第二，通過異步機制打破同步算法所帶來的低容錯缺點。第三，本文引入高斯分布來模擬用戶對文件請求的行為變化。

3 系統(tǒng)模型

3.1 拓?fù)浣Y(jié)構(gòu)

本文模型和文獻(xiàn)[10]保持一致，如圖1，整個模型由m個集群和一個主站（master site）組成，主節(jié)點通過GRC（global replica controller）和各個集群交流，主站包含所有文件，即其容量足夠大總是能存儲所有文件。主站一般是專業(yè)的存儲服務(wù)提供者，比如存儲云等。每個集群都有本地副本控制服務(wù)器LRC（local replica controller），通過集群內(nèi)部路由和集群內(nèi)各個資源節(jié)點相連，資源節(jié)點容量有限，只能存儲一部分文件。

集群內(nèi)資源節(jié)點地理分布較為接近，而集群之間地理分布較為遙遠(yuǎn)。此模型由樹形拓?fù)浜喕鴣恚墨I(xiàn)[1]已證明其合理性。每個集群內(nèi)部的LRC負(fù)責(zé)管理存儲在集群中資源節(jié)點中的副本，并提供策略在適當(dāng)?shù)臅r間和位置存儲副本，由于服務(wù)器容量有限，同時也要在適當(dāng)?shù)臅r機刪除一部分不太重要的副本，為后續(xù)更重要的副本騰出空間。

用戶通過向存儲服務(wù)器發(fā)出副本請求來獲取副本，如果本地服務(wù)器中沒有對應(yīng)副本，則需要從遠(yuǎn)程服務(wù)器中請求對應(yīng)文件。當(dāng)副本放置策略無法有效滿足用戶需求時，遠(yuǎn)程服務(wù)器需要滿足大量用戶需求，而受限于網(wǎng)絡(luò)帶寬，用戶獲取文件的延遲有可能會變得非常大，因此，可以通過在此模型上模擬多種用戶偏好變化來檢測副本放置策略的有效性。

3.2 評價指標(biāo)

評價指標(biāo)包括三部分：平均請求延遲、平均消耗帶寬、副本發(fā)現(xiàn)比率。

平均請求延遲。請求延遲反映了用戶下載文件的時長，延遲越大，用戶需要等待越久。平均請求延遲越小，證明越多的文件請求在本地得到滿足，副本放置算法越有效。

Fig.1 Simulation topology圖1 模擬系統(tǒng)拓?fù)浣Y(jié)構(gòu)

平均消耗帶寬。文件消耗帶寬根據(jù)文件大小和傳輸時經(jīng)過的中間節(jié)點數(shù)量計算，文件傳輸帶寬消耗越大，表示文件越大或者需要經(jīng)過越多的中間節(jié)點。平均文件消耗帶寬越小，副本放置算法越有效。

副本發(fā)現(xiàn)比率。驗證副本放置算法是否有效的直接指標(biāo)，就是計算副本命中率。命中率越高，表示集群內(nèi)部的副本能滿足更多的請求。但是副本發(fā)現(xiàn)率在文獻(xiàn)[10]提出的算法下對小文件有明顯的偏心。雖然副本發(fā)現(xiàn)率能在一定程度上反映算法的有效性，但是不一定能反映網(wǎng)絡(luò)傳輸環(huán)境的改善情況。比如，當(dāng)副本服務(wù)器的容量一定時，文獻(xiàn)[10]的算法更偏向于選擇體積較小的文件作為副本，因此，副本服務(wù)器能放置更多的副本，自然能擁有更大的副本命中率。但是，網(wǎng)絡(luò)的擁塞，體積較大的文件的傳輸產(chǎn)生的影響不可忽視。同時，由于大文件的邊際延遲更大，如果只是偏向于對小文件放置副本，網(wǎng)絡(luò)中每增加一次對大文件的請求，網(wǎng)絡(luò)傳輸環(huán)境惡化得更嚴(yán)重，邊際延遲將在第4章詳述。

4 流行度定義和算法

IPFRF是一個基于間隔執(zhí)行機制（round-based）的副本放置策略，它將時間分成固定長度的時間片段，在每個時間片段結(jié)束時，它會采取4個步驟來進(jìn)行副本放置。第一步，IPFRF從所有集群收集文件請求信息。第二步，IPFRF計算每個文件在對應(yīng)集群中的流行度，然后再取平均作為文件的全局流行度。第三步，將每個集群中請求的文件按照流行度降序排序，并且選擇排名靠前的一定數(shù)量的文件作為候選副本。第四步，IPFRF根據(jù)集群中資源節(jié)點的地理位置分布、容量和已有副本，將候選副本放置到最合適的資源節(jié)點中。本文從兩方面對IPFRF進(jìn)行了優(yōu)化：文件流行度定義和算法結(jié)構(gòu)。

4.1 文件流行度

文件流行度是一個評價文件是否應(yīng)該被復(fù)制到集群中資源節(jié)點的重要因素，IPFRF對文件流行度(FPi,c,n)的定義：

其中，Ri,c,n為集群c在第n個時間間隔對文件i收集的請求次數(shù)；TRn為第n個時間間隔內(nèi)對所有集群收集的文件請求總數(shù)；FSi為文件i的大??；a是一個常量，在文獻(xiàn)[10]中并沒有顯式給出，本文根據(jù)文獻(xiàn)[1]進(jìn)行取值。IPFRF中平均流行度（APi,n）的定義如下：

其中，noc表示集群數(shù)量。IPFRF的文件熱度定義考慮了文件數(shù)量、文件大小，其權(quán)重也根據(jù)不同集群不同時期的總需求量動態(tài)變化。但是仍然有不足之處。本文通過邊際分析方法，重新對文件熱度進(jìn)行了定義。定義邊際延遲（marginal delay，MD）如下：

其中，nor表示文件傳輸過程中經(jīng)過的路由數(shù)量；Bi,i+1表示從發(fā)送節(jié)點i到接收節(jié)點i+1的網(wǎng)絡(luò)帶寬；Di,i+1表示從發(fā)送節(jié)點i到接收節(jié)點i+1的距離；在真實環(huán)境下，k和m的取值是一定的。

所謂邊際延遲，即網(wǎng)絡(luò)中每增加一個文件請求所增加的傳輸和發(fā)送延遲。顯而易見的是，一個請求對兩個大小不一的文件所造成的延遲是不一樣的，文件越大，所造成的延遲越多，因此，網(wǎng)絡(luò)中每增加一個對于大文件的請求所造成的延遲，遠(yuǎn)大于網(wǎng)絡(luò)中每增加一個對小文件請求所造成的延遲。即大文件的邊際延遲大于小文件的邊際延遲，雖然網(wǎng)絡(luò)中對于大文件的請求不一定比小文件多，但是其重復(fù)傳輸所產(chǎn)生的延遲依然很大。比如：現(xiàn)有兩個文件存儲在主站中，文件大小如表1。

Table 1 Files'information表1 文件信息

用戶對文件的請求需要經(jīng)過兩次路由才能到達(dá)，假設(shè)用戶在兩個時間段內(nèi)都對兩個文件進(jìn)行了請求，網(wǎng)絡(luò)帶寬為100 Mb/s，傳播延遲相等，請求數(shù)量如表2。

Table 2 The first interval表2 第一次間隔

按照IPFRF的計算方式，文件A和文件B的流行度如表3所示（因為傳播延遲相等，所以只計算發(fā)送延遲，每個文件的初始流行度都為0.5，a=0.5）。

Table 3 Result after the first interval表3 第一次間隔后結(jié)果

如表3由于文件A的流行度遠(yuǎn)大于文件B，因此IPFRF選擇將文件A作為候選副本，但是由邊際分析可知，文件B的額外請求會造成更多延遲，雖然文件B比文件A需要更多存儲空間，但是在一定條件下，需要優(yōu)先放置文件B。按照IPFRF的方法將文件A作為副本放置后，第二個時間間隔假設(shè)用戶對文件A和文件B的請求數(shù)量和第一個時間間隔一樣，第二個時間間隔產(chǎn)生的延遲如表4。

Table 4 Delay caused by files using IPFRF in the 2nd interval表4 IPFRF第二個間隔產(chǎn)生延遲

如果第一輪不放置文件A為副本，而選擇B為副本時，第二個時間間隔產(chǎn)生延遲如表5。

Table 5 If replicate file B表5 假設(shè)為文件B創(chuàng)建副本

由此可見，IPFRF在流行度定義上仍有不足，通過邊際延遲考慮文件大小對延遲的影響，本文定義改進(jìn)的流行度如下：

其中，GFPi,n表示全局流行度；Ri,n表示第n個時間間隔文件i在所有集群中的請求次數(shù)；Rn表示所有文件在所有集群中的總請求次數(shù)；LFPi,c,n表示集群c中文件i在第n個時間間隔的本地流行度；MDi表示文件i的邊際延遲；0≤a≤1。如果采用本文流行度定義，則上文舉例中第一個間隔結(jié)束后結(jié)果如表6。

Table 6 Result by refined definition表6 按本文熱度定義結(jié)果

4.2 算法

IPFRF算法僅由主站完成副本選擇和放置任務(wù)，這種集中式的算法不利于負(fù)載均衡且容錯性較低，因此本文重新設(shè)計了算法框架，將副本選擇和放置任務(wù)交給LRC執(zhí)行，而GRC負(fù)責(zé)收集全局信息并記錄維護(hù)全局流行度表。算法中符號意義如表7。

Table 7 Symbol table表7 符號表

GRC算法（算法1）由兩部分組成，第一部分從各個集群中收集文件請求。第二部分利用歷史文件流行度表以及新的文件請求更新文件流行度表，然后排降序。

貪心算法（算法2）負(fù)責(zé)根據(jù)文件大小、文件流行度貪心選擇出候選副本。然后再將候選副本交由LRC算法，根據(jù)對應(yīng)節(jié)點剩余容量、已有副本、文件流行度來放置副本，如果節(jié)點剩余容量充足，就直接將副本傳輸?shù)綄?yīng)節(jié)點，如果節(jié)點剩余存儲容量不足，就根據(jù)文件大小和文件流行度的比較看是否值得替換已有文件副本。

LRC算法（算法3）為各個集群分別運行的算法，主要負(fù)責(zé)本集群的文件請求信息收集以及候選副本的選擇和放置。經(jīng)過式（4）計算文件流行度后排降序。

算法1收集文件請求，維護(hù)全局流行度

算法3副本選擇和放置

4.3 存取模式

文獻(xiàn)[10]使用了兩種偏好模式來模擬用戶的存取行為，第一種為均勻分布，如圖2。第二種為Zipf，均勻分布對文件基本無偏好，如圖3?？梢詸z測算法在一般條件下的性能，Zipf分布能模擬用戶帶偏好的文件請求。所謂用戶偏好，即用戶對不同文件的喜好，比如一部分用戶更偏向于使用視頻文件，另一部分用戶偏向于使用文本文件或者音頻文件，不同類型的用戶擁有不同的偏好。

Zipf分布中，不同集群的用戶擁有不同偏好，第一個集群中的用戶對文件0～20的文件更加喜好。第二個集群中對文件50～70的文件更加喜好。每個集群在每一個時間間隔都有不同的喜好。前兩種存取模式應(yīng)用在文獻(xiàn)[10]中用來測試IPFRF算法的有效性。本文引入第三種存取模式：高斯分布來模擬用戶偏好行為，如圖4。

高斯分布的曲線沒有Zipf分布陡峭，能比較好地適應(yīng)當(dāng)用戶從無偏好狀態(tài)逐漸轉(zhuǎn)移到有偏好狀態(tài)的情況。

Fig.2 Average distribution圖2 平均分布

Fig.3 Zipf distribution圖3 Zipf分布

Fig.4 Normal distribution圖4 高斯分布

均勻分布中用戶對文件無特定偏好，用戶對文件的請求次數(shù)總是在固定值上下小范圍波動。

為了確保每一個時間間隔的用戶偏好動態(tài)變化，每一次生成用戶對文件的請求時進(jìn)行一定程度的平移：

其中，F(xiàn)ID為實際生成的文件ID；GID為由不同的存取模式生成的文件ID；T為文件數(shù)量。

5 實驗

5.1 模擬實驗

模擬實驗的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為星型拓?fù)?，模擬參數(shù)如表8。

Table 8 Simulation parameters表8 模擬參數(shù)

每個集群內(nèi)部的LRC負(fù)責(zé)管理存儲在集群中資源節(jié)點中的副本，并提供策略在適當(dāng)?shù)臅r間和位置存儲副本，由于服務(wù)器容量有限，同時也要在適當(dāng)?shù)臅r機刪除一部分不太重要的副本，為后續(xù)更重要的副本騰出空間。

所有集群都和主站連接，集群之間無直接連接。為方便實驗，假設(shè)主站容量為無限大，實際上，在現(xiàn)實生活中可以認(rèn)為其為云端。本文的網(wǎng)絡(luò)拓?fù)浜臀墨I(xiàn)[10]保持一致。模擬請求次數(shù)表示用戶總共發(fā)出的文件請求次數(shù)。模擬將會分4次進(jìn)行，每一次模擬的時間間隔100次，每一次時間間隔中產(chǎn)生的文件數(shù)量可以代表時間長短，數(shù)量越多，任務(wù)時間間隔越長。4次模擬文件請求總數(shù)分別為200 000、400 000、800 000、1 600 000次，在不同壓力下來檢測算法的有效性。集群內(nèi)的資源節(jié)點和LRC連接，資源節(jié)點之間無直接連接。常量a的取值根據(jù)文獻(xiàn)[1]，由于IPFRF中沒有對a的顯示賦值，也無常量a取值的討論，因此參考PFRF算法中對a的取值。

對集群地理位置的模擬采用以下公式在模擬時生成：

其中，region為集群偏移量；offset為集群內(nèi)資源節(jié)點的偏移量；(x,y)為資源節(jié)點的位置。

5.2 模擬實驗結(jié)果及分析

實驗利用Java多線程編程實現(xiàn)。實驗分三部分進(jìn)行：第一部分模擬用戶請求行為符合均勻分布時的場景；第二部分模擬用戶請求行為符合Zipf分布時的場景；第三部分模擬用戶請求符合高斯分布時的場景，每個場景進(jìn)行8次實驗取平均為最后實驗結(jié)果。

第一場景為均勻分布場景，各個集群的用戶不會產(chǎn)生特定偏好，由于差異較小，算法容易產(chǎn)生誤判斷導(dǎo)致最后結(jié)果較差，但是從表9和表10可以看出本文提出的算法策略較IPFRF仍有一定程度的提升。由于文件請求數(shù)量差異性較小，因此由本文基于邊際分析定義的流行度能選擇邊際延遲較大的文件放置副本，而IPFRF偏向選擇小文件，雖然能放置更多副本，但是在請求數(shù)量差異較小的情況下，體積較大的文件產(chǎn)生的延遲遠(yuǎn)大于體積較小的文件產(chǎn)生的延遲。

Table 9 Average latency表9 平均文件延遲

Table 10 Average bandwidth表10 平均帶寬消耗

第二場景為Zipf分布，從其分布圖中可以看出，各個集群的用戶帶有非常強烈的不同偏好，這種帶有非常強烈偏好的用戶一般為老用戶。在此情境下，只需要預(yù)測命中少量的副本即可大幅度降低文件延遲，在資源節(jié)點容量有限的情況下，IPFRF達(dá)到了很好的性能，但是同樣在副本命中率相似的情況下，優(yōu)先大文件的放置相比優(yōu)先小文件的放置能減少更多的延遲。

第三場景為高斯分布。這種情境適合新用戶到老用戶的過渡階段，帶有偏好但是對其他不同類型文件懷有好奇心，因此偏好差異沒有Zipf劇烈。在這種情況下不僅考驗算法的副本命中率，而且需要平衡文件大小和存儲容量對資源節(jié)點的影響。

6 結(jié)束語

本文通過邊際分析方法，改進(jìn)了IPFRF利用請求密度(即文件請求數(shù)除以文件體積)來定義文件流行度的方法，IPFRF的定義偏向于選擇體積較小的文件，而實際情況大文件在同等情況下會產(chǎn)生更大的延遲。本文根據(jù)邊際延遲分析重新定義了文件流行度。同時，根據(jù)IPFRF的算法框架過于中心化的缺點，將副本放置算法分成兩部分分別在GRC和LRC處執(zhí)行，分散了主站的壓力并將副本選擇和放置任務(wù)交給集群自己處理，更能適應(yīng)集群偏好變化，而主站對全局流行度的把握能更好地預(yù)防經(jīng)驗錯誤，提高副本選擇的準(zhǔn)確性。最后本文通過傳統(tǒng)的兩種存取模型模擬用戶行為變化之外，引入了第三種分布模型：高斯分布，更能反映新老用戶交替的文件請求的行為變化。但是本文提出的算法仍有不足之處，比如算法所適用拓?fù)淠Ｐ捅容^局限，算法框架仍然屬于中心式，但是集群和主站的異步交互方式讓算法擁有良好的可擴展性。算法實驗環(huán)境也需要在真實的用戶網(wǎng)絡(luò)中進(jìn)行檢測和驗證。隨著CDN和P2P的發(fā)展，如何在更加復(fù)雜的網(wǎng)絡(luò)上部署副本放置技術(shù)也成為本文未來的研究方向。