基于預(yù)測(cè)的云計(jì)算熱點(diǎn)數(shù)據(jù)副本因子決策算法

張 松，杜慶偉，孫 靜，孫 振

(1.南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016;2.中國(guó)人民解放軍94860 部隊(duì)，江蘇 南京 210018)

0 引言

云計(jì)算的出現(xiàn)和發(fā)展，滿(mǎn)足了用戶(hù)對(duì)超大規(guī)模計(jì)算和存儲(chǔ)的需求。為了克服單點(diǎn)失效帶來(lái)的數(shù)據(jù)可用性差等問(wèn)題，HDFS 等分布式云存儲(chǔ)平臺(tái)普遍采用了多副本技術(shù)［1］。副本技術(shù)的原理就是將數(shù)據(jù)的副本復(fù)制多份并放置于集群的不同節(jié)點(diǎn)上，使得部分節(jié)點(diǎn)失效時(shí)，用戶(hù)依然可以通過(guò)其他副本訪問(wèn)資源［2］。HDFS 采用統(tǒng)一副本管理策略，默認(rèn)副本因子為3［3-4］。然而由于數(shù)據(jù)的訪問(wèn)熱度存在較大的差異［5-7］，對(duì)于熱點(diǎn)資源的訪問(wèn)競(jìng)爭(zhēng)將導(dǎo)致系統(tǒng)瓶頸，增加作業(yè)的執(zhí)行時(shí)間。因此，為了解決熱點(diǎn)數(shù)據(jù)對(duì)節(jié)點(diǎn)的訪問(wèn)壓力和集群負(fù)載的不均衡，應(yīng)該對(duì)熱點(diǎn)數(shù)據(jù)的副本因子進(jìn)行動(dòng)態(tài)調(diào)整。當(dāng)數(shù)據(jù)的熱度增加時(shí)，應(yīng)增大副本因子，以降低資源競(jìng)爭(zhēng)和網(wǎng)絡(luò)流量，減少因訪問(wèn)競(jìng)爭(zhēng)導(dǎo)致的作業(yè)執(zhí)行時(shí)間延長(zhǎng);當(dāng)數(shù)據(jù)的熱度降低時(shí)，應(yīng)降低副本因子，以節(jié)省存儲(chǔ)空間，降低維護(hù)成本。綜上所述，合理的副本因子不僅能夠提升分布式存儲(chǔ)系統(tǒng)負(fù)載的均衡性，更能提高數(shù)據(jù)的可用性和讀寫(xiě)性能。

熱點(diǎn)數(shù)據(jù)副本因子動(dòng)態(tài)調(diào)整是云計(jì)算中的一個(gè)研究熱點(diǎn)，但基于當(dāng)前熱度的副本調(diào)整不僅具有滯后性，亦會(huì)受到突發(fā)訪問(wèn)波動(dòng)的影響，因此副本因子的調(diào)整應(yīng)當(dāng)以該文件的未來(lái)熱度為依據(jù)［6，8-9］。于是，精確預(yù)測(cè)文件的未來(lái)熱度成為副本決策中至關(guān)重要的一環(huán)［5，8］。若對(duì)文件的未來(lái)熱度預(yù)估不準(zhǔn)，那么有可能創(chuàng)建過(guò)多的副本而浪費(fèi)存儲(chǔ)空間和網(wǎng)絡(luò)帶寬，也有可能創(chuàng)建過(guò)少的副本，從而無(wú)法減輕熱點(diǎn)訪問(wèn)對(duì)節(jié)點(diǎn)造成的訪問(wèn)壓力和負(fù)載傾斜［5，7］?；诖耍疚奶岢龈鶕?jù)熱點(diǎn)數(shù)據(jù)歷史訪問(wèn)特征，基于灰色預(yù)測(cè)模型預(yù)測(cè)數(shù)據(jù)的未來(lái)訪問(wèn)熱度，采用馬爾科夫預(yù)測(cè)模型修正因數(shù)據(jù)波動(dòng)和突發(fā)訪問(wèn)造成的預(yù)測(cè)偏差，并基于預(yù)測(cè)值建立有限通道服務(wù)模型，尋找滿(mǎn)足用戶(hù)需求的最小副本因子。

1 相關(guān)工作

