副本放置中的更新策略及算法*

李 帥，黨 鑫，王 旭，武繼剛

1.天津工業大學 計算機科學與軟件學院，天津 300387

2.廣東工業大學 計算機科學與技術學院，廣州 510006

副本放置中的更新策略及算法*

李 帥1，黨 鑫1，王 旭1，武繼剛2+

1.天津工業大學 計算機科學與軟件學院，天津 300387

2.廣東工業大學 計算機科學與技術學院，廣州 510006

LI Shuai,DANG Xin,WANG Xu,et al.Replica update strategy and algorithms for replica placement.Journal of Frontiers of Computer Science and Technology,2016,10(11):1633-1640.

副本技術廣泛應用于云計算及分布式系統中，合理的數據副本放置是降低網絡運行成本的重要手段，也是副本技術的核心問題。副本更新是針對網絡中數據訪問請求的動態變化而進行的副本添加與刪除。針對副本放置問題，提出了一種基于多訪問策略的副本動態更新算法MPFSF（min_placement far servers first）。該算法在引入通信距離限制的同時，盡可能多地重用網絡中已存在的副本，并根據需要實施必要的副本更新，最大使用每個副本的處理能力，以便降低數據訪問的時延，提高數據訪問效率。最后通過實驗結果和分析證明，該算法在不同的通信距離限制下，網絡的運行成本得到了明顯的降低，對原有算法的改進最高可達84.6%。

樹形網絡；副本放置；多訪問策略；更新

1 引言

在樹形網絡中，副本放置問題是指在網絡中如何合理地放置副本以及如何使放置的副本數量最少。通過將副本分布在網絡中，可以進行負載均衡，提高數據的可用性、可靠性，降低訪問時延，節省網絡帶寬等。副本放置問題廣泛應用于視頻點播、互聯網服務、內容分發系統等重要領域[1-7]。

為了解決網絡中的副本放置問題，許多副本放置算法被提出[8-15]。文獻[8]證明了在一般網絡中的副本放置問題是NP完全的。文獻[9]提出了一種副本放置節點選擇的分布式算法，并將該問題轉化為背包問題，在考慮對副本的訪問頻率的基礎上，提出了一種近似算法。文獻[10]將一般網絡中的副本放置問題轉換成經典的裝箱問題，并給出了多項式時間的近似算法。文獻[11]提出了一種廣域分布式存儲系統中的通用數據副本放置策略，實現最小化系統數據通信時延。文獻[12]面向線性總線網絡的需要，提出了兩種數據副本優化放置策略，可以最大化數據有效性和最小化數據訪問的代價。文獻[13]面向提高云系統可用性的需要，通過建立數學模型，描述了系統有效性和副本數量關系，給出了副本計量方法和副本機制算法。文獻[14]在Hadoop架構內，根據節點間距離與負載計算每個節點的調度評價值，選擇最佳節點放置數據副本。為了降低數據訪問延遲，提高網絡的服務質量（quality of service，QoS），文獻[15]在選擇節點放置副本時，考慮了副本和客戶間的通信距離，證明了新問題在距離約束下是NP難的，并給出了在二叉樹上解決該問題的一個多項式時間最優算法。文獻[16]提出了一種改進的近似算法，在多項式時間內解決副本位置選擇問題，提高了網絡容錯性能。文獻[17-18]對已存在的一些副本放置和選擇策略進行了較為全面的介紹和分析。

在樹形網絡中，葉節點作為客戶周期性地發送若干數據訪問請求，該請求從含有相應副本的祖先節點獲得服務。樹形網絡中廣泛使用最近策略分配副本，即任一客戶的所有數據訪問請求只能由一個副本提供服務，且該副本是在客戶節點到根節點的唯一路徑上，距離客戶節點最近的副本節點。然而最近策略的限制過高，導致副本使用率過低。為了提高副本使用率，即以盡可能少的副本數量滿足所有客戶請求，文獻[19]提出了兩個高效的策略：（1）單一策略，任一客戶的所有請求由一個副本提供服務，該副本可以是客戶節點到根節點的唯一路徑上的任一副本。與最近策略相比，單一策略提高了副本的使用率，但若為客戶提供服務的副本放置偏遠，可能會造成服務時間過長。（2）多訪問策略，任一客戶的所有數據訪問請求可由該客戶的祖先節點中的一個或多個副本共同提供服務。與最近策略和單一策略相比，多訪問策略更加靈活且副本使用率最高。同時，文獻[20]已證明異構網絡中基于多訪問策略的副本放置問題是NP難解的。

