基于時間序列的PDM 文件數據塊分布算法

夏秀峰，張 羽

（1.沈陽航空航天大學 計算機學院，遼寧 沈陽110136；2.沈陽航空航天大學 遼寧省通用航空重點實驗室，遼寧 沈陽110136）

0 引 言

為解決RDB （relational data base）高并發讀寫和水平擴展限制、PDM （product data management）數據高效存儲和訪問問題，將NoSQL 數據庫和企業私有云存儲技術應用到PDM 系統中，構建基于企業私有云環境下的PDM 文件系統，以滿足海量數據存儲和訪問的要求是一種有益的探索和嘗試。

HDFS （Hadoop distributed file system）對數據塊副本采用隨機放置策略，數據塊分布不能根據系統運行情況而發生動態變化。隨機放置策略造成文件數據塊存儲集中在某個節點，不僅降低系統容錯性，且造成集群節點資源未能充分利用。

考慮到企業私有云環境下，影響數據節點服務性能的主要因素為文件訪問數量，而非網絡距離和存儲空間，據此，本文提出基于時間序列的PDM 文件數據塊分布算法，算法根據數據塊訪問量進行數據塊的動態遷移，在實現數據塊合理分布的同時均勻分布文件數據塊副本，從而有效提高系統的容錯性。

1 時間序列分析

時間序列分析方法通過對數據的動態處理及分析，根據建模方法建立相應的數據擬合模型去近似描述數據特點。通過對數據發展趨勢的預測，從而采取合理的方法實現有效控制的目的。文獻 ［1］詳細介紹了時間序列的相關知識、常用時間序列模型和預測方法。

1.1 白噪聲過程

若隨機過程 ｛Xt｝ （t∈T）滿足以下條件則稱為白噪聲過程。

（1）E（Xt）＝0；

（2）Var（Xt）＝σ2＜∞，t∈T；

（3）Cov（Xt，Xt－k）＝0，（t－k）∈T，k≠0。

白噪聲是平穩的時間序列，平穩時間序列的行為不會隨著時間的變化而變化，因此可以通過過去的行為對未來的行為進行預測。

1.2 基本時間序列模型

p階自回歸模型AR（p）

式 （1）稱為p階自回歸模型，其中i（1≤i≤p）稱為自回歸參數，μt 是白噪聲過程。式 （1）引入滯后算子后表示為

（L）＝1－1L－2L2－…－PLP稱為特征方程或者自回歸算子，如果特征方程（L）＝0的所有根均在單位圓之外，則AR（p）模型具有平穩性。

q階移動平均模型MA（q）

式 （3）稱為q階移動平均模型，其中θj（1≤j≤q）稱為回歸參數，μt 為白噪聲過程。式 （3）引入滯后算子后表示為

MA（q）是由q＋1個白噪聲變量的加權和組成。因此有限階移動平均過程總是平穩的，其中θ（L）＝1－θ1Lθ2L2－…－θqLq。如果特征方程θ（L）＝0所有根在單位圓之外，則MA（q）模型具有可逆性。

ARMA（p，q）模型是AR（p）和MA（q）的混合模型，一般描述為

引入滯后算子后式 （5）表示為

AR、MA、ARMA 模型只適用于平穩時間序列的擬合，對于非平穩時間序列則需要通過差分將其變換為平穩的時間序列。如果一個隨機時間序列經過d次差分后可以變換為一個平穩的自回歸移動平均過程，則該隨機序列被稱為自回歸單整移動平均過程ARIMA（p，d，q）。

因篇幅有限，本文僅對時間序列模型做簡單介紹。時間序列分析在負載均衡預測方面被廣泛應用。文獻 ［2］介紹了常用的預測方法，并對常用時間序列模型的建立進行了詳細說明。文獻 ［3］介紹了預測模型在云計算資源管理中的應用并展望了預測模型的發展方向。文獻 ［4，5］分別對預測模型進行改進，預測精度明顯提高。文獻 ［6］通過對集群系統中節點負載特點的分析，提出服務器集群負載預測模型，有效提高了集群系統的利用率。文獻 ［7］介紹了時間序列模型與預測相關內容，通過實驗分析對比了各時序模型在網絡流量中的預測效果。

本文通過對數據塊訪問次數時間序列的分析，擬合出適當的數學模型預測數據塊訪問趨勢，使用預測結果為數據塊合理分布提供依據。

2 數據塊分布算法

通常，HFDS采用機架感知策略實現數據塊放置，將數據塊優先放置于本地節點或相同機架的節點中。默認放置策略優先考慮網絡傳輸代價，提供一種通用的放置策略。但在企業私有云環境下，網絡傳輸代價并不是影響用戶訪問質量的關鍵因素。而且PDM 文件系統中用戶訪問并不是隨機進行，現階段生產和設計相關數據的訪問量明顯大于歷史數據的訪問量。因此需要根據數據塊訪問量合理分布數據塊，以解決數據塊隨機放置造成的節點訪問量不均衡問題，從而實現集群的負載均衡。