副本技術(shù)不僅能夠減少網(wǎng)絡(luò)負(fù)載和訪問(wèn)延遲，而且還能增加存儲(chǔ)系統(tǒng)的利用效率和數(shù)據(jù)的可用性。因此，其他一些相關(guān)領(lǐng)域，諸如P2P 網(wǎng)絡(luò)，網(wǎng)格計(jì)算等也采用副本技術(shù)來(lái)增強(qiáng)系統(tǒng)性能。常見(jiàn)的副本技術(shù)有靜態(tài)副本技術(shù)和動(dòng)態(tài)副本技術(shù)。靜態(tài)副本技術(shù)在文件創(chuàng)建時(shí)固定副本個(gè)數(shù)和副本位置，并且在文件的可用周期內(nèi)副本因子無(wú)法更改，無(wú)法適應(yīng)數(shù)據(jù)熱度隨時(shí)間變化的趨勢(shì)，容易造成網(wǎng)絡(luò)擁塞和節(jié)點(diǎn)過(guò)熱，降低集群效用。動(dòng)態(tài)副本策略依據(jù)用戶(hù)需求、網(wǎng)絡(luò)狀況和副本熱度進(jìn)行動(dòng)態(tài)調(diào)整，更適合變化較大的存儲(chǔ)系統(tǒng)。近年來(lái)，云計(jì)算環(huán)境下動(dòng)態(tài)副本技術(shù)逐漸成為一個(gè)重要的研究點(diǎn)，眾多研究集中在動(dòng)態(tài)副本決策方面。

文獻(xiàn)［1］提出一種基于工作負(fù)載變化的動(dòng)態(tài)副本管理模型CDRM。該模型以提高系統(tǒng)性能、均衡負(fù)載為優(yōu)化目標(biāo)，綜合考慮存儲(chǔ)空間和訪問(wèn)模式的變化，并以節(jié)點(diǎn)的阻塞概率作為副本調(diào)整的評(píng)價(jià)指標(biāo)，動(dòng)態(tài)調(diào)整副本因子;文獻(xiàn)［5］基于對(duì)實(shí)際商業(yè)云計(jì)算平臺(tái)的運(yùn)行數(shù)據(jù)進(jìn)行分析，闡述了數(shù)據(jù)熱度的不均衡性以及熱點(diǎn)數(shù)據(jù)對(duì)MapReduce 集群的影響，強(qiáng)調(diào)了數(shù)據(jù)本地化和準(zhǔn)確預(yù)測(cè)副本熱度的重要性，為本文的研究提供了重要的理論依據(jù)。然而副本因子的決策依據(jù)文件的最大并發(fā)訪問(wèn)數(shù)，缺乏理論分析，依賴(lài)專(zhuān)家經(jīng)驗(yàn);文獻(xiàn)［6，9］充分利用文件的歷史訪問(wèn)信息決策未來(lái)熱度，并以此為基礎(chǔ)調(diào)整副本因子，提高系統(tǒng)性能和最小化存儲(chǔ)負(fù)載;文獻(xiàn)［8］以輔助資源調(diào)度提高數(shù)據(jù)本地化為研究目標(biāo)，指出數(shù)據(jù)熱度的增加易造成本地化的下降，從而加重網(wǎng)絡(luò)負(fù)載。通過(guò)充分利用非本地化任務(wù)獲取遠(yuǎn)端數(shù)據(jù)的優(yōu)勢(shì)，基于數(shù)據(jù)熱度決策數(shù)據(jù)的存留，在不增加多余網(wǎng)絡(luò)負(fù)載的同時(shí)，提高了數(shù)據(jù)的本地;文獻(xiàn)［7，10-12］以提高數(shù)據(jù)的可用性和可靠性為目標(biāo)，動(dòng)態(tài)調(diào)整副本因子，實(shí)驗(yàn)表明集群的性能和存儲(chǔ)資源的利用率都有了顯著的提高;文獻(xiàn)［13］采用灰色預(yù)測(cè)技術(shù)預(yù)測(cè)文件未來(lái)熱度，但沒(méi)有考慮文件熱度的波動(dòng)性。且在副本因子決策階段，單純依靠文件熱度是否超過(guò)平均熱度決策副本創(chuàng)建。