初始時，大多相關文獻假設樹形網絡中不存在任何副本，然而客戶發送的數據訪問請求是單位時間動態變化，因此這種假設并不完全符合實際要求。為了有效降低網絡運行成本，需要平衡重用舊副本和添加新副本之間的關系。其中，重用舊副本的成本通常小于添加新副本的成本。對于樹形動態網絡中的副本更新問題，目前僅有文獻[21]考慮了基于最近策略的副本更新問題，并提出了一種動態規劃求最優解的方法。

本文的主要貢獻：區別于最近策略，提出了基于多訪問策略的啟發式更新算法，即最小放置更新算法。本文算法是以最大重用網絡中已存在的副本，降低網絡放置的副本數量為目標，從而實現降低網絡運行及更新成本的目的。本文算法不僅能夠最大使用網絡中每個副本的處理能力，而且不會過多增加網絡運行及副本更新成本。同時，在所研究的副本更新問題中，為了降低訪問時延，提高訪問效率，額外考慮了通信距離的限制，即所有客戶的數據訪問請求需要在一定通信距離內獲得服務，從而保證整個網絡服務質量。

2 問題描述

在給定的樹形網絡中，將其節點分成兩部分，客戶集合C和內部節點集合N。任一葉節點代表一個客戶，且客戶i∈C在每個單位時間內發送ri個數據訪問請求。內部節點 j∈N是可以放置副本的節點，且放有副本的節點稱為服務器，并可為該節點子樹中的客戶提供服務。

設R是網絡中放置副本的集合，ris表示服務器s為客戶i提供服務的請求數。根據多訪問策略可知，任一客戶i的數據訪問請求ri都能夠被一個或多個服務器Servers(i)∈R提供服務：

為了滿足客戶的請求，需要通過不斷地在網絡中放置副本來實現這一目標，而每個副本的處理能力是相異的。設服務器s的處理能力為Ws，則該服務器能夠提供的數據訪問請求不得超過其最大處理能力：

為了有效降低訪問時延，提高訪問效率，本文在增加通信距離受限的條件下研究副本更新問題，即客戶的請求必須在有限的通信距離內獲得服務。因此該問題可定義為：對任一客戶i，為其提供服務的服務器s與其距離d(i,s)不得超過給定的邊界值qi：

若某客戶的數據請求被其自身處理，即該客戶節點上放有副本，將該節點分割成一個葉節點和一個內部節點。因此，副本只能是放置在樹形網絡中的內部節點上，且該節點與放有副本節點之間的通信距離為0。

設E表示網絡中已存在的服務器集合，即含有副本的內部節點集合，集合E中的每一個副本在客戶請求發生變化后或被重用，或被刪除。N-E表示由不含有副本的內部節點構成的集合，在更新過程中，可在集合N-E中選擇節點添加新副本。由于重用已存在的副本代價小于放置副本的代價，刪除副本的代價小于重用副本的代價，根據上述描述，添加副本s的代價為其自身的處理能力Ws，重用副本s的代價為αWs(0<α<1)，刪除副本s的代價為βWs（0<β<α<1）。則整個網絡的運行及更新成本為：

本文的目標是找出一個新的服務器集合R，在保證每個客戶的數據訪問請求能夠獲得服務，且不超過其允許的最大通信距離前提下，使得cost_upd (R)最小，這可形式化如下：

3 副本更新的策略及算法

基于多訪問策略的副本放置問題，文獻[4]提出一種啟發式算法——最近優先放置算法（multiple small QoS close servers first，MSQoSC）。其中qi表示客戶i的最大獲得服務的通信距離，d(i,r)表示客戶i到根節點r的距離。

