基于時(shí)間序列的PDM 文件數(shù)據(jù)塊分布算法

夏秀峰，張 羽

（1.沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，遼寧 沈陽110136；2.沈陽航空航天大學(xué) 遼寧省通用航空重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽110136）

0 引 言

為解決RDB （relational data base）高并發(fā)讀寫和水平擴(kuò)展限制、PDM （product data management）數(shù)據(jù)高效存儲(chǔ)和訪問問題，將NoSQL 數(shù)據(jù)庫和企業(yè)私有云存儲(chǔ)技術(shù)應(yīng)用到PDM 系統(tǒng)中，構(gòu)建基于企業(yè)私有云環(huán)境下的PDM 文件系統(tǒng)，以滿足海量數(shù)據(jù)存儲(chǔ)和訪問的要求是一種有益的探索和嘗試。

HDFS （Hadoop distributed file system）對(duì)數(shù)據(jù)塊副本采用隨機(jī)放置策略，數(shù)據(jù)塊分布不能根據(jù)系統(tǒng)運(yùn)行情況而發(fā)生動(dòng)態(tài)變化。隨機(jī)放置策略造成文件數(shù)據(jù)塊存儲(chǔ)集中在某個(gè)節(jié)點(diǎn)，不僅降低系統(tǒng)容錯(cuò)性，且造成集群節(jié)點(diǎn)資源未能充分利用。

考慮到企業(yè)私有云環(huán)境下，影響數(shù)據(jù)節(jié)點(diǎn)服務(wù)性能的主要因素為文件訪問數(shù)量，而非網(wǎng)絡(luò)距離和存儲(chǔ)空間，據(jù)此，本文提出基于時(shí)間序列的PDM 文件數(shù)據(jù)塊分布算法，算法根據(jù)數(shù)據(jù)塊訪問量進(jìn)行數(shù)據(jù)塊的動(dòng)態(tài)遷移，在實(shí)現(xiàn)數(shù)據(jù)塊合理分布的同時(shí)均勻分布文件數(shù)據(jù)塊副本，從而有效提高系統(tǒng)的容錯(cuò)性。

1 時(shí)間序列分析

時(shí)間序列分析方法通過對(duì)數(shù)據(jù)的動(dòng)態(tài)處理及分析，根據(jù)建模方法建立相應(yīng)的數(shù)據(jù)擬合模型去近似描述數(shù)據(jù)特點(diǎn)。通過對(duì)數(shù)據(jù)發(fā)展趨勢(shì)的預(yù)測(cè)，從而采取合理的方法實(shí)現(xiàn)有效控制的目的。文獻(xiàn) ［1］詳細(xì)介紹了時(shí)間序列的相關(guān)知識(shí)、常用時(shí)間序列模型和預(yù)測(cè)方法。

1.1 白噪聲過程

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

（1）E（Xt）＝0；

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

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

白噪聲是平穩(wěn)的時(shí)間序列，平穩(wěn)時(shí)間序列的行為不會(huì)隨著時(shí)間的變化而變化，因此可以通過過去的行為對(duì)未來的行為進(jìn)行預(yù)測(cè)。

1.2 基本時(shí)間序列模型

p階自回歸模型AR（p）

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

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

q階移動(dòng)平均模型MA（q）

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

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

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

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

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

因篇幅有限，本文僅對(duì)時(shí)間序列模型做簡(jiǎn)單介紹。時(shí)間序列分析在負(fù)載均衡預(yù)測(cè)方面被廣泛應(yīng)用。文獻(xiàn) ［2］介紹了常用的預(yù)測(cè)方法，并對(duì)常用時(shí)間序列模型的建立進(jìn)行了詳細(xì)說明。文獻(xiàn) ［3］介紹了預(yù)測(cè)模型在云計(jì)算資源管理中的應(yīng)用并展望了預(yù)測(cè)模型的發(fā)展方向。文獻(xiàn) ［4，5］分別對(duì)預(yù)測(cè)模型進(jìn)行改進(jìn)，預(yù)測(cè)精度明顯提高。文獻(xiàn) ［6］通過對(duì)集群系統(tǒng)中節(jié)點(diǎn)負(fù)載特點(diǎn)的分析，提出服務(wù)器集群負(fù)載預(yù)測(cè)模型，有效提高了集群系統(tǒng)的利用率。文獻(xiàn) ［7］介紹了時(shí)間序列模型與預(yù)測(cè)相關(guān)內(nèi)容，通過實(shí)驗(yàn)分析對(duì)比了各時(shí)序模型在網(wǎng)絡(luò)流量中的預(yù)測(cè)效果。