以上工作都沒(méi)有考慮到數(shù)據(jù)訪問(wèn)的突發(fā)波動(dòng)以及部分訪問(wèn)隨機(jī)性等狀況對(duì)熱度預(yù)測(cè)的影響。因此本文以副本因子的決策為目標(biāo)，修正數(shù)據(jù)訪問(wèn)突發(fā)波動(dòng)對(duì)預(yù)測(cè)值的影響，并建立有限通道服務(wù)模型，尋找滿(mǎn)足用戶(hù)設(shè)定文件服務(wù)策略的最小副本數(shù)。

2 熱度預(yù)測(cè)和副本因子決策

2.1 熱度預(yù)測(cè)

2.1.1 灰色預(yù)測(cè)和馬爾科夫預(yù)測(cè)

灰色預(yù)測(cè)結(jié)合馬爾科夫預(yù)測(cè)已經(jīng)被證實(shí)是一種行之有效的解決數(shù)據(jù)序列波動(dòng)較大情況下預(yù)測(cè)準(zhǔn)確度降低的時(shí)間序列預(yù)測(cè)模型。在路由節(jié)點(diǎn)行為預(yù)測(cè)［14］、經(jīng)濟(jì)指數(shù)、網(wǎng)絡(luò)流量預(yù)測(cè)［15］等領(lǐng)域得到了廣泛運(yùn)用?；疑A(yù)測(cè)模型的特點(diǎn)是樣本預(yù)測(cè)所需的數(shù)據(jù)量較小、計(jì)算簡(jiǎn)單，可以提高新信息的權(quán)重，符合副本預(yù)測(cè)的特點(diǎn)。通過(guò)累加生成來(lái)尋找數(shù)據(jù)的規(guī)律性，但對(duì)于波動(dòng)數(shù)據(jù)預(yù)測(cè)準(zhǔn)確度不高。通過(guò)使用Markov模型對(duì)預(yù)測(cè)結(jié)果進(jìn)行修正，可以達(dá)到較高的預(yù)測(cè)準(zhǔn)確度。

而其他預(yù)測(cè)算法，諸如神經(jīng)網(wǎng)絡(luò)模型［16］、小波等，需要大量樣本空間進(jìn)行訓(xùn)練，并且對(duì)于神經(jīng)網(wǎng)絡(luò)的層次設(shè)置依賴(lài)專(zhuān)家經(jīng)驗(yàn)［14］，在數(shù)據(jù)量較小的情況下，訓(xùn)練精度不高，準(zhǔn)確度無(wú)法保證。ARMA 預(yù)測(cè)模型［17］依賴(lài)于對(duì)參數(shù)的準(zhǔn)確估計(jì)，數(shù)據(jù)的突發(fā)波動(dòng)會(huì)影響數(shù)據(jù)發(fā)展的規(guī)律性，對(duì)于預(yù)測(cè)的準(zhǔn)確性造成較大的干擾。

2.1.2 灰色預(yù)測(cè)GM(1，1)模型的建立

灰色預(yù)測(cè)的目的是預(yù)測(cè)文件在未來(lái)時(shí)刻的訪問(wèn)熱度，原始數(shù)據(jù)序列為該文件在前n 個(gè)等時(shí)距內(nèi)的訪問(wèn)頻次。具體建模過(guò)程如下:

2)對(duì)原始訪問(wèn)頻次序列進(jìn)行累加處理，尋找其中蘊(yùn)含的規(guī)律性:

3)對(duì)累加后的訪問(wèn)頻次序列建立GM(1，1)模型的一階微分方程，其相應(yīng)的白化微分方程為:

其中，a 和b 為待識(shí)別常量，a 為發(fā)展系數(shù)，b 為灰作用量。

采用最小二乘法求得待識(shí)別常量的估計(jì)值:

其中:

λ 為新舊數(shù)據(jù)的權(quán)重，為突出新數(shù)據(jù)優(yōu)先的思想，即最近的數(shù)據(jù)訪問(wèn)特征應(yīng)當(dāng)具有更高的權(quán)重，λ 取值0.75。

4)將求得的估計(jì)值代入公式(4)，得訪問(wèn)頻次的時(shí)間響應(yīng)函數(shù)為:

2.1.3 對(duì)預(yù)測(cè)數(shù)據(jù)的馬爾科夫修正

馬爾科夫預(yù)測(cè)根據(jù)系統(tǒng)的初始狀態(tài)和狀態(tài)轉(zhuǎn)移概率，預(yù)測(cè)未來(lái)一段內(nèi)系統(tǒng)可能處于的狀態(tài)。由于用戶(hù)訪問(wèn)的隨機(jī)性和數(shù)據(jù)熱度變化的突發(fā)性，灰色預(yù)測(cè)可能存在較大偏差，因此本文采用馬爾科夫模型修正因訪問(wèn)熱度的波動(dòng)造成的預(yù)測(cè)偏差。具體步驟如下:

