大數據存儲系統中負載均衡的數據遷移算法

李甜甜　王智　宋杰

摘要：認為在大數據時代，數據遷移已成為以數據為中心的挖掘分析操作的基礎環節。通過對大數據存儲系統中的數據遷移進行需求分析，首先提出了數據遷移模型，并分析了影響遷移性能的因素；然后基于上述模型，從作業層面提出一種負載均衡的數據遷移算法。該算法能夠規避數據訪問熱點，提高數據遷移效率。

關鍵詞：大數據；數據遷移；負載均衡

Abstract：In the big data era， data migration has become the basis for data centric mining analysis. In this paper， we analyze the requirements of data migration in big data storage systems and propose the corresponding migration model. We then analyze the factors affecting the migration performance. Then， using our proposed model， we design a load balanced migration algorithm from the aspect of job level， which can efficiently improve migration performance through avoiding data retrieving hotspots.

Key words：big data； data migration； load balance

隨著云計算、物聯網等的發展，各行業產生的數據爆炸性增長，人類已經進入大數據時代?；ヂ摼W數據中心（IDC）曾在2012年的報告中指出：全球數據量每兩年翻一番，至2020年將增至40 ZB[1]。大數據時代，能否從海量數據中快速獲取知識來指導業務發展很大程度上決定了企業的競爭力，如何將企業各業務沉淀的數據進行全面匯總并快速返回分析結果是大數據分析亟待解決的問題。

海量數據分析往往依賴于分布式環境，然而由于業務數據類型各異，數據遷移匯總將是首要任務。能否高效、穩定地將源數據遷移到目標存儲系統很大程度上決定了數據的分析效率，因此一個高效的數據遷移方法亟待發現?，F有遷移技術按照應用對象不同大致可分為兩類：面向虛擬機和面向存儲。面向虛擬機[2-4]主要解決整個虛擬系統在不同物理環境之間的遷移問題，是整個邏輯系統或計算容器的遷移，它更多關注于實時（服務不間斷）和無縫（遷移之后切換對用戶透明）兩個特性，與文中關注的分布式存儲系統間的數據遷移不同。面向存儲主要解決數據在存儲系統之間或同一存儲系統的不同實例之間的遷移問題，系統之間的遷移重點考慮數據的存儲格式、傳輸路徑、網絡狀況等因素[5-8]，實例之間的遷移重點考慮存儲系統的存儲形式、接口性能等一系列因素（如數據庫[9-10] 、VxVM[11]、獨立冗余磁盤陣列[12-13]（RAID）、云數據庫[14-17]）。

文中我們研究分布式系統間的數據遷移方法，屬于面向存儲的數據遷移，主要關注數據的遷移性能。雖然也有類似文獻同樣關注于遷移性能，但大部分文獻僅考慮了集群單方面的均衡，而忽略了集群間遷移作業的負載均衡性。文中我們首先結合現有需求給出數據遷移的抽象模型并分析影響遷移性能的因素；其次，基于上述模型從作業層面提出一種負載均衡的數據遷移算法；最后，通過大量實驗模擬分析了該算法的均衡效果。

1 數據遷移模型

我們將數據源構成的集合記作DS={D1， D2，…， DM}，其中M代表數據源的個數，|Di|為數據源的規模；將遷移作業構成的集合記作JS={J1， J2，…， JN}，其中N代表遷移作業的個數；將每個遷移作業需要訪問的數據源構成的集合記作DSj={D1j， D2j，…， DMjj}，其中Mj代表Jj需要訪問的數據源個數，DSj?DS，遷移作業的規模|Jj|=∑|Dij|；將Jj從Di拉取數據的遷移任務記作P（Di， Jj），所用時間記為Tij。

遷移策略好壞最直觀的衡量方式是性能，而時間是性能的最好表征，我們首先給出遷移性能的評估函數，見式（1）。其中，CJS是包含所有串行執行的作業集合中執行最慢的那些遷移作業，CDSj是Jj中包含最后結束的P（Di， Jj）的、串行運行的數據集集合，Tj表示Jj的運行時間。

