周虹+富春巖+支援+劉越+于占龍+薛佳楣+韋韞韜+王超+張立銘+李微娜

摘要：目前在金融、移動(dòng)數(shù)據(jù)、網(wǎng)絡(luò)監(jiān)控及物聯(lián)網(wǎng)等領(lǐng)域中，經(jīng)常會(huì)需要處理一些海量的、實(shí)時(shí)的、需要快速響應(yīng)的數(shù)據(jù)流。為了對(duì)這些數(shù)據(jù)流進(jìn)行有效的管理，提出了基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)，并對(duì)相應(yīng)的數(shù)據(jù)流并發(fā)連接算法進(jìn)行了優(yōu)化，以得到數(shù)據(jù)流預(yù)處理器所需的控制信息。

關(guān)鍵詞：數(shù)據(jù)流管理系統(tǒng)；連續(xù)查詢；查詢優(yōu)化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）33-0025-02

數(shù)據(jù)流的特點(diǎn)是：數(shù)據(jù)具有實(shí)時(shí)性，需要即時(shí)響應(yīng)；數(shù)據(jù)量大，而且無(wú)界；它還具有不可預(yù)知性，不可預(yù)期、無(wú)法控制數(shù)據(jù)流中元素的到達(dá)次序。以上這些特點(diǎn)都決定了，對(duì)數(shù)據(jù)流的查詢只能近似實(shí)時(shí)。而且，目前大多數(shù)基于軟件實(shí)現(xiàn)的數(shù)據(jù)流管理系統(tǒng)的處理速度都是有一定限制的。當(dāng)數(shù)據(jù)流的流速達(dá)到一定的速度之后，就會(huì)出現(xiàn)瓶頸，利用軟件就難以實(shí)現(xiàn)了。目前看來(lái)，比較可行的方法是來(lái)設(shè)計(jì)專門的硬件進(jìn)行預(yù)處理來(lái)解決這個(gè)問(wèn)題，即將數(shù)據(jù)流處理的某些操作利用硬件來(lái)實(shí)現(xiàn)。

提高對(duì)數(shù)據(jù)流連接操作的處理效率，是解決數(shù)據(jù)流管理系統(tǒng)中，如何提高處理速度的關(guān)鍵問(wèn)題。利用多條數(shù)據(jù)流并發(fā)執(zhí)行連接理論上可以提高處理效率，但是如何處理連接順序又在很大程度上影響了系統(tǒng)的速度。因此，如何優(yōu)化數(shù)據(jù)流并發(fā)連接查詢算法則成為了研究數(shù)據(jù)流管理系統(tǒng)的關(guān)鍵技術(shù)之一。

1 基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)

目前基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)主要由兩部分組成，包括：位于前端的預(yù)處理器和位于后端的數(shù)據(jù)引擎部分。位于前端的預(yù)處理器主要功能是完成對(duì)數(shù)據(jù)流的預(yù)處理操作?？梢詫?duì)后端傳輸過(guò)來(lái)的一些控制命令進(jìn)行初始化處理，還可以對(duì)數(shù)據(jù)流中的數(shù)據(jù)進(jìn)行濾波、壓縮和加標(biāo)記等處理工作。這種位于前端的預(yù)處理器，采用的是軟、硬件協(xié)同的方式進(jìn)行工作的，可以大大提高數(shù)據(jù)的處理速度。經(jīng)過(guò)前端預(yù)處理之后的數(shù)據(jù)通過(guò)網(wǎng)絡(luò)被傳輸?shù)胶蠖说臄?shù)據(jù)引擎部分。

系統(tǒng)后端的數(shù)據(jù)引擎主要的功能是進(jìn)行連續(xù)查詢的語(yǔ)法分析、生成要進(jìn)行并行查詢的計(jì)劃、將經(jīng)過(guò)預(yù)處理的元組分到相應(yīng)的數(shù)據(jù)緩存中，將通過(guò)并行處理后得到的查詢結(jié)果再進(jìn)行組裝分發(fā)，后端數(shù)據(jù)引擎還負(fù)責(zé)負(fù)載的均衡、服務(wù)質(zhì)量的監(jiān)控等功能。用戶提交的查詢要經(jīng)過(guò)詞法及語(yǔ)義的分析、要進(jìn)行查詢優(yōu)化才能得到所需的查詢抽象語(yǔ)法樹(shù)，在后端要對(duì)生成的抽象語(yǔ)法樹(shù)用相應(yīng)的算法進(jìn)行處理，得到所需控制信息，再將這些控制信息，經(jīng)過(guò)查詢輸出控制器交給前端的硬件查詢處理模塊進(jìn)行相應(yīng)的處理。

2 基于硬件預(yù)處理的數(shù)據(jù)流連續(xù)查詢語(yǔ)言X-SQL

在傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)中，常用的查詢語(yǔ)言是SQL，它不能用于數(shù)據(jù)流查詢中，不支持?jǐn)?shù)據(jù)流中的連續(xù)查詢語(yǔ)義。為了處理數(shù)據(jù)流中的數(shù)據(jù)，就需要使用專門處理數(shù)據(jù)流查詢的語(yǔ)言。目前，用于數(shù)據(jù)流研究的查詢語(yǔ)言主要有：基于關(guān)系的、基于對(duì)象的和基于過(guò)程的這三種語(yǔ)言[1]。

