基于數(shù)據(jù)關聯(lián)度的遷移策略研究

張陸軍，聶瑞華* ，王進宏，譚黎立

(1.華南師范大學計算機學院，廣州510631;2. 北明軟件股份有限公司，廣州510633)

如今，互聯(lián)網(wǎng)上出現(xiàn)許多公有云服務，如Google的GFS 和Google Apps、IBM 的藍色云、Amazon 的EC2 等，在海量數(shù)據(jù)到來時，私有云規(guī)模小，需將大部分計算任務分配到公有云上，這就需要解決數(shù)據(jù)遷移問題.目前普遍采用的數(shù)據(jù)遷移方法有高低水位法［1］、cache 替換遷移算法［2］、分級存儲管理的數(shù)據(jù)遷移技術［3］和以它們?yōu)榛A的一些改進算法. 以判斷磁盤空間是否飽和來決定數(shù)據(jù)是否遷移的高低水位法，忽略了數(shù)據(jù)本身的特征屬性.Cache 替換遷移算法主要是參考虛擬內存頁面置換方法，常用的有FIFO、LRU 和LFU 等算法，F(xiàn)IFO 和LRU［4－5］算法主要考慮時間因子，將近年來最少使用的數(shù)據(jù)遷出磁盤，但沒有考慮數(shù)據(jù)集大小.LFU 算法主要考慮數(shù)據(jù)的訪問頻率，將訪問次數(shù)最少的數(shù)據(jù)遷移出磁盤，缺點是沒有考慮到多長時間失效，有可能造成長久未失效的數(shù)據(jù)滯留磁盤. 分級存儲管理的數(shù)據(jù)遷移技術［5］，讓數(shù)據(jù)能在不同級別存儲設備上實現(xiàn)自動遷移，同時也能很好地降低數(shù)據(jù)管理成本，主要適用在不同級別設備之間的訪問，使用范圍受到限制.文獻［6］在混合云存儲環(huán)境下，研究了適合于云存儲環(huán)境下海洋數(shù)據(jù)的遷移算法，延伸了算法的使用范圍.但是該算法未考慮在尋找遷移數(shù)據(jù)前，數(shù)據(jù)之間有一定的關聯(lián)性，尋找出數(shù)據(jù)之間的關聯(lián)性有助于增加數(shù)據(jù)遷移前的尋找準確性，能更好地找出需要遷移的數(shù)據(jù).文獻［7－9］提出了基于價值評估模型的數(shù)據(jù)遷移方法，考慮了數(shù)據(jù)之間的相關性，但都是基于用戶角度出發(fā)尋找數(shù)據(jù)集的潛在用戶量. 由此計算數(shù)據(jù)預計遷移值，忽略了數(shù)據(jù)集本身之間的關系.本文結合上述的遷移算法的優(yōu)點和不足性，根據(jù)環(huán)境中的數(shù)據(jù)屬性，研究了基于數(shù)據(jù)關聯(lián)度的遷移策略.

1 相關描述與介紹

圖1 電子政務云服務中心總體規(guī)劃架構圖Figure 1 Overall planning architecture diagram of cloud service center of e-government

圖1 為電子政務云服務中心的總體規(guī)劃架構，電子政務云服務中心由廣州市科信局主持總體規(guī)劃設計，廣州市電子政務中心組織實施和管理，2 家資格服務商提供物理層、資源層、云服務層的建設，云平臺為委局單位電子政務系統(tǒng)提供全面、高效、安全、穩(wěn)定的服務.

1.1 大數(shù)據(jù)生命周期

