宋曉偉，孫　陽，殷守林

（沈陽師范大學(xué)科信軟件學(xué)院，沈陽110034）

?

一種基于數(shù)據(jù)流的滑動窗口查詢策略

宋曉偉，孫陽，殷守林

（沈陽師范大學(xué)科信軟件學(xué)院，沈陽110034）

摘要：滑動窗口既可以傳送幀，也可以傳送字節(jié)數(shù)據(jù)。它是用來改善吞吐量的一種技術(shù)，即容許發(fā)送方在接收任何應(yīng)答之前傳送附加的包，接收方告訴發(fā)送方在某一時刻能送多少包。TCP中采用滑動窗口來進(jìn)行傳輸控制，滑動窗口的大小意味著接收方還有多大的緩沖區(qū)可以用于接收數(shù)據(jù)。設(shè)計(jì)一種基于數(shù)據(jù)流的滑動窗口查詢策略，首先按照滑動窗口的跳數(shù)的大小將整個滑動窗口劃分為若干個區(qū)域，然后建立索引連接，進(jìn)行查詢批處理，最后，通過實(shí)驗(yàn)證明此方法的有效性。

關(guān)鍵詞：滑動窗口；查詢策略；索引；批處理

0　引言

隨著網(wǎng)絡(luò)的發(fā)展，許多應(yīng)用中的數(shù)據(jù)不再是數(shù)據(jù)庫中靜態(tài)的數(shù)據(jù)，而是以一種流的方式在線的到達(dá)的動態(tài)數(shù)據(jù)。這樣的數(shù)據(jù)具有數(shù)據(jù)無界，數(shù)據(jù)量大，流速快，并且要求實(shí)時處理等特性，這種新型的數(shù)據(jù)被稱為流數(shù)據(jù)[1-3]。對應(yīng)的，包含流數(shù)據(jù)的應(yīng)用被稱為數(shù)據(jù)流的應(yīng)用。如同傳統(tǒng)數(shù)據(jù)庫中存在數(shù)據(jù)庫管理系統(tǒng)一樣，在研究數(shù)據(jù)流時需要開發(fā)數(shù)據(jù)流管理系統(tǒng)，這樣的系統(tǒng)負(fù)責(zé)對流式數(shù)據(jù)進(jìn)行查詢處理。

數(shù)據(jù)流管理系統(tǒng)中的核心是查詢處理功能模塊。通常情況下，在數(shù)據(jù)流上基本的查詢處理包括選擇、投影和連接操作。相對于選擇與投影，連接操作更為復(fù)雜。由于數(shù)據(jù)流的無限性和連接操作的阻塞性質(zhì)，使得在數(shù)據(jù)流上的連接操作必須要加以限制。因此滑動窗口[4-6]的概念也就很自然的引入到數(shù)據(jù)流中，通過對處理的數(shù)據(jù)加上滑動窗口的限制，變傳統(tǒng)的阻塞操作為流上的非阻塞操作。本文提出了一種在多流多查詢環(huán)境下能夠?qū)α鲾?shù)據(jù)進(jìn)行基本的查詢處理以及優(yōu)化的策略，通過實(shí)驗(yàn)測試，結(jié)果表明采用了索引技術(shù)后可以較大幅度地提高查詢處理的效率。

1　相關(guān)工作

現(xiàn)在對滑動窗口上的連接的研究較為廣泛，一些研究學(xué)者們給出了不同的連接算法，在這一節(jié)中將簡要地介紹滑動窗口連接上的相關(guān)工作。連接處理是查詢處理中復(fù)雜的操作，在各種文獻(xiàn)中給出了許多不同的連接算法。在這里主要介紹一下對稱式的哈希連接[7-8]、擴(kuò)展的哈希脈動連接和XJoin[9-10]。

（1）對稱式的哈希連接

