馮 徑 張梁梁 沈 曄 梁陸萍

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

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

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

在常規(guī)狀態(tài)監(jiān)測中,通常利用主控服務(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ì)帶來較大的延時(shí),導(dǎo)致監(jiān)測結(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ì)這一問題,目前工程上的解決辦法是降低心跳頻率,但這會(huì)導(dǎo)致監(jiān)測精度降低[5].

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

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

1.1 壓縮感知理論

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

Y=ΦXY∈RM

(1)

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

(2)

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

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

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

(3)

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

(4)

利用式(2)可以完成信號(hào)的重構(gòu),但Donoho等[2]指出,求解最小l0范數(shù)是NP問題,無法直接求解.為此,研究者們提出了一系列求次優(yōu)解的算法,如匹配追蹤(matching pursuit, MP)算法[9]及其改進(jìn)算法等.MP算法的本質(zhì)是貪婪迭代算法,具體過程見算法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)測的實(shí)際需求,對(duì)經(jīng)典壓縮感知理論中的重構(gòu)目標(biāo)函數(shù)進(jìn)行改進(jìn),并證明在特定測量矩陣的條件下,改進(jìn)后的目標(biāo)函數(shù)與原有目標(biāo)函數(shù)等價(jià),即MP算法依然適用.

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

FFS云存儲(chǔ)系統(tǒng)異常狀態(tài)監(jiān)測中采集的信號(hào)包括磁盤占用率、網(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à),需要選擇滿足行和為零的測量矩陣,即

(6)

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

(7)

式中,Δ=X-C.

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

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

主控服務(wù)器通過輪詢的方式收集各存儲(chǔ)服務(wù)器的負(fù)載．隨著存儲(chǔ)集群的增大,輪詢周期增加,監(jiān)測精度降低.本文采用基于壓縮感知的異常狀態(tài)測量方法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)致其磁盤耗費(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)測.

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

2.2 FFS異常狀態(tài)

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

(8)

式中,xw為存儲(chǔ)集群中第w臺(tái)存儲(chǔ)服務(wù)器的負(fù)載值,%;aw為存儲(chǔ)服務(wù)器的磁盤可用空間百分?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)測量機(jī)制

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

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

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

Y=∑ΦcXc=ΦX

(9)

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

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

主控服務(wù)器對(duì)收集到的狀態(tài)測量值進(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)測仿真,其拓?fù)浣Y(jié)構(gòu)見圖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ā)生軟硬件故障,需要通過狀態(tài)監(jiān)測及時(shí)發(fā)現(xiàn),并進(jìn)行數(shù)據(jù)遷移.

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

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

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

3.3 解碼精度

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

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

3.4 壓縮比率測試

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

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

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

f(ε)=9274ε+101.2

(10)

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

(11)

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

3.5 定位效率測試

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

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

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

4 結(jié)語

本文對(duì)壓縮感知理論進(jìn)行了改進(jìn),提出了一種SDCS方法,并將其應(yīng)用于解決大規(guī)模FFS云存儲(chǔ)系統(tǒng)實(shí)時(shí)監(jiān)測問題中,證明了采集綜合狀態(tài)信息的可行性與有效性,分析了有效壓縮監(jiān)控流量的集群異常率閾值.與傳統(tǒng)狀態(tài)監(jiān)測方法相比,SDCS方法編解碼復(fù)雜度低,監(jiān)測精度高．測量數(shù)據(jù)從底層向主控服務(wù)器匯總過程中,數(shù)據(jù)維度可保持不變,便于采集含有多種要素信息的信號(hào),避免了常規(guī)監(jiān)測方法在監(jiān)測大規(guī)模云存儲(chǔ)平臺(tái)時(shí)出現(xiàn)的數(shù)據(jù)膨脹問題,使得監(jiān)測規(guī)?？蛇M(jìn)一步提高．在數(shù)據(jù)重構(gòu)過程中,優(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.