遷移模型主要圍繞電子政務云中大數(shù)據(jù)的生命周期——數(shù)據(jù)采集、數(shù)據(jù)存儲、數(shù)據(jù)處理、數(shù)據(jù)分析和應用等5個階段展開研究，與大數(shù)據(jù)處理和管理緊密聯(lián)系.圖2 為本文研究的數(shù)據(jù)處理技術架構圖.數(shù)據(jù)采集中心從不同的業(yè)務系統(tǒng)中采集數(shù)據(jù)模塊，該模塊在采集完數(shù)據(jù)后也實現(xiàn)對數(shù)據(jù)的初步預處理，如數(shù)據(jù)清洗、數(shù)據(jù)去重、數(shù)據(jù)壓縮、數(shù)據(jù)轉換等.經(jīng)過數(shù)據(jù)采集中心的預處理后數(shù)據(jù)存儲到大數(shù)據(jù)存儲中心.數(shù)據(jù)物流中心主要負責海量數(shù)據(jù)遷移和數(shù)據(jù)交換. 數(shù)據(jù)分析挖掘中心是基于Hadoop/Mahout平臺搭建的數(shù)據(jù)分析和數(shù)據(jù)挖掘環(huán)境. 底層的電子政務云平臺是一個面向物聯(lián)網(wǎng)的云基礎設施平臺，通過虛擬化計算，以動態(tài)、分布式和按需的方式提供計算和存儲資源，并且統(tǒng)籌優(yōu)化.本文所研究的是大數(shù)據(jù)處理物流中心模塊中的數(shù)據(jù)遷移技術. 針對物流中心模塊中的數(shù)據(jù)遷移進行了深入分析.

圖2 數(shù)據(jù)處理技術實現(xiàn)框架Figure 2 Implementation framework of data processing technology

1.2 面向大數(shù)據(jù)對象的數(shù)據(jù)遷移因子分析

文獻［7－9］提出了基于價值評估模型的數(shù)據(jù)遷移方法，在計算價值評估模型時候也考慮了數(shù)據(jù)的靜態(tài)和動態(tài)因素.本文在數(shù)據(jù)物流中心中，挖掘數(shù)據(jù)的靜態(tài)特征和訪問的動態(tài)特征，并將其作為數(shù)據(jù)遷移對象的判斷標準.

1.2.1 數(shù)據(jù)的靜態(tài)因素 指的是數(shù)據(jù)集數(shù)據(jù)的大小S 和數(shù)據(jù)集的用戶數(shù)量C［9］.對于已達PB 量級的存儲系統(tǒng)來說，小且熱的數(shù)據(jù)集更適合存儲在性能高且容量有限的高性能磁盤陣列中［7］. 一個數(shù)據(jù)集被訪問的用戶數(shù)量越多，數(shù)據(jù)集的價值越高，因為如果一個數(shù)據(jù)集被多個用戶訪問，那么該數(shù)據(jù)集影響因子越高，故而可以得到頻繁調度計算的大數(shù)據(jù)集S 與遷移函數(shù)成正比關系，與用戶量成反比關系.

1.2.2 數(shù)據(jù)的動態(tài)因素 (1)數(shù)據(jù)時間長度. 在存儲系統(tǒng)中，從數(shù)據(jù)被創(chuàng)建之后數(shù)據(jù)每次被訪問和修改的時間集合為{t1，t2，…，tn}. 設數(shù)據(jù)當前一次操作時間是t，隨著被訪問后，數(shù)據(jù)集被訪問的概率隨著未使用的時間越長而變低. 數(shù)據(jù)集每次被訪問距離當前時刻的時間長度為t－t1，t－t2，…，t－tn，記上述的時間長度依次為T1，T2，…，Tn，則數(shù)據(jù)集D的時間由此，計算數(shù)據(jù)集的訪問頻率記為:

(2)數(shù)據(jù)關聯(lián)度R(d).數(shù)據(jù)關聯(lián)定義即若數(shù)據(jù)X 在任意時刻被訪問前后的短時間內(如10 分鐘)，數(shù)據(jù)Y 也會被訪問，則認為數(shù)據(jù)X 和數(shù)據(jù)Y 是相關聯(lián)的［7］.有些數(shù)據(jù)是注定相關聯(lián)的，例如如果用戶要訪問一個數(shù)據(jù)，必然先訪問它的目錄數(shù)據(jù)，但大部分數(shù)據(jù)間的關聯(lián)是不明確的. 數(shù)據(jù)的關聯(lián)度參數(shù)R(d)的計算方法為在每個時間區(qū)間T 標記該區(qū)間內有無讀寫操作，進而獲得在T 上每個數(shù)據(jù)集的一個N 維操作標記向量R，若在任意的第i (i =1，2，…，n)個時間段上有讀/寫操作就將該向量的第i 維標記為1，否則標記為0，因此每一個數(shù)據(jù)可得到一個操作標記列向量(1，0，…，0)T，所以操作標記向量都是只有1個位為1、其余位全為0 的形式，這是沒考慮數(shù)據(jù)關聯(lián)度之前的向量表. 在引入數(shù)據(jù)關聯(lián)度時可以根據(jù)數(shù)據(jù)之間相互影響的規(guī)則構造出操作矩陣A，這個矩陣是一個方陣，因為數(shù)據(jù)自己會對自己有影響，所以方陣對角線元素全為1.操作列向量Od是實際進行的讀寫操作，但由于操作之間相互影響，我們只有一個結果，這個結果就稱為效果列向量E，效果列向量等于操作矩陣S 與操作列向量的乘積.只有效果列向量才可以對一個狀態(tài)起作用，對于2個效果列向量，可以進行群運算，群運算符號用?表示.所謂群算，就是按位異或E1?E2=E1XORE2，對于一個狀態(tài)S，E1?E2(S)表示對狀態(tài)S 進行E1?E2作用，它表示先對狀態(tài)S 進行E2作用，然后再做群運算.一個數(shù)據(jù)經(jīng)過操作矩陣和操作列向量乘積最后得到結果為1，那么這個數(shù)據(jù)句柄就與數(shù)據(jù)X 相關聯(lián).Ed為效果列向量，效果列向量等于操作矩陣A 與操作列向量Od的乘積，即AOd=Ed，最后得到的Ed所有1 的總和為數(shù)據(jù)d 的關聯(lián)度參數(shù)R(d).

在混合云存儲的遷移算法［6］中，將公有云存儲中的數(shù)據(jù)中心集合記為文中將電子政務云中心作為公有云存儲數(shù)據(jù)中心，則集合Pubc 的存儲空間記為+∞;其使用服務的相關部門記為私有云存儲中心，其數(shù)據(jù)中心集合記為其中Prici表示編號為i 的數(shù)據(jù)中心，cLi表示數(shù)據(jù)中心Prici的可存儲空間.Li為私有云數(shù)據(jù)中心i 當前已使用的存儲空間大小，則私有云數(shù)據(jù)中心i 的空間飽和度θi=Li/cLi，當數(shù)據(jù)中心存儲空間飽和度θ ＞σ，則觸發(fā)系統(tǒng)執(zhí)行遷移過程，σ 是數(shù)據(jù)中心飽和度的閾值.

2 遷移策略模型

文獻［6］研究了在混合云存儲環(huán)境下，適合于云存儲環(huán)境下海洋數(shù)據(jù)的遷移算法. 該算法在設計遷移函數(shù)時，并未考慮數(shù)據(jù)關聯(lián)性這一重要因素.結合遷移因子的研究分析得知，在計算數(shù)據(jù)遷移函數(shù)的時候應該考慮數(shù)據(jù)集的數(shù)據(jù)關聯(lián)度，用于計算預計遷移值的遷移函數(shù)和數(shù)據(jù)存儲的時間長度T 和數(shù)據(jù)的訪問頻率F 都成正比關系.同時遷移函數(shù)同數(shù)據(jù)集的大小S 和數(shù)據(jù)集的關聯(lián)度R(d)也為正比關系，將遷移函數(shù)記為M(d)，綜合考慮得到用于計算數(shù)據(jù)預遷移的遷移函數(shù)為:

在得到新的數(shù)據(jù)遷移函數(shù)后，根據(jù)混合云的遷移算法，本節(jié)給出新的適合于電子政務云存儲的基于數(shù)據(jù)關聯(lián)度的遷移策略模型，其算法遷移步驟如下:

步驟1:建立遷移隊列，根據(jù)數(shù)據(jù)存儲的要求對數(shù)據(jù)進行存儲，創(chuàng)建遷移線程和候選遷移隊列.

步驟2:計算T=Ti第i個數(shù)據(jù)中心內的飽和度θ，判斷是否大于第i個數(shù)據(jù)中心內的閾值σ.

步驟3:當T =Ti時，計算私有云內第i個服務器中每個數(shù)據(jù)集j 的預計遷移值M(dj)，根據(jù)M(dj)值進行排序，并依次將數(shù)據(jù)存入數(shù)據(jù)集合S_OUT 中等待遷移.

步驟4:利用數(shù)據(jù)遷移工具從S_OUT 中選擇對M(d)最大的待遷移的數(shù)據(jù)集，執(zhí)行數(shù)據(jù)遷移.