在研究過(guò)程中，我們數(shù)據(jù)流管理系統(tǒng)使用的是基于硬件預(yù)處理的數(shù)據(jù)流連續(xù)流查詢語(yǔ)言X-SQL。它是一種基于關(guān)系查詢語(yǔ)言，具有類SQL 的句法規(guī)則，它還可以提供對(duì)窗口以及對(duì)排序的支持。通過(guò)基于關(guān)系的流語(yǔ)言，用戶即可指定查詢的語(yǔ)義，也定義數(shù)據(jù)流的采樣率。

X-SQL是用滑動(dòng)窗口來(lái)實(shí)現(xiàn)連續(xù)查詢中的抽象語(yǔ)義的。我們可在系統(tǒng)后端進(jìn)行X-SQL連續(xù)查詢的輸入，再進(jìn)行交叉編譯得出相應(yīng)的一些查詢指令和信息，再通過(guò)網(wǎng)絡(luò)傳輸，將這些指令和數(shù)據(jù)輸送到硬件的預(yù)處理器中，即可進(jìn)行對(duì)數(shù)據(jù)流的各種查詢。

X-SQL由數(shù)據(jù)流定義語(yǔ)言和數(shù)據(jù)流查詢語(yǔ)言兩種語(yǔ)言構(gòu)成。其中，數(shù)據(jù)流定義語(yǔ)言是用來(lái)給數(shù)據(jù)流管理系統(tǒng)輸入元數(shù)據(jù)信息的，而數(shù)據(jù)流查詢語(yǔ)言則是實(shí)現(xiàn)對(duì)數(shù)據(jù)流進(jìn)行查詢的。

在X-SQL語(yǔ)言中，也是用SELECT語(yǔ)句來(lái)實(shí)現(xiàn)查詢功能的。只不過(guò)除了像傳統(tǒng)SQL語(yǔ)言一樣給出要返回的屬性選擇列表、要檢索數(shù)據(jù)的流的流列表和條件外，還有窗口聲明部分。窗口聲明部分是用來(lái)聲明相應(yīng)的滑動(dòng)窗口大小的。語(yǔ)法如下所示：

X-SQL查詢語(yǔ)句通過(guò)WINDOW子句就可以實(shí)現(xiàn)對(duì)滑動(dòng)窗口查詢，也就可以實(shí)現(xiàn)對(duì)數(shù)據(jù)流的連續(xù)查詢操作。

3 并發(fā)連接查詢的優(yōu)化算法

在基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)中，當(dāng)用戶提交了查詢，該查詢首先要經(jīng)過(guò)編譯器的詞法分析、語(yǔ)法分析和語(yǔ)義分析。在進(jìn)行了這些分析之后，才能得一棵語(yǔ)義正確的查詢語(yǔ)法樹(shù)。然后再依據(jù)這棵語(yǔ)意正確的語(yǔ)法樹(shù)生成相應(yīng)的目標(biāo)代碼。但是，只是可以生成目標(biāo)代碼，用這種方法生成的代碼執(zhí)行效率并不高，我們?yōu)榱颂岣卟樵兿到y(tǒng)的工作效率，就需要對(duì)一些查詢進(jìn)行優(yōu)化。

3.1 對(duì)謂詞進(jìn)行化簡(jiǎn)的優(yōu)化算法

對(duì)謂詞進(jìn)行化簡(jiǎn)就是利用應(yīng)用邏輯運(yùn)算的相應(yīng)規(guī)則，將用到的謂詞表達(dá)式，等價(jià)地置換成更簡(jiǎn)單的式子。謂詞化簡(jiǎn)的邏輯運(yùn)算規(guī)則如下表1所示：

根據(jù)規(guī)則，我們?cè)O(shè)計(jì)出謂詞化簡(jiǎn)算法，如下所示：

3.2 對(duì)謂詞進(jìn)行規(guī)范化優(yōu)化算法

除了可以對(duì)謂詞進(jìn)行化簡(jiǎn)，我們還可以在X-SQL查詢中對(duì)謂詞的規(guī)則進(jìn)行規(guī)范化優(yōu)化，規(guī)謂詞范化優(yōu)化算法如下所示：

4 結(jié)論

目前來(lái)看，大多數(shù)的數(shù)據(jù)流管理系統(tǒng)基本還是基于軟件系統(tǒng)來(lái)實(shí)現(xiàn)管理的。那么，當(dāng)數(shù)據(jù)流速過(guò)快時(shí)，處理速度就出現(xiàn)問(wèn)題。為了能提高數(shù)據(jù)流的處理速度，我們采用了基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)。并對(duì)數(shù)據(jù)流查詢語(yǔ)言X-SQL進(jìn)行了優(yōu)化。通過(guò)查詢優(yōu)化，可得到查詢語(yǔ)法樹(shù)，再對(duì)相應(yīng)的語(yǔ)法樹(shù)進(jìn)行處理，即可生成基于硬件預(yù)處理的數(shù)據(jù)流管理系統(tǒng)所需的優(yōu)化的控制信息。

參考文獻(xiàn)：

[1] Qian Jiang-bo， Xu Hong-bing， Dong Yi-sheng， et al. FPGA Acceleration window Joins over Multiple Data Stream， Journal of Circuits， Systems， and Computers， 2012，14（4）：813-830.

[2] Babcock B， Babu S， Datar M， et al. Models and Issues in Data Stream Systems [J]. In Proc. of the 2014 ACM Symp， In Principles of Database Systems， 2014：12-16.