從性能評估函數中可以看出：影響遷移性能的因素有CJS、CDSj和Tij，而并發度和負載均衡又是影響這三者的因素。遷移并發度越高，|CJS|和|CDS|越小，同時遷移的數據量就越多，Tij越短；數據遷移的負載越均衡，任務相互等待的時間越短，從而降低遷移作業的運行時間。

2 負載均衡策略

基于前面給出的數據遷移模型以及對性能影響因素的分析，我們設計了如圖1所示的數據遷移系統，包括數據源層、作業調度層以及遷移目標層。

數據源層將不同類型的數據源水平擴展成分布式數據源；作業調度層使用MapReduce框架作為分布式程序的基礎，使用YARM精確控制數據遷移使用的資源；遷移目標層使用分布式文件存儲系統將目標集群虛擬為一個整體存儲系統。

從上述架構中可以看出，提高遷移效率可從兩方面著手：在數據源層和遷移目標層內部進行數據移動以充分利用閑置資源，從數據角度避免訪問熱點；在作業調度層設計實現負載均衡的遷移策略，從作業角度避免對同一塊數據的熱點訪問。對于前者，一種稱作間接遷移[18]的技術可用來實現集群內部的負載均衡，這種技術已被證明在閑置資源較多的環境中能夠有效提高性能。此外，數據源層和遷移目標層的優化還可通過Sharding技術[19-20]直接保證數據的均衡分布，為高效率的數據遷移提供保證。因此，文章中我們著重研究第2種方法，通過合理調度作業盡可能錯開訪問同一數據源任務的執行時間。

2.1 問題定義

基于第1節給出的遷移模型，本節對遷移任務層的負載均衡問題進行形式化描述。

對給定的JS和DS，矩陣A=[aij]M×N描述Di和Jj的對應關系，矩陣B=[bjk]N×C描述Jj和Pk的對應關系，計算方法見式（2）和（3）；定義Pk的熱度hk為Pk中作業運行時需要訪問的所有Di中的熱度最大值，Di的熱度hik計算見式（4）。負載均衡的目標為尋找JS上的一個劃分P_JS={Pk}并且使其滿足以下約束條件：[?k∈{1，2，…，C}， Jj∈Pk|Jj|≤Ω]，且[1Chk]最小，其中Ω為目標集群的容量。

然而通過進一步分析我們發現：保證P_JS的熱度總和最小并不能等價保證執行時間最短。這是因為熱點訪問會帶來明顯的性能下降。執行時間T與訪問并發數b之間具有以下關聯特征：T隨b的增大而增大；T增長的速度隨b的增大而增大。那么，必然存在一個臨界點b0，使得當b>b0時并發執行的總時間大于串行執行b次的總時間，也即T>b×T0，其中T0為b=1時的執行時間。根據本文研究對象的特點，數據源的吞吐量是被嚴格限制的，又由于遷移作業的容器分配了足夠的資源，因此b0≤1，這一結論在實際業務環境中得到了驗證。

因此，P_JS還需滿足以下條件：Pk包含的任意一個Jj涉及的Di的熱度為1。由此可得hk=1且P_JS的熱度總和[1Chk]=C。此外，鑒于遷移任務是高度并行的，且數據源又通過已有技術保證是均衡分布的，設單個遷移作業的執行時間為T0，則遷移作業的執行總時間T=C×T0，其中C=|P_JS|。至此，優化目標最終等價轉換為尋找JS的一個包含元素個數最小的劃分P_JS，該劃分滿足以下約束條件：

P_JS的最優解獲取問題（記為Q0）可以歸約到一個經典的NP完全（NPC）問題（均分問題），也即該問題至少是一個NP-hard問題，無法在可接受的時間范圍內求解，因此文章提出Astraea近似求解算法。

2.2 近似求解

Q0的最優解需要滿足式（5）中的3個條件，近似求解算法Astraea則滿足了前2個條件，放寬了條件③的約束。為了量化解的近似性，文章基于數據源的訪問熱度與運行時間之間的關聯關系給出一個近似評價函數Approxi（P_JS），見式（6）。

