一種基于數據流的滑動窗口查詢策略

宋曉偉，孫　陽，殷守林

（沈陽師范大學科信軟件學院，沈陽110034）

?

一種基于數據流的滑動窗口查詢策略

宋曉偉，孫陽，殷守林

（沈陽師范大學科信軟件學院，沈陽110034）

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

關鍵詞：滑動窗口；查詢策略；索引；批處理

0　引言

隨著網絡的發展，許多應用中的數據不再是數據庫中靜態的數據，而是以一種流的方式在線的到達的動態數據。這樣的數據具有數據無界，數據量大，流速快，并且要求實時處理等特性，這種新型的數據被稱為流數據[1-3]。對應的，包含流數據的應用被稱為數據流的應用。如同傳統數據庫中存在數據庫管理系統一樣，在研究數據流時需要開發數據流管理系統，這樣的系統負責對流式數據進行查詢處理。

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

1　相關工作

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

（1）對稱式的哈希連接

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

（2）擴展的哈希脈動連接

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

①結合了并行與采樣的技術，從而能加快算法的收斂；

②在內存溢出的情況下仍然能維護一個好的性能。

文章最后給出了可擴展的哈希脈動連接算法并且進行了實驗比較。

（3）XJoin

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

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

XJoin技術比較先進，因為在其中存在對主存與輔存之間進行控制、后臺處理、確保最后的結果能夠全部產生和進行一些消除重復結果的操作等，而這些無疑都是很復雜的。

2　數據流的滑動窗口查詢策略

（1）滑動窗口的劃分

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

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

（2）建立索引

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

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

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

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

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

（3）索引連接

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

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

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

3　索引共享及聚集查詢

（1）多連接的索引查詢

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

查詢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表示窗口約束條件是基于時間的滑動窗口連接，兩個參數分別為窗口大小和更新頻率hop的大小。這兩個查詢具有相同的連接條件和窗口約束條件，我們分別對流Stock1和流Stock2建立索引，按照窗口的約束條件，可以將每個滑動窗口分成10/2=5個BW區域，對每個區域中的數據建立一個紅黑樹索引。在進行連接查詢處理的時候，Q1和Q2兩個查詢可以共享使用所建立起來的索引。每次使用其中一個流上的一個元組去掃描另一個流所對應的索引，得到連接的結果同時返回給兩個查詢，然后各自獨立的繼續執行查詢計劃的其他部分（對Q1可以直接返回連接的結果了，而Q2則還需要對連接結果做投影操作）。

然后再考慮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的窗口維護索引信息，在查詢處理的過程中控制處理元組的范圍，將不同范圍的結果返回給相應的查詢。

（2）流上的聚集查詢

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

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

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

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

4　實驗與結果分析

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

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

5　結語

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

參考文獻：

[1]金澈清,錢衛寧,周傲英.流數據分析與管理綜述[J].軟件學報,2004,08:1172-1181.

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

[3]孫玉芬,盧炎生.流數據挖掘綜述[J].計算機科學,2007,01:1-5+11.

[4]常建龍,曹鋒,周傲英+.基于滑動窗口的進化數據流聚類[J].軟件學報,2007,04:905-918.

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

[6]李建中,張冬冬.滑動窗口規模的動態調整算法[J].軟件學報,2004,12:1800-1814.

[7]馬莎,楊波,李康順.外包數據庫中的哈希連接一致性算法[J].計算機科學,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的細粒度無阻塞連接算法[J].計算機科學,2009,08:49-53.

[10]張萌,朱曉民. IIP系統XJOIN框架的設計與實現[J].電信工程技術與標準化,2014,12:79-82.

[11]沈志榮,薛巍,舒繼武.可搜索加密機制研究與進展[J].軟件學報,2014,04:880-895.

[12]特日根,李巍,李雄飛.動態有序樹存儲模型與實現方法[J].計算機研究與發展,2013,05:969-985.

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

宋曉偉（1990-），男，遼寧東港人，本科，研究方向為數據挖掘、網絡安全

孫陽（1978-），男，副教授，遼寧沈陽人，碩士研究生導師，研究方向為網絡工程、網絡安全

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-），男，河南濮陽人，碩士研究生，研究方向為數據挖掘、網絡安全

作者簡介：

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

DOI：10.3969/j.issn.1007-1423.2016.09.005