間隔執行的異步副本放置策略*

謝紀東，武繼剛

廣東工業大學 計算機學院，廣州 510006

1 引言

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

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

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

本文通過改進文獻[10]中對文件熱度的定義，利用間隔執行機制以及異步策略來設計算法，算法由兩部分組成，一部分是全局算法，負責收集各個集群的用戶文件請求計算候選副本，另一部分為局部（本地）算法，由集群中心控制，局部算法負責放置副本到合適位置以適應集群網絡環境。本文主要有3點貢獻：

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

（2）通過異步機制，分而治之的思想重構文獻[10]中的算法。

（3）通過高斯分布、冪律分布來模擬用戶行為進行模擬實驗，實驗結果表明本文提出的策略有效改善了網絡傳輸環境。

2 相關工作

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

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

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

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

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

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

3 系統模型

3.1 拓撲結構

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

集群內資源節點地理分布較為接近，而集群之間地理分布較為遙遠。此模型由樹形拓撲簡化而來，文獻[1]已證明其合理性。每個集群內部的LRC負責管理存儲在集群中資源節點中的副本，并提供策略在適當的時間和位置存儲副本，由于服務器容量有限，同時也要在適當的時機刪除一部分不太重要的副本，為后續更重要的副本騰出空間。

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

3.2 評價指標

評價指標包括三部分：平均請求延遲、平均消耗帶寬、副本發現比率。

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

Fig.1 Simulation topology圖1 模擬系統拓撲結構

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

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

4 流行度定義和算法

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

4.1 文件流行度

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

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

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

其中，nor表示文件傳輸過程中經過的路由數量；Bi,i+1表示從發送節點i到接收節點i+1的網絡帶寬；Di,i+1表示從發送節點i到接收節點i+1的距離；在真實環境下，k和m的取值是一定的。

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

Table 1 Files'information表1 文件信息

用戶對文件的請求需要經過兩次路由才能到達，假設用戶在兩個時間段內都對兩個文件進行了請求，網絡帶寬為100 Mb/s，傳播延遲相等，請求數量如表2。

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

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

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

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

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

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

Table 5 If replicate file B表5 假設為文件B創建副本

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

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

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

4.2 算法

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

Table 7 Symbol table表7 符號表

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

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

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

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

算法3副本選擇和放置

4.3 存取模式

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

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

高斯分布的曲線沒有Zipf分布陡峭，能比較好地適應當用戶從無偏好狀態逐漸轉移到有偏好狀態的情況。

Fig.2 Average distribution圖2 平均分布

Fig.3 Zipf distribution圖3 Zipf分布

Fig.4 Normal distribution圖4 高斯分布

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

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

其中，FID為實際生成的文件ID；GID為由不同的存取模式生成的文件ID；T為文件數量。

5 實驗

5.1 模擬實驗

模擬實驗的網絡拓撲結構為星型拓撲，模擬參數如表8。

Table 8 Simulation parameters表8 模擬參數

每個集群內部的LRC負責管理存儲在集群中資源節點中的副本，并提供策略在適當的時間和位置存儲副本，由于服務器容量有限，同時也要在適當的時機刪除一部分不太重要的副本，為后續更重要的副本騰出空間。

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

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

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

5.2 模擬實驗結果及分析

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

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

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

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

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

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

6 結束語

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