內容分塊數據中心光網絡災前數據轉移

揭水平,李泳成

(1.蘇州大學 電子信息學院,江蘇 蘇州 215006; 2.中天寬帶技術有限公司,江蘇 南通 226000)

0 引 言

數據中心光網絡中每個數據中心都存儲了用戶大量的重要數據,一旦受到自然或人為災難(例如地震、臺風和戰爭等)影響,將造成重要數據的永久丟失。為避免這種情況發生,數據中心光網絡通常采用高效的內容備份策略,如內容復制(Content Replication,CR)[1]和內容分塊(Content Fragmentation,CF)[2]。高效的內容備份策略能確保單個數據中心發生故障后數據中心光網絡中存儲的數據被恢復[3]。然而,發生大范圍災難時,多個數據中心同時毀壞,內容備份無法保證所有內容都被恢復,必須轉移災難區域內存儲的部分數據[4]。由于數據中心中存儲了海量數據,其需要轉移的數據量為TB級甚至PB級。因此,如何對多個數據中心的大量數據在短時間內進行快速數據轉移是一個具有挑戰性的問題。Ferdousi等人雖然針對CR數據中心光網絡提出了一種數據轉移算法[5],但目前并沒有針對更為復雜的CF數據中心光網絡數據快速轉移問題的相關研究。

本文對CF數據中心光網絡災前數據轉移問題展開研究,首次針對該問題進行了問題描述,構建了混合整數線性規劃(Mixed Integer Linear Programming,MILP)模型且為大規模網絡也提出了一種高效的最小時延(Least Delay,LD)快速數據轉移算法(簡稱LD算法)。仿真結果表明,LD算法性能與MILP模型接近,證明了其高效性。其次,本文也首次從災前數據轉移性能的角度評估了CF與CR策略的性能差異。仿真結果表明,相同數據冗余度情況下(都為100%),采用LD算法的CF數據中心光網絡比CR數據中心光網絡最多節省42%的數據轉移時間。

1 CF數據中心光網絡災前數據轉移問題

CR策略是復制出x個備份,然后將所有的x+1份相同內容存儲在不同的數據中心。該策略的優點是只有當所有x+1份內容都被災難損毀時內容才會丟失；缺點是數據冗余度非常高(≥100%),嚴重降低了存儲資源的利用率。為降低數據冗余度,一種擁有更高存儲資源利用率的CF策略被提出。該策略使用(k,r)擦除編碼,首先將一個大小為F GB的內容平均拆分為k個內容塊,每個內容塊的大小為F/k GB；然后,再額外添加r(r＜k)個大小為F/k GB的奇偶校驗塊,最終形成k+r個數據塊。CF策略允許在k+r個數據塊中≤r個數據塊丟失的情況下,整個內容仍可被恢復,因此其數據冗余度為r/k＜100%。本文中的CF策略采用了具有較小編碼開銷的Reed-Solomon(RS)擦除編碼[6]。大范圍災難發生前,一旦某個內容中有ψ(ψ＞r)個數據塊在災難區域中,為保證內容不丟失,則需將ψ-r個數據塊從受災區域轉移到安全的數據中心中存儲。

1.1 CF數據中心光網絡災前數據轉移實例

圖1所示為一個CF數據中心光網絡災前數據轉移實例。假設該CF策略采用RS(5,2)編碼將內容分成了5個內容塊和2個奇偶校驗塊共7個數據塊(即k=5,r=2),并將其存儲在各個節點(N2、N3、N4和N5)的數據中心中。具體的,節點N2、N3和N5都存儲了2個數據塊,節點N4存儲了1個數據塊。假設M區域即將發生大范圍災難,節點N2和N3將被損毀。這兩個數據中心存儲的ψ=4個數據塊即將丟失。因此,最少需要轉移ψ-r=2個數據塊。現有兩種數據轉移方案S1和S2。方案S1將數據塊4沿路徑N2-N1-N5轉移至數據中心N5,轉移時間為3 s；將數據塊6沿路徑N2-N1-N4轉移至數據中心N4。由于共享鏈路N2-N1,數據塊6需要等到數據塊4轉移完成后再進行轉移。因此,方案S1所需的轉移時間為6 s。方案S2則將數據塊4沿路徑N2-N1-N5轉移至N5,數據塊7沿路徑N3-N4轉移至數據中心N4,總轉移時間為4 s。方案S2比S1節省了33%的轉移時間。