這種連接方式最開始是設(shè)計(jì)在并行數(shù)據(jù)庫中的一種技術(shù)，用來允許高度的并行應(yīng)用。由于高度并行的需求，這種連接的方式將兩個進(jìn)行連接的輸入所對應(yīng)的哈希表都存儲在主存中。因此這種連接方式并不適合于大量輸入的連接操作。所謂對稱式的是指等同的對待連接的兩個輸入以及這兩個輸入所對應(yīng)的哈希表。采用哈希連接的的方式，提高等值連接的效率。由于在并行中存在同步的問題，這大大地限制了從并行中的獲益，采用了這種對稱式的哈希連接，又叫做一種流水線方式的哈希連接，減少了同步的限制，從而在性能上有所提高。

（2）擴(kuò)展的哈希脈動連接

前面介紹傳統(tǒng)數(shù)據(jù)庫連接算法的時候，已經(jīng)介紹了脈動連接這種連接方式，這種連接方法是對脈動連接的一種擴(kuò)展。脈動連接算法對連接聚集查詢給出一個較好的估測，但如果滿足連接條件的元組比較少的時候，算法則收斂的很慢；另外，如果為了能夠得到精確的結(jié)果而內(nèi)存溢出的時候，脈動連接算法會退化為阻塞的連接操作。而擴(kuò)展的哈希脈動連接改進(jìn)了基本的脈動連接算法，做出了兩點(diǎn)貢獻(xiàn)：

①結(jié)合了并行與采樣的技術(shù)，從而能加快算法的收斂；

②在內(nèi)存溢出的情況下仍然能維護(hù)一個好的性能。

文章最后給出了可擴(kuò)展的哈希脈動連接算法并且進(jìn)行了實(shí)驗(yàn)比較。

（3）XJoin

XJoin采用的仍然是非阻塞的并行機(jī)制。XJoin是一個非阻塞的連接操作符，系統(tǒng)中允許多個這樣的操作符并行執(zhí)行，是適用于廣域分布的應(yīng)用的一種連接操作符。

這種連接操作符XJoin可以看作是對稱哈希連接[11]和脈動連接的一個擴(kuò)展。正如前面介紹對稱哈希連接中提到的，對稱式的哈希連接方法需要將兩個進(jìn)行連接的輸入所對應(yīng)的哈希表都存儲在主存中，因此這種連接方式并不適合于大量輸入的連接操作。因此Xjoin擴(kuò)展了哈希連接的方法，允許部分的哈希表存儲到輔存中從而降低了內(nèi)存資源的使用。但是并不能僅僅簡單地將哈希表轉(zhuǎn)移到輔存中，因?yàn)檫@樣系統(tǒng)需要忍受長時間的延遲，從而大大地降低系統(tǒng)查詢處理的效率。必須要通過一定的方法來進(jìn)行改善才能達(dá)到預(yù)期的目標(biāo)。在XJoin中采用的一個關(guān)鍵技術(shù)就是reactively-scheduled的流水線方法，采用后臺處理，利用諸如元組傳輸?shù)鹊难舆t來盡快產(chǎn)生查詢處理的結(jié)果。

XJoin技術(shù)比較先進(jìn)，因?yàn)樵谄渲写嬖趯χ鞔媾c輔存之間進(jìn)行控制、后臺處理、確保最后的結(jié)果能夠全部產(chǎn)生和進(jìn)行一些消除重復(fù)結(jié)果的操作等，而這些無疑都是很復(fù)雜的。

2　數(shù)據(jù)流的滑動窗口查詢策略

（1）滑動窗口的劃分

滑動窗口一般有兩個參數(shù)，滑動窗口的大小和跳數(shù)。我們采用了對滑動窗口進(jìn)行劃分的方法，按照滑動窗口的跳數(shù)的大小將整個滑動窗口劃分為若干個區(qū)域，即：按照跳數(shù)hi將整個滑動窗口Wi劃分為若干個BWi，每一個劃分出來的BWi稱為基本窗口。注意到，每一個基本窗口實(shí)際上就是一個滑動窗口的跳數(shù)，其大小與跳數(shù)的大小是完全相等的。在下面將會介紹這樣去劃分整個滑動窗口的好處。