其中，hik為Pk中作業涉及到的Di的訪問熱度，hk為Pk的熱度。這里，之所以選擇（e-1）作為時間隨熱度的增速是因為它比線性增長快（與事實相符）又不至于過快而影響到解的準確性。

通過對問題Q0的解空間進行分析，發現該問題并不適合采用絕大多數傳統的啟發式優化算法求解，因此我們提出了Astraea近似求解算法，它運用了貪婪算法的思想，利用每一步Set Packing結果的評價值對結果集進行過濾，并使用一個樹形結構對每一次Set Packing的結果進行記錄，不斷迭代直至算法結束，再從樹中取出最優結果。

Astraea將Q0看成C次Set Packing問題，每次求得矩陣B的一列。實際運行環境中，大部分情況下|DS|比較大，但|JS|比較小，因此我們采用簡單的蠻力算法解決Set Packing問題。

運行過程中，Astraea構造一個B的解空間搜索樹，并對樹中每個節點進行搜索。節點可以找到其父節點和子節點集合，通過序列號記錄其所在層級（Pk的下標），保存第k次Set Packing得到的Pk（記作node.p，即node.k和node.p構成了Pk），記錄其是否為最終節點及其評分。當前節點到根節點的路徑上的所有p構成了當前解X。

Astraea的求解過程就是構造“B的解空間搜索樹”的迭代過程，包含以下7步：

（1）對于任意葉子節點，根據當前節點到根節點上的所有p，構造當前調度計劃X；

（2）根據X和node.p判斷是否每個作業都被分配，若是則標明節點結束；否則，進入下一步；

（3）遍歷所有可能的Pk，并結合X判斷其是否滿足條件②，保留滿足條件的Pk，記為List_P。其中，Pk遍歷過程的復雜度已被充分降低，后文會詳細解釋，條件①也在這里滿足；

（4）按公式（7）計算Pk評分，Pk的熱度越低越好，包含的作業個數越多越好；

（5）采用加權貪婪策略，保留前[γ]×size（List_P）個Score最大的Pk，其中[γ]是過濾參數；

（6）將剩余的Pk構造成新節點添加到當前節點的子節點中；

（7）返回第（1）步，對所有子節點進行迭代。

迭代過程結束時，Astraea得到一棵B的解空間搜索樹，其葉子節點全為結束狀態。這時，任意葉子節點通往根節點的路徑上的Pk都可以構造一個完整的調度計劃X。Astraea對所有X進行評估，近似度最高的X就是所求解。

Astraea的輸入為A=[aij]M×N、可行解的過濾比例[γ]以及目標集群能容納的任務數量[?]；輸出為最優的近似解X。第（3）步的Pk遍歷過程，是指在當前調度計劃X的基礎上，遍歷下一個批次的作業集合Pk所有可能情況的過程。構造List_P實際上就是構造Pk所有可能的取值，并排除不滿足條件的取值。一方面，條件①要求已分配的作業不能再次分配，因此Pk可以填入1的位置組成的集合可以通過對當前調度計劃X的分析得到；另一方面，Pk中1的總數就是本次調度的作業數量。由于資源限制，每次最多處理[?]個數據集，所以Astraea可以得到當前調度計劃X下最少還需要運行min個批次的作業。min個Pk中至少有一個包含的作業個數≤|NS_JS|/min，其中NS_JS為當前調度計劃X下未被分配的作業集合。因為B各個列的順序與最終運行時間無關，Astraea可以將當前的作業批次包含的作業數量的上限設置為|NS_JS|/min。

3 實驗驗證

針對第2節提出的Astraea近似求解算法，本節設計大量實驗進行驗證分析。

測試用例設計如表1所示，包含3個變量：作業個數|JS|、數據源個數|DS|以及算法中影響解的近似性的參數γ。其中，|JS|取值為3、4、…、 8；|DS|取值為10、 20、…、100；γ取值為0.2、0.4、0.6、0.8和1。|JS|、|DS|和γ均能夠影響Astraea所求解的近似性以及算法性能，我們通過控制它們的變化來分析算法的有效性。