1)首先計(jì)算擬合值與實(shí)際值之間的相對(duì)殘差。

2)根據(jù)相對(duì)殘差的大小以及檢驗(yàn)精度對(duì)殘差的要求，將相對(duì)殘差劃分成6 個(gè)狀態(tài)區(qū)間，具體狀態(tài)如表1 所示。

表1 狀態(tài)及其相應(yīng)狀態(tài)區(qū)間

3)計(jì)算狀態(tài)轉(zhuǎn)移概率。

其中，nij(k)表示狀態(tài)Ei 經(jīng)過(guò)k 步到狀態(tài)Ej 出現(xiàn)的次數(shù)，且ni為Ei 出現(xiàn)的次數(shù)。于是可得到一步狀態(tài)轉(zhuǎn)移概率矩陣為:

其中，m 為狀態(tài)數(shù)。

通過(guò)狀態(tài)轉(zhuǎn)移概率矩陣和當(dāng)前時(shí)間段擬合值的狀態(tài)，可以預(yù)測(cè)下一時(shí)刻灰色預(yù)測(cè)值的相對(duì)殘差的狀態(tài)。取相對(duì)殘差狀態(tài)區(qū)間的中值作為灰色預(yù)測(cè)值的修正值，具體公式見(jiàn)式(10):

2.2 副本因子決策

通過(guò)前述預(yù)測(cè)模型，得到了一個(gè)相對(duì)較為精準(zhǔn)的文件熱度值，下面通過(guò)文件的未來(lái)熱度建立有限通道服務(wù)模型，依據(jù)用戶(hù)設(shè)定的訪問(wèn)競(jìng)爭(zhēng)概率，計(jì)算合適的副本因子。為保證數(shù)據(jù)的可用性，采用HDFS 默認(rèn)的副本因子數(shù)作為文件的最小副本因子。

HDFS 分布式存儲(chǔ)平臺(tái)中，如果同時(shí)訪問(wèn)某一文件的作業(yè)數(shù)量超過(guò)該文件的副本數(shù)，那么部分作業(yè)對(duì)數(shù)據(jù)的訪問(wèn)將產(chǎn)生競(jìng)爭(zhēng)，或者從遠(yuǎn)端讀取數(shù)據(jù)［5］，此時(shí)必然增加作業(yè)的執(zhí)行時(shí)間和網(wǎng)絡(luò)負(fù)載。文獻(xiàn)［5］通過(guò)對(duì)實(shí)際商用集群的分析指出對(duì)熱點(diǎn)數(shù)據(jù)的訪問(wèn)競(jìng)爭(zhēng)將導(dǎo)致作業(yè)的平均執(zhí)行時(shí)間延長(zhǎng)16%。

考慮某一熱點(diǎn)文件訪問(wèn)分布情況。由于作業(yè)的執(zhí)行相互干擾導(dǎo)致執(zhí)行時(shí)間的波動(dòng)性和數(shù)據(jù)訪問(wèn)到達(dá)時(shí)刻的隨機(jī)性，因此可以假設(shè)時(shí)間間隔T 內(nèi)作業(yè)的執(zhí)行時(shí)間服從參數(shù)為μ 的負(fù)指數(shù)分布，并假設(shè)數(shù)據(jù)訪問(wèn)到達(dá)的時(shí)刻符合泊松流。其中1/μ 表示作業(yè)的平均執(zhí)行時(shí)間，該值可通過(guò)統(tǒng)計(jì)作業(yè)的執(zhí)行時(shí)間并計(jì)算均值獲取。即單位時(shí)間內(nèi)有k 次訪問(wèn)的概率為:

其中λ 表示單位時(shí)間t'內(nèi)的平均訪問(wèn)頻次，該值可由預(yù)測(cè)訪問(wèn)頻次計(jì)算得知。設(shè)N(t)表示在時(shí)間區(qū)間［0，t)內(nèi)的訪問(wèn)頻次(t ＞0)，那么{N(t)，t≥0}就構(gòu)成了一個(gè)符合生滅過(guò)程的有限通道服務(wù)模型(M/M/r/∞)。副本因子的決策轉(zhuǎn)化為尋找滿(mǎn)足用戶(hù)設(shè)定訪問(wèn)競(jìng)爭(zhēng)概率的最小通道數(shù)r。為得到N(t)的分布Pn(t)=P{N(t)=n}，n=0，1，2，...，需獲得系統(tǒng)到達(dá)平衡后的平穩(wěn)分布，記做Pn，n=0，1，2，...。