對滑動窗口進(jìn)行了劃分之后，就可以對整個滑動窗口上的數(shù)據(jù)建立索引了。在這里，滑動窗口上的連接查詢處理有兩種情況：等值的連接查詢處理與非等值的連接查詢處理（也可以稱為范圍連接）。下面將分別對這兩種情況進(jìn)行討論，但主要是以范圍連接為主。正如前面所提到的，當(dāng)前的研究都是以等值連接為基礎(chǔ)進(jìn)行展開的。所以在本文中著眼于范圍連接。

（2）建立索引

本文采用的方法是上面詳細(xì)介紹了的劃分滑動窗口的方法，并且對劃分出來的每一個基本窗口維護(hù)一個索引。

在滑動窗口上建立了索引之后，進(jìn)行連接查詢處理的時候就采用在索引上進(jìn)行，從而能提高查詢處理的效率。這里將詳細(xì)的介紹建立索引的方法以及建立索引后采用索引進(jìn)行連接的查詢處理方法。

首先在圖1中給出一個簡單的圖示，描述了劃分滑動窗口以及利用這種策略建立索引的方法：

圖1　滑動窗口的劃分及索引建立

在圖1中的處理過程是這樣的：在這里設(shè)定滑動窗口大小為6秒，而跳數(shù)的大小為2秒。則可以將窗口分成6/2=3個BW區(qū)域。7和8中是滑動窗口在更新時刻新到一個跳數(shù)中的元組（第7秒和第8秒），當(dāng)這個跳數(shù)到達(dá)后，1和2組成的跳數(shù)中的元組就過期了（因?yàn)榇翱诖笮?），就需要刪除過期的一個跳數(shù)。每到一個窗口的更新時刻，查詢處理系統(tǒng)把一個跳數(shù)的元組加入到窗口中，這個新的跳數(shù)中元組組成的是一個新的基本窗口，在系統(tǒng)中生成這個新的基本窗口對應(yīng)的索引。然后驗(yàn)證并刪除最舊的一個基本窗口中的過期元組，同時一次刪除這個過期的基本窗口（也就是一個基本窗口）對應(yīng)的索引。

（3）索引連接

經(jīng)過上面的步驟之后，對數(shù)據(jù)流滑動窗口上每個基本窗口中的數(shù)據(jù)元組索引建立好。這樣，采用索引進(jìn)行連接查詢處理的方法是一個批處理的方法。

每次到達(dá)一個窗口的更新時刻，流上將會有一個新的跳數(shù)范圍內(nèi)的元組產(chǎn)生，這部分的元組的產(chǎn)生會使得最舊的一個跳數(shù)中的元組過期。在上面的圖中，R流（以R為例）上新到了一個跳數(shù)的元組，這個跳數(shù)中的元組首先被用來搜索S流的各個基本窗口中的索引，并且匹配連接結(jié)果輸出。然后將這些元組加入到，R流當(dāng)前的滑動窗口中。這些元組構(gòu)成了一個新的基本窗口，生成這個基本窗口的索引。同時驗(yàn)證并且刪除已經(jīng)過期的最舊的一個基本窗口的所有數(shù)據(jù)元組，而這個過期的基本窗口所對應(yīng)的索引信息也已經(jīng)過期，只需要將整個的索引樹刪除即可。

這樣，對于兩個流R與S進(jìn)行連接的情況，以R流產(chǎn)生一個hop的元組為例（對于流S情況相同，是對稱的），經(jīng)過這個過程之后，R流上新到達(dá)的這個hop中的所有元組與S流當(dāng)前窗口中的所有元組進(jìn)行了連接并且構(gòu)造了結(jié)果。采用這種方法，采用增量的、批處理的方式進(jìn)行連接的查詢處理，每次對流上新到的一個hop中的全部元組進(jìn)行處理。在一般的情況下，產(chǎn)生的結(jié)果是立即返回給注冊該查詢的用戶，并且是連續(xù)的返回。結(jié)果在返回給用戶后就可以立即的刪除，釋放其所占用的內(nèi)存資源，這樣的結(jié)果是最終的查詢結(jié)果；但是如果在連接結(jié)果之上還存在其他的查詢，那么就需要緩存中間的結(jié)果。是立即輸出還是暫時緩存視具體的情況而定。