3.1 最近優先放置算法

所有客戶i∈C按其qi升序排序，若同一父節點的客戶節點具有相同的距離約束，則根據客戶請求大小降序，從而得到表list，依次對表list中的每個客戶節點執行以下操作。

（1）在距離qi內查詢客戶的祖先節點上是否存在已放副本。若不存在，在距離該客戶節點最近的祖先節點上放置副本；否則，轉（2）。

（2）判斷已放副本的處理能力是否能夠滿足客戶的數據訪問請求。若滿足，該副本的處理能力減去當前客戶請求數，剩余處理能力可以繼續處理其他客戶請求；若不滿足，轉（3）。

（3）選擇距離該客戶最近祖先空節點添加副本，滿足當前客戶剩余請求。

該算法的時間復雜度為O(n2)，n為樹形結構大小。該算法并不適用于具有較小請求數的客戶，可能會造成副本資源的極大浪費。隨著客戶請求每單位時間內發生變化，最近優先放置算法需要每單位時間內重復部署副本，這需要花費極高的代價。因此，需要重用網絡中已存在的副本，從而降低整個網絡的運行成本。由于重用已存在副本的代價小于添加新副本的代價，在重新部署副本的過程中，從降低整個網絡運行成本角度出發，應優先使用已存在副本。

3.2 最小放置更新算法

對所有客戶i∈C按其到根節點r的距離d(i,r)的升序進行排序，構成列表list_d，依次對表中的各個節點進行操作。若按d(i,r)降序順序處理客戶請求，在處理距離根節點較遠的客戶時，可能會在距離根節點較近的客戶節點的祖先節點上放置副本，從而導致距離根節點較近的客戶節點沒有足夠多的節點放置副本為其提供服務。

排序后，依次對表list_d中的每個客戶節點，在其允許的通信距離內，選擇節點放置副本為其提供服務。由于處理節點前其祖先節點可能已存在若干副本，為了充分使用每個副本，減少副本放置個數，首先判斷已存在副本是否還有剩余能力繼續為該節點服務。選擇策略如下：

（1）判斷該節點的祖先節點中是否存在副本（集合E中的副本），若有則進行副本更新，依次從距離該客戶節點最遠的節點開始，重用已存在的副本，并最大使用每一個副本的處理能力，直至客戶請求均獲得服務或不存在符合條件的節點。

（2）若該節點的祖先節點不含任何副本或所有已放副本的剩余處理能力均為0或不滿足當前客戶需求，依次在距離該客戶最遠的節點添加副本，直至所有請求獲得服務或不存在能夠繼續放置副本的節點。

（3）對于集合E中的副本，若在副本更新過程中沒有使用，則刪除對應節點中的副本。

算法的偽代碼描述如下。

3.3 時間復雜度

對于含有n個節點的樹形結構，使用最小放置更新算法時，首先對所有的客戶節點進行排序，最壞情況下時間復雜度為O(n lb n)。對任一客戶選擇節點重用或添加時，至多花費O(n)，那么整個網絡中的副本放置至多花費O(n2)。因此，算法在最壞情況下的時間復雜度為O(n2)。

4 實驗

任一客戶節點i的數據訪問請求量ri為r≤ri≤2r且r= |N|/|C|×50×λ。

當考慮距離限制的副本放置問題時，根據通信距離范圍可分成3類；（1）通信距離限制嚴緊，即q∈{1,2}。（2）通信距離限制為樹高的一半，即q=h/2。（3）無通信距離限制，即q=h+1。其中，h為樹的高度。

在含有n個節點的樹形結構中隨機放置|E|=N/4個副本。在樹形網絡中，重用舊副本的成本通常小于添加新副本的成本，而刪除未重用的舊副本成本通常小于重用舊副本的成本，即0<β<α<1。因此，為了研究網絡中重用和刪除副本的代價對算法性能的影響，β/α取值為0.1，0.2，…，0.9。隨機生成20個不同的且含有n=200個節點的樹形結構。在同一樹形結構中，本文提出的最小放置更新算法MPFSF和文獻[4]中啟發式算法MSQoSC，按照式（5）計算參數變化對整個網絡的運行及更新成本的影響，如圖1所示。