步驟5:計算下一個數(shù)據(jù)中心的飽和度θ，并判斷是否執(zhí)行了數(shù)據(jù)遷移，修改各數(shù)據(jù)中心數(shù)據(jù)集的屬性值.

由上面的分析得出本文的遷移模型的偽代碼和數(shù)據(jù)遷移策略流程圖(圖3).模型的偽代碼如下:

初始化:令私有云數(shù)據(jù)中心編號i=0，數(shù)據(jù)中心編號上的數(shù)據(jù)集編號j=0;

{根據(jù)遷移函數(shù)對第j個數(shù)據(jù)集進行計算，求出max(M(dj));j++;}

對M(D)最大的數(shù)據(jù)集執(zhí)行數(shù)據(jù)遷移;

跳出本次循環(huán)，i++;

if(執(zhí)行了數(shù)據(jù)遷移)

圖3 數(shù)據(jù)遷移策略模型流程圖Figure 3 Flow chart of data migration strategy model

3 實驗結果與分析

3.1 成本分析

目前，傳統(tǒng)的電子政務平臺大都基于集中式存儲［10］，經(jīng)調研得知采購規(guī)模8TB 的服務器需要4 000 美元.按單位存儲量計算即0.5 美元/GB，每臺服務器的功率為0.6 kW(傳統(tǒng)集中式存儲一般有2 臺服務器，1 臺作為備份用)，空調平均功率為2 kW，則1 天內，管理成本中耗電量為76.8 kW·h.傳統(tǒng)集中式數(shù)據(jù)存儲需要有數(shù)據(jù)維護人員的開支以及服務器的耗電電費，數(shù)據(jù)維護人員按照1個月5 000 元算，其他開支忽略不計，按照每度電0.62 元計算，人民幣兌美元的匯率為1 美元=6.12 元，則可以計算出傳統(tǒng)的管理數(shù)據(jù)成本.目前，公有云的提供商網(wǎng)上均價為0.1 美元/(GB·月－1). 存儲成本的計算結果，利用本文提出的遷移模型與傳統(tǒng)的集中式存儲方式相比較(表1)，可見本文的數(shù)據(jù)管理能明顯降低數(shù)據(jù)管理成本，且數(shù)據(jù)量越大，管理成本節(jié)省越多.

表1 數(shù)據(jù)管理成本對比表Table 1 Comparison table of data management cost

3.2 模擬實驗分析

本實驗環(huán)境為Windows8.1、64 位操作系統(tǒng)、CPU 為雙核2.2 GHz，java 集成開發(fā)工具eclipse-jeekepler，仿真軟件Matlab7.0R14. 為了檢驗上述遷移算法的計算預遷移能力及優(yōu)化能力，本實驗用UCI數(shù)據(jù)庫的IrisData 數(shù)據(jù)集作為實驗測試數(shù)據(jù)，用于計算其在某一時刻數(shù)據(jù)集的預計遷移值M(d).Iris數(shù)據(jù)集［11］以鳶尾花的特征作為數(shù)據(jù)來源，包含150個數(shù)據(jù)集，分為3 類:setosa、versicolor 和virginica.每類50個數(shù)據(jù)，每個數(shù)據(jù)(即每個樣本)包含4個屬性，實驗將樣本中的數(shù)據(jù)作為本文中的遷移屬性值來算.實驗主要分為2個部分，在訪問頻率、訪問量和訪問時間區(qū)間都一樣的條件下，分別引入數(shù)據(jù)關聯(lián)度R 和不引入數(shù)據(jù)關聯(lián)度計算數(shù)據(jù)集的預遷移值M(d)(計算過程中和圖中用符號md 表示該值)，并加以比較.從結果可以看出，2 種方法都能找出需遷移的數(shù)據(jù)集，但是引入數(shù)據(jù)關聯(lián)度的分析明顯會比不引入數(shù)據(jù)關聯(lián)度的預數(shù)據(jù)遷移值更高. 在數(shù)據(jù)遷移時，預計遷移值越高，找到所需數(shù)據(jù)的準確率越高，對比分析(圖4)可知.引入數(shù)據(jù)關聯(lián)度，更加有效計算出遷移值，得到的md 值比沒有引入數(shù)據(jù)關聯(lián)度的md 值明顯偏大，其中，md 值的單位為數(shù)量值1.圖像中出現(xiàn)的1 ～50 號文件遷移值較小，因為IrisData 數(shù)據(jù)屬性值本身就小，按上述計算方式計算得到的md 值也較小.