3　索引共享及聚集查詢

（1）多連接的索引查詢

在流的應(yīng)用中，系統(tǒng)中通常都存在很多個連續(xù)查詢，而如果兩個（或多個）查詢的hop參數(shù)相同，那么查詢間就可以共享索引。我們只維護(hù)一個索引讓不同的查詢都可以使用，而不是對每一個查詢都單獨(dú)的維護(hù)索引，這樣的共享可以提高效率。

查詢hop相同的情況下，還需要再分為查詢間的窗口大小相同和不同兩種情況來考慮。首先我們考慮hop相同，窗口也相同的情況，如下面兩個查詢：

Q1: SELECT *

FROM Stock1[SLIDINGRANGE(10,2)],

Stock2[SLIDINGRANGE(12,4)]

WHERE A.price>B.price

Q2: SELECT Stock1.sid, Stock2.sid

FROM Stock1[SLIDINGRANGE(10,2)],

Stock2[SLIDINGRANGE(12,4)]

WHERE A.price>B.price

這兩個查詢是查詢兩支股票的信息，其中SLIDINGRANGE表示窗口約束條件是基于時間的滑動窗口連接，兩個參數(shù)分別為窗口大小和更新頻率hop的大小。這兩個查詢具有相同的連接條件和窗口約束條件，我們分別對流Stock1和流Stock2建立索引，按照窗口的約束條件，可以將每個滑動窗口分成10/2=5個BW區(qū)域，對每個區(qū)域中的數(shù)據(jù)建立一個紅黑樹索引。在進(jìn)行連接查詢處理的時候，Q1和Q2兩個查詢可以共享使用所建立起來的索引。每次使用其中一個流上的一個元組去掃描另一個流所對應(yīng)的索引，得到連接的結(jié)果同時返回給兩個查詢，然后各自獨(dú)立的繼續(xù)執(zhí)行查詢計(jì)劃的其他部分（對Q1可以直接返回連接的結(jié)果了，而Q2則還需要對連接結(jié)果做投影操作）。

然后再考慮hop相同，但是窗口大小不同的情況，如下面三個查詢：

Q1: SELECT *

FROM Stock1[SLIDINGRANGE(10,2)],

Stock2[SLIDINGRANGE(12,4)]

WHERE A.price>B.price

Q2: SELECT *

FROM Stock1[SLIDINGRANGE(8,2)],

Stock2[SLIDINGRANGE(12,4)]

WHERE A.price>B.price

Q3: SELECT *

FROM Stock1[SLIDINGRANGE(6,2)],

Stock2[SLIDINGRANGE(12,4)]

WHERE A.price>B.price

三個查詢條件相同，只是對Stock1流上的窗口大小不同（Stock2流也可以窗口不同，情況是和Stock1完全類似的），我們選擇一個最大的窗口大小10，對大小為10的窗口維護(hù)索引信息，在查詢處理的過程中控制處理元組的范圍，將不同范圍的結(jié)果返回給相應(yīng)的查詢。

（2）流上的聚集查詢

數(shù)據(jù)流上的聚集操作從類型上來說與傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)類似，主要有MAX、MIN、SUM、COUNT和AVG幾種。

傳統(tǒng)數(shù)據(jù)庫當(dāng)中的聚集操作一般來說需要看到所有的數(shù)據(jù)才可以輸出結(jié)果，即便由于內(nèi)存的限制不能一次性看到全部數(shù)據(jù)，也可以通過多趟算法分步從二級存儲器中讀取數(shù)據(jù)進(jìn)行處理。但是在數(shù)據(jù)流的環(huán)境中，不僅內(nèi)存容量受限，而且因?yàn)閷?shí)時性的要求也不能求助于二級存儲器。對于沒有盡頭的數(shù)據(jù)，如果一定要等到流結(jié)束再輸出結(jié)果，那么聚集操作就永遠(yuǎn)不會有數(shù)據(jù)輸出。從本質(zhì)上講聚集操作與連接操作是同一個類型的查詢處理操作，改變傳統(tǒng)的阻塞的性質(zhì)是不可回避的，這樣就需要考慮在數(shù)據(jù)流上的聚集操作中作一些特殊處理。