3.1 3個因素對解的近似性的影響

本實驗主要分析|JS|、|DS|和γ對Astraea所求解的近似性的影響。當γ=1時，需對整個解空間進行遍歷，此時Astraea所求解即是最優解。文中我們采用近似解與最優解執行時間之間的比值來衡量解的近似度，該比值越小越近似。此外，鑒于實驗數量較多，僅選取具有代表性的幾組進行展示。

圖2分別展示了5組γ設置下， |DS|和|JS|對Astraea所求解的近似性的影響。在圖2（a），分別固定|JS|的值為3、5和8，研究|DS|取值為20、60和100時對解的近似性的影響。從圖中可以看出：當|JS|較小時（取值為3），無論|DS|取值多少，Astraea獲取的解都是最優解（近似度為1）；當|JS|取值為5時，解的近似程度隨著|DS|的增大而變小，但最多都在γ=0.4的時候取得最優解；當|JS|較大時（取值為8），解的近似程度也隨著|DS|的增大而變小，但最多都在γ=0.6的時候取得最優解。在圖2（b），分別固定|DS|的值為20、60和100，研究|JS|取值為3、5和8時對解的近似性的影響。從圖中可以看出：當|DS|較小時（取值為20），解的近似程度隨著|JS|的增大而變小，但最多都在γ=0.4的時候取得最優解；當|DS|取值為60和100時，解的近似程度也隨著|JS|的增大而變小，但最多都在γ=0.6的時候取得最優解。

綜上所述，Astraea算法獲取的解與最優解之間的差距主要取決于|JS|、|DS|和γ3個因素，當|JS|和|DS|較大時，要獲取較優的近似解就需要設置更大的γ。

3.2 3個因素對算法性能的影響

本實驗主要分析|JS|、|DS|和γ對Astraea算法性能的影響。衡量性能最常用的指標是時間，因此本節選取算法在不同實驗設置下的執行時間來衡量Astraea的性能。同樣，僅選取具有代表性的幾組進行展示。

圖3分別展示了5組γ設置下，|DS|和|JS|對Astraea算法性能的影響，圖中的縱坐標采取對數坐標軸。在圖3（a）中，分別固定|JS|的值為3、5和8，研究|DS|取值為20、60和100時對Astraea算法性能的影響。從圖中可以看出：算法的執行時間均隨|DS|以及γ的增加而增大，并且|JS|越大，這種增長效果越明顯。在圖3（b）中，分別固定|DS|的值為20、60和100，研究|JS|取值為3、5和8時對Astraea算法性能的影響。從圖中可以看出：算法的執行時間均隨|JS|以及γ的增加而增大，并且|DS|越大，這種增長效果越明顯。此處，γ是影響解的近似性的重要因素，當對Astraea算法求解的近似性越高時，γ的值就需要設置越大，進而執行的時間就越長。

綜上所述，Astraea算法的性能主要取決于|JS|、|DS|和γ3個因素，|JS|和|DS|較大時，獲取較優的近似解就需要設置更大的γ值，需要更長的執行時間。

4 結束語

大數據時代，高效地從數據中發現知識已經成為企業重要的競爭力之一，而存儲系統間的數據遷移則是知識發現的一個基礎環節。我們首先給出數據遷移模型并對遷移性能影響因素進行分析，接著基于遷移模型從遷移任務層面提出負載均衡的優化方法，最后通過實驗驗證提出的優化方法的有效性。遷移任務層的優化方法主要通過調控遷移任務的執行順序使得包含同一數據源的作業盡可能避免在同一時間執行，盡可能避免遷移時的數據訪問熱點，從而提高遷移任務的并行性，改善遷移效率。作業調度的最優解獲取問題可以證明是一個NP-hard問題，因此文中提出Astraea近似的求解算法來獲取一個可接受范圍內的問題解。