圖1中，網絡運行及更新成本是指網絡中的副本運行和更新成本。在3種不同距離約束下，隨著β/α值的變化，本文算法MPFSF始終保持著整體較低的網絡運行及更新成本，而算法MSQoSC則需要花費極高的代價重新部署副本。當通信距離限制嚴緊時，即q∈{1,2}，算法MPFSF和MSQoSC都需要放置較多的副本來滿足所有客戶的需求。然而本文算法在重新部署副本時，最大重用網絡中已存在的副本，減少了副本添加的數量，從而降低了整個網絡的運行及更新成本。當q=h/2和q=h+1時，通信距離限制寬松，本文算法通過重用網絡中已存在的副本，最大程度上降低整個網絡運行成本，而算法MSQoSC為滿足所有的客戶動態變化請求，需要花費極高的代價去重新部署網絡中的副本。

隨機生成若干含有n個節點的樹形結構，10≤n≤300（n=|N|+|C|）。每個節點最多有5個孩子節點，任一服務器j的處理能力為50≤Wj≤150。網絡中最重要的參數是負載，即所有客戶的數據訪問請求總和與所有服務器的處理能力之比，用λ表示，則

Fig.1 Effect of β/αfor algorithms in different distance constraints圖1 β/α取值在不同距離限制下對算法的影響

為了進一步分析網絡規模對網絡中重用副本數的影響，取α=0.1,β=0.08。當網絡中的節點數n=10, 50,100,150,200時，對同一樹形結構，計算每個算法對副本的平均重用數目，如圖2所示。

在不同的通信距離限制下，由本文算法MPFSF得到的整個網絡運行及更新成本低于算法MSQoSC。由圖2可知，本文算法MPFSF與MSQoSC相比，在最大使用網絡中已存在副本的同時，降低了網絡中新添加的副本數。

當q∈{1,2}時，通信距離限制嚴緊，本文算法MPFSF最大且優先重用網絡中已有的副本，而算法MSQoSC逐步放置副本且可能在客戶自身上放有副本，從而隨著網絡規模的變大，使得MPFSF算法和MSQoSC算法的重用副本數差別較大。

當q=h/2和q=h+1時，通信距離放寬，隨著網絡規模的變大，本文算法MPFSF和算法MSQoSC對已存在副本的重用數逐漸增加，而本文算法MPFSF優先重用網絡中已有的副本。因而，MPFSF算法和MSQoSC算法的重用副本數差別較小。

Fig.2 Number of replicas reused in different distance constraints圖2 在不同距離限制中的重用副本數

為了更直觀地比較算法的性能，根據式（5）計算整個網絡的運行及更新成本，如圖3所示。

Fig.3 Effect of the size of a tree in different distance constraints圖3 不同距離限制下網絡規模對算法的影響

在圖3中，對于不同網絡規模的樹形結構，本文算法MPFSF在不同的通信距離限制下，與算法MSQoSC相比，始終保持較低的網絡運行及更新成本。

當q∈{1,2}時，通信距離限制嚴緊，需要放置較多的副本來滿足客戶的需求，從而隨著網絡規模的變大，網絡運行成本逐漸增加。在此過程中，本文算法MPFSF優先重用網絡中已存在副本且最大使用每一個副本，與算法MSQoSC相比，網絡運行及更新成本平均降低了20.3%。

當q=h/2時，通信距離限制放寬，隨著網絡規模的變大，本文算法MPFSF對已存在副本的重用數逐漸增加，與嚴緊的通信距離限制相比，網絡運行成本逐漸降低。算法MSQoSC隨著網絡規模的變大，重新部署副本所需花費的成本不斷提高。與算法MSQoSC相比，網絡運行及更新成本平均降低了79.8%。

當q=h+1時，即無通信距離限制，客戶的請求可以被網絡中任意放有副本的節點處理。隨著網絡規模的變大，本文算法MPFSF在最大重用已存在的副本同時，最大使用網絡中每一個副本，而算法MSQoSC則需要不斷地重新部署網絡中的副本。與算法MSQoSC相比，網絡運行及更新成本平均降低了84.6%。