由生滅過(guò)程理論可知單通道平穩(wěn)狀態(tài)的分布為:

在多通道服務(wù)模型中，通道數(shù)r 即為當(dāng)前副本因子。有λn=λ，n=0，1，2，…，且:記。

注意到只有當(dāng)ρr＜1 時(shí)，該模型才有意義。因此，需修正當(dāng)前通道數(shù)r 值為。

由公式(12)～公式(14)，根據(jù)生滅過(guò)程理論得:

公式(16)給出了在平穩(wěn)分布條件下，該熱點(diǎn)文件同一時(shí)刻文件并發(fā)訪問(wèn)為n 的概率。當(dāng)n≥r 時(shí)，系統(tǒng)中對(duì)數(shù)據(jù)的并發(fā)訪問(wèn)大于或等于通道個(gè)數(shù)。這時(shí)，新來(lái)的數(shù)據(jù)訪問(wèn)必然將產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)，因此記訪問(wèn)競(jìng)爭(zhēng)概率為:

用戶(hù)基于訪問(wèn)競(jìng)爭(zhēng)概率Pc劃分文件服務(wù)等級(jí)。對(duì)于高優(yōu)先級(jí)文件或高級(jí)用戶(hù)文件，可賦予較小的訪問(wèn)競(jìng)爭(zhēng)概率，以降低并發(fā)訪問(wèn)競(jìng)爭(zhēng)帶來(lái)的執(zhí)行時(shí)間延長(zhǎng)，為用戶(hù)提供高質(zhì)量的服務(wù)，此時(shí)需要更大的副本因子，以空間換時(shí)間。對(duì)于低優(yōu)先級(jí)文件或臨時(shí)用戶(hù)文件，可賦予較大的訪問(wèn)競(jìng)爭(zhēng)概率，容許高并發(fā)對(duì)作業(yè)執(zhí)行時(shí)間的延長(zhǎng)。

對(duì)于某一熱點(diǎn)文件，基于用戶(hù)設(shè)定的訪問(wèn)競(jìng)爭(zhēng)概率，代入公式(18)，計(jì)算滿(mǎn)足用戶(hù)需求的最小副本因子。

3 實(shí)驗(yàn)分析

測(cè)試環(huán)境包括3 個(gè)機(jī)架共9 個(gè)節(jié)點(diǎn)組成，每個(gè)機(jī)架都有1 臺(tái)交換機(jī)，Namenode 節(jié)點(diǎn)位于機(jī)架B 中編號(hào)為3 的節(jié)點(diǎn)。所有節(jié)點(diǎn)安裝Ubuntu12.04 操作系統(tǒng)，其拓?fù)浣Y(jié)構(gòu)如圖1 所示。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

實(shí)驗(yàn)采用的測(cè)試用例為Hadoop 云計(jì)算平臺(tái)自帶的WordCount 例程。本實(shí)驗(yàn)?zāi)繕?biāo)是為了驗(yàn)證副本動(dòng)態(tài)變化對(duì)系統(tǒng)性能的影響，由于集群環(huán)境較小，為使實(shí)驗(yàn)結(jié)果更加明顯，將HDFS 的默認(rèn)副本因子設(shè)定為2。用戶(hù)設(shè)定訪問(wèn)競(jìng)爭(zhēng)概率為10%，由于作業(yè)的執(zhí)行時(shí)間大約為10 分鐘，因此，可以設(shè)定等時(shí)距間隔T=10 min。作業(yè)的到達(dá)模擬文件的熱度增減以及突發(fā)訪問(wèn)。實(shí)驗(yàn)從副本數(shù)的動(dòng)態(tài)變化、網(wǎng)絡(luò)流量以及作業(yè)的完成時(shí)間來(lái)評(píng)價(jià)現(xiàn)有HDFS 靜態(tài)副本管理策略與本文的動(dòng)態(tài)副本管理策略。這里引出了副本管理中的副本放置策略的問(wèn)題，而該問(wèn)題超出了本研究范疇，將在后續(xù)研究中討論該問(wèn)題。本實(shí)驗(yàn)新增副本的放置采用隨機(jī)放置的策略，并遵循不同副本不能放置在同一數(shù)據(jù)節(jié)點(diǎn)的原則。2 種副本管理策略下，調(diào)度算法均采用容量調(diào)度器。用Default 表示HDFS 的靜態(tài)副本因子策略用DR2P(Dynamic Replicas based on Predicted Popularity)表示本文的動(dòng)態(tài)副本因子策略。