圖1 CF數據中心光網絡災前數據轉移實例

1.2 問題描述

給定一個數據中心光網絡G(N,L,D,C)。其中,N為節點的集合；L為鏈路的集合；D為數據中心的集合；C為存儲內容的集合；αc為內容c的重要性權重。假設一個大范圍災難即將影響區域M,Din為M內數據中心集合,Do為M外數據中心集合。CF數據中心光網絡災前數據轉移問題的目標是在恢復所有內容的前提下,最小化數據轉移時間。

本文考慮多個約束條件,包括:(1)通過轉移,所有內容都被恢復；(2)每一個數據塊有且只有一條轉移路徑；(3)重要性權重高的內容先完成轉移；(4)數據中心光網絡中每條鏈路上帶寬資源有限；(5)任意兩個數據塊轉移路徑重疊時,其轉移時間不重疊；(6)每個數據中心存儲資源有限；(7)節點之間采用鏈路不相交的k-shortest算法搜索k條最短路由。

2 MILP模型

基于上節的問題描述,我們構建了一個MILP模型,其集合、參數、變量和優化目標定義如下。

集合:

G(N,L,D,C) 網絡拓撲。

Pd,sd、s兩節點間k條最短路徑的集合,d,s∈D:d≠s。

DinM內數據中心集合。

DoM外數據中心集合。

Gc內容c在M內存儲的數據塊集合。

Pd節點d到安全數據中心路徑集合∪s∈DoPd,s。

參數:

αc整數,內容c的重要性權重值。

Bp整數,路徑p的可用傳輸容量。

N 內容c數據塊總數。

r 內容c需轉移數據塊總數。c

Sd/Gb yte 數據中心d可用存儲資源。

Δ 一個極大值。

變量:

T 整個網絡數據轉移時間。

優化目標:最小化T。

約束條件:

內容c轉移數據塊總數達到恢復要求。

內容c第k個數據塊沿路徑p轉移的傳輸時間。

內容c第k個數據塊沿路徑p轉移的結束時間。

計算內容c轉移的開始時間,該時間不大于內容c任意一個數據塊轉移的開始時間。

計算內容c轉移的結束時間,該時間不小于內容c任意一個數據塊轉移的結束時間。

內容c數據塊轉移路徑共享鏈路時,確保這些數據塊轉移時間不重疊。

重要性高的內容優先轉移。

重要性相同的內容,內容數據塊使用相同鏈路轉移時,確保內容轉移時間不重疊。

數據中心存儲的數據不能超過其存儲資源限制。

計算整個網絡的數據轉移時間。

整個網絡的數據轉移時間大于所有內容的傳輸時間之和(冗余公式加快模型求解速度)。

3 LD算法

雖然MILP模型能找到問題的最優解,但受限于其高計算復雜度,無法為大規模網絡在有限時間內獲得最優解。目前,并沒有專門針對CF數據中心光網絡數據轉移的算法。由于既要選擇轉移的數據塊,又要選擇轉移路徑,整個問題變得更加復雜。本文為CF數據中心光網絡提出一種LD算法,該算法主要分為兩部分,轉移內容的選擇和轉移數據塊及轉移路徑的選擇。

3.1 轉移內容的選擇

遍歷各個數據中心存儲的所有內容,一旦某個內容在災難區域內存儲的內容塊總數超過r,則將其加入到轉移內容集合CEva。遍歷完所有內容后,將集合CEva中的內容按照其重要性權重值αc由大到小排列。

3.2 轉移數據塊與轉移路徑的選擇

針對獲取的集合CEva,該啟發式算法將進一步為每個內容選擇轉移的數據塊及每個轉移數據塊的轉移路徑。具體步驟如下:

End for

對于內容c,遍歷其在災難區域內存儲的數據塊集合Gc,對其中每一個數據塊分別計算所有可能轉移路徑的轉移時間,并計算LD(即每個數據塊結束轉移的時間)。比較每一個數據塊的LD,選擇具有最小LD的數據塊k*進行轉移。從Gc中移除已轉移的數據塊k*,若轉移的數據不足以恢復內容c,則重復以上步驟,否則選擇下一個內容進行轉移。當所有內容完成轉移時,獲取整個網絡數據轉移時間T。

圖2 測試網絡拓撲圖

4 結果與性能分析

4.1 測試條件