5 結束語

樹形網絡廣泛存在于計算機網絡的各個領域，數據的共享訪問是其亟待解決的一個重要問題。在實際網絡中，客戶發送的數據訪問請求是動態變化的，為了確保網絡的服務質量，降低數據訪問延遲，副本更新策略的提出刻不容緩。本文提出了基于多訪問策略解決樹形網絡中的副本更新問題的啟發式算法，與算法MSQoSC相比，不僅最大使用網絡中的每一個副本，同時大大降低網絡運行及更新成本。

除了降低訪問數據時延，減少副本更新代價，為了提高服務質量，網絡中的副本放置還要考慮其他問題，如通信代價最小，網絡的容錯性等，這將是未來工作的主要方向。同時，也將考慮其他網絡模型上副本放置和更新問題。

[1]Han Guodong,Zhu Yige.Replica placement for time-shifted IPTV system[J].Application of Electronic Technique,2012, 38(7):116-119.

[2]Lin Yifang,Liu Pangfeng,Wu Janjan.Optimal placement of replicas in data grid environments with locality assurance [C]//Proceedings of the 12th IEEE International Conference on Parallel and Distributed Systems,Minneapolis, USA,Jul 12-15,2006.Piscataway,USA:IEEE,2006:465-474.

[3]Corporation H P.Efficient dynamic replication algorithm using agent for data grid[J].The Scientific World Journal,2014, 14(3):713-730.

[4]Benoit A,Rehn-Sonigo V,Robert Y.Replica placement and access policies in tree networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(12):1614-1627.

[5]Chen Y,Katz R H,Kubiatowicz J D.Dynamic replica placement for scalable content delivery[M]//Peer-to-Peer Systems.Berlin,Heidelberg:Springer,2002:306-318.

[6]Wauters T,Coppens J,De Turck F,et al.Replica placement in ring based content delivery networks[J].Computer Communications,2006,29(16):3313-3326.

[7]Fu Xiong,Wang Yibo,Zhu Xinxin,et al.QoS-aware replica placement in data grids[J].Systems Engineering and Electronics,2014,36(4):784-788.

