馬爾科夫決策過程在移動端云存儲策略中的應(yīng)用

　　摘要: 針對傳統(tǒng)移動端云存儲系統(tǒng)數(shù)據(jù)量急劇增加時對存儲效率產(chǎn)生嚴(yán)重影響的實(shí)際情況，從理論上對移動端云存儲的存儲狀態(tài)進(jìn)行分析，提出了一種基于馬爾科夫的移動端云存儲策略，該策略以節(jié)點(diǎn)存儲代價的量化描述為基礎(chǔ)，引入馬爾科夫決策理論并結(jié)合存儲節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移，選擇最優(yōu)存儲節(jié)點(diǎn)實(shí)現(xiàn)移動端云存儲訪問。通過仿真實(shí)驗(yàn)對該存儲策略進(jìn)行了驗(yàn)證，結(jié)果表明，當(dāng)數(shù)據(jù)大小發(fā)生改變時，該存儲策略能夠準(zhǔn)確預(yù)測并將數(shù)據(jù)實(shí)時調(diào)度到合適的存儲組機(jī)群的存儲節(jié)點(diǎn)上，有效降低因數(shù)據(jù)大小不同而導(dǎo)致存儲效率降低的影響。

　　關(guān)鍵詞: 馬爾科夫; 存儲狀態(tài); 云存儲策略; 存儲代價; 決策理論; 狀態(tài)轉(zhuǎn)移

　　0 引言

　　傳統(tǒng)移動端云存儲系統(tǒng)的存儲密度不大，綜合存儲效率比較低，不能很好地適應(yīng)各種不同的應(yīng)用環(huán)境，且不能保證云數(shù)據(jù)的完整性和機(jī)密性，因此將敏感數(shù)據(jù)直接存放在云上是非常危險的。云存儲系統(tǒng)中的存儲過程近似為馬爾科夫過程，該文提出一種基于馬爾科夫的云存儲策略以實(shí)現(xiàn)移動端可靠安全地存儲，從概率的角度來衡量各個存儲節(jié)點(diǎn)的存儲代價并綜合調(diào)度，選擇最優(yōu)存儲節(jié)點(diǎn)實(shí)現(xiàn)云存儲訪問。

　　當(dāng)移動終端發(fā)出請求時，基于馬爾科夫的云存儲策略選擇存儲代價最優(yōu)的存儲節(jié)點(diǎn)能夠有效節(jié)省時間，提高存儲效率，同時保證系統(tǒng)的負(fù)載均衡?；隈R爾科夫的云存儲策略改進(jìn)優(yōu)化了傳統(tǒng)云存儲系統(tǒng)的不足，提出可靠性模型，最后通過一系列仿真實(shí)驗(yàn)驗(yàn)證該文提出的基于馬爾科夫的云存儲策略具有較高的可靠性。

　　1 移動端云系統(tǒng)副本策略

　　傳統(tǒng)的移動端云存儲系統(tǒng)使用多副本機(jī)制，當(dāng)移動終端發(fā)出請求時選擇最近的副本，最近的節(jié)點(diǎn)是指該節(jié)點(diǎn)存儲代價最低。云系統(tǒng)副本策略包括動態(tài)副本策略( Dynamic Replication Strategies，DRS) 和靜態(tài)副本策略( Static Replication Strategies，SRS) 。靜態(tài)副本策略指的是副本個數(shù)、放置的位置從創(chuàng)建開始到數(shù)據(jù)失效期間都是固定不變的，而動態(tài)副本策略指的是系統(tǒng)運(yùn)行中根據(jù)系統(tǒng)性能、負(fù)載等各種因素的變化，實(shí)時調(diào)整副本個數(shù)及放置位置等，包括小文件動態(tài)副本策略( Small File Dynamic Replication Strategies，SFDRS ) 和大文件動態(tài)副本策略 ( Large File Dynamic Replication Strategies，LFDRS) 。

　　1. 1 小文件副本策略

　　不超過 10 MB 的文件定義為小文件，小文件副本策略采用 SQLServer 關(guān)系數(shù)據(jù)庫。接收到移動終端傳來的文件后，調(diào)度機(jī)群會先判斷其大小，一旦確認(rèn)是小文件，則交給關(guān)系數(shù)據(jù)庫機(jī)群處理，并且將文件相關(guān)屬性存儲到數(shù)據(jù)庫表中。數(shù)據(jù)庫機(jī)群動態(tài)選擇最優(yōu)節(jié)點(diǎn)，即將機(jī)群中負(fù)載最輕的數(shù)據(jù)庫服務(wù)器選出來存儲文件，并保存一份副本確保數(shù)據(jù)的可靠性。文件所存放的數(shù)據(jù)庫服務(wù)器 IP 地址將被存儲到主服務(wù)器中，查詢時需先從主服務(wù)器獲取文件存放的服務(wù)器 IP，然后再與數(shù)據(jù)庫服務(wù)器交互。小文件存放處理模式

