任 穎 、李華偉 ,2、趙 媛 ,呂海燕
(1.海軍航空工程學(xué)院 山東 煙臺(tái) 264000;2.山東商務(wù)職業(yè)學(xué)院 山東 煙臺(tái) 264000)
網(wǎng)絡(luò)安全監(jiān)控?cái)?shù)據(jù)流的查詢優(yōu)化方法
任 穎1、李華偉1,2、趙 媛1,呂海燕1
(1.海軍航空工程學(xué)院 山東 煙臺(tái) 264000;2.山東商務(wù)職業(yè)學(xué)院 山東 煙臺(tái) 264000)
本文針對(duì)網(wǎng)絡(luò)安全監(jiān)控?cái)?shù)據(jù)流中的查詢機(jī)制進(jìn)行了研究,采用了一種以流數(shù)據(jù)方作為物化共享中間結(jié)果的方法,研究流數(shù)據(jù)方在內(nèi)存中的壓縮存儲(chǔ)。實(shí)驗(yàn)通過兩種流數(shù)據(jù)方存儲(chǔ)結(jié)構(gòu)StreamQCTree-D和QC-Tree,驗(yàn)證了采用動(dòng)態(tài)物化方案的StreamQCTree相對(duì)QC-Tree在降低部分查詢性能獲得較高的數(shù)據(jù)壓縮率,進(jìn)一步驗(yàn)證了數(shù)據(jù)壓縮對(duì)多查詢優(yōu)化的有效性。
數(shù)據(jù)流;網(wǎng)絡(luò)安全;數(shù)據(jù)壓縮;查詢優(yōu)化
近年來,信息處理技術(shù)的應(yīng)用領(lǐng)域得到了廣泛拓展,各種網(wǎng)絡(luò)安全威脅也越來越多,對(duì)網(wǎng)絡(luò)進(jìn)行以安全為目的的監(jiān)控并對(duì)監(jiān)控?cái)?shù)據(jù)進(jìn)行分析,具有重要的現(xiàn)實(shí)意義。網(wǎng)絡(luò)安全監(jiān)控產(chǎn)生了海量、持續(xù)、快速的數(shù)據(jù)。采用數(shù)據(jù)流處理技術(shù)可以持續(xù)、快速地分析實(shí)時(shí)數(shù)據(jù),因而數(shù)據(jù)流處理技術(shù)成為數(shù)據(jù)庫研究領(lǐng)域的又一熱點(diǎn)[1]。
大規(guī)模網(wǎng)絡(luò)安全監(jiān)控流數(shù)據(jù)處理系統(tǒng)在管理和分析安全監(jiān)控時(shí),多個(gè)系統(tǒng)將同時(shí)登陸系統(tǒng),并產(chǎn)生大量查詢,而每個(gè)查詢分別處理,這種查詢方式是低效的[2]。多個(gè)查詢可能共享相同的子任務(wù),通過多查詢優(yōu)化可提高用戶查詢效率、降低系統(tǒng)計(jì)算開銷。多查詢優(yōu)化一般采用兩類方法:優(yōu)化查詢計(jì)劃和物化共享中間結(jié)果。本文針對(duì)數(shù)據(jù)流中的查詢處理機(jī)制進(jìn)行了深入的研究,提出了一種以流數(shù)據(jù)方作為物化共享中間結(jié)果的方法,研究流數(shù)據(jù)方在內(nèi)存中的壓縮存儲(chǔ),優(yōu)化系統(tǒng)存儲(chǔ)效率以便保存更多的中間結(jié)果。
給定查詢集Q={Q1, …,Qq}由復(fù)雜 SQL查詢 Q1…,Qq組成,并包含關(guān)系集R1…,Rr,每個(gè)查詢Qi為該關(guān)系屬性集合的子集。用表示關(guān)系Ri中元組數(shù)。數(shù)據(jù)流查詢處理引擎只允許順序、單遍掃描數(shù)據(jù)流表R1…,Rr,并且不能再次讀取。采用物化共享中間結(jié)果的多查詢優(yōu)化技術(shù),將多個(gè)查詢共享的子表達(dá)式計(jì)算機(jī)結(jié)果緩存于內(nèi)存中以便于多個(gè)查詢的多次讀取,適合于數(shù)據(jù)流單遍掃描數(shù)據(jù)的特征,同時(shí)提高查詢效率。物化共享中間結(jié)果的多查詢優(yōu)化技術(shù)系統(tǒng)結(jié)構(gòu)如圖1所示。
圖1 數(shù)據(jù)流多查詢優(yōu)化Fig.1 Multiple query optimization in data stream
壓縮物化中間結(jié)果存儲(chǔ)于內(nèi)存中重復(fù)使用,隨著查詢時(shí)間窗口不斷增大,存儲(chǔ)占用空間隨之提高。有限的內(nèi)存空間無法滿足不斷增大的存儲(chǔ)需求,壓縮物化共享中間結(jié)果的方法可以較好的解決這一問題。
將多查詢集中所有查詢限定為聚集查詢時(shí),物化中間結(jié)果可以映射為部分流數(shù)據(jù)方。較好的流數(shù)據(jù)方壓縮方法應(yīng)盡量滿足 個(gè)條件:
1)壓縮時(shí)去除數(shù)據(jù)方冗余;
3)有針對(duì)性的預(yù)計(jì)算數(shù)據(jù)流上的查詢。
選擇適當(dāng)?shù)牧鲾?shù)據(jù)方壓縮結(jié)構(gòu)可以在相同容量的內(nèi)存保存更多的信息。目前有多種壓縮結(jié)構(gòu)如QC-tree[4]、Dwarf[5]等,這些壓縮結(jié)構(gòu)都是針對(duì)靜態(tài)數(shù)據(jù)的完全物化數(shù)據(jù)方。而動(dòng)態(tài)數(shù)據(jù)的流數(shù)據(jù)方存儲(chǔ)于內(nèi)存中,動(dòng)態(tài)數(shù)據(jù)是持續(xù)產(chǎn)生、無限的,在有限的內(nèi)存空間中無法容納整個(gè)完全物化的數(shù)據(jù)方壓縮結(jié)構(gòu),只能存儲(chǔ)一定時(shí)間內(nèi)的流數(shù)據(jù)方切片;為了在內(nèi)存中保存更多的流數(shù)據(jù)方切片,需進(jìn)一步減小單個(gè)切片的容量。
本文針對(duì)實(shí)時(shí)數(shù)據(jù)流分析需求提出數(shù)據(jù)流系統(tǒng)生成流數(shù)據(jù)方的實(shí)現(xiàn)框架,并實(shí)現(xiàn)壓縮流數(shù)據(jù)方結(jié)構(gòu)StreamQCTree[6],以及其更新和查詢算法
定義 1StreamQCTree StreamQCTree類似于 QC-Tree,除以下性質(zhì):
1)StreamQCTree中根結(jié)點(diǎn)root直接用邊連接每個(gè)時(shí)間維time結(jié)點(diǎn)。每個(gè)時(shí)間維結(jié)點(diǎn)包括一個(gè)QC-Tree子樹,該子樹對(duì)應(yīng)數(shù)據(jù)方時(shí)間切片SCti。
2)StreamQCTree中包含所有基本上界類,并選擇添加部分附加上屆類。
3)在StreamQCTree中每個(gè)結(jié)點(diǎn)包含一個(gè)附加值cost,表示檢索結(jié)點(diǎn)的成本。對(duì)于物化結(jié)點(diǎn),成本為1;非物化結(jié)點(diǎn),表示為在聚集查詢時(shí),訪問其后續(xù)結(jié)點(diǎn)的時(shí)間。
4)所有的非物化結(jié)點(diǎn)不存儲(chǔ)其度量值。
“我在這里聞一種氣味,它們發(fā)生在泥土里面。整整一早晨我都在干這件事。要不是這些霧……玉蘭花的每一個(gè)瓣兒里……還有那些胖胖的地蠶?!?/p>
定義2物化結(jié)點(diǎn)選擇問題[7]給定一個(gè)數(shù)據(jù)庫模式R、約束條件T、查詢集合Q和成本評(píng)估函數(shù)C,物化結(jié)點(diǎn)的選擇問題就是在R之上選擇一個(gè)物化結(jié)點(diǎn)集合V,使得V中的物化結(jié)點(diǎn)滿足條件T情況下代價(jià)C(R,V,Q)最小化。
設(shè)指針存儲(chǔ)占P,維標(biāo)記存儲(chǔ)占La,度量值存儲(chǔ)占Me,其后續(xù)結(jié)點(diǎn)數(shù)為cost。如果增加一個(gè)附加上界類,將增加存儲(chǔ)空間為
對(duì)于任意附加上界UBi,若在查詢集中訪問UBi在樹中結(jié)點(diǎn)概率 Pubi,已物化 UBi的訪問次數(shù)為Cm(UBi),未物化 UBi的訪問次數(shù)為Cum(UBi)。物化上界UBi的收益率為Bubi:
Bubi是個(gè)對(duì)比值,可以評(píng)價(jià)UBi相對(duì)于其他上界的物化收益,以評(píng)價(jià)并選擇最佳的附加上界類物化,達(dá)到最低的平均查詢響應(yīng)時(shí)間。
StreamQCTree使用時(shí)間片數(shù)據(jù)方模型。更新算法中,數(shù)據(jù)流不斷到達(dá),因?yàn)槊總€(gè)時(shí)間間隔△t將生成一個(gè)該數(shù)據(jù)方時(shí)間切片的QC-Tree子樹。更新只需要將該Ti時(shí)間的子樹添加到StreamQCTree中的Root結(jié)點(diǎn)。
刪除只有一種情況,當(dāng)時(shí)刻Ti數(shù)據(jù)方時(shí)間切片在內(nèi)存中過期,將該子樹從內(nèi)存中刪除。只要將該QC-Tree子樹內(nèi)存釋放并去掉Root指向子樹的指針。
查詢算法類似于QC-Tree的查詢算法,因?yàn)椴糠纸Y(jié)點(diǎn)未物化,所以在查詢涉及到未物化結(jié)點(diǎn)時(shí)會(huì)產(chǎn)生查詢異常。在定位查詢異常之后,根據(jù)異常所處樹的層次i來確定第i-1層需要訪問的樹中基本上界類結(jié)點(diǎn),即函數(shù) traverBUB()。
實(shí)驗(yàn)中算法采用VC++6.0實(shí)現(xiàn),運(yùn)行環(huán)境是安裝Windows XP Professional的PC,硬件配置為160G硬盤,2G內(nèi)存。假定數(shù)據(jù)流上的元組在時(shí)間維上是均勻分布的。數(shù)據(jù)共有6個(gè)維度,每個(gè)維度的基數(shù)均為100,數(shù)據(jù)方時(shí)間窗口W=10,Zipf(factor=1.2),每個(gè)時(shí)刻有100k個(gè)新元組到達(dá),總共分配200M內(nèi)存空間,每個(gè)時(shí)間片分配內(nèi)存10M。實(shí)驗(yàn)采用了兩種流數(shù)據(jù)方存儲(chǔ)結(jié)構(gòu)StreamQCTree-D和 QC-Tree,StreamQCTree-D采用動(dòng)態(tài)選擇方案StreamQCTree。
實(shí)驗(yàn)結(jié)果驗(yàn)證了StreamQCTree的壓縮方法的有效性,如圖2所示,StreamQCTree相對(duì)QC-Tree進(jìn)一步壓縮了內(nèi)存占有空間。StreamQCTree-D采用了動(dòng)態(tài)選擇方案選擇部分物化樹結(jié)點(diǎn),該方案物化查詢頻率最高的樹中結(jié)點(diǎn),盡量裁剪查詢頻率低或未查詢到得樹結(jié)點(diǎn),相對(duì)QC-Tree的查詢響應(yīng)時(shí)間差距較小,降低較小查詢性能,如圖3所示。
圖2 內(nèi)存空間占用對(duì)比Fig.2 The memory space occupied by contrast
圖3 查詢響應(yīng)時(shí)間對(duì)比Fig.3 The query response time by contrast
本文采用了一種以流數(shù)據(jù)方作為物化共享中間結(jié)果的方法,實(shí)驗(yàn)通過兩種流數(shù)據(jù)方存儲(chǔ)結(jié)構(gòu)StreamQCTree-D和QC-Tree,通過實(shí)驗(yàn)結(jié)果驗(yàn)證了采用動(dòng)態(tài)物化方案的StreamQCTree相對(duì)QC-Tree在降低部分查詢性能獲得較高的數(shù)據(jù)壓縮率,進(jìn)一步驗(yàn)證了數(shù)據(jù)壓縮對(duì)多查詢優(yōu)化的有效性。
[1]Chien J T,Wu C C.Discriminant waveletfaces and nearest feature classifiers for face recognition [J].IEEE Trans.on PAMI,2002,24(12):1644-1649.
[2]ZHENG Wen-ming,ZOU Cai-rong,ZHAO Li.Face Recognition using two novelnearestneighborclassifiers[C]//Proceedings of ICASSP,2004:725-728.
[3]Roy P,Seshadri S,Sudarshan S,et al.Efficient and Extensible algorithms for multi query optimization[C].//Proceedings of the 19th ACM SIGMOD InternationalConference on Management of Data,2000:249-260.
[4]Lakshmanan LVS,PEI Jian,ZHAN Yan.QC-trees:An efficient summary structure for semantic OLAP[C].//Proc of the 2003 ACM SIGMOD International Conference on Management of Data,2003:64-75.
[5]Sismanis Y,Deligiannakis A,Roussopoulos N,et al.Dwarf shrinking the petacube[C].//Proc of the 2002 ACM-SIGMOD international conference management of data,2002:464-475.
[6]甘亮,劉東紅,賈焰,等.StreamQCTree:一種流數(shù)據(jù)方壓縮結(jié)構(gòu)[J].計(jì)算機(jī)工程與應(yīng)用,2011:62-65.
GAN Liang,LIU Dong-hong,JIA Yan,et al.StreamQCTree:A stream data compression structure[J].Computer engineering and Applications,2011:62-65.
[7]Harinarayan V,Rajaraman A,Ullman J D.Implementing data cubes efficiently [C]//Proc of the 1996 ACM SIGMOD International Conference on Management of Data,1996:205-216.
Query optimum scheduling strategy on network security monitoring data streams
REN Ying1,LI Hua-wei1,2,ZHAO Yuan1,LV Hai-yan1
(1.Naval Aeronautical and Astronautical University,Yantai 264000,China;2.Shandong Businss Institute,Yantai 264000,China)
This thesis studies on the query mechanism of network security monitoring datastreams,and researchs storage flow data in memory adopting a method of using flow data as materialized sharing intermediate results of compression.Through the experiments of two kinds of flow data storage structure of StreamQCTree-D and QC-Tree,confirmed the dynamic scheme of StreamQCTree relative to QC-Tree in the lower part of the query performance to get higher data compression rate,further validation of the data compression of multiple query optimization is effective.
data strean;network security;data compression;query optimum
TP311.13
A
1674-6236(2014)13-0028-03
2013-06-26 稿件編號(hào):201306169
任 穎(1979—),女,山東鄆城人,碩士研究生,講師。研究方向飛:計(jì)算機(jī)應(yīng)用。