[8]Tang Xueyan,Xu Jianliang.QoS-aware replica placement for content distribution[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(10):921-932.

[9]Zaman S,Grosu D.A distributed algorithm for the replica placement problem[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(9):1455-1468.

[10]Beaumont O,Bonichon N,Larchevêque H.Modeling and practical evaluation of a service location problem in large scale networks[C]//Proceedings of the 2011 IEEE International Conference on Parallel Processing,Taipei,China, Sep 13-16,2011.Piscataway,USA:IEEE,2011:482-491.

[11]Chandy J A.A generalized replica placement strategy to optimize latency in a wide area distributed storage system[C]// Proceedings of the 2008 International Workshop on Data-Aware Distributed Computing,Boston,USA,Jun 23-27, 2008.New York,USA:ACM,2008:49-54.

[12]Hsu F,Hu X D,Huang H J,et al.Optimal data replica placements in linear bus networks[C]//Proceedings of the 7th IEEE International Symposium on Parallel Architectures,Algorithms,and Networks,Hong Kong,China,May 10-12,2004.Piscataway,USA:IEEE,2004:129-134.

[13]Sun Dawei,Chang Guiran,Gao Shang,et al.Modeling a dynamic data replication strategy to increase system availability in cloud computing environments[J].Journal of Computer Science and Technology,2012,27(2):256-272.

[14]Lin Weiwei.An improved data placement strategy for ha-doop[J].Journal of South China University of Technology: Natural Science Edition,2012,40(1):65-71.

[15]Benoit A,Larchevêque H,Renaud-Goud P.Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks[C]//Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium,Shanghai,May 21-25,2012.Piscataway,USA:IEEE,2012:1022-1033.

[16]Chudak F A,Williamson D P.Improved approximation algorithms for capacitated facility location problems[J].Mathematical Programming,2005,102:207-222.

[17]Kingsy G R,Manimegalai R.Dynamic replica placement and selection strategies in data grids—a comprehensive survey[J].Journal of Parallel and Distributed Computing,2014, 74(2):2099-2108.

[18]Benoit A.Comparison of access policies for replica placement in tree networks[C]//LNCS 5704:Proceedings of the 15th International Conference on Parallel Processing,Delft, The Netherlands,Aug 25-28,2009.Berlin,Heidelberg: Springer,2009:253-264.

[19]Benoit A,Rehn V,Robert Y.Strategies for replica placement in tree networks[C]//Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium, Long Beach,USA,Mar 26-30,2007.Piscataway,USA:IEEE, 2007:1-15.

[20]Aupy G,Benoit A,Matthieu J,et al.Power-aware replica placement in tree networks with multiple servers per client[J]. Sustainable Computing:Informatics and Systems,2015,5: 41-53.

[21]Benoit A,Renaud-Goud P,Robert Y.Power-aware replica placement and update strategies in tree networks[C]//Proceedings of the 2011 IEEE International Parallel and Distributed Processing Symposium,Anchorage,USA,May 16-20,2011.Piscataway,USA:IEEE,2011:2-13.

LI Shuai was born in 1989.He is an M.S.candidate at Tianjin Polytechnic University.His research interest is data center.

李帥（1989—），男，江蘇贛榆人，天津工業大學碩士研究生，主要研究領域為數據中心。

DANG Xin was born in 1983.He received the Ph.D.degree in intelligence science from Shizuoka University in 2013.Now he is a lecturer at Tianjin Polytechnic University.His research interests include embedded system,high performance architecture and machine learning.

黨鑫（1983—），男，陜西合陽人，2013年于日本國立靜岡大學信息科學系獲得博士學位，現為天津工業大學講師，主要研究領域為嵌入式系統，高性能體系結構，機器學習。

WANG Xu was born in 1989.She received the M.S.degree in computer technology from Tianjin Polytechnic University in 2015.Her research interests include high performance computing and data center.

王旭（1989—），女，山東城武人，2015年于天津工業大學計算機技術專業獲得碩士學位，主要研究領域為高性能計算，數據中心。

WU Jigang was born in 1963.He received the Ph.D.degree from University of Science and Technology of China in 2000.Now he is a chair professor at Guangdong University of Technology.His research interests include theoretical computer science and high performance architecture.

武繼剛（1963—），男，江蘇沛縣人，2000年于中國科學技術大學獲得博士學位，現為廣東工業大學計算機科學與技術學院特聘教授，主要研究領域為理論計算機科學，高性能體系結構。在國際重要學術期刊與會議上發表學術論文200余篇，主持國家自然科學基金課題、教育部博士點科研基金課題。

Replica Update Strategy andAlgorithms for Replica Placement?

LI Shuai1,DANG Xin1,WANG Xu1,WU Jigang2+
1.School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China
2.School of Computer Science and Technology,Guangdong University of Technology,Guangdong 510006,China
+Corresponding author:E-mail:asjgwucn@outlook.com

Replica technology is widely applied in cloud computing and distributed systems,the reasonable data replica placement is an important means to reduce the operation cost of network,and is also the key issue of replica technology. Replica update is that the replicas are added and deleted when data access requirements dynamically change.Based on multiple policy,this paper proposes a dynamic updating algorithm named MPFSF(min_placement far servers first)to solve the update problem.According to the need to implement the necessary replica update,this paper reuses as much as possible the pre-existing replicas and maximizes the capacity of each replica to reduce the date access latency and improve the efficiency of data access,by adding the constraint of communication distance.The experimental results show that,for the proposed algorithm with update policy,the running cost of the network gets a considerable reduction under the different distance limits,and the best improvement is up to 84.6%in comparison to the state-of-the-art.

tree network;replica placement;multiple policy;update

10.3778/j.issn.1673-9418.1507048

A

TP302

*The National Natural Science Foundation of China under Grant No.61403276(國家自然科學基金);the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20131201110002(高等學校博士學科點專項科研基金).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版:2015-10-09,http://www.cnki.net/kcms/detail/11.5602.TP.20151009.1542.004.html