本中提出的負載均衡的數據遷移方法能夠應用到很多系統中，例如淘寶商品搜索的索引數據存儲處理系統，該系統的輸入數據往往來自于多個存儲系統，不同存儲系統組成了一個擁有海量數據的數據源集群，需要該系統同步這些數據到Hadoop分布式文件系統（HDFS）、HBase等分布式存儲系統。數據同步過程中，該系統一方面要保證數據的同步性能，同時還要盡可能降低對數據源系統查詢性能的影響。文中提出的負載均衡的數據遷移方法能夠成功地避開數據源的熱點訪問問題，從而實現系統的上述目標。

參考文獻

[1] GANTZ J， REINSEL D. The Digital Universe in 2020： Big Data， Bigger Digital Shadows， and Biggest Growth in the Far East [EB/OL].[2012-03-22]. www.emc.com/leadership/digital-universe/index.htm

[2] AHMAD R W， GANI A， HAMID S， et al. A Survey on Virtual Machine Migration and Server Consolidation Frameworks for Cloud Data Centers[J]. Journal of Network and Computer Applications， 2015， 52： 11-25

[3] DERBEKO P， NATANZON A， EYAL A， et al. System and Method for Live Migration of a Virtual Machine with Dedicated Cache： US Patent 8，930，947[P]， 2015

[4] FORSMAN M， GLAD A， LUNDERG L， et al. Algorithms for Automated Live Migration of Virtual Machines [J]. Journal of Systems and Software， 2015， 101： 110-126

[5] LI C. Transforming Relational Database into HBase： A Case Sudy [C]// 2010 IEEE International Conference on Software Engineering and Service Sciences （ICSESS）. USA： IEEE， 2010： 683-687

[6] LIU C， FU Z， YANG Z， et al. General Research on Database Migration from RDBMS to Hbase[C]// 2015 International Symposium on Computers & Informatics. French： Atlantis Press， 2015： 124-237

[7] VUKOTIC A， FOX D， Partner J， et al. Neo4j in Action [M]. USA： Manning Publications， 2014

[8] SHIRAZI M N， KUAN H C， DOLATABADI H. Design Patterns to Enable Data Portability between Clouds Databases[J]. Computational Science and Its Applications （ICCSA）， 2012： 117-120

[9] PANT P， THAKUR S. Data Migration Across the Clouds [J]. International Journal of Soft Computing and Engineering （IJSCE）， 2013， 3（2）：14-21

[10] LONEY K. Oracle Database 10g： the Complete Reference [M]. USA： McGraw-Hill/Osborne， 2004

[11] MADELL T. Disk and File Management Tasks on HP-UX [M]. USA： Prentice-Hall， 1997

[12] ZHENG W， ZHANG G. FastScale： Accelerate RAID Scaling by Minimizing Data Migration [J]. FAST， 2011： 149-161

[13] KING A， CHIU D C. Efficient Fault-Tolerant Preservation of Data Integrity During Dynamic RAID Data Migration： US Patent 6，530，004[P]. 2003

[14] Chodorow K. MongoDB： the definitive guide [M]， 2nd Edition. USA： OReilly Media， 2013

[15] CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： A Distributed Storage System for Structured Data [J]. ACM Transactions on Computer Systems （TOCS）， 2008， 26（2）： 4

[16] GEORGE L. HBase： the Definitive Guide [M]. USA： OReilly Media， 2011

[17] ANDERSON JC， LEHNARDT J， SLATER N. CouchDB： the Definitive Guide [M]. USA： OReilly Media， 2010

[18] ANDERSON E， HALL J， HARTLINE J， et al. An Experimental Study of Data Migration Algorithms [M]. British： Springer， 2001

[19] BAGUI S， NGUYEN L T. Database Sharding： To Provide Fault Tolerance and Scalability of Big Data on the Cloud [J]. International Journal of Cloud Application Computing， 2015， 5（2）：36-52. http：//dx.doi.org/10.4018/IJCAC.2015040103

[20] LIU Y， WANG Y， JIN Y. Research on the improvement of MongoDB Auto-Sharding in Cloud Environment[C]// 2012 7th International Conference on Computer Science & Education （ICCSE）. USA： IEEE， 2012： 851-854