基于壓縮感知的云存儲(chǔ)系統(tǒng)狀態(tài)監(jiān)測(cè)方法

馮 徑 張梁梁 沈 曄 梁陸萍

(1解放軍理工大學(xué)氣象海洋學(xué)院氣象水文指揮系, 南京 211101)

(2解放軍理工大學(xué)第六十三研究所,南京 210007)

異常狀態(tài)的及時(shí)監(jiān)測(cè)對(duì)提升云存儲(chǔ)效率有重要意義.為了對(duì)大規(guī)模云計(jì)算平臺(tái)的異常狀態(tài)進(jìn)行有效監(jiān)測(cè), Kung等[1]將壓縮感知理論應(yīng)用于云計(jì)算狀態(tài)監(jiān)測(cè)中.壓縮感知理論是應(yīng)用數(shù)學(xué)和信號(hào)處理領(lǐng)域中的一個(gè)新的研究方向,這一理論對(duì)于稀疏性信息的處理具有明顯優(yōu)勢(shì)[2-3]．壓縮感知理論指出,對(duì)于可壓縮的信號(hào),利用遠(yuǎn)低于奈奎斯特準(zhǔn)則的方式進(jìn)行數(shù)據(jù)采樣后,仍能精確地恢復(fù)出原始信號(hào).

在常規(guī)狀態(tài)監(jiān)測(cè)中,通常利用主控服務(wù)器對(duì)注冊(cè)到云存儲(chǔ)平臺(tái)的所有存儲(chǔ)服務(wù)器進(jìn)行輪詢,或者由各存儲(chǔ)服務(wù)器周期性地向主控服務(wù)器發(fā)送心跳信息[4].這2種方法僅適用于云存儲(chǔ)系統(tǒng)規(guī)模較小的情況．隨著云存儲(chǔ)系統(tǒng)規(guī)模的進(jìn)一步擴(kuò)大,前一種方法會(huì)帶來(lái)較大的延時(shí),導(dǎo)致監(jiān)測(cè)結(jié)點(diǎn)收集到的狀態(tài)不能及時(shí)反映全局當(dāng)前狀態(tài);后一種方法則會(huì)在心跳報(bào)文向上匯總時(shí)出現(xiàn)數(shù)據(jù)量膨脹的現(xiàn)象,對(duì)主控服務(wù)器產(chǎn)生類似于“洪泛攻擊”的影響,針對(duì)這一問(wèn)題,目前工程上的解決辦法是降低心跳頻率,但這會(huì)導(dǎo)致監(jiān)測(cè)精度降低[5].

本文對(duì)經(jīng)典壓縮感知理論進(jìn)行了改進(jìn),設(shè)計(jì)了一種適用于FFS云存儲(chǔ)異常狀態(tài)監(jiān)測(cè)的方法,并構(gòu)造了一種適合于測(cè)量云存儲(chǔ)系統(tǒng)狀態(tài)的行和為零的貝努利測(cè)量矩陣.利用改進(jìn)后的壓縮感知方法對(duì)FFS集群監(jiān)控機(jī)制進(jìn)行調(diào)整,并在仿真環(huán)境下對(duì)解碼精度、壓縮比率、定位效率進(jìn)行測(cè)試和分析.

1 壓縮感知理論及其算法改進(jìn)

1.1 壓縮感知理論

壓縮感知理論[2-3]是一種關(guān)于在欠采樣條件下重構(gòu)原始信號(hào)的理論,即已知原始信號(hào)X和測(cè)量矩陣Φ(Φ∈RM×N,M?N),將X投影到Φ,則線性測(cè)量值為

Y=ΦXY∈RM

(1)

顯然,由于Y的維數(shù)遠(yuǎn)低于X的維數(shù),方程(1)有無(wú)窮多個(gè)解,即這是一個(gè)不適定問(wèn)題.然而,如果已知所尋找的解為這無(wú)窮多個(gè)解中最稀疏的,且Y與Φ滿足約束等距性條件(RIP)[6],則信號(hào)X可以由測(cè)量值Y通過(guò)求解最小l0范數(shù)來(lái)精確重構(gòu),即