本文通過對(duì)數(shù)據(jù)塊訪問次數(shù)時(shí)間序列的分析，擬合出適當(dāng)?shù)臄?shù)學(xué)模型預(yù)測(cè)數(shù)據(jù)塊訪問趨勢(shì)，使用預(yù)測(cè)結(jié)果為數(shù)據(jù)塊合理分布提供依據(jù)。

2 數(shù)據(jù)塊分布算法

通常，HFDS采用機(jī)架感知策略實(shí)現(xiàn)數(shù)據(jù)塊放置，將數(shù)據(jù)塊優(yōu)先放置于本地節(jié)點(diǎn)或相同機(jī)架的節(jié)點(diǎn)中。默認(rèn)放置策略優(yōu)先考慮網(wǎng)絡(luò)傳輸代價(jià)，提供一種通用的放置策略。但在企業(yè)私有云環(huán)境下，網(wǎng)絡(luò)傳輸代價(jià)并不是影響用戶訪問質(zhì)量的關(guān)鍵因素。而且PDM 文件系統(tǒng)中用戶訪問并不是隨機(jī)進(jìn)行，現(xiàn)階段生產(chǎn)和設(shè)計(jì)相關(guān)數(shù)據(jù)的訪問量明顯大于歷史數(shù)據(jù)的訪問量。因此需要根據(jù)數(shù)據(jù)塊訪問量合理分布數(shù)據(jù)塊，以解決數(shù)據(jù)塊隨機(jī)放置造成的節(jié)點(diǎn)訪問量不均衡問題，從而實(shí)現(xiàn)集群的負(fù)載均衡。

為提高云存儲(chǔ)系統(tǒng)性能及數(shù)據(jù)的合理分布，文獻(xiàn) ［8］提出基于一致性哈希數(shù)據(jù)分布和節(jié)點(diǎn)容量感知的負(fù)載均衡方法，該策略改善了存儲(chǔ)資源負(fù)載均衡程度并優(yōu)化了系統(tǒng)整體性能。文獻(xiàn) ［9］基于節(jié)點(diǎn)網(wǎng)絡(luò)距離和數(shù)據(jù)節(jié)點(diǎn)負(fù)載兩種因素計(jì)算節(jié)點(diǎn)的負(fù)載評(píng)價(jià)值，根據(jù)評(píng)價(jià)值選擇最佳的放置節(jié)點(diǎn)。文獻(xiàn) ［10］綜合考慮節(jié)點(diǎn)的存儲(chǔ)性能和網(wǎng)絡(luò)距離兩種因素進(jìn)行數(shù)據(jù)節(jié)點(diǎn)的選擇，算法改善了數(shù)據(jù)塊放置的均衡性。文獻(xiàn) ［11］根據(jù)數(shù)據(jù)節(jié)點(diǎn)的狀態(tài)信息動(dòng)態(tài)選擇節(jié)點(diǎn)以實(shí)現(xiàn)負(fù)載均衡。

結(jié)合PDM 文件訪問特點(diǎn)和企業(yè)私有云環(huán)境優(yōu)勢(shì)，本文提出基于時(shí)間序列的PDM 文件數(shù)據(jù)塊分布算法，將數(shù)據(jù)塊訪問量作為分布依據(jù)。算法在保證節(jié)點(diǎn)訪問量平均的前提下，使文件數(shù)據(jù)塊副本均勻分布在各數(shù)據(jù)節(jié)點(diǎn)中，從而實(shí)現(xiàn)集群的負(fù)載均衡并提高系統(tǒng)的容錯(cuò)性。

為減少頻繁遷移對(duì)系統(tǒng)的影響，使用擬合數(shù)據(jù)模型對(duì)數(shù)據(jù)塊訪問量進(jìn)行多步預(yù)測(cè)。算法根據(jù)多步預(yù)測(cè)結(jié)果選擇合理的數(shù)據(jù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)塊遷移，減少頻繁數(shù)據(jù)塊遷移造成系統(tǒng)的額外開銷。

下面給出算法描述，預(yù)測(cè)步長(zhǎng)為m 步：

（1）計(jì)算當(dāng)日節(jié)點(diǎn)平均訪問量x，訪問量大于等于x的節(jié)點(diǎn)加入S隊(duì)列，小于x的節(jié)點(diǎn)加入T 隊(duì)列，計(jì)算得到S隊(duì)列和T 隊(duì)列。如果n大于m，轉(zhuǎn) （10）；