圖2 副本數(shù)

圖2 為默認(rèn)HDFS 副本策略和機(jī)制下，文件的副本數(shù)變化的示意圖，其中橫坐標(biāo)表示時(shí)間間隔序號(hào)，從第10 個(gè)時(shí)間間隔開(kāi)始觀察，縱坐標(biāo)表示熱點(diǎn)文件的副本個(gè)數(shù)。由圖2 可知，當(dāng)文件的訪問(wèn)熱度增加時(shí)，文件的副本數(shù)增加，以降低作業(yè)執(zhí)行時(shí)的訪問(wèn)競(jìng)爭(zhēng)對(duì)作業(yè)執(zhí)行時(shí)間的影響，當(dāng)文件的訪問(wèn)熱度降低時(shí)，算法計(jì)算出滿(mǎn)足訪問(wèn)競(jìng)爭(zhēng)的最低副本數(shù)，此時(shí)文件的副本數(shù)降低，節(jié)約了存儲(chǔ)空間和系統(tǒng)一致性維護(hù)的難度。而現(xiàn)有的HDFS 副本策略下，副本的數(shù)目保持不變。

圖3 網(wǎng)絡(luò)流量

圖3 為現(xiàn)有HDFS 和本文副本管理機(jī)制下，數(shù)據(jù)節(jié)點(diǎn)之間的數(shù)據(jù)傳輸量示意圖，網(wǎng)絡(luò)流量的統(tǒng)計(jì)宏觀上以非本地化任務(wù)引起的網(wǎng)絡(luò)負(fù)載為基準(zhǔn)，統(tǒng)計(jì)依據(jù)為熱點(diǎn)數(shù)據(jù)的熱度增加導(dǎo)致非本地化任務(wù)的增多。從圖3 中可以看出，在文件被頻繁訪問(wèn)時(shí)，數(shù)據(jù)節(jié)點(diǎn)間數(shù)據(jù)傳輸頻繁，網(wǎng)絡(luò)流量增加。通過(guò)本文的動(dòng)態(tài)副本管理策略，系統(tǒng)為熱點(diǎn)數(shù)據(jù)動(dòng)態(tài)創(chuàng)建多余副本，相較于現(xiàn)有HDFS 下默認(rèn)的靜態(tài)副本管理策略，在文件被熱點(diǎn)訪問(wèn)期間，系統(tǒng)的網(wǎng)絡(luò)流量明顯下降。

圖4 作業(yè)完成時(shí)間

圖4 為默認(rèn)HDFS 靜態(tài)副本策略和本文動(dòng)態(tài)副本策略下，作業(yè)執(zhí)行時(shí)間的對(duì)比。從圖4 中可以得知，在文件的熱度較低時(shí)，數(shù)據(jù)訪問(wèn)頻次較少，此時(shí)為非熱點(diǎn)數(shù)據(jù)，副本數(shù)沒(méi)有增加，作業(yè)的執(zhí)行時(shí)間與靜態(tài)副本策略相比沒(méi)有明顯變化。當(dāng)文件熱度較高時(shí)，并發(fā)訪問(wèn)發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)，此時(shí)文件的副本數(shù)增加，以降低競(jìng)爭(zhēng)，相較于靜態(tài)副本策略，作業(yè)的執(zhí)行時(shí)間有相應(yīng)的減少。

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有的HDFS 副本管理策略沒(méi)有考慮文件熱度的不均衡性，在文件的生存周期內(nèi)創(chuàng)建固定數(shù)目的副本，無(wú)法滿(mǎn)足現(xiàn)實(shí)環(huán)境中文件熱度隨時(shí)間周期性規(guī)律波動(dòng)的情況，本文提出根據(jù)數(shù)據(jù)的最近訪問(wèn)特征，建立灰色預(yù)測(cè)模型，并采用馬爾科夫預(yù)測(cè)模型修正因數(shù)據(jù)波動(dòng)和突發(fā)訪問(wèn)造成的預(yù)測(cè)偏差，并基于預(yù)測(cè)熱度建立有限通道服務(wù)模型、決策最優(yōu)副本因子。實(shí)驗(yàn)表明，較之現(xiàn)有的副本管理策略和實(shí)時(shí)熱度調(diào)整策略，本文的副本因子決策算法可以有效減少熱點(diǎn)數(shù)據(jù)的訪問(wèn)沖突，降低熱點(diǎn)數(shù)據(jù)作業(yè)的執(zhí)行時(shí)間和網(wǎng)絡(luò)負(fù)載。