類似的，解決聚集查詢阻塞性質(zhì)的方法與連接中是完全相同，仍然是在數(shù)據(jù)流上加上滑動窗口的約束。一般情況下，在數(shù)據(jù)流上的聚集查詢也都是指的數(shù)據(jù)流上的滑動窗口聚集查詢這種處理就是在聚集操作中也要有窗口結(jié)構(gòu)的輔助才可以執(zhí)行，既然聚集操作就像連接操作一樣不可能處理流上的全部數(shù)據(jù)，那么就必須把需要處理的數(shù)據(jù)在范圍上加以限定。在聚集操作上的操作符窗口和連接操作符上的操作符窗口基本上是一樣的。

對數(shù)據(jù)流上的聚集查詢，按照操作的性質(zhì)，也可以分成兩類：MAX和MIN的聚集查詢是一種求極值（extreme）的操作；而對于COUNT、SUM和AVG這樣的聚集查詢，則可以成為累加（accumulate）的聚集查詢。因?yàn)榫奂樵兣c連接查詢有相似之處，解決聚集查詢處理的方法和連接也有很多相同的地方。同樣，可以采用上面介紹的劃分滑動窗口的辦法，并且一般情況下也會對流數(shù)據(jù)元組建立滿足聚集查詢的索引，從而能夠提高聚集查詢的處理效率。例如在文獻(xiàn)[12]中就提出了一種稱為有序樹的索引結(jié)構(gòu)，以這種索引來解決窗口上的極值的查詢處理問題。連接與聚集都是流上的阻塞查詢，在這一節(jié)中主要介紹了流上的阻塞連接查詢處理的方法，其中主要都是圍繞流上的連接查詢處理展開的。核心的思想是在流上采用索引連接的方法。通過后面的性能評測，能夠說明采用索引連接策略好處。對于索引的共享和流上聚集的阻塞[13]查詢處理，并不是本文要討論的重點(diǎn)，因此在這一節(jié)中只是給出了簡要的介紹和說明。

4　實(shí)驗(yàn)與結(jié)果分析

對于阻塞的連接操作符的查詢處理，分別實(shí)現(xiàn)嵌套循環(huán)連接的方法和在滑動窗口上建立索引的連接方法，比較二者的效率，在同樣的情況下測試二者的執(zhí)行時間進(jìn)行性能的比較。具體的過程是這樣的：系統(tǒng)生成數(shù)據(jù)元組，模擬兩個同步的流進(jìn)行連接，這兩個流的滑動窗口參數(shù)相同：滑動窗口大小為6s，更新頻率為2s。每到一個更新時刻，兩個流各自產(chǎn)生一個hop大小的元組，兩個流各自產(chǎn)生6個hop的元組為止。在下面的實(shí)驗(yàn)中，除了特別說明之外，流速s為800元組/s，兩個流上元組的連接屬性值的范圍均為[0，128)，規(guī)定兩個流連接條件為Stream1.attr > Stream2.attr。分別測出嵌套循環(huán)連接方法和建立索引方法的執(zhí)行時間并進(jìn)行比較?？刂七B接操作符的選擇度為0.07。從圖2中可以看出，在低的選擇度情況下，流速增加時，索引算法的優(yōu)勢變得更加的明顯。

圖2　不同流速對算法的影響

5　結(jié)語

本文介紹連接操作符的查詢處理索引技術(shù)，主要圍繞滑動窗口上連接查詢處理展開，介紹了如何劃分滑動窗口以及如何在連接查詢處理過程中采用索引的技術(shù)提高阻塞查詢處理的效率。最后通過實(shí)驗(yàn)進(jìn)行了性能的評價(jià)，通過實(shí)驗(yàn)可以看出，采用了索引技術(shù)后可以較大幅度地提高查詢處理的效率。