　　1. 2 大文件副本策略

　　當(dāng)文件超過 10 MB 時稱之為大文件，大文件副本策略采用存儲組機(jī)群處理，存儲組機(jī)群系統(tǒng)采用全連接網(wǎng)絡(luò)，

　　存儲組機(jī)群的存儲空間統(tǒng)一編址且為環(huán)狀結(jié)構(gòu)。通過虛擬連續(xù)存儲空間的方式，存儲組機(jī)群可以抵消不同 PC 機(jī)間設(shè)備性能的不同。使用哈希算法 - 信息摘要算法 5( Message - Digest Algorithm 5， MD5) 實(shí)現(xiàn)地址轉(zhuǎn)換，通過 MD5 算法將實(shí)際物理地址處理轉(zhuǎn)換為 32 位信息串，然后再存儲到虛擬連續(xù)地址中，抵消設(shè)備間性能的不同。MD5 算法將地址轉(zhuǎn)換映射到存儲組機(jī)群的虛擬存儲空間環(huán)中，將數(shù)據(jù)存儲到第一個被映射的 PC 設(shè)備中，并且備份到相鄰的 2 個 PC 設(shè)備上。

　　存儲組機(jī)群采用 PC 作為存儲介質(zhì)，PC 可靠性不高，有時還會存儲失效，因此需要存儲副本確保數(shù)據(jù)可靠。當(dāng)某節(jié)點(diǎn)故障時，相鄰節(jié)點(diǎn)會及時修改路由信息并將該設(shè)備存儲的所有信息進(jìn)行重新備份。

　　2 基于馬爾科夫決策的移動端云存儲策略

　　在傳統(tǒng)的云存儲副本策略中，只有主副本錯誤了才請求備用副本，不考慮地域，極大地影響存儲速度。將馬爾科夫轉(zhuǎn)移概率應(yīng)用到移動端云存儲策略，從概率角度衡量各個存儲節(jié)點(diǎn)的存儲代價，預(yù)測某時刻云存儲策略的存儲概率，選擇最優(yōu)存儲節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)存儲。

　　基于馬爾科夫決策的移動端云存儲策略( Cloud Storage Strategy Based on Markov，CSSBM) 首先提出對應(yīng)的存儲狀態(tài)空間轉(zhuǎn)移表達(dá); 然后根據(jù)云存儲系統(tǒng)的歷史數(shù)據(jù)樣本得到狀態(tài)轉(zhuǎn)移概率矩陣。利用狀態(tài)轉(zhuǎn)移概率矩陣和當(dāng)前收斂的存儲狀態(tài)矩陣，快速預(yù)測未來某個時刻云系統(tǒng)存儲狀態(tài)的存儲概率實(shí)現(xiàn)存儲。

　　2. 1 有限狀態(tài)空間及狀態(tài)分布

　　在云系統(tǒng)中，存儲組機(jī)群中的服務(wù)器叫做存儲節(jié)點(diǎn)，每個存儲節(jié)點(diǎn)都可以存儲大文件、中文件以及小文件。由于存儲組機(jī)群中存儲節(jié)點(diǎn)的硬件性能、負(fù)載情況以及網(wǎng)絡(luò)鏈路狀態(tài)都不同，每個存儲節(jié)點(diǎn)存儲大、中、小 3 種不同類別的數(shù)據(jù)所耗費(fèi)的成本也不同，導(dǎo)致每個存儲節(jié)點(diǎn)存儲不同大小文件的存儲代價不同，一般選擇代價最低的存儲節(jié)點(diǎn)。

　　根據(jù)以上分析，將存儲組機(jī)群中存儲節(jié)點(diǎn)存儲 3 種不同大小的數(shù)據(jù)的存儲過程視為離散狀態(tài)空間 S，數(shù)據(jù)存儲過程中下一個存儲節(jié)點(diǎn)的選取只與當(dāng)前存儲節(jié)點(diǎn)的存儲代價有關(guān)，因而云系統(tǒng)的數(shù)據(jù)存儲過程符合馬爾科夫鏈的特征。該文所提出的云存儲策略中，狀態(tài)空間 S 表示為以下 3 種:

　　1) 狀態(tài) 1( 小文件狀態(tài))

