馮 徑 張梁梁 沈 曄 梁陸萍

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

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

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

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

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

1 壓縮感知理論及其算法改進

1.1 壓縮感知理論

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

Y=ΦXY∈RM

(1)

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

(2)

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

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

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

(3)

貝努利隨機測量矩陣可表示為

(4)

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

算法1MP算法

② 找到索引λt,使得

④ 令t=t+1,如果t

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

1.2 含直流分量的稀疏信號壓縮感知方法

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

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

(5)

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

(6)

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

(7)

式中,Δ=X-C.

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

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

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

2.1 FFS

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

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

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

2.2 FFS異常狀態(tài)

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

(8)

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

異常程度可表示為

2.3 異常狀態(tài)測量機制

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

圖2 分層狀態(tài)測量的拓撲結(jié)構(gòu)

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

Y=∑ΦcXc=ΦX

(9)

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

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

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

3 仿真

3.1 仿真背景

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

FFS中主控服務器模塊對云存儲客戶端提供目錄服務和元數(shù)據(jù)服務,并對存儲服務器集群進行監(jiān)控,部署于一臺性能較好的服務器中.下面針對FFS中的服務器進行監(jiān)測仿真,其拓撲結(jié)構(gòu)見圖1.

3.2 仿真環(huán)境

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

圖3 各工作結(jié)點子任務完成進度

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

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

3.3 解碼精度

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

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

3.4 壓縮比率測試

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

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

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

f(ε)=9274ε+101.2

(10)

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

(11)

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

3.5 定位效率測試

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

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

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

4 結(jié)語

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