（2）如果S隊(duì)列為空或T 隊(duì)列為空，n＋＋，轉(zhuǎn) （1）；

（3）從S隊(duì)列中取出節(jié)點(diǎn)Si；

（4）從Si中取出一個(gè)數(shù)據(jù)塊賦值給變量b，找出T 隊(duì)列中保存數(shù)據(jù)塊b 所屬文件的數(shù)據(jù)塊數(shù)目最少的數(shù)據(jù)節(jié)點(diǎn)Tj；

（5）如果Tj已保存數(shù)據(jù)塊b的副本，轉(zhuǎn) （4）；

（6）數(shù)據(jù)塊b加入移動(dòng)集合中，將數(shù)據(jù)塊b中目標(biāo)節(jié)點(diǎn)數(shù)組中Tj值加1，從Si中刪除數(shù)據(jù)塊b；

（7）如果Si的訪問量小于x，則將Si從S隊(duì)列中刪除，轉(zhuǎn) （2）；

（8）如果Tj的訪問量大于等于x，則將Tj從T 隊(duì)列中刪除，轉(zhuǎn) （4）；

（9）轉(zhuǎn) （4）；

（10）如果移動(dòng)集合為空，則轉(zhuǎn) （13）；

（11）從移動(dòng)集合中取出一個(gè)數(shù)據(jù)塊賦值給變量b，選擇數(shù)據(jù)塊b的目標(biāo)數(shù)組中出現(xiàn)次數(shù)最多的節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，并將數(shù)據(jù)塊b遷移至目標(biāo)節(jié)點(diǎn)中；

（12）將數(shù)據(jù)塊b從移動(dòng)集合中刪除，轉(zhuǎn) （10）；

（13）結(jié)束。

基于時(shí)間序列的PDM 文件數(shù)據(jù)塊分布算法以平均數(shù)據(jù)節(jié)點(diǎn)訪問量為目標(biāo)。算法在數(shù)據(jù)塊移時(shí)避免文件數(shù)據(jù)塊副本集中存儲(chǔ)在某個(gè)節(jié)點(diǎn)中，使文件數(shù)據(jù)塊副本分布更加均勻，因此有效提高了系統(tǒng)的容錯(cuò)性。同時(shí)算法綜合考慮數(shù)據(jù)塊未來多日訪問量進(jìn)行遷移，有效減少了數(shù)據(jù)塊的頻繁遷移。

3 實(shí)驗(yàn)結(jié)果分析

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

數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)塊數(shù)目對(duì)比如圖1所示。從圖1中看出基于存儲(chǔ)空間分布算法使數(shù)據(jù)塊均勻分布到各數(shù)據(jù)節(jié)點(diǎn)中。默認(rèn)算法和本文算法基本實(shí)現(xiàn)數(shù)據(jù)塊均勻分布，但與基于存儲(chǔ)空間分布算法有一定差距?；诖鎯?chǔ)空間分布算法實(shí)現(xiàn)了數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)空間的合理利用，但并未解決數(shù)據(jù)節(jié)點(diǎn)訪問量不均衡問題。

圖1 數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)塊數(shù)目對(duì)比

默認(rèn)算法數(shù)據(jù)節(jié)點(diǎn)訪問量如圖2所示。默認(rèn)算法作為一種通用的數(shù)據(jù)塊放置策略能夠?qū)?shù)據(jù)塊較均勻的分布到數(shù)據(jù)節(jié)點(diǎn)中，但數(shù)據(jù)節(jié)點(diǎn)訪問量差距較大容易造成集群負(fù)載不均衡問題的出現(xiàn)。

基于存儲(chǔ)空間分布算法數(shù)據(jù)節(jié)點(diǎn)訪問量如圖3所示。算法能夠較好的實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)空間的均衡。但由于PDM文件訪問特點(diǎn)造成文件訪問次數(shù)差別較大。因此雖然數(shù)據(jù)節(jié)點(diǎn)保存數(shù)據(jù)塊數(shù)目接近，但未解決數(shù)據(jù)節(jié)點(diǎn)訪問量不均衡問題。

圖2 默認(rèn)算法數(shù)據(jù)節(jié)點(diǎn)訪問量

圖3 基于存儲(chǔ)空間分布算法數(shù)據(jù)節(jié)點(diǎn)訪問量