為評估所提算法的性能,我們考慮了如圖2所示的兩個測試網絡,圖2(a)為具有6個節點、8條鏈路和6個數據中心的n6s8網絡,圖2(b)為具有24個節點、43條鏈路和8個數據中心的USNET網絡。假設一個大范圍災難將分別影響n6s8網絡中的節點1和2以及USNET網絡中的節點6、9和12。每個數據中心可用存儲資源在10～100 TB范圍內均勻分布,且平均占用率為40%(剩余60%可用于存儲轉移內容塊)。網絡中每個鏈路上的傳輸容量在500 Gbit/s～1 Tbit/s范圍內,其中30%用于傳輸數據中心間正常的業務(剩余70%可以用于數據轉移)。假設數據中心存儲的每個內容的大小在200～500 GB范圍內均勻分布。這里的單個內容都是由許多較小的內容聚合而成。每個內容的重要性因子從1～10分成10個等級,因子越大,重要性越高。在MILP模型中,我們采用了K條最短路徑搜索算法為每個節點對找到了3條最短路徑作為候選路徑。通過商用軟件AMPL/Gurobi[7](版本5.6.2)求解MILP模型,模型的MIPGAP(Relative MIP Optimality Gap)設置為1%。啟發式算法使用JAVA進行仿真。

4.2 整個網絡數據轉移時間

圖3比較了MILP模型與LD算法的整個網絡數據轉移時間。其中,數據中心光網絡采用基于RS(4,2)編碼的CF策略進行內容備份。

圖3 整個網絡數據轉移時間

由圖可知,在兩個測試網例的結果中,MILP模型所需的整個網絡數據轉移時間較短,LD算法的結果與MILP模型結果總是非常接近。其次,隨著整個網絡存儲內容總數的增加,MILP模型和LD算法所需的整個網絡數據轉移時間越來越大。這是因為整個網絡存儲內容總數的增加將導致需要進行數據轉移的內容增加,從而增加了整個網絡數據轉移的時間。最后,在USNET網絡中,MILP模型和LD算法所需的整個網絡數據轉移時間都少于n6s8網絡。這是因為USNET網絡的平均節點維度高于n6s8網絡,能為轉移的數據提供更多的可選路徑。

4.3 CF vs CR

本文也比較了CF和CR策略在轉移內容數據總量和數據轉移時間方面的性能差異。圖4給出了在USNET網絡中,兩種策略需要轉移的內容數據總量。圖中每個點為基于6個隨機種子仿真結果的平均值。CF分別采用了RS(2,2)、RS(3,2)和RS(4,2)3種編碼方式,數據冗余度分別為100%、67%和50%。CR為每個內容都復制了一個備份(即x=1),數據冗余度為100%。

由圖可知,隨著整個網絡存儲內容總數的增加,兩種策略需要轉移的內容數據總量也不斷增加。這也是由于整個網絡存儲內容總數的增加將導致需要進行數據轉移的內容增加。我們發現,當k值增大時(即數據冗余度降低),其需轉移的內容數據總量也將變大。這是因為更低的數據冗余度使得內容無法恢復的概率更大,需要進行數據轉移的內容變得更多。在相同數據冗余度下(都為100%),CF所需轉移的數據與CR相比最多節省了34%。

圖5所示為兩種內容備份策略的整個網絡數據轉移時間。CF采用了LD算法,CR采用了文獻[5]中的算法。由圖可知,當數據冗余度都為100%時,CF數據中心光網絡比CR數據中心光網絡最多節省42%的數據轉移時間；當數據冗余度為67%時,CF數據中心光網絡依然可以比100%數據冗余度的CR數據中心光網絡更快完成數據轉移；當數據冗余度為50%時,CF數據中心光網絡與CR數據中心光網絡相比,無法總是獲得更低的數據轉移時間,這與其需要轉移的數據總量過大有關。

圖4 CF和CR策略中需要轉移的內容數據總量

圖5 CF和CR策略中整個網絡數據轉移時間

5 結束語

本文針對CF數據中心光網絡災前數據轉移問題展開了研究。以最小化整個網絡數據轉移時間為目標,構建了一個MILP模型并提出了一種LD算法。仿真結果表明,LD算法與MILP模型的最優解非常接近。同時,我們也比較了CF和CR策略在災前數據轉移方面的性能。結果表明,數據冗余度都為100%時,采用LD算法的CF數據中心光網絡比CR數據中心光網絡最多節省42%的數據轉移時間。