為提高云存儲系統性能及數據的合理分布，文獻 ［8］提出基于一致性哈希數據分布和節點容量感知的負載均衡方法，該策略改善了存儲資源負載均衡程度并優化了系統整體性能。文獻 ［9］基于節點網絡距離和數據節點負載兩種因素計算節點的負載評價值，根據評價值選擇最佳的放置節點。文獻 ［10］綜合考慮節點的存儲性能和網絡距離兩種因素進行數據節點的選擇，算法改善了數據塊放置的均衡性。文獻 ［11］根據數據節點的狀態信息動態選擇節點以實現負載均衡。

結合PDM 文件訪問特點和企業私有云環境優勢，本文提出基于時間序列的PDM 文件數據塊分布算法，將數據塊訪問量作為分布依據。算法在保證節點訪問量平均的前提下，使文件數據塊副本均勻分布在各數據節點中，從而實現集群的負載均衡并提高系統的容錯性。

為減少頻繁遷移對系統的影響，使用擬合數據模型對數據塊訪問量進行多步預測。算法根據多步預測結果選擇合理的數據節點進行數據塊遷移，減少頻繁數據塊遷移造成系統的額外開銷。

下面給出算法描述，預測步長為m 步：

（1）計算當日節點平均訪問量x，訪問量大于等于x的節點加入S隊列，小于x的節點加入T 隊列，計算得到S隊列和T 隊列。如果n大于m，轉 （10）；

（2）如果S隊列為空或T 隊列為空，n＋＋，轉 （1）；

（3）從S隊列中取出節點Si；

（4）從Si中取出一個數據塊賦值給變量b，找出T 隊列中保存數據塊b 所屬文件的數據塊數目最少的數據節點Tj；

（5）如果Tj已保存數據塊b的副本，轉 （4）；

（6）數據塊b加入移動集合中，將數據塊b中目標節點數組中Tj值加1，從Si中刪除數據塊b；

（7）如果Si的訪問量小于x，則將Si從S隊列中刪除，轉 （2）；

（8）如果Tj的訪問量大于等于x，則將Tj從T 隊列中刪除，轉 （4）；

（9）轉 （4）；

（10）如果移動集合為空，則轉 （13）；

（11）從移動集合中取出一個數據塊賦值給變量b，選擇數據塊b的目標數組中出現次數最多的節點作為目標節點，并將數據塊b遷移至目標節點中；

（12）將數據塊b從移動集合中刪除，轉 （10）；

（13）結束。

基于時間序列的PDM 文件數據塊分布算法以平均數據節點訪問量為目標。算法在數據塊移時避免文件數據塊副本集中存儲在某個節點中，使文件數據塊副本分布更加均勻，因此有效提高了系統的容錯性。同時算法綜合考慮數據塊未來多日訪問量進行遷移，有效減少了數據塊的頻繁遷移。

3 實驗結果分析

本節對文中提出的基于時間序列的PDM 文件數據塊分布算法進行仿真實驗。通過對本文算法、默認算法和基于存儲空間的數據塊分布算法 （以下簡稱基于存儲空間分布算法）3種算法進行比較，驗證本文算法的有效性。實驗使用擬合數據模型預測未來五日的數據塊訪問量作為實驗數據。在多次實驗數據中隨機選擇一組實驗進行3種算法的數據對比。

數據節點存儲數據塊數目對比如圖1所示。從圖1中看出基于存儲空間分布算法使數據塊均勻分布到各數據節點中。默認算法和本文算法基本實現數據塊均勻分布，但與基于存儲空間分布算法有一定差距。基于存儲空間分布算法實現了數據節點存儲空間的合理利用，但并未解決數據節點訪問量不均衡問題。

圖1 數據節點存儲數據塊數目對比

默認算法數據節點訪問量如圖2所示。默認算法作為一種通用的數據塊放置策略能夠將數據塊較均勻的分布到數據節點中，但數據節點訪問量差距較大容易造成集群負載不均衡問題的出現。

基于存儲空間分布算法數據節點訪問量如圖3所示。算法能夠較好的實現數據節點存儲空間的均衡。但由于PDM文件訪問特點造成文件訪問次數差別較大。因此雖然數據節點保存數據塊數目接近，但未解決數據節點訪問量不均衡問題。

圖2 默認算法數據節點訪問量

圖3 基于存儲空間分布算法數據節點訪問量

本文算法數據節點訪問量如圖4所示。算法使數據節點訪問量更加平均，同時讓遷移數據塊均勻分布在數據節點中，有效提高了集群的容錯性。

數據塊遷移結果見表1，文件14數據塊分別被本文算法和基于存儲空間分布算法選中進行遷移，因此更容易對比實驗效果。

圖4 本文算法數據節點訪問量

表1 數據塊遷移結果