參考文獻(xiàn)：

[1]金澈清,錢衛(wèi)寧,周傲英.流數(shù)據(jù)分析與管理綜述[J].軟件學(xué)報(bào),2004,08:1172-1181.

[2]張杰,趙峰.流數(shù)據(jù)概念漂移的檢測算法[J].控制與決策,2013,01:29-35.

[3]孫玉芬,盧炎生.流數(shù)據(jù)挖掘綜述[J].計(jì)算機(jī)科學(xué),2007,01:1-5+11.

[4]常建龍,曹鋒,周傲英+.基于滑動窗口的進(jìn)化數(shù)據(jù)流聚類[J].軟件學(xué)報(bào),2007,04:905-918.

[5]劉學(xué)軍,徐宏炳,董逸生,錢江波,王永利.基于滑動窗口的數(shù)據(jù)流閉合頻繁模式的挖掘[J].計(jì)算機(jī)研究與發(fā)展,2006,10:1738-1743.

[6]李建中,張冬冬.滑動窗口規(guī)模的動態(tài)調(diào)整算法[J].軟件學(xué)報(bào),2004,12:1800-1814.

[7]馬莎,楊波,李康順.外包數(shù)據(jù)庫中的哈希連接一致性算法[J].計(jì)算機(jī)科學(xué),2012,02:198-202+221.

[8]Tianhua Liu,Shoulin Yin. An Improved K-means Clustering Algorithm for Kalman Filter [J]. ICIC Express Letters Part B: Applications. 2015 Vol.6(10):2687-2692.

[9]陳剛,李國徽,顧晉廣,楊兵,陳輝,唐向紅.基于XJoin的細(xì)粒度無阻塞連接算法[J].計(jì)算機(jī)科學(xué),2009,08:49-53.

[10]張萌,朱曉民. IIP系統(tǒng)XJOIN框架的設(shè)計(jì)與實(shí)現(xiàn)[J].電信工程技術(shù)與標(biāo)準(zhǔn)化,2014,12:79-82.

[11]沈志榮,薛巍,舒繼武.可搜索加密機(jī)制研究與進(jìn)展[J].軟件學(xué)報(bào),2014,04:880-895.

[12]特日根,李巍,李雄飛.動態(tài)有序樹存儲模型與實(shí)現(xiàn)方法[J].計(jì)算機(jī)研究與發(fā)展,2013,05:969-985.

[13]殷守林,劉天華,李航.基于模擬退火算法的卡爾曼濾波在室內(nèi)定位中的應(yīng)用研究[J].沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,01: 86-90.

宋曉偉（1990-），男，遼寧東港人，本科，研究方向?yàn)閿?shù)據(jù)挖掘、網(wǎng)絡(luò)安全

孫陽（1978-），男，副教授，遼寧沈陽人，碩士研究生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)工程、網(wǎng)絡(luò)安全

A Sliding Window Query Strategy Based on Data Stream

SONG Xiao-wei，SUN Yang，YIN Shou-lin
（Software College, Shenyang Normal University, Liaoning 110034）

Abstract：Sliding window not only can transmit frames, but also can send byte data. It is used to improve the throughput, namely, it allows the sender transmitting additional packages before receiving any reply, and the receiver tells the sender that packages can be sent at a time. Sliding window is used to in the TCP transmission control; its size means that what size of the buffer in the receiver can be used to receive data. Designs a sliding window based on data stream query strategy, according to the size of the hop in sliding window, divides the whole of sliding window into several zones, then builds indexed connection, and processes query batch, finally, through the experiment it proves the validity of this method.

Keywords：Sliding Window; Query Strategy; Index; Batch Processing

收稿日期：2016-03-02修稿日期：2016-03-20

通信作者：殷守林（1990-），男，河南濮陽人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、網(wǎng)絡(luò)安全

作者簡介：

文章編號：1007-1423（2016）09-0022-05

DOI：10.3969/j.issn.1007-1423.2016.09.005