本文算法數(shù)據(jù)節(jié)點(diǎn)訪問量如圖4所示。算法使數(shù)據(jù)節(jié)點(diǎn)訪問量更加平均，同時(shí)讓遷移數(shù)據(jù)塊均勻分布在數(shù)據(jù)節(jié)點(diǎn)中，有效提高了集群的容錯(cuò)性。

數(shù)據(jù)塊遷移結(jié)果見表1，文件14數(shù)據(jù)塊分別被本文算法和基于存儲(chǔ)空間分布算法選中進(jìn)行遷移，因此更容易對(duì)比實(shí)驗(yàn)效果。

圖4 本文算法數(shù)據(jù)節(jié)點(diǎn)訪問量

表1 數(shù)據(jù)塊遷移結(jié)果

默認(rèn)算法隨機(jī)放置數(shù)據(jù)塊，節(jié)點(diǎn)1存儲(chǔ)了文件14全部數(shù)據(jù)塊，節(jié)點(diǎn)2存儲(chǔ)4個(gè)數(shù)據(jù)塊，因此數(shù)據(jù)塊存儲(chǔ)過于集中。本文算法和基于存儲(chǔ)空間分布算法分別對(duì)文件14進(jìn)行了數(shù)據(jù)塊遷移。本文算法將數(shù)據(jù)塊從節(jié)點(diǎn)1分別遷移至節(jié)點(diǎn)5、節(jié)點(diǎn)6，同時(shí)將數(shù)據(jù)塊從節(jié)點(diǎn)2遷移至節(jié)點(diǎn)6、節(jié)點(diǎn)4，從而使文件數(shù)據(jù)塊更均勻的分布在各數(shù)據(jù)節(jié)點(diǎn)中。而基于存儲(chǔ)空間分布算法使用存儲(chǔ)空間作為評(píng)判因素，將文件數(shù)據(jù)塊大量遷移至節(jié)點(diǎn)3中，造成節(jié)點(diǎn)3存儲(chǔ)文件的全部數(shù)據(jù)塊，并未有效解決遷移中數(shù)據(jù)塊存儲(chǔ)集中的問題。

實(shí)驗(yàn)通過數(shù)據(jù)節(jié)點(diǎn)訪問量和數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)塊數(shù)目?jī)煞矫鎸?duì)3種算法進(jìn)行了對(duì)比。默認(rèn)算法使用隨機(jī)放置策略數(shù)據(jù)塊基本均勻分布，但存在文件數(shù)據(jù)塊存儲(chǔ)集中的問題而且數(shù)據(jù)節(jié)點(diǎn)訪問量差別較大；基于存儲(chǔ)空間的數(shù)據(jù)塊分布算法能夠較好的實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)空間的平均使用，但存在與默認(rèn)算法相同的問題；本文算法實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)訪問量平均的同時(shí)減少了文件數(shù)據(jù)塊存儲(chǔ)集中的問題，有效提高了系統(tǒng)的容錯(cuò)性。

4 結(jié)束語

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

［1］WANG Yan.Applied time series analysis［M］.Beijing：Chi－na Renmin University Press，2012 （in Chinese）.［王燕.應(yīng)用時(shí)間序列分析 ［M］.北京：中國人民大學(xué)出版社，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）.［武偉，劉希玉，楊怡，等.時(shí)間序列分析方法及ARMA，GARCH 兩種常用模型 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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ì)算資源管理中的預(yù)測(cè)模型綜述 ［J］.計(jì)算機(jī)工程與設(shè)計(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）. ［高興旺，王瓊，歐陽一鳴.基于混合預(yù)測(cè)模型的負(fù)載均衡算法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(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 模型的時(shí)間序列預(yù)測(cè) ［J］.計(jì)算機(jī)與現(xiàn)代化，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）. ［喬國娟，陳光.一種基于預(yù)測(cè)模型的負(fù)載均衡算法 ［J］.計(jì)算機(jī)與現(xiàn)代化，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）. ［姜明，吳春明，張旻，等.網(wǎng)絡(luò)流量預(yù)測(cè)中的時(shí)間序列模型比較研究 ［J］.電子學(xué)報(bào)，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）. ［周 敬利，周正達(dá).改進(jìn)的云存儲(chǔ)系統(tǒng)數(shù)據(jù)分布策略 ［J］.計(jì)算機(jī)應(yīng)用，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）. ［林偉偉.一種改進(jìn)的Hadoop數(shù)據(jù)放置策略 ［J］.華南理工大學(xué)學(xué)報(bào) （自然科學(xué)版），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中的一種數(shù)據(jù)放置策略 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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.