　　在小文件狀態(tài)下，選擇存儲組機(jī)群中存儲小文件的最優(yōu)存儲節(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)存儲。

　　2) 狀態(tài) 2( 中文件狀態(tài))

　　在中文件狀態(tài)下，會從存儲組機(jī)群中選擇介于小文件和大文件之間的最優(yōu)存儲節(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)存儲。

　　3) 狀態(tài) 3( 大文件狀態(tài))

　　在大文件狀態(tài)下，會選擇存儲組機(jī)群中存儲大文件的最優(yōu)存儲節(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)存儲。

　　基于馬爾科夫的云存儲的狀態(tài)空間定義為 S = { s1，s2，s3 } 。si ( i = 1，2，3) 分別表示機(jī)群中各個存儲節(jié)點(diǎn)實(shí)現(xiàn)小文件、中文件和大文件存儲的存儲代價。

　　進(jìn)行云存儲策略的研究，存儲方案狀態(tài)的劃分以適中為宜。顯然，該文定義的存儲組機(jī)群存儲大、中、小文件 3 種狀態(tài)比較簡捷，能很好地滿足云系統(tǒng)中對數(shù)據(jù)存儲的要求。

　　狀態(tài)分布 R 為某一存儲節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)存儲的存儲代價，根據(jù)存儲節(jié)點(diǎn)在大、中、小 3 種不同狀態(tài)下的存儲代價，得到 ti時刻云系統(tǒng)的存儲狀態(tài)分布

　　2. 2 狀態(tài)轉(zhuǎn)移概率矩陣

　　根據(jù)前文分析可知，存儲組機(jī)群中的每個存儲節(jié)點(diǎn)均有存儲 3 種不同大小文件的存儲代價，若云系統(tǒng)中某個存儲節(jié)點(diǎn)存儲大、中、小文件的綜合存儲代價越高，使用該節(jié)點(diǎn)存儲數(shù)據(jù)的可能性越小; 相反，存儲大、中、小文件的存儲代價越小則被選中的可能性越大。

　　2. 3 基于 Markov 云存儲策略算法

　　對于數(shù)據(jù)在不同節(jié)點(diǎn)存儲的存儲代價，獲得系統(tǒng)當(dāng)前時刻的存儲代價矩陣，即系統(tǒng)的狀態(tài)分布矩陣

　　2. 4 云存儲策略的可靠性分析

　　假設(shè)系統(tǒng)可靠性為 A，采取不同存儲策略實(shí)現(xiàn)存儲的時間取反并經(jīng)過歸一處理后的值為 Aj ，依據(jù)馬爾科夫決策不同節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)存儲的存儲代價經(jīng)過歸一處理后的值為 Ak，云存儲的存儲狀態(tài)數(shù)為 n，則系統(tǒng)的可靠性模型用式( 6) 表示:

　　A =[1 –( 1 - Aj ) n ][1 –( 1 - Ak ) n ] ( 6)

　　從可靠性模型得出當(dāng)時間 t→∞ 時，云系統(tǒng)的存儲代價也趨近于某一穩(wěn)定值，此時存儲策略的狀態(tài)趨于穩(wěn)定，當(dāng) Aj和 Ak的值越接近于 1，且存儲狀態(tài)數(shù) n 越大，則云存儲策略越可靠。

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

　　論文使用 python 語言驗(yàn)證 CSSBM 存儲策略算法。用蒙特卡羅模擬 8000 次樣本，模擬時間間隔為 300 個，統(tǒng)計(jì)存儲狀態(tài)在這些間隔內(nèi)的分布及相鄰時間間隔存儲狀態(tài)的變化情況，得到存儲策略的狀態(tài)轉(zhuǎn)移概率矩陣

　　通過存儲狀態(tài)分布矩陣 R( i) 可快速選出存儲代價最低的節(jié)點(diǎn)以實(shí)現(xiàn)數(shù)據(jù)存儲。系統(tǒng)對同等大小的文 件，當(dāng)采用不同的算法 SFDRS，LFDRS 或 CSSBM 分別進(jìn)行處理的時間數(shù)據(jù)。

　　SFDRS 算法對比 LFDRS 存儲時間相對較短，對于文件傳輸總的時間損耗和用戶體驗(yàn)影響不大。 LFDRS 存儲耗時相對較長，會對系統(tǒng)造成較大的額外時 間 開 銷。CSSBM 對文件存儲的時間相對 SFDRS 沒有明顯增加，存儲效率較高。

　　利用前面提出的可靠性模型式( 6) ，結(jié)合表 1 中對同 等 大 小 的 文 件，采用不同的策略 SFDRS、 LFDRS 或 CSSBM 算法進(jìn)行數(shù)據(jù)存儲，對時間取反并經(jīng)過歸一處理后的值 Aj越接近 1，同理經(jīng)過歸一處理后的存儲代價 Ak也越接近 1，且存儲狀態(tài)數(shù)目越多，系統(tǒng)的可靠性也就越高。連續(xù)采樣移動端 1 小時內(nèi)使用不同策略的存儲時間和傳輸速率，得到不同策略的可靠性對比圖，如圖 5 所示。

　　通過對圖 5 中的數(shù)據(jù)對比發(fā)現(xiàn)，使用 SFDRS 算法存儲系統(tǒng)的可靠性值基本維持在 1，系統(tǒng)可靠性相對較高，即使用 SFDRS 存儲數(shù)據(jù)對于文件傳輸和用戶體驗(yàn)影響不大。LFDRS 算法耗時相對較長，且系統(tǒng)可靠性值抖動較大，使用 LFDRS 存儲數(shù)據(jù)時系統(tǒng)可靠性較低。CSSBM 存儲數(shù)據(jù)時間相對 SFDRS 沒有明顯增加，可靠性的值也維持在 1 左右，可見，使用 CSSBM 存儲數(shù)據(jù)，系統(tǒng)的可靠性相對較高。

　　通過仿真實(shí)驗(yàn)驗(yàn)證了基于馬爾科夫的云存儲策略具有較高的可靠性，該存儲策略能夠依據(jù)存儲狀態(tài)矩陣和狀態(tài)轉(zhuǎn)移概率矩陣實(shí)現(xiàn)存儲狀態(tài)預(yù)測，將數(shù)據(jù)實(shí)時調(diào)度到存儲代價最低的存儲節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)存儲，有效節(jié)省時間，降低因文件大小不同而導(dǎo)致存儲效率降低的影響。

　　4 結(jié)語

　　該文用馬爾科夫解決云系統(tǒng)的存儲調(diào)度，預(yù)測數(shù)據(jù)的安全存儲。文章首先將云系統(tǒng)的存儲狀態(tài)劃分為 3 個，然后分階段使用馬爾科夫決策，并根據(jù)存儲節(jié)點(diǎn)的存儲代價獲取當(dāng)前時刻的存儲狀態(tài)矩陣，在足夠多樣本數(shù)量的支持下，統(tǒng)計(jì)出狀態(tài)轉(zhuǎn)移概率矩陣，快速預(yù)測未來某時刻云系統(tǒng)的存儲狀態(tài)概率，選擇最優(yōu)存儲節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)存儲。最后通過仿真實(shí)驗(yàn)表明當(dāng)數(shù)據(jù)大小發(fā)生改變時，該存儲策略能夠準(zhǔn)確預(yù)測并將數(shù)據(jù)實(shí)時調(diào)度到存儲代價最低的節(jié)點(diǎn)，有效降低因數(shù)據(jù)量大小不同而采用相同的存儲方法造成的影響，驗(yàn)證了將馬爾科夫決策應(yīng)用在移動端云系統(tǒng)中的存儲策略具有較高的可靠性。相關(guān)論文還可參考：淺析云計(jì)算與云存儲技術(shù)研究

　　參考文獻(xiàn):

　　[1] 張迪，朱立谷，侯振宇，等. 基于 WEB 的移動端云存儲技術(shù)研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2010，46( 36) : 66.

　　[2] Iliadis I，Sotnikov D，Ta - Shma P，et al. Reliability of georeplicated cloud storage systems[C]. In: 2014 IEEE 20th Pacific Rim International Symposium on Dependable Computing，2014: 169.

　　[3] 徐婧，楊壽保，王淑玲，等. CDRS: 云存儲中一種代價驅(qū)動的自適應(yīng)副本策略[J]. 中國科學(xué)院研究生院學(xué)報， 2011，8( 6) : 759.

　　[4] 馮登國，張敏，張妍，等. 云計(jì)算安全研究[J]. 軟件學(xué)報，2011，22( 01) : 71.

　　[5] 牛德華，馬建峰，馬卓，等. 基于屬性的安全增強(qiáng)云存儲訪問控制方案[J]. 通信學(xué)報，2013，34( Z1) :

《馬爾科夫決策過程在移動端云存儲策略中的應(yīng)用》

上一篇：計(jì)算機(jī)硬件虛擬仿真實(shí)驗(yàn)平臺的建設(shè)與設(shè)計(jì)

下一篇：并行計(jì)算實(shí)驗(yàn)課程建設(shè)的實(shí)踐與探討