基于壓縮感知的云存儲系統狀態監測方法

馮 徑 張梁梁 沈 曄 梁陸萍

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

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

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

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

本文對經典壓縮感知理論進行了改進,設計了一種適用于FFS云存儲異常狀態監測的方法,并構造了一種適合于測量云存儲系統狀態的行和為零的貝努利測量矩陣.利用改進后的壓縮感知方法對FFS集群監控機制進行調整,并在仿真環境下對解碼精度、壓縮比率、定位效率進行測試和分析.

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

1.1 壓縮感知理論

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

Y=ΦXY∈RM

(1)

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

(2)

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

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

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

(3)

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

(4)

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

算法1MP算法

② 找到索引λt,使得

④ 令t=t+1,如果t

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

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

FFS云存儲系統異常狀態監測中采集的信號包括磁盤占用率、網卡負載、網絡延遲等.在同構的云存儲集群中,這類信號通常包含某一直流分量,故不屬于經典稀疏信號.

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

(5)

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

(6)

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

(7)

式中,Δ=X-C.

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

2 基于壓縮感知的狀態監測方法

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

2.1 FFS

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

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

圖1 FFS云存儲系統部署圖

2.2 FFS異常狀態

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

(8)

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

異常程度可表示為

2.3 異常狀態測量機制

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

圖2 分層狀態測量的拓撲結構

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

Y=∑ΦcXc=ΦX

(9)

式中，c為機柜總數.

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

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

3 仿真

3.1 仿真背景

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

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

3.2 仿真環境

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

圖3 各工作結點子任務完成進度

利用基于壓縮感知的監測方法,選取不同的測量次數,分別對圖4所示的狀態信息進行了測量和重構,并將重構結果與原狀態分布情況進行比較.

圖4 不同測量次數下的重構誤差曲線

3.3 解碼精度

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

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

3.4 壓縮比率測試

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

圖5 測量次數與異常率的關系

對所測得的數據進行線性擬合,得到擬合后的線性方程為

f(ε)=9274ε+101.2

(10)

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

(11)

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

3.5 定位效率測試

本實驗驗證了在重構原始狀態信息的迭代過程中,定位異常結點的先后順序與結點異常程度間的關系.仿真條件與3.2節相同,測量次數為80,統計結果見圖6.

圖6 定位順序與結點異常程度的關系

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

4 結語

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

)

[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.