圖4 數(shù)據(jù)集預遷移值引入數(shù)據(jù)關聯(lián)度前后對比Figure 4 Comparison of the migration of expected value before and after data relevance introduced into the data sets

4 結束語

本文在電子政務云平臺下，研究了數(shù)據(jù)的遷移算法，總結影響數(shù)據(jù)遷移的若干因素.從靜態(tài)因素和動態(tài)因素兩方面提出了改進的數(shù)據(jù)遷移模型，以實現(xiàn)數(shù)據(jù)在云平臺的動態(tài)遷移.經(jīng)過實驗分析，運用本文的算法，和傳統(tǒng)的遷移集中式管理相比大大減少了數(shù)據(jù)的管理成本.在引入數(shù)據(jù)關聯(lián)度后，在計算數(shù)據(jù)預計遷移值時具有明顯的優(yōu)越性，能夠得到較準確的數(shù)據(jù)遷移預計值. 未來可以在數(shù)據(jù)間關聯(lián)規(guī)則方面進行作進一步的研究.如果數(shù)據(jù)大，需深入挖掘數(shù)據(jù)間的相互關聯(lián)性規(guī)律，以更好地找出所需要的預計遷移的數(shù)據(jù)，提高數(shù)據(jù)遷移前命中率.

［1］Lugar J. Hierarchical storage management:Leveraging new capabilities［J］. IT Professional，2001，3(2):53－55.

［2］Maguluri S T，Srikant R，Lei Y. Stochastic models of load balancing and scheduling in cloud computing clusters［C］∥INFOCOM，Proceedings IEEE. Orlando，F(xiàn)L，2012:702－710.

［3］He D S，Zhang X B，Du D H C，et al.Coordinating parallel hierarchical storage management in object-based cluster file system［EB/OL］.［2014－ 12－ 28］. http:∥www.dtc.umn.edu/publications/reports/2006-13.pdf.

［4］Smitha，Reddy A L N.LRU-RED:An active queue management scheme to contain high bandwidth flows at congested routers［C］∥proceeding of the global telecommunications conference. San Antonio，TX，2001:2311－2315.

［5］Modha D，Megiddo N. Outperforming LRU with an adaptive replacement cache algorithm［J］. Computer，2004，37(4):58－65.

［6］黃冬梅，杜艷玲，賀琪，等. 混合云存儲中海洋大數(shù)據(jù)遷移算法的研究［J］. 計算機研究與發(fā)展，2014，51(1):199－205.Huang D M，Du Y L，He Q，et al. Big ocean data migration algorithm in the hybrid cloud storage research［J］.Journal of Computer Research and Development，2014，51(1):199－205.

［7］呂帥，劉光明，徐凱，等.海量信息分級存儲數(shù)據(jù)遷移策略研究［J］. 計算機工程與科學，2009，31(S1):163－167.Lv S，Liu G M，Xu K，et al. Massive information storage of data migration strategy study［J］. Computer Engineering and Science，2009，31(S1):163－167.

［8］劉國楊.基于價值評估的衛(wèi)星遙感數(shù)據(jù)遷移方法探討［J］.航天器工程，2008，17(4):114－117.Liu G Y. Based on the evaluation of satellite remote sensing data migration method［J］. Journal of Spacecraft Engineering，2008(4):114－117.

［9］江菲，湯小春，張曉，等. 基于價值評估的數(shù)據(jù)遷移策略研究［J］.電子設計工程，2011，19(7):11－13.Jiang F，Tang X C，Zhang X，et al. Based on the evaluation of data migration strategy research［J］. Journal of Electronic Design Engineering，2011，19(7):11－13.

［10］吳彥華.基于云計算的電子政務應用研究——以青島市電子政務云平臺為例［D］. 北京:首都經(jīng)濟貿易大學，2014.Wu Y H. E-government application based on cloud computing research:In Qingdao e-government cloud platform，for example［D］.Beijing:Capital University of Economics and Business，2014.

［11］宋麗.基于決策樹的組合分類器的研究［D］.西安:西安電子科技大學，2012.Song L.Research on classifier ensemble based on decision tree［D］.Xi'an:Xidian University，2012.