(2)

然而,常見(jiàn)的自然信號(hào)S在時(shí)域內(nèi)幾乎是不稀疏,故上述信號(hào)的重構(gòu)過(guò)程不能直接用于自然信號(hào)重構(gòu),需要通過(guò)某正交變換Ψ將自然信號(hào)S進(jìn)行稀疏表示,即X=ΨS.

由此可知,壓縮感知理論包含3個(gè)方面:測(cè)量矩陣的設(shè)計(jì)、稀疏信號(hào)的重構(gòu)以及自然信號(hào)的稀疏表示.由于云計(jì)算平臺(tái)的異常狀態(tài)信息具有稀疏性,因此本文僅關(guān)注前2個(gè)方面.

目前,已有不少類型的測(cè)量矩陣被相繼提出,最常用的包括高斯隨機(jī)測(cè)量矩陣和貝努利隨機(jī)測(cè)量矩陣等[7]．這類測(cè)量矩陣具有強(qiáng)的隨機(jī)性,文獻(xiàn)[8]已從理論上證明其滿足RIP性質(zhì).高斯隨機(jī)測(cè)量矩陣可表示為

(3)

貝努利隨機(jī)測(cè)量矩陣可表示為

(4)

利用式(2)可以完成信號(hào)的重構(gòu),但Donoho等[2]指出,求解最小l0范數(shù)是NP問(wèn)題,無(wú)法直接求解.為此,研究者們提出了一系列求次優(yōu)解的算法,如匹配追蹤(matching pursuit, MP)算法[9]及其改進(jìn)算法等.MP算法的本質(zhì)是貪婪迭代算法,具體過(guò)程見(jiàn)算法1.

算法1MP算法

② 找到索引λt,使得

④ 令t=t+1,如果t

文獻(xiàn)[9]對(duì)MP算法的收斂性進(jìn)行了理論推導(dǎo).本文針對(duì)FFS云存儲(chǔ)系統(tǒng)異常狀態(tài)監(jiān)測(cè)的實(shí)際需求,對(duì)經(jīng)典壓縮感知理論中的重構(gòu)目標(biāo)函數(shù)進(jìn)行改進(jìn),并證明在特定測(cè)量矩陣的條件下,改進(jìn)后的目標(biāo)函數(shù)與原有目標(biāo)函數(shù)等價(jià),即MP算法依然適用.

1.2 含直流分量的稀疏信號(hào)壓縮感知方法

FFS云存儲(chǔ)系統(tǒng)異常狀態(tài)監(jiān)測(cè)中采集的信號(hào)包括磁盤(pán)占用率、網(wǎng)卡負(fù)載、網(wǎng)絡(luò)延遲等.在同構(gòu)的云存儲(chǔ)集群中,這類信號(hào)通常包含某一直流分量,故不屬于經(jīng)典稀疏信號(hào).

針對(duì)包含直流分量的稀疏信號(hào),需要對(duì)經(jīng)典壓縮感知理論中的目標(biāo)函數(shù)進(jìn)行修改,即

(5)

為了使式(5)與式(2)等價(jià),需要選擇滿足行和為零的測(cè)量矩陣,即

(6)

由此可知,ΦC=0,式(5)等價(jià)為

(7)

式中,Δ=X-C.

下文中出現(xiàn)的測(cè)量矩陣,若無(wú)特別說(shuō)明,均指通過(guò)這種方法構(gòu)造的行和為零的貝努利矩陣.

2 基于壓縮感知的狀態(tài)監(jiān)測(cè)方法

主控服務(wù)器通過(guò)輪詢的方式收集各存儲(chǔ)服務(wù)器的負(fù)載．隨著存儲(chǔ)集群的增大,輪詢周期增加,監(jiān)測(cè)精度降低.本文采用基于壓縮感知的異常狀態(tài)測(cè)量方法SDCS (state detection with compressive sensing)對(duì)FFS原先狀態(tài)收集機(jī)制進(jìn)行改進(jìn).