默認算法隨機放置數據塊，節點1存儲了文件14全部數據塊，節點2存儲4個數據塊，因此數據塊存儲過于集中。本文算法和基于存儲空間分布算法分別對文件14進行了數據塊遷移。本文算法將數據塊從節點1分別遷移至節點5、節點6，同時將數據塊從節點2遷移至節點6、節點4，從而使文件數據塊更均勻的分布在各數據節點中。而基于存儲空間分布算法使用存儲空間作為評判因素，將文件數據塊大量遷移至節點3中，造成節點3存儲文件的全部數據塊，并未有效解決遷移中數據塊存儲集中的問題。

實驗通過數據節點訪問量和數據節點存儲數據塊數目兩方面對3種算法進行了對比。默認算法使用隨機放置策略數據塊基本均勻分布，但存在文件數據塊存儲集中的問題而且數據節點訪問量差別較大；基于存儲空間的數據塊分布算法能夠較好的實現數據節點存儲空間的平均使用，但存在與默認算法相同的問題；本文算法實現數據節點訪問量平均的同時減少了文件數據塊存儲集中的問題，有效提高了系統的容錯性。

4 結束語

針對HDFS默認數據塊分布算法在PDM 文件系統中存在的不足，提出基于時間序列的PDM 文件數據塊分布算法。算法使用數據塊歷史訪問記錄建立擬合模型預測未來數據塊訪問趨勢，從而進行數據塊的合理分布并減少文件數據塊存儲集中問題的出現。通過實驗對比本文算法、默認算法及基于存儲空間分布算法3種算法實驗數據，驗證了本文算法的有效性及合理性。

［1］WANG Yan.Applied time series analysis［M］.Beijing：Chi－na Renmin University Press，2012 （in Chinese）.［王燕.應用時間序列分析 ［M］.北京：中國人民大學出版社，2012.］

［2］WU Wei，LIU Xiyu，YANG Yi，et al.Analysis method of time array and two models of ARMA and GARCH ［J］.Computer Technology and Development，2010，20 （1）：247－249（in Chinese）.［武偉，劉希玉，楊怡，等.時間序列分析方法及ARMA，GARCH 兩種常用模型 ［J］.計算機技術與發展，2010，20 （1）：247－249.］

［3］ZHANG Feifei，WU Jie，LV Zhihui.Survey on prediction models in cloud resource management schemes［J］.Computer Engineering and Design，2013，34 （9）：3078－3083 （in Chinese）. ［張飛飛，吳杰，呂智慧.云計算資源管理中的預測模型綜述 ［J］.計算機工程與設計，2013，34 （9）：3078－3083.］

［4］GAO Xingwang，WANG Qiong，OUYANG Yiming.Algorithm research of load balancing based on blending prediction model［J］.Computer Engineering and Design，2010，31（16）：3557－3561 （in Chinese）. ［高興旺，王瓊，歐陽一鳴.基于混合預測模型的負載均衡算法研究 ［J］.計算機工程與設計，2010，31 （16）：3557－3561.］

［5］LIN Huijun，XU Rongcong.Time series prediction based on mixture of ARMA and SVR model［J］.Computer and Modernization，2009，25 （8）：19－22 （in Chinese）.［林慧君，徐榮聰.組合ARMA 與SVR 模型的時間序列預測 ［J］.計算機與現代化，2009，25 （8）：19－22.］

［6］QIAO Guojuan，CHEN Guang.A load balance algorithm based on prediction model［J］.Computer and Modernization，2014，30 （8）：91－95 （in Chinese）. ［喬國娟，陳光.一種基于預測模型的負載均衡算法 ［J］.計算機與現代化，2014，30（8）：91－95.］

［7］JIANG Ming，WU Chunming，ZHANG Min，et al.Research on the comparison of time series models for network traffic prediction ［J］.ACTA Electronica Sinica，2009，37 （11）：2353－2358 （in Chinese）. ［姜明，吳春明，張旻，等.網絡流量預測中的時間序列模型比較研究 ［J］.電子學報，2009，37（11）：2353－2358.］

［8］ZHOU Jingli，ZHOU Zhengda.Improved data distribution strategy for cloud storage system ［J］.Journal of Computer Applications，2012，32 （2）：309－312 （in Chinese）. ［周 敬利，周正達.改進的云存儲系統數據分布策略 ［J］.計算機應用，2012，32 （2）：309－312.］

［9］LIN Weiwei.An improved data placement strategy for Hadoop［J］.Journal of South China University of Technology （Natural Science Edition），2012，40 （1）：152－158 （in Chinese）. ［林偉偉.一種改進的Hadoop數據放置策略 ［J］.華南理工大學學報 （自然科學版），2012，40 （1）：152－158.］

［10］WANG Yongzhou，MAO Su.A blocks placement strategy in HDFS ［J］.Computer Technology and Development，2013，23 （5）：90－96 （in Chinese）.［王永洲，茅蘇.HDFS中的一種數據放置策略 ［J］.計算機技術與發展，2013，23 （5）：90－96.］

［11］YE Xianglong，HUANG Mengxing，ZHU Donghai，et al.A novel blocks placement strategy for Hadoop ［C］／／IEEE／ACIS 11th International Conference on Computer and Information Science.Shanghai：IEEE，2012：4－7.