［1］Wei Qingsong，Veeravalli B，Gong Bozhao，et al.CDRM:A cost-effective dynamic replication management scheme for cloud storage cluster［C］// IEEE International Conference on Cluster Computing(CLUSTER).2010:188-196.

［2］王意潔，孫偉東，周松，等.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)［J］.軟件學(xué)報(bào)，2012，23(4):962-986.

［3］White Tom.Hadoop:The Definitive Guide［M］.O'Reilly Media，Inc.，2009.

［4］Kala Karun A，Chitharanjan K.A review on Hadoop—HDFS infrastructure extensions［C］// IEEE Conference on Information ＆ Communication Technologies(ICT).2013:132-137.

［5］Ananthanarayanan G，Agarwal S，Kandula S，et al.Scarlett:Coping with skewed content popularity in mapreduce clusters［C］// Proceedings of the 6th ACM Conference on Computer Systems.2011:287-300.

［6］Kousiouris G，Vafiadis G，Varvarigou T.Enabling proactive data management in virtualized Hadoop clusters based on predicted data activity patterns［C］// IEEE 8th International Conference on P2P，Parallel，Grid，Cloud and Internet Computing(3PGCIC).2013:1-8.

［7］孫大為，常桂然，高尚，等.Modeling a dynamic data replication strategy to increase system availability in cloud computing environments［J］.Journal of Computer Science and Technology，2012，27(2):256-272.

［8］Abad C L，Lu Y，Campbell R H.DARE:Adaptive data replication for efficient cluster scheduling［C］// IEEE International Conference on Cluster Computing (CLUSTER).2011:159-168.

［9］Wang Zhe，Li Tao，Xiong Naiyue，et al.A novel dynamic network data replication scheme based on historical access record and proactive deletion［J］.The Journal of Supercomputing，2012，62(1):227-250.

［10］Shen Chunhui，Lu Weiming，Wu Jiangqin，et al.A digitallibrary architecture supporting massive small files and efficient replica maintenance［C］// Proceedings of the 10th Annual Joint Conference on Digital Libraries.2010:391-392.

［11］Li Wendong，Yang Yun，Yuan Dong.A novel cost-effective dynamic data replication strategy for reliability in cloud data centres［C］// IEEE 9th International Conference on Dependable，Autonomic and Secure Computing(DASC).2011:496-502.

［12］Khaneghah E M，Mirtaheri S L，Grandinetti L，et al.A Dynamic Replication Mechanism to Reduce Response-Time of I/O Operations in High Performance Computing Clusters［C］// IEEE International Conference on Social Computing(SocialCom).2013:738-743.

［13］陶永才，張寧寧，石磊，等.異構(gòu)環(huán)境下云計(jì)算數(shù)據(jù)副本動(dòng)態(tài)管理研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34(7):1487-1492.

［14］夏怒，李偉，羅軍舟，等.一種基于波動(dòng)類(lèi)型識(shí)別的路由節(jié)點(diǎn)行為預(yù)測(cè)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37(2):326-334.

［15］溫祥西，孟相如，馬志強(qiáng)，等.小時(shí)間尺度網(wǎng)絡(luò)流量混沌性分析及趨勢(shì)預(yù)測(cè)［J］.電子學(xué)報(bào)，2012，40(8):1609-1616.

［16］周開(kāi)利，康耀紅.神經(jīng)網(wǎng)絡(luò)模型及其MATLAB 仿真程序設(shè)計(jì)［M］.北京:清華大學(xué)出版社，2005.

［17］Box G E，Jenkins G M，Reinsel G C.Time Series Analysis:Forecasting and Control［M］.John Wiley ＆ Sons，2013.