2.1 FFS

FFS是通用低性能PC集群構(gòu)建的高可靠高性能云存儲(chǔ)系統(tǒng),由三大模塊組成:主控服務(wù)器模塊、存儲(chǔ)服務(wù)器模塊和客戶端代理模塊[10]．系統(tǒng)結(jié)構(gòu)如圖1所示.這種系統(tǒng)結(jié)構(gòu)包含2個(gè)主控服務(wù)器,采用主-備的工作方式(Active-Standby)，即一臺(tái)服務(wù)器處于某種業(yè)務(wù)的激活狀態(tài)(Active狀態(tài)),而另一臺(tái)服務(wù)器處于該業(yè)務(wù)的備用狀態(tài)(Standby狀態(tài)).

FFS中異常狀態(tài)是指存在少部分存儲(chǔ)結(jié)點(diǎn),由于新加入或者發(fā)生故障的原因,導(dǎo)致其磁盤(pán)耗費(fèi)偏離平均值．當(dāng)多個(gè)熱點(diǎn)文件被存儲(chǔ)于同一臺(tái)存儲(chǔ)服務(wù)器時(shí),該服務(wù)器的網(wǎng)卡占用率明顯高于其他存儲(chǔ)服務(wù)器.對(duì)于大規(guī)模的云存儲(chǔ)系統(tǒng),這類異常狀態(tài)往往只發(fā)生于少數(shù)結(jié)點(diǎn)上,具有稀疏性,故可采用壓縮感知方法監(jiān)測(cè).

圖1 FFS云存儲(chǔ)系統(tǒng)部署圖

2.2 FFS異常狀態(tài)

云存儲(chǔ)集群在長(zhǎng)期運(yùn)行后會(huì)出現(xiàn)數(shù)據(jù)分布不平衡的問(wèn)題.為新建文件分配存儲(chǔ)服務(wù)器時(shí),不僅需要考慮磁盤(pán)負(fù)載,還要考慮存儲(chǔ)服務(wù)器的工作負(fù)載,它們之間存在乘性關(guān)系.存儲(chǔ)服務(wù)器的負(fù)載值計(jì)算公式為

(8)

式中,xw為存儲(chǔ)集群中第w臺(tái)存儲(chǔ)服務(wù)器的負(fù)載值,%;aw為存儲(chǔ)服務(wù)器的磁盤(pán)可用空間百分?jǐn)?shù),%;uw,dw,nw分別為存儲(chǔ)服務(wù)器網(wǎng)卡的上行速率、下行速率和最大速率,kbit/s.主控服務(wù)器會(huì)根據(jù)各結(jié)點(diǎn)的負(fù)載值周期性地對(duì)存儲(chǔ)服務(wù)器列表進(jìn)行排序.

異常程度可表示為

2.3 異常狀態(tài)測(cè)量機(jī)制

對(duì)于大規(guī)模FFS云存儲(chǔ)系統(tǒng),需采用分層狀態(tài)測(cè)量機(jī)制(見(jiàn)圖2).

圖2 分層狀態(tài)測(cè)量的拓?fù)浣Y(jié)構(gòu)

由圖2可知,根據(jù)式(8),機(jī)柜監(jiān)測(cè)結(jié)點(diǎn)收集本機(jī)柜內(nèi)各存儲(chǔ)服務(wù)器的負(fù)載信息,并生成新的測(cè)量值Yi=ΦiXi．機(jī)房監(jiān)控結(jié)點(diǎn)用于收集其所屬各機(jī)柜監(jiān)控結(jié)點(diǎn)的測(cè)量值,并將這些測(cè)量值累加生成新的測(cè)量值.最終,將各機(jī)柜測(cè)量值的累加值匯總至主控服務(wù)器,即

Y=∑ΦcXc=ΦX

(9)

式中，c為機(jī)柜總數(shù).

這種測(cè)量機(jī)制的優(yōu)點(diǎn)在于:① 狀態(tài)測(cè)量中,中間結(jié)點(diǎn)與主控服務(wù)器僅需執(zhí)行簡(jiǎn)單的累加操作．與傳統(tǒng)墑編碼方式相比,這種編碼方式的復(fù)雜度較低．② 狀態(tài)信息從底層向主控服務(wù)器匯總的過(guò)程中,數(shù)據(jù)維度保持不變,避免了數(shù)據(jù)量膨脹問(wèn)題．③ 中間結(jié)點(diǎn)總是保存其下層結(jié)點(diǎn)的最后一次狀態(tài)測(cè)量值.這種方式無(wú)需對(duì)全局?jǐn)?shù)據(jù)進(jìn)行同步,且不依賴于數(shù)據(jù)的可靠傳輸.

主控服務(wù)器對(duì)收集到的狀態(tài)測(cè)量值進(jìn)行周期性重構(gòu),即求解式(9)的稀疏解.對(duì)于狀態(tài)向量X,偏離均值較大的分量往往對(duì)應(yīng)異常程度較嚴(yán)重的狀態(tài)參數(shù).因此,利用MP算法,可優(yōu)先定位到異常程度較嚴(yán)重的結(jié)點(diǎn)上,從而使主控服務(wù)器可以按異常嚴(yán)重程度發(fā)現(xiàn)感興趣的結(jié)點(diǎn),并及時(shí)進(jìn)行處理.

3 仿真

3.1 仿真背景

在FFS中,實(shí)時(shí)獲取全局狀態(tài)信息有利于任務(wù)分配和資源調(diào)度的優(yōu)化.如多個(gè)熱點(diǎn)數(shù)據(jù)存放在同一臺(tái)存儲(chǔ)服務(wù)器上,該存儲(chǔ)服務(wù)器將成為瓶頸結(jié)點(diǎn),實(shí)時(shí)獲取云存儲(chǔ)平臺(tái)全局狀態(tài)有利于及時(shí)將瓶頸結(jié)點(diǎn)的熱點(diǎn)數(shù)據(jù)進(jìn)行重分配,從而提高云存儲(chǔ)系統(tǒng)的吞吐量(MBPS)和響應(yīng)速度(IOPS)[11].

FFS中主控服務(wù)器模塊對(duì)云存儲(chǔ)客戶端提供目錄服務(wù)和元數(shù)據(jù)服務(wù),并對(duì)存儲(chǔ)服務(wù)器集群進(jìn)行監(jiān)控,部署于一臺(tái)性能較好的服務(wù)器中.下面針對(duì)FFS中的服務(wù)器進(jìn)行監(jiān)測(cè)仿真,其拓?fù)浣Y(jié)構(gòu)見(jiàn)圖1.

3.2 仿真環(huán)境

采用Matlab軟件進(jìn)行仿真．假設(shè)FFS云存儲(chǔ)系統(tǒng)中包含2000個(gè)存儲(chǔ)服務(wù)器、1個(gè)主控服務(wù)器和1個(gè)備份服務(wù)器.如圖3所示,大部分存儲(chǔ)服務(wù)器的負(fù)載值約為35%．僅少部分存儲(chǔ)服務(wù)器(10個(gè),占總數(shù)的0.5%)的負(fù)載遠(yuǎn)偏離于平均水平,這類存儲(chǔ)服務(wù)器存在某種異常,可能是新加入的結(jié)點(diǎn),也可能存在熱點(diǎn)數(shù)據(jù),或者發(fā)生軟硬件故障,需要通過(guò)狀態(tài)監(jiān)測(cè)及時(shí)發(fā)現(xiàn),并進(jìn)行數(shù)據(jù)遷移.

圖3 各工作結(jié)點(diǎn)子任務(wù)完成進(jìn)度

利用基于壓縮感知的監(jiān)測(cè)方法,選取不同的測(cè)量次數(shù),分別對(duì)圖4所示的狀態(tài)信息進(jìn)行了測(cè)量和重構(gòu),并將重構(gòu)結(jié)果與原狀態(tài)分布情況進(jìn)行比較.

圖4 不同測(cè)量次數(shù)下的重構(gòu)誤差曲線

3.3 解碼精度

重構(gòu)誤差分為2種:① 過(guò)檢測(cè),即將某非異常結(jié)點(diǎn)誤判為異常結(jié)點(diǎn);② 欠監(jiān)測(cè),即未能檢測(cè)出某異常結(jié)點(diǎn).這2種誤差中,過(guò)檢測(cè)可通過(guò)系統(tǒng)的二次確認(rèn)進(jìn)行修正,但會(huì)在一定程度上增加系統(tǒng)的二次確認(rèn)開(kāi)銷;欠檢測(cè)可在系統(tǒng)的后續(xù)重構(gòu)周期得到修正,但會(huì)降低系統(tǒng)探測(cè)到異常結(jié)點(diǎn)的效率. 圖4為不同測(cè)量次數(shù)下的重構(gòu)誤差曲線.

由圖4可知,對(duì)于稀疏度為10的原狀態(tài)信息,當(dāng)測(cè)量次數(shù)超過(guò)70時(shí),即可無(wú)誤差地精確定位所有異常結(jié)點(diǎn).此時(shí),數(shù)據(jù)的壓縮比率達(dá)到3.5%.即在保持與常規(guī)狀態(tài)監(jiān)測(cè)方法相同的監(jiān)測(cè)精度下,若集群中異常結(jié)點(diǎn)數(shù)占總結(jié)點(diǎn)數(shù)的0.5%,則基于壓縮感知的監(jiān)測(cè)方式所能有效監(jiān)測(cè)的集群規(guī)模比常規(guī)方式提高約28.6倍.

3.4 壓縮比率測(cè)試

為了測(cè)試SDCS在集群異常率不同時(shí)的壓縮比率,將異常率(即集群中異常結(jié)點(diǎn)數(shù)占總結(jié)點(diǎn)數(shù)的百分?jǐn)?shù))控制在0.5%～15%,對(duì)SDCS選取不同的測(cè)量次數(shù)分別進(jìn)行了實(shí)驗(yàn),結(jié)果見(jiàn)圖5.

圖5 測(cè)量次數(shù)與異常率的關(guān)系

對(duì)所測(cè)得的數(shù)據(jù)進(jìn)行線性擬合,得到擬合后的線性方程為

f(ε)=9274ε+101.2

(10)

式中,ε表示異常率;f(ε)表示測(cè)量次數(shù).令γ(ε)=f(ε)/2000為本文方法相對(duì)于輪詢與心跳監(jiān)測(cè)方法所占用網(wǎng)絡(luò)監(jiān)控流量的壓縮比率,則

(11)

由此可知,當(dāng)集群中異常率低于20.5%時(shí)(絕大多數(shù)可正常工作的網(wǎng)絡(luò)都滿足該要求),相對(duì)于傳統(tǒng)方法,使用本文方法可更有效地壓縮監(jiān)控流量.

3.5 定位效率測(cè)試

本實(shí)驗(yàn)驗(yàn)證了在重構(gòu)原始狀態(tài)信息的迭代過(guò)程中,定位異常結(jié)點(diǎn)的先后順序與結(jié)點(diǎn)異常程度間的關(guān)系.仿真條件與3.2節(jié)相同,測(cè)量次數(shù)為80,統(tǒng)計(jì)結(jié)果見(jiàn)圖6.

圖6 定位順序與結(jié)點(diǎn)異常程度的關(guān)系

如圖6所示,重構(gòu)算法共迭代了10次,按迭代順序所定位的結(jié)點(diǎn),其異常程度的絕對(duì)值依次下降，說(shuō)明該算法具有優(yōu)先定位當(dāng)前異常程度最嚴(yán)重結(jié)點(diǎn)的優(yōu)良特性.通過(guò)異常狀態(tài)的成功檢測(cè),可以在FFS中采用負(fù)載均衡機(jī)制來(lái)保證各存儲(chǔ)結(jié)點(diǎn)的磁盤(pán)耗費(fèi)與網(wǎng)卡占用率接近平均值.

4 結(jié)語(yǔ)

本文對(duì)壓縮感知理論進(jìn)行了改進(jìn),提出了一種SDCS方法,并將其應(yīng)用于解決大規(guī)模FFS云存儲(chǔ)系統(tǒng)實(shí)時(shí)監(jiān)測(cè)問(wèn)題中,證明了采集綜合狀態(tài)信息的可行性與有效性,分析了有效壓縮監(jiān)控流量的集群異常率閾值.與傳統(tǒng)狀態(tài)監(jiān)測(cè)方法相比,SDCS方法編解碼復(fù)雜度低,監(jiān)測(cè)精度高．測(cè)量數(shù)據(jù)從底層向主控服務(wù)器匯總過(guò)程中,數(shù)據(jù)維度可保持不變,便于采集含有多種要素信息的信號(hào),避免了常規(guī)監(jiān)測(cè)方法在監(jiān)測(cè)大規(guī)模云存儲(chǔ)平臺(tái)時(shí)出現(xiàn)的數(shù)據(jù)膨脹問(wèn)題,使得監(jiān)測(cè)規(guī)模可進(jìn)一步提高．在數(shù)據(jù)重構(gòu)過(guò)程中,優(yōu)先定位當(dāng)前異常程度較嚴(yán)重的結(jié)點(diǎn),可有效提高系統(tǒng)異?；謴?fù)效率.在下一步工作中,將研究如何針對(duì)具體情況對(duì)各類狀態(tài)進(jìn)行統(tǒng)一編碼.

)

[1]Kung H T, Lin C K, Vlah D. CloudSense: continuous fine-grain cloud monitoring with compressive sensing[C]//Proceedingsofthe3rdUSENIXWorkshoponHotTopicsinCloudComputing. Portland, OR, USA, 2011：15-19.

[2]Donoho D L. Compressed sensing[J].IEEETransactionsonInformationTheory, 2006,52(4): 1289-1306.

[3]Candes E J. Compressive sampling[C]//ProceedingsoftheInternationalCongressofMathematicians. Madrid, Spain, 2006(3): 1433-1452.

[4]Lei L, Wo T Y, Hu C M. CREST: towards fast speculation of straggler tasks in MapReduce[C]//ProceedingsoftheIEEE8thInternationalConferenceonE-businessEngineering. Beijing, China, 2011: 311-316.

[5]Tom White.Hadoop:thedefinitiveguide[M]. Sebastopol, CA, USA:O’Relly Media Inc, 2011: 170-173.

[6]Candes E J. The restricted isometry property and its implications for compressed sensing[J].ComputesRendusMathematique, 2008,346(9/10): 589-592.

[7]Tsaig Y, Donoho D L. Extensions of compressed sensing[J].SignalProcessing, 2006,86(3): 549-571.

[8]Baraniuk R, Davenport M, Devore R, et al. A simple proof of the restricted isometry property for random matrices[J].ConstructiveApproximation, 2008,28(3): 253-263.

[9]Davis G, Mallat S, Avellaneda M. Adaptive greedy approximations[J].ConstructiveApproximation, 1997,13(1): 57-98.

[10]Wu Haijia,Chen Weiwei,Hu Guyu. FFS: a PB-level cloud-storage system based on network [J].JournalonCommunications, 2011,32(9): 24-33.

[11]Wu Haijia,Chen Weiwei, Liu Peng. Synchronization strategy for metadata cache in cloud storage system based on change-log[J].TelecommunicationsScience,2011,27(9): 32-36.