面向?qū)崟r(shí)事件流的復(fù)雜事件處理方法

收稿日期：2021-12-30；修回日期：2022-03-28" 基金項(xiàng)目：國家自然科學(xué)基金青年基金資助項(xiàng)目（62002245）；遼寧省教育廳基礎(chǔ)研究項(xiàng)目（JYT2020027）

作者簡(jiǎn)介：邱濤（1989-），男，江西萍鄉(xiāng)人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)樾蛄袛?shù)據(jù)處理、查詢優(yōu)化、數(shù)據(jù)挖掘；謝沛良（1997-），男（通信作者），江西贛州人，碩士研究生，主要研究方向?yàn)閺?fù)雜事件處理（xiepl1997@163.com）；鄧國鵬（1977-），男，遼寧開原人，學(xué)士，主要研究方向?yàn)檫b測(cè)數(shù)據(jù)分析處理；郗紅梅（1969-），女，遼寧沈陽人，學(xué)士，主要研究方向?yàn)檫b測(cè)數(shù)據(jù)分析處理；鄭智（1988-），男，遼寧撫順人，學(xué)士，主要研究方向?yàn)檫b測(cè)數(shù)據(jù)分析處理；夏秀峰（1964-），男，山東青島人，教授，碩導(dǎo)，博士，主要研究方向?yàn)閿?shù)據(jù)庫、數(shù)據(jù)倉庫、數(shù)據(jù)挖掘.

摘 要：

復(fù)雜事件處理技術(shù)通常基于有限狀態(tài)自動(dòng)機(jī)實(shí)現(xiàn)，匹配過程中會(huì)在事件流上產(chǎn)生大量且重疊的部分匹配，有限狀態(tài)自動(dòng)機(jī)需維護(hù)大量的重復(fù)匹配狀態(tài)，導(dǎo)致基于該技術(shù)的方法都會(huì)出現(xiàn)冗余計(jì)算的問題。為了提高復(fù)雜事件處理的匹配效率，提出了使用復(fù)雜事件實(shí)例覆蓋技術(shù)來實(shí)現(xiàn)復(fù)雜事件處理的方法。通過設(shè)計(jì)臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)以及基于此結(jié)構(gòu)的匹配算法來利用復(fù)雜事件實(shí)例覆蓋減少冗余計(jì)算，從而實(shí)現(xiàn)匹配效率的提升。在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)測(cè)試與分析，與兩種常用的復(fù)雜事件處理技術(shù)進(jìn)行比較。實(shí)驗(yàn)表明，提出方法能夠在保證匹配正確性的同時(shí)有效地減少匹配過程中的冗余計(jì)算，提高整體匹配效率。

關(guān)鍵詞：復(fù)雜事件處理； 查詢優(yōu)化； 有限狀態(tài)自動(dòng)機(jī)； 分區(qū)存儲(chǔ)

中圖分類號(hào)：TP315"" 文獻(xiàn)標(biāo)志碼：A"" 文章編號(hào)：1001-3695（2022）09-018-2677-06

doi： 10.19734/j.issn.1001-3695.2021.12.0707

Complex event processing method over real-time event streams

Qiu Tao1， Xie Peiliang1， Deng Guopeng2， Xi Hongmei2， Zheng Zhi2， Xia Xiufeng1

（1.School of Computer Science， Shenyang Aerospace University， Shenyang 110136， China; 2. Flight Test Station， Shenyang Aircraft Industry （Group） Co. Ltd.， Shenyang 110034， China）

Abstract：Complex event processing technology is usually implemented based on finite state automaton. During the matching process，a large number of overlapping partial matches will be generated by the event stream. The finite state automaton needs to maintain a large number of repeated matching states，which leads to the problem of redundant calculation in the methods based on this technology. In order to improve the matching efficiency of complex event processing，this paper proposed a method of using complex event instance coverage technology to realize complex event processing. By designing a temporary matching chain partition storage structure and matching algorithms based on this structure，it used complex event instance coverage to reduce redundant calculations，so as to improve the matching efficiency. Experiments were performed on simulated and real datasets，and compared with two commonly used complex event processing technologies. The experimental results show that the proposed method can effectively reduce the redundant computation in the matching process while ensuring the correctness of the matching，and improve the overall matching efficiency.

Key words：complex event processing（CEP）; query optimization; nondeterministic finite automaton（NFA）; partition storage

0 引言

隨著信息社會(huì)的進(jìn)一步發(fā)展，越來越多的行業(yè)采用復(fù)雜事件處理（CEP）技術(shù)來對(duì)海量的事件流進(jìn)行實(shí)時(shí)的分析。復(fù)雜事件處理通過分析事件中的關(guān)系，通過關(guān)聯(lián)、聚合、過濾等技術(shù)，根據(jù)事件間的時(shí)序關(guān)系和聚合關(guān)系制定查詢規(guī)則，持續(xù)地從事件流中獲取符合要求的事件序列。該技術(shù)在金融交易分析［1，2］、傳感器網(wǎng)絡(luò)［3］、物聯(lián)網(wǎng)［4～6］、交通［7］領(lǐng)域都有著廣泛的應(yīng)用。

目前，基于有限狀態(tài)自動(dòng)機(jī)（NFA）的處理模型是最流行的復(fù)雜事件處理技術(shù)實(shí)現(xiàn)方式，例如SASE［8，9］、Cayuga［10，11］和Siddhi［12］。通過NFA的方式來實(shí)現(xiàn)的復(fù)雜事件處理技術(shù)，在事件流上進(jìn)行匹配的過程中都會(huì)產(chǎn)生臨時(shí)匹配，所產(chǎn)生的臨時(shí)匹配能夠被后續(xù)的事件使用，并且生成新的臨時(shí)匹配以及最終的匹配結(jié)果。所以匹配過程中會(huì)在事件流上產(chǎn)生大量且重疊的部分匹配，有限狀態(tài)自動(dòng)機(jī)需維護(hù)大量的重復(fù)匹配狀態(tài)，導(dǎo)致基于該技術(shù)的方法都會(huì)出現(xiàn)冗余計(jì)算的問題。尤其當(dāng)復(fù)雜事件查詢的時(shí)間窗口跨度大時(shí)，冗余計(jì)算將會(huì)給處理器和存儲(chǔ)器等硬件資源帶來巨大的額外開銷。

為了減少基于有限狀態(tài)自動(dòng)機(jī)的復(fù)雜事件處理技術(shù)中的冗余計(jì)算，提高匹配效率，本文利用鏈?zhǔn)椒謪^(qū)存儲(chǔ)的結(jié)構(gòu)來管理臨時(shí)匹配，利用復(fù)雜事件實(shí)例覆蓋來減少臨時(shí)匹配的冗余產(chǎn)生和冗余拷貝，從而提高復(fù)雜事件匹配的效率。

綜上所述，本文的主要貢獻(xiàn)如下：

a）提出了復(fù)雜事件實(shí)例覆蓋的概念，通過復(fù)雜事件實(shí)例覆蓋，可以建立臨時(shí)匹配之間的關(guān)聯(lián)關(guān)系，基于此關(guān)系來減少臨時(shí)匹配的冗余產(chǎn)生和冗余復(fù)制。

b）設(shè)計(jì)了一個(gè)臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)，通過該結(jié)構(gòu)避免了臨時(shí)匹配的集中式存儲(chǔ)及使用，同時(shí)該結(jié)構(gòu)也作為復(fù)雜事件實(shí)例覆蓋的載體，構(gòu)建了臨時(shí)匹配之間的關(guān)聯(lián)。

c）提出了基于臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)的復(fù)雜事件匹配算法CoverMatch和CombineMatch。通過這兩個(gè)算法，能夠在減少臨時(shí)匹配數(shù)量和復(fù)制的情況下保證復(fù)雜事件處理匹配結(jié)果的正確性和完整性。

d）通過在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上對(duì)優(yōu)化方法的性能進(jìn)行對(duì)比實(shí)驗(yàn)和分析，驗(yàn)證了所提算法的有效性和高效性。

1 相關(guān)工作

復(fù)雜事件處理是從事件驅(qū)動(dòng)業(yè)務(wù)出發(fā)的，將系統(tǒng)中產(chǎn)生的每一條數(shù)據(jù)記錄都看成是一個(gè)事件，實(shí)時(shí)輸入的數(shù)據(jù)流即為實(shí)時(shí)事件流，復(fù)雜事件執(zhí)行引擎會(huì)根據(jù)事先制定好的復(fù)雜事件描述規(guī)則來對(duì)事件流進(jìn)行相應(yīng)的判斷、過濾、關(guān)聯(lián)等操作，然后給用戶輸出一系列的更高層次的復(fù)合事件。其中復(fù)雜事件描述規(guī)則一般包含用戶感興趣的事件語義，或者是專業(yè)領(lǐng)域中某種既定的標(biāo)準(zhǔn)和規(guī)范。即是說，復(fù)雜事件處理能夠在實(shí)時(shí)事件流中識(shí)別某一個(gè)人為定義的復(fù)合事件，并且為用戶反饋?zhàn)R別的結(jié)果。

目前復(fù)雜事件處理技術(shù)已經(jīng)有了很多的研究成果，復(fù)雜事件處理技術(shù)一般采用非確定性有限狀態(tài)自動(dòng)機(jī)的變體模型來處理復(fù)雜事件的識(shí)別。

Diao等人提出的SASE是一種復(fù)雜事件處理引擎，同時(shí)還提出了一種能夠定義復(fù)合事件的事件描述語言 CEL［13，14］，這種語言具有類似SQL的高級(jí)結(jié)構(gòu)，可定義事件序列、匹配策略、事件約束和事件窗口約束等。通過SASE引擎可將事件描述語言所定義的復(fù)合事件轉(zhuǎn)變?yōu)榉谴_定性有限狀態(tài)自動(dòng)機(jī)，從而實(shí)現(xiàn)在事件流上的事件獲取和計(jì)算。Diao等人［15］還在SASE+中對(duì)SASE進(jìn)行了擴(kuò)展，引入了對(duì)克林閉包、否定和聚合操作的支持。SASE/SASE+的主要缺陷在于，在NFA進(jìn)行匹配的過程中需要產(chǎn)生匹配結(jié)果的臨時(shí)匹配，同時(shí)為了保證結(jié)果的準(zhǔn)確性，不允許在時(shí)間窗口約束內(nèi)將臨時(shí)匹配丟棄，這種機(jī)制導(dǎo)致了臨時(shí)匹配的堆積，從而影響了自動(dòng)機(jī)的處理效率。

康奈爾大學(xué)開發(fā)的Cayuga也采用NFA作為計(jì)算模型來處理事件的識(shí)別，但是它對(duì)于事件的描述能力相對(duì)較差。Cayuga支持發(fā)布—訂閱技術(shù)，并且提供了良好的可擴(kuò)展性，此外還運(yùn)用了查詢優(yōu)化技術(shù)，可將多個(gè)擁有相同時(shí)間戳的具有等價(jià)狀態(tài)的事件一同進(jìn)行處理。但是由于它的內(nèi)核是單線程的，并沒有有效地從這些優(yōu)化技術(shù)中獲益。

FlinkCEP［16］在設(shè)計(jì)思想上與SASE很接近，同樣使用事件約束作為NFA節(jié)點(diǎn)狀態(tài)轉(zhuǎn)變的條件。從事件描述語言的角度來看，F(xiàn)linkCEP與SASE的一個(gè)最大的區(qū)別是FlinkCEP沒有支持定義復(fù)合事件的語言。為了替代事件描述語言，F(xiàn)linkCEP需要用戶使用Java或者Scala編寫事件描述，這種定義方式可讀性差且編寫時(shí)易出錯(cuò)。

除了基于NFA模型實(shí)現(xiàn)的復(fù)雜事件處理技術(shù)之外，另外一種使用樹來作為計(jì)算模型的實(shí)現(xiàn)復(fù)雜事件處理的技術(shù)也得到了廣泛的研究和應(yīng)用。

Mei等人［17］提出的ZStream是CEP領(lǐng)域基于樹實(shí)現(xiàn)復(fù)雜事件處理技術(shù)的典型研究成果。ZStream的事件描述語言與SASE非常相似，所遵循的語法大多數(shù)都相同。ZStream將事件存儲(chǔ)在葉子節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)于操作符。在進(jìn)行事件流處理時(shí)，它不會(huì)立刻判斷到達(dá)事件的約束條件，而是先把事件收集到一定量，進(jìn)而對(duì)其進(jìn)行批處理。樹結(jié)構(gòu)和批處理的結(jié)合允許ZStream根據(jù)期望成本和條件約束來執(zhí)行各種復(fù)雜事件處理任務(wù)。例如，對(duì)于給定的復(fù)雜事件序列〈A，B〉，SASE將會(huì)為每一個(gè)出現(xiàn)的A事件新建一個(gè)臨時(shí)匹配，即使B事件的出現(xiàn)概率很低，而ZStream則可以遵循另一個(gè)匹配規(guī)則，一直等待B事件到達(dá)，再去批量檢查先前到達(dá)的A事件。但是ZStream仍然不能避免大量的未處理事件的堆積，這與NFA產(chǎn)生臨時(shí)匹配的堆積本質(zhì)上是一樣的。

基于以上的研究可以發(fā)現(xiàn)，無論是基于NFA還是基于樹的方法來實(shí)現(xiàn)復(fù)雜事件處理技術(shù)，為了復(fù)雜事件匹配結(jié)果的正確性和完整性，都需要存儲(chǔ)至少一個(gè)時(shí)間窗口范圍內(nèi)的臨時(shí)匹配。假設(shè)時(shí)間窗口跨度很大，復(fù)雜事件的處理將對(duì)處理器計(jì)算能力和存儲(chǔ)器等硬件資源帶來不小的負(fù)荷。

2 預(yù)備工作

復(fù)雜事件處理是一種面向事件流的查詢分析技術(shù)，其目標(biāo)是從大量的基本事件構(gòu)成的事件流中找出滿足復(fù)雜事件描述語義的更高層次的復(fù)雜事件。本章將詳細(xì)介紹復(fù)雜事件處理涉及的預(yù)備知識(shí)。

定義1 事件流。事件流S（s1，s2，…，sn）由一系列的基本事件實(shí)例構(gòu)成，其中si為事件實(shí)例，它包含了事件的類型、事件的屬性和事件發(fā)生時(shí)的時(shí)間戳等信息。

事件流往往是由多個(gè)數(shù)據(jù)源的數(shù)據(jù)構(gòu)成的，在使用海量數(shù)據(jù)的很多研究應(yīng)用領(lǐng)域里，例如氣象預(yù)測(cè)［18］、海上航行［19］和交通數(shù)據(jù)研究［20］，數(shù)據(jù)源可以是采集設(shè)備或者是傳感器，因此需要先對(duì)數(shù)據(jù)使用融合技術(shù)［21，22］進(jìn)行融合以得到包含多事件類型的事件流。

圖1是船只在航行中產(chǎn)生事件流的示例圖。其中事件流包含了A、B、C三種事件類型，A表示低速啟動(dòng)，B表示船頭左轉(zhuǎn)90°，C表示低速停靠。每個(gè)事件實(shí)例都包含時(shí)間戳以及屬性值，此處使用相應(yīng)的小寫英文字母表示事件實(shí)例。例如，b1為B事件類型的第一個(gè)事件實(shí)例，其時(shí)間戳為2，此外還包括行駛速度、行駛方向以及傾斜角度等屬性。

通過觀察圖1所示的事件流可以得知，在時(shí)間窗口1～12內(nèi)，船只先是低速開始啟動(dòng)，之后在航行過程中轉(zhuǎn)了一個(gè)圈，最后低速停靠。

復(fù)雜事件是由事件流S（s1，s2，…，sn）上的若干事件實(shí)例構(gòu)成的一個(gè)復(fù)合事件，表示為R（r1，r2，…，rn），ri∈S（0≤i≤n） 。復(fù)雜事件表示在事件流上發(fā)生的客觀存在的具體事件，其語義通常通過復(fù)雜事件描述語言所定義的查詢來進(jìn)行表示。

定義2 復(fù)雜事件查詢。復(fù)雜事件查詢Q是由一組定義在基本事件上的約束條件構(gòu)成，用以定義和表示更高層次的復(fù)雜事件的屬性特征。

當(dāng)前研究工作中已提出多種形式的復(fù)雜事件描述語言用以定義復(fù)雜事件查詢，其中SASE提出了最具有代表性的復(fù)雜事件描述語言。其具備簡(jiǎn)潔的語法規(guī)則、靈活的表達(dá)能力，所以本文將使用SASE復(fù)雜事件描述語言來定義復(fù)雜事件查詢。SASE事件描述語言是一種聲明式語言，總體結(jié)構(gòu)如下：

PATTERN" 〈sequence pattern〉

［WHERE〈qualification〉］

［AND〈other qualifications〉］

［WITHIN〈time window〉］

使用上述的結(jié)構(gòu)可以編寫復(fù)雜事件查詢。默認(rèn)情況下，查詢將讀取事件流中實(shí)時(shí)到達(dá)的事件，從而進(jìn)行復(fù)雜事件處理，最后將匹配成功的復(fù)雜事件反饋給用戶。

為了解釋SASE事件描述語言結(jié)構(gòu)的含義，現(xiàn)在使用一個(gè)基于道路交通場(chǎng)景構(gòu)造的例子來說明。在這個(gè)例子中，事件類型TrafficInfo為道路地點(diǎn)所收集到該地點(diǎn)的交通數(shù)據(jù)報(bào)告，一個(gè)報(bào)告對(duì)應(yīng)一個(gè)事件實(shí)例。假設(shè)報(bào)告內(nèi)容包含該地點(diǎn)的位置，以及某一時(shí)刻的車流量、平均車速等。所構(gòu)造的查詢?nèi)鏠1所示。

Q1：PATTERN" SEQ（TrafficInfo a， TrafficInfo+b［］）

WHEREskip-till-any-match

ANDa.pos=tollA

ANDb.posgt;a.pos+5 miles

ANDb［i］.countgt;b［i-1］.count

WITHIN1 hour

上述查詢定義了一個(gè)復(fù)雜事件：距離A收費(fèi)站5英里遠(yuǎn)的某地點(diǎn)，其車流量在1 h的時(shí)間范圍內(nèi)逐漸增大，其中事件之間的默認(rèn)時(shí)間戳約束為a.timestamplt;b.timestamp、b［i］.timestamplt;b［i+1］.timestamp。

其中PATTERN部分定義了復(fù)雜事件的事件序列，使用SEQ結(jié)構(gòu)來指定兩個(gè)事件類型構(gòu)成事件序列。可以看到兩個(gè)事件類型都是TrafficInfo，后者使用了克林閉包，使用“+”來表示一個(gè)或者多個(gè)指定類型的事件，同時(shí)需要結(jié)合“［］”來申明。除了定義順序序列和閉包序列，PATTERN部分還可以定義否定操作，只需要在事件類型前面加上“！”，例如SEQ（A a，！B b，C c）表示在a.timestamplt;c.timestamp的條件下，A和C類型的事件實(shí)例之間不允許出現(xiàn)B類型的事件實(shí)例。

WHERE部分指定了當(dāng)前查詢所用到的匹配策略，skip-till-any-match表示將在事件流中匹配所有的結(jié)果，本文將只討論該策略下的復(fù)雜事件匹配，其他策略匹配出的結(jié)果都是skip-till-any-match策略所匹配結(jié)果的子集，故不做另外討論。AND部分定義了事件約束，是作為WHERE約束的延伸。WITHIN則定義了時(shí)間窗口約束，將所要匹配的結(jié)果事件跨度限制在一定范圍內(nèi)。

通過以上事件描述語言的語法規(guī)則寫成的一個(gè)復(fù)雜事件查詢Q，將通過復(fù)雜事件處理引擎在事件流上進(jìn)行查詢分析，并得到查詢結(jié)果。

3 查詢優(yōu)化技術(shù)

本章將對(duì)提出的復(fù)雜事件查詢優(yōu)化技術(shù)進(jìn)行詳細(xì)的介紹。首先對(duì)于基于有限狀態(tài)自動(dòng)機(jī)的復(fù)雜事件匹配技術(shù)進(jìn)行分析，通過設(shè)計(jì)并實(shí)現(xiàn)一個(gè)臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)以及查詢優(yōu)化算法，來優(yōu)化基于有限狀態(tài)自動(dòng)機(jī)的復(fù)雜事件匹配方法的技術(shù)，提升查詢匹配的效率。

3.1 基于有限狀態(tài)自動(dòng)機(jī)的匹配方法

基于有限狀態(tài)自動(dòng)機(jī)的匹配方式是目前使用最廣泛并且有效的復(fù)雜事件匹配技術(shù)。以SASE為例，處理一個(gè)復(fù)雜事件查詢的步驟有：a）將查詢解析為一個(gè)有限狀態(tài)自動(dòng)機(jī)；b）讀取事件流；c）進(jìn)行復(fù)雜事件匹配，產(chǎn)生臨時(shí)匹配結(jié)果或成功匹配結(jié)果。

本節(jié)通過構(gòu)造一個(gè)查詢Q2及其匹配過程來詳細(xì)介紹基于有限狀態(tài)自動(dòng)機(jī)的匹配方法。

Q2：PATTERN" SEQ（A a，B+b［］，C c）

WHEREskip-till-any-match

ANDb［i］.valgt;=b［i+1］.val

WITHIN50

Q2包含了一個(gè)B事件類型的克林閉包，表示匹配一個(gè)或者多個(gè)B類型的事件實(shí)例，并且在B事件的約束條件下， Q2只會(huì)匹配屬性值val遞減的B事件序列，所以Q2匹配的復(fù)雜事件是以A事件類型的事件實(shí)例開頭，然后是B事件類型的val遞減事件實(shí)例序列，最后以C事件類型的事件實(shí)例作為結(jié)尾。將Q2以文本的形式作為SASE的輸入，Q2經(jīng)過編譯后，在SASE內(nèi)部得到一個(gè)對(duì)應(yīng)的有限狀態(tài)自動(dòng)機(jī)，如圖2所示。

在圖2展示的有限狀態(tài)自動(dòng)機(jī)中，begin表示在當(dāng)前狀態(tài)下獲取一個(gè)符合條件的事件實(shí)例并保存，從而轉(zhuǎn)移到下一個(gè)狀態(tài)。ignore表示當(dāng)遇到不符合條件的事件實(shí)例，就保持當(dāng)前狀態(tài)不變。take和proceed是閉包節(jié)點(diǎn)獨(dú)有的動(dòng)作，take表示獲取相同類型并且符合條件的事件實(shí)例，并保持當(dāng)前狀態(tài)。而proceed可以將NFA從閉包節(jié)點(diǎn)狀態(tài)跳出到下一個(gè)狀態(tài)，并且take和proceed動(dòng)作是同時(shí)發(fā)生的。也就是說在b［i］節(jié)點(diǎn)，狀態(tài)機(jī)的狀態(tài)既可以轉(zhuǎn)換為c，也可以保持b［i］的狀態(tài)不變。

在SASE中是通過NFA來處理事件流的，例如當(dāng)數(shù)據(jù)流中來了一個(gè)A事件類型的實(shí)例，則圖2中的NFA則會(huì)初始化一個(gè)包含該實(shí)例的臨時(shí)匹配，這個(gè)臨時(shí)匹配會(huì)一直存在，直到事件流當(dāng)前的時(shí)間戳與該臨時(shí)匹配的時(shí)間跨度超過了查詢的時(shí)間窗口，才會(huì)將其移除。此外，當(dāng)NFA在該臨時(shí)匹配的基礎(chǔ)上與當(dāng)前事件流中的事件能夠發(fā)生狀態(tài)變化時(shí)，將會(huì)對(duì)臨時(shí)匹配進(jìn)行拷貝，然后把新的事件添加到新拷貝的臨時(shí)匹配上，而原來的臨時(shí)匹配繼續(xù)保留。這樣做的目的是為了保留NFA的上一個(gè)狀態(tài)以及其中的匹配序列。

為清晰說明基于有限狀態(tài)自動(dòng)機(jī)的匹配過程，假設(shè)Q2在一段特定事件流S（a1，b1，b2，b3，c1）上進(jìn)行查詢，事件流S的時(shí)間戳和屬性值如圖3所示。Q2在S上的匹配過程，可以通過圖4來展示。

由圖4可知，在SASE中通過有限狀態(tài)自動(dòng)機(jī)來處理事件流，當(dāng)a1事件到達(dá)時(shí)，驗(yàn)證成功，初始化一個(gè)包含a1事件實(shí)例的臨時(shí)匹配（a1，-），該臨時(shí)匹配的存在表示著圖2中NFA的“a”節(jié)點(diǎn)狀態(tài)的匹配存在。當(dāng)b1事件實(shí)例到達(dá)并且驗(yàn)證成功后，系統(tǒng)將會(huì)把（a1，-）備份，然后將原有的臨時(shí)匹配進(jìn)行更新，更新為（a1，b1，-），所以系統(tǒng)中出現(xiàn)了兩個(gè)臨時(shí)匹配，等到下一個(gè)到達(dá)的事件并且驗(yàn)證成功后，就需要對(duì)兩個(gè)臨時(shí)匹配進(jìn)行拷貝和更新，于是就出現(xiàn)了四個(gè)臨時(shí)匹配。

通過這個(gè)方法顯然可以將事件流中的正確匹配結(jié)果都找出來，但是缺點(diǎn)也是顯而易見的，在匹配的過程中產(chǎn)生了很多的臨時(shí)匹配用以表示臨時(shí)匹配序列，同時(shí)用以保存NFA的匹配狀態(tài)。所以隨著匹配的進(jìn)行，最壞的情況下系統(tǒng)中的臨時(shí)匹配數(shù)量呈現(xiàn)指數(shù)增長趨勢(shì)，系統(tǒng)的計(jì)算開銷和存儲(chǔ)開銷也將越來越大。

3.2 減少冗余計(jì)算

針對(duì)基于NFA的復(fù)雜事件處理中產(chǎn)生的大量臨時(shí)匹配和拷貝而導(dǎo)致的冗余計(jì)算，本文提出了事件實(shí)例覆蓋和復(fù)雜事件實(shí)例覆蓋的概念，同時(shí)設(shè)計(jì)了一個(gè)臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)和基于此結(jié)構(gòu)的匹配算法CoverMatch來減少冗余計(jì)算從而提高基于NFA的復(fù)雜事件處理的性能，另外設(shè)計(jì)了匹配結(jié)果聯(lián)結(jié)算法CombineMatch來完善匹配結(jié)果的生成。

定義3 事件實(shí)例覆蓋。當(dāng)事件實(shí)例si與事件流中相鄰的前一個(gè)事件實(shí)例si-1同屬一個(gè)事件類型，并且都能夠被當(dāng)前的NFA驗(yàn)證成功且作用在NFA的同一個(gè)狀態(tài)節(jié)點(diǎn)，則稱si是si-1的一個(gè)事件實(shí)例覆蓋。

定義4 復(fù)雜事件實(shí)例覆蓋。對(duì)于兩個(gè)匹配結(jié)果M1和M2來說，如果M1中的每一個(gè)事件實(shí)例，都相等于M2中對(duì)應(yīng)的事件實(shí)例或是M2中對(duì)應(yīng)事件實(shí)例的事件實(shí)例覆蓋，則稱M1是M2的一個(gè)復(fù)雜事件實(shí)例覆蓋。

事件實(shí)例覆蓋是可傳遞的，例如在圖3的事件流S中的三個(gè)事件實(shí)例b1～b3，事件類型都是相同的，并且能夠被Q2對(duì)應(yīng)的NFA驗(yàn)證成功且作用在同一個(gè)狀態(tài)節(jié)點(diǎn)，所以b2是b1的事件實(shí)例覆蓋，b3是b2的事件實(shí)例覆蓋，則b3也是b1的事件實(shí)例覆蓋。同理，復(fù)雜事件實(shí)例覆蓋也是可傳遞的。例如在圖3中的事件流上，進(jìn)行SEQ（A a，B b，C c）的匹配，則會(huì)得到的匹配結(jié)果是m1（a1，b1，c4）、m2（a1，b2，c4）、m3（a1，b3，c4）。按照定義4，m2是m1的復(fù)雜事件實(shí)例覆蓋，m3是m2的復(fù)雜事件實(shí)例覆蓋，且可傳遞，則m3也是m1的一個(gè)復(fù)雜事件實(shí)例覆蓋。

很多場(chǎng)景都能夠應(yīng)用復(fù)雜事件實(shí)例覆蓋，因?yàn)閺?fù)雜事件實(shí)例覆蓋能運(yùn)用在匹配距離當(dāng)前事件最近的復(fù)雜事件上，例如在股票事件流上尋找某一只股票最近的一次價(jià)格反彈事件、在交通數(shù)據(jù)事件流上尋找某地點(diǎn)最新的擁堵事件等。

在復(fù)雜事件匹配的過程中，如果只去匹配復(fù)雜事件實(shí)例覆蓋的話，在出現(xiàn)連續(xù)的相同事件類型實(shí)例的情況下，可以以更快的效率完成匹配任務(wù)。同時(shí)，相對(duì)于SASE中的基于NFA下的skip-till-any-match利用大量臨時(shí)匹配計(jì)算所有結(jié)果的策略，使用本文方法可以在匹配復(fù)雜事件實(shí)例覆蓋的同時(shí)，利用結(jié)果聯(lián)結(jié)算法，可以得到所有的匹配結(jié)果，過程高效并且不產(chǎn)生額外臨時(shí)匹配，從而達(dá)到減少冗余計(jì)算的目的。

3.2.1 臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)

為了讓有限狀態(tài)自動(dòng)機(jī)支持本文優(yōu)化方法達(dá)到減少冗余計(jì)算的目的，本文對(duì)NFA進(jìn)行了增強(qiáng)，為其設(shè)計(jì)了一個(gè)臨時(shí)匹配的鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)，用以替代原來的集中式的臨時(shí)匹配存儲(chǔ)方式。集中式的臨時(shí)匹配存儲(chǔ)方式的缺陷上面已經(jīng)提到過了，每次新的事件到來時(shí)都需要對(duì)所有的臨時(shí)匹配進(jìn)行遍歷驗(yàn)證，這將嚴(yán)重消耗計(jì)算資源。而臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)則借助事件實(shí)例覆蓋和復(fù)雜事件實(shí)例覆蓋的概念來設(shè)計(jì)，規(guī)避了集中式臨時(shí)匹配存儲(chǔ)的缺點(diǎn)。

假設(shè)當(dāng)前存在查詢Q4：SEQ（A a，B b，C c），以及事件流St（a1，a2，b1，b2，a3，b3，c1，c2）。為了簡(jiǎn)明易懂，Q4的事件約束條件將置為空，且設(shè)置其時(shí)間窗口大于事件流St的時(shí)間范圍。當(dāng)查詢Q4在事件流St上進(jìn)行復(fù)雜事件實(shí)例覆蓋匹配時(shí)，臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)如圖5所示。

在Q4被編譯成NFA之后，存在三個(gè)主要狀態(tài)（狀態(tài)F為終止?fàn)顟B(tài)），這三個(gè)狀態(tài)將分別產(chǎn)生三個(gè)分區(qū)，簡(jiǎn)稱為A～C分區(qū)。事件流St中的事件實(shí)例a1和a2到達(dá)處理系統(tǒng)之后，將分別產(chǎn)生臨時(shí)匹配并存儲(chǔ)在A分區(qū)，同時(shí)分別打包成鏈表節(jié)點(diǎn)〈a1〉和〈a2〉。由于a2是a1的事件實(shí)例覆蓋，所以〈a2〉將作為〈a1〉的后繼節(jié)點(diǎn)，并且暴露給下一個(gè)B分區(qū)。在一個(gè)分區(qū)中所有的鏈表都僅將鏈表尾節(jié)點(diǎn)暴露給下一個(gè)分區(qū)。當(dāng)事件實(shí)例b1到達(dá)，首先會(huì)在上一個(gè)A分區(qū)中尋找暴露節(jié)點(diǎn)并拷貝下來，也就是〈a2〉節(jié)點(diǎn)，然后進(jìn)行更新成為〈a2，b1〉節(jié)點(diǎn)，并作為鏈表頭存儲(chǔ)在B分區(qū)并暴露給C分區(qū)。隨后事件實(shí)例b2到達(dá)，b2也會(huì)找到A分區(qū)的暴露節(jié)點(diǎn)〈a2〉，會(huì)產(chǎn)生一個(gè)節(jié)點(diǎn)〈a2，b2〉，由于〈a2，b2〉是〈a2，b1〉的復(fù)雜事件實(shí)例覆蓋，所以〈a2，b2〉會(huì)成為〈a2，b1〉的后繼節(jié)點(diǎn)，并且替代〈a2，b1〉暴露給C分區(qū)。同理，當(dāng)事件流St中的事件都到達(dá)并被處理之后，最終會(huì)得到三個(gè)復(fù)雜事件實(shí)例覆蓋〈a2，b2，c2〉、〈a2，b3，c2〉、〈a3，b3，c2〉。該匹配過程見算法1。

算法1 基于鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)的匹配算法CoverMatch

輸入：事件流Se；查詢Q。

輸出：復(fù)雜事件實(shí)例覆蓋集Rs。

1 e←1;

2 Rs←;

3 nfa←parse（Q）;

4 while （e←Se.nextEvent（）amp;amp;e！=1） do

5" if ！nfa.verfy（e） do

6"" continue;

7" tempMatchList←buildTempMatch（e）;

8" checkTimeWindow（tempMatchList）;

9" if tempMatchList.isEmpty（） do

10"" continue;

11" region←nfa.getRegion（e.eventType）;

12" for each tempMatch in tempMatchList do

13"" node←getDominateMatch（tempMathch， region.getcandidates（））;

14"" if node！=1 do

15""" node.next=tempMatch;

16"" else

17""" region.setcandidate（tempMatch）;

18 for each r in nfa.getLastRegion（）.getcandidates do

19" Rs.add（r.prev）;

20 return Rs

在算法1中，第7行的buildTempMatch方法表示了使用事件e在上一個(gè)分區(qū)中遍歷暴露的匹配節(jié)點(diǎn)，將能夠進(jìn)行更新的節(jié)點(diǎn)拷貝，進(jìn)行更新，然后再進(jìn)入到當(dāng)前分區(qū)進(jìn)行復(fù)雜事件實(shí)例覆蓋的檢查，如果不是某個(gè)節(jié)點(diǎn)的復(fù)雜事件實(shí)例覆蓋，就單獨(dú)成鏈（第17行），否則成為某個(gè)鏈的鏈尾節(jié)點(diǎn)（第15行）。最后返回最終的復(fù)雜事件實(shí)例覆蓋。由于采用的數(shù)據(jù)結(jié)構(gòu)是雙向環(huán)形鏈?zhǔn)浇Y(jié)構(gòu)，所以第19行使用prev可以直接定位到鏈尾節(jié)點(diǎn)從而得到最終復(fù)雜事件實(shí)例覆蓋。

現(xiàn)在對(duì)算法1的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行分析。若系統(tǒng)正在對(duì)事件e進(jìn)行處理，假設(shè)待處理的事件流S中，在兩倍的時(shí)間窗口內(nèi)單一事件類型的實(shí)例數(shù)量最多為K個(gè)，則e事件所屬分區(qū)中的鏈?zhǔn)浇Y(jié)構(gòu)實(shí)例數(shù)量最大值為K，設(shè)事件e在所屬分區(qū)中產(chǎn)生的臨時(shí)匹配數(shù)量為m，由于臨時(shí)匹配的產(chǎn)生只根據(jù)上一個(gè)分區(qū)中每一個(gè)鏈結(jié)構(gòu)的鏈尾節(jié)點(diǎn)來產(chǎn)生的，所以m的最大值也為K，則處理e事件匹配的時(shí)間復(fù)雜度為O（K2），算法1的時(shí)間復(fù)雜度為O（|S|K2），其中|S|為事件流S中的事件個(gè)數(shù)。由于在事件e所在的分區(qū)的臨時(shí)匹配鏈?zhǔn)浇Y(jié)構(gòu)中，只有尾節(jié)點(diǎn)會(huì)參與構(gòu)建新的臨時(shí)匹配節(jié)點(diǎn)，所以通過事件e得到新的臨時(shí)匹配節(jié)點(diǎn)的空間復(fù)雜度為O（K2）。

在復(fù)雜事件處理中，臨時(shí)匹配的拷貝處理需要使用深拷貝來實(shí)現(xiàn)。完成一次臨時(shí)匹配的深拷貝需要在內(nèi)存中產(chǎn)生一個(gè)新的臨時(shí)匹配實(shí)例，并且將原臨時(shí)匹配實(shí)例中的全部屬性值以及實(shí)例中存在的引用復(fù)制到新的臨時(shí)匹配實(shí)例中。傳統(tǒng)方法中臨時(shí)匹配的拷貝是在遍歷所有臨時(shí)匹配的過程中進(jìn)行的，這將不利于為復(fù)雜事件處理提供良好的系統(tǒng)吞吐能力，系統(tǒng)的計(jì)算開銷也將增大。同時(shí)，所有臨時(shí)匹配都被找出并顯式地在內(nèi)存中以實(shí)例的形式存在，將增加內(nèi)存的開銷。以查詢Q4在事件流St上進(jìn)行匹配的過程為例，使用基于有限狀態(tài)自動(dòng)機(jī)的傳統(tǒng)匹配方法進(jìn)行匹配，需要產(chǎn)生24個(gè)以及21次臨時(shí)匹配的拷貝，而通過臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)以及上述匹配算法，只產(chǎn)生13個(gè)以及10次臨時(shí)匹配的拷貝。臨時(shí)匹配的數(shù)量和拷貝次數(shù)以及遍歷操作的減少將提高系統(tǒng)的吞吐能力，并減少內(nèi)存的開銷。

臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)是基于復(fù)雜事件實(shí)例覆蓋的概念提出的。借助分區(qū)存儲(chǔ)的特點(diǎn)，處理復(fù)雜事件時(shí)并不需要遍歷系統(tǒng)中所有的臨時(shí)匹配，在實(shí)現(xiàn)減少臨時(shí)匹配數(shù)量和拷貝的同時(shí)，并不會(huì)對(duì)最后的正確匹配結(jié)果有所影響。

當(dāng)用戶僅需要距離當(dāng)前時(shí)間最近的一個(gè)復(fù)雜事件實(shí)例，通過指定系統(tǒng)保存〈a3，b3，c2〉即可。假設(shè)用戶需要的是像skip-till-any-match策略那樣將所有的結(jié)果全部匹配出來，則需要使用到所有最終的復(fù)雜事件實(shí)例覆蓋，利用其所在鏈表上的其他節(jié)點(diǎn)信息來進(jìn)行結(jié)果聯(lián)結(jié)，從而得到所有的匹配結(jié)果。

3.2.2 匹配結(jié)果聯(lián)結(jié)

本文進(jìn)一步地完善了匹配結(jié)果的生成。當(dāng)用戶指定需要獲取全部匹配結(jié)果時(shí)，則需要使用算法1所得到的結(jié)果來進(jìn)行反向的匹配結(jié)果聯(lián)結(jié)。繼續(xù)使用查詢Q4：SEQ（A a，B b， C c）以及事件流St（a1，a2，b1，b2，a3，b3，c1，c2）來舉例，在圖5所示的匹配過程及結(jié)果中，Q4的查詢結(jié)果是〈a2，b2，c2〉、〈a2，b3，c2〉、〈a3，b3，c2〉，將通過該結(jié)果以及鏈?zhǔn)椒謪^(qū)結(jié)構(gòu)來得到全部的匹配結(jié)果。

由于采用的是雙向環(huán)形鏈?zhǔn)浇Y(jié)構(gòu)，可以從最底端的復(fù)雜事件實(shí)例覆蓋出發(fā)，反向遍歷所在的鏈表。通過收集每個(gè)分區(qū)的該鏈表節(jié)點(diǎn)的最后一個(gè)事件實(shí)例，最后利用遞歸實(shí)現(xiàn)各個(gè)分區(qū)事件實(shí)例的聯(lián)結(jié)，該過程如算法2所示。對(duì)于Q4來說，只需要將〈a2，b2，c2〉、〈a2，b3，c2〉、〈a3，b3，c2〉三個(gè)節(jié)點(diǎn)分別傳入到算法2中，就能得到Q4所有的匹配結(jié)果。

算法2 匹配結(jié)果聯(lián)結(jié)算法CombineMatch

輸入：復(fù)雜事件實(shí)例覆蓋R。

輸出：所有匹配結(jié)果M。

1 M←;

2 list←;

3 while true do

4" list.add（R.getLastEvent（））;

5" R←R.prev;

6" if R.isHead（） do

7"" R←getPrevBlockNode（R）;

8"" break;

9 return M←doCombine（list，CombineMatch（R））

在算法2第7行的方法getPrevBlockNode中，通過傳入鏈表頂點(diǎn)R，能夠獲取上一個(gè)分區(qū)中R的傳遞節(jié)點(diǎn)。第9行使用了遞歸的形式來獲取最終的聯(lián)結(jié)結(jié)果，其中doCombine方法進(jìn)行了聯(lián)結(jié)操作。

現(xiàn)在對(duì)算法2的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行分析。假設(shè)當(dāng)前分區(qū)數(shù)為n，在多復(fù)雜事件查詢中所定義的最長的復(fù)雜事件序列長度為N，則n的最大值即為N，且通過遞歸調(diào)用函數(shù)次數(shù)最多為N次，若每個(gè)分區(qū)中與復(fù)雜事件實(shí)例覆蓋S關(guān)聯(lián)的臨時(shí)匹配鏈平均長度為m，則算法2的空間復(fù)雜度為O（Nm）。由于每次遞歸函數(shù)體中的執(zhí)行操作復(fù)雜度為O（m），所以算法2的時(shí)間復(fù)雜度為O（Nm）。

利用臨時(shí)匹配鏈上的節(jié)點(diǎn)信息進(jìn)行結(jié)果聯(lián)結(jié)，可在算法1的基礎(chǔ)上得到全部的匹配結(jié)果。聯(lián)結(jié)過程中無須進(jìn)行臨時(shí)匹配的構(gòu)建和拷貝工作，并不會(huì)增大系統(tǒng)中臨時(shí)匹配的規(guī)模，因此節(jié)省了系統(tǒng)的內(nèi)存開銷。

使用圖5中最左側(cè)的鏈表來舉例，首先拿到C分區(qū)的節(jié)點(diǎn)〈a2，b2，c1〉，在C分區(qū)通過獲取每個(gè)節(jié)點(diǎn)的最后一個(gè)事件實(shí)例從而得到［c1，c2］，然后在B分區(qū)對(duì)應(yīng)的鏈表獲得了［b1，b2］，繼而在A分區(qū)獲得了［a1，a2］，通過遞歸doCombine方法將三者聯(lián)結(jié)，得到八個(gè)匹配結(jié)果（a1，b1，c1）（a1，b1，c2）（a1，b2，c1）（a1，b2，c2）（a2，b1，c1）（a2，b1， c2）（a2，b2，c1）（a2，b2，c2），同理，使用C分區(qū)的另外兩個(gè)復(fù)雜事件實(shí)例覆蓋也能得到其對(duì)應(yīng)的所有匹配，最終通過此方式得到所有的匹配結(jié)果以實(shí)現(xiàn)skip-till-any-match策略的匹配效果，且避免了大量臨時(shí)匹配的生成和拷貝。

4 實(shí)驗(yàn)

本章通過實(shí)驗(yàn)對(duì)比來對(duì)本文提出的基于臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)的匹配優(yōu)化方法的有效性進(jìn)行分析和驗(yàn)證。實(shí)驗(yàn)采用Java實(shí)現(xiàn)了優(yōu)化方法的編寫。

4.1 實(shí)驗(yàn)設(shè)置

本文在通過事件流生成器所生成的模擬數(shù)據(jù)流和真實(shí)數(shù)據(jù)集兩個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。

第一個(gè)數(shù)據(jù)集是ABC類型事件流，該數(shù)據(jù)集通過把事件類型簡(jiǎn)寫為大寫英文字母方式來定義事件的類型。其中每個(gè)事件都帶有時(shí)間戳以及各自的屬性值。生成事件流之前可在事件流生成器中自定義事件類型的數(shù)量、屬性個(gè)數(shù)以及屬性值的范圍，流中的每個(gè)事件都是隨機(jī)生成的。實(shí)驗(yàn)中該數(shù)據(jù)集包含了100 000個(gè)原始事件。

第二個(gè)數(shù)據(jù)集包含了車輛交通數(shù)據(jù)，該數(shù)據(jù)由傳感器收集，來自于丹麥奧胡斯市［23］。該數(shù)據(jù)集是通過傳感器在449個(gè)觀測(cè)點(diǎn)位收集了4個(gè)月的數(shù)據(jù)而得到的，總共包含13 577 132個(gè)原始事件。每個(gè)事件代表一個(gè)觀察點(diǎn)的交通情況，一個(gè)事件的屬性包括ID、該點(diǎn)平均車速以及過去5 min內(nèi)觀察到的車輛總數(shù)。

本文優(yōu)化方法將與目前比較流行的基于有限狀態(tài)自動(dòng)機(jī)的SASE方法和Siddhi方法進(jìn)行對(duì)比實(shí)驗(yàn)。其中本文提出的基于臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)的匹配優(yōu)化方法記為LinkedCEP，實(shí)驗(yàn)在Intel Core 2.60 GHz CPU i7和16 GB內(nèi)存的Linux系統(tǒng)上進(jìn)行。

4.2 實(shí)驗(yàn)分析

首先實(shí)驗(yàn)比較的是LinkedCEP與SASE、Siddhi在不同數(shù)據(jù)集上的匹配性能和臨時(shí)匹配產(chǎn)生的數(shù)量。由于本文提出的CoverMatch算法只會(huì)匹配事件流中的復(fù)雜事件實(shí)例覆蓋，并不會(huì)產(chǎn)生所有的匹配結(jié)果，為了公平地進(jìn)行匹配性能的比較，在LinkedCEP中將包含匹配結(jié)果聯(lián)結(jié)算法CombineMatch以支持產(chǎn)生所有的匹配結(jié)果。

由于兩個(gè)數(shù)據(jù)集的原始事件、事件屬性存在差異，為了更好地在兩個(gè)數(shù)據(jù)集上執(zhí)行匹配，針對(duì)兩個(gè)數(shù)據(jù)集分別合成了不同的查詢，并在兩個(gè)數(shù)據(jù)集上分別使用LinkedCEP、SASE、Siddhi來執(zhí)行對(duì)應(yīng)的查詢。以下將設(shè)計(jì)兩組實(shí)驗(yàn)進(jìn)行對(duì)比分析。

實(shí)驗(yàn)1 對(duì)兩個(gè)數(shù)據(jù)集各合成了5組查詢，每組查詢包含10個(gè)基本復(fù)雜事件查詢，這些復(fù)雜事件查詢的序列長度為3，由于時(shí)間窗口對(duì)匹配時(shí)間的影響很大，所以時(shí)間窗口統(tǒng)一為50 s，對(duì)應(yīng)的值則是該組查詢的平均匹配時(shí)間。

圖6、7所展示的是分別在ABC事件流和交通事件流上匹配性能的對(duì)比結(jié)果。在查詢序列長度和事件窗口一致的情況下，無論在任一組查詢上，LinkedCEP的匹配效率都要優(yōu)于其余兩種方法。例如，對(duì)于圖6中Q3查詢組的匹配結(jié)果來說，LinkedCEP花費(fèi)的時(shí)間為220 ms，而SASE、Siddhi所花費(fèi)的時(shí)間分別為385 ms和290 ms。同樣在圖7中，在處理交通事件流的查詢匹配上，LinkedCEP的匹配效率同樣優(yōu)于SASE和Siddhi，例如對(duì)于Q2查詢組的匹配結(jié)果來說，LinkedCEP花費(fèi)的時(shí)間為130 ms，而SASE、Siddhi花費(fèi)的時(shí)間分別為240 ms和160 ms。

實(shí)驗(yàn)2 測(cè)試在不同時(shí)間窗口下的匹配性能。使用查詢1中的查詢組，更改查詢的時(shí)間窗口為50 s、100 s、150 s、200 s、300 s，對(duì)應(yīng)的值為該組查詢的平均匹配時(shí)間。

如圖8、9所示，在不同的時(shí)間窗口下，LinkedCEP的處理性能優(yōu)于其余兩個(gè)方法。例如圖8的實(shí)驗(yàn)對(duì)比結(jié)果中，當(dāng)時(shí)間窗口為200 s時(shí)，LinkedCEP的處理性能比SASE提升了34%，比Siddhi提升了19%。并且通過圖8、9可以發(fā)現(xiàn)，隨著時(shí)間窗口的增大，LinkedCEP對(duì)比另外兩個(gè)方法的性能提升更大，這是因?yàn)闀r(shí)間窗口的大小會(huì)影響臨時(shí)匹配的數(shù)量，當(dāng)時(shí)間窗口很大，堆積的臨時(shí)匹配就多，對(duì)性能的影響也就越大。

實(shí)驗(yàn)3 測(cè)試在處理不同的查詢規(guī)模時(shí)的事件吞吐量。事件吞吐量指的是方法每秒處理的事件個(gè)數(shù)，吞吐量越大，說明方法的計(jì)算效率越高。實(shí)驗(yàn)中為ABC數(shù)據(jù)集和交通數(shù)據(jù)集分別生成了五組查詢，其中每組查詢中的查詢數(shù)量依次為50、100、150、200、250，每個(gè)查詢的時(shí)間窗口都固定為50 s。實(shí)驗(yàn)對(duì)SASE、Siddhi、CoverMatch以及LinkedCEP分別展開了測(cè)試。

如圖10、11所示，在兩個(gè)數(shù)據(jù)集上，LinkedCEP的吞吐量比SASE和Siddhi更大，而CoverMatch由于只匹配了復(fù)雜事件實(shí)例覆蓋，LinkedCEP是在CoverMatch的基礎(chǔ)上進(jìn)行匹配結(jié)果聯(lián)結(jié)得到全部的匹配結(jié)果，所以CoverMatch的吞吐量要比LinkedCEP更大。通過實(shí)驗(yàn)結(jié)果可以觀察到，在交通數(shù)據(jù)集上進(jìn)行復(fù)雜事件處理的吞吐量比在ABC數(shù)據(jù)集上進(jìn)行相同工作時(shí)的吞吐量要小，這是由于ABC數(shù)據(jù)集在通過事件流生成器生成時(shí)采用了相同事件類型在一定概率上相鄰的策略，以此來模擬出現(xiàn)復(fù)雜事件實(shí)例覆蓋的場(chǎng)景，將會(huì)存在更多的匹配結(jié)果，而交通數(shù)據(jù)集中匹配結(jié)果較少，致使臨時(shí)匹配由于無法產(chǎn)生最終匹配而在系統(tǒng)中一直停留，直到起始時(shí)間戳超出當(dāng)前時(shí)間窗口范圍才被淘汰，由此導(dǎo)致吞吐量降低。

在圖11中，由于交通數(shù)據(jù)集中復(fù)雜事件實(shí)例匹配數(shù)量的減少，CoverMatch和LinkedCEP方法的吞吐量大小接近。在ABC數(shù)據(jù)集中，CoverMatch和LinkedCEP方法的吞吐量在五種查詢規(guī)模的情況下都在SASE和Siddhi之上，并且比在交通數(shù)據(jù)集上提升更顯著，這說明了當(dāng)數(shù)據(jù)流中出現(xiàn)類型相同的事件相鄰的情況時(shí)，本文方法性能提升更加顯著。

上述實(shí)驗(yàn)表明，本文方法能夠有效地提升基于有限狀態(tài)自動(dòng)機(jī)的復(fù)雜事件處理技術(shù)的匹配效率，無論是在查詢序列長度較多還是查詢時(shí)間窗口較大的情況下都能夠通過減少冗余計(jì)算來獲得效能的提升。

5 結(jié)束語

本文研究了基于有限狀態(tài)自動(dòng)機(jī)的復(fù)雜事件匹配優(yōu)化問題。為了解決匹配過程中出現(xiàn)大量臨時(shí)匹配所造成的低效匹配的問題，提出了復(fù)雜事件實(shí)例覆蓋的概念。同時(shí)設(shè)計(jì)了一種基于臨時(shí)匹配的鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)以及在該結(jié)構(gòu)上進(jìn)行高效匹配的方法來利用復(fù)雜事件實(shí)例覆蓋，減少匹配過程中的冗余計(jì)算。實(shí)驗(yàn)結(jié)果表明了利用復(fù)雜事件實(shí)例覆蓋的匹配技術(shù)所進(jìn)行的匹配能夠有效提升復(fù)雜事件匹配性能。

復(fù)雜事件處理技術(shù)具有廣闊的應(yīng)用空間，未來的研究工作將主要圍繞多個(gè)復(fù)雜事件之間進(jìn)行查詢優(yōu)化來展開。首先在多個(gè)查詢上，設(shè)計(jì)一種算法來利用本文提出的臨時(shí)匹配鏈?zhǔn)椒謪^(qū)存儲(chǔ)結(jié)構(gòu)來共享復(fù)雜事件實(shí)例覆蓋鏈，探索并設(shè)計(jì)出一種適用于多查詢進(jìn)行結(jié)果共享的監(jiān)測(cè)模型。最后進(jìn)行模型的共享能力分析并通過實(shí)驗(yàn)來分析其處理性能。

參考文獻(xiàn)：

［1］Demers A，Gehrke J，Hong M，et al. Towards expressive publish/subscribe systems［C］// Proc of International Conference on Extending Database Technology. Berlin： Springer，2006： 627-644.

［2］產(chǎn)院東，郭喬進(jìn)，梁中巖，等. 規(guī)則引擎發(fā)展綜述［J］. 信息化研究，2021，47（2）： 1-6. （Chan Yuandong，Guo Qiaojin，Liang Zhongyan，et al. A survey of rule engine［J］. Informatization Research，2021，47（2）： 1-6.）

［3］Hill M，Campbell M，Chang Yuanchi，et al. Event detection in sensor networks for modern oil fields［C］// Proc of the 2nd International Conference on Distributed Event-Based Systems. 2008： 95-102.

［4］Zhou Qunzhi，Simmhan Y，Prasanna V. Incorporating semantic know-ledge into dynamic data processing for smart power grids［C］// Proc of International Semantic Web Conference. Berlin： Springer，2012： 257-273.

［5］趙會(huì)群，李會(huì)峰，劉金鑾. RFID物聯(lián)網(wǎng)復(fù)雜事件模式聚類算法研究 ［J］. 計(jì)算機(jī)應(yīng)用研究，2018，35（2）： 339-341. （Zhao Huiqun，Li Huifeng，Liu Jinluan. Study on RFID complex event pattern clustering algorithm of Internet of Things［J］. Application Research of Computers，2018，35（2）： 339-341.）

［6］Rahmani A M，Babaei Z，Souri A. Event-driven IoT architecture for data analysis of reliable healthcare application using complex event processing［J］. Cluster Computing，2021，24（2）： 1347-1360.

［7］喬雅正，程良倫，王濤，等. 地鐵列車環(huán)境中多依賴復(fù)雜事件處理研究［J］. 計(jì)算機(jī)應(yīng)用研究，2019，36（8）： 2355-2358，2367. （Qiao Yazheng，Cheng Lianglun，Wang Tao，et al. Study on multi-dependency complex event processing in subway train environment ［J］. Application Research of Computers，2019，36（8）： 2355-2358，2367.）

［8］Agrawal J，Diao Y，Gyllstrom D，et al. Efficient pattern matching over event streams［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2008： 147-160.

［9］Zhang Haopeng，Diao Yanlei，Immerman N. On complexity and optimization of expensive queries in complex event processing［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2014： 217-228.

［10］Demers A J，Gehrke J，Panda B，et al. Cayuga： a general purpose event monitoring system［C］// Proc of the 3rd Biennial Conference on Innovative Data Systems Research. 2007： 412-422.

［11］Brenna L，Demers A，Gehrke J，et al. Cayuga： a high-performance event processing engine［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2007： 1100-1102.

［12］Suhothayan S，Gajasinghe K，Narangoda I L，et al. Siddhi： a second look at complex event processing architectures［C］// Proc of ACM Workshop on Gateway Computing Environments. New York： ACM Press， 2011： 43-50.

［13］Noh W F. CEL： a time-dependent，two-space-dimensional，coupled Eulerian-Lagrange code，UCRL-7463［R/OL］. （1963-08-01）. https：//doi.org/10.2172/4621975.

［14］王亦雄，廖湖聲，孔祥翾，等. CEStream：一種復(fù)雜事件流處理語言［J］. 計(jì)算機(jī)科學(xué)，2017，44（4）： 140-143，164. （Wang Yixiong，Liao Husheng，Kong Xiangxuan，et al. CEStream： a complex event stream processing language［J］. Computer Science，2017，44（4）： 140-143，164.）

［15］Diao Yanlei，Immerman N，Gyllstrom D. SASE+： an agile language for Kleene closure over event streams［EB/OL］. （2015-03-22）. https：//www. doc88.com/p-1008534200775.html.

［16］Apache Filnk. FlinkCEP-complex event processing for Flink ［EB/OL］. ［2020-12-04］. https：//ci.apache.org/projects/flink/flink-docs-stable/dev/ libs/cep.html.

［17］Mei Yuan，Madden S. ZStream： a cost-based query processor for adaptively detecting composite events［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2009： 193-206.

［18］Kareem F Q，Abdulazeez A M，Hasan D A. Predicting weather forecasting state based on data mining classification algorithms［J］. Asian Journal of Research in Computer Science，2021，9（3）： 13-24.

［19］Patroumpas K，Alevizos E，Artikis A，et al. Online event recognition from moving vessel trajectories［J］. GeoInformatica，2017，21（2）： 389-427.

［20］Huang Qiuyang，Yang Yongjian，Xu Yuanbo，et al. Citywide road-network traffic monitoring using large-scale mobile signaling data［J］. Neurocomputing，2021，444： 136-146.

［21］Zhang Jixian. Multi-source remote sensing data fusion： status and trends［J］. International Journal of Image and Data Fusion，2010，1（1）： 5-24.

［22］盧莉萍，張曉倩.復(fù)雜環(huán)境下多傳感器目標(biāo)識(shí)別的數(shù)據(jù)融合方法［J］.西安電子科技大學(xué)學(xué)報(bào)，2020，47（4）： 31-38. （Lu Liping，Zhang Xiaoqian. Datafusion method of multi-sensor target recognition in complex enviroment［J］. Journal of Xidian University，2020，47（4）： 31-38.）

［23］Ali M I，Gao F，Mileo A. Citybench： a configurable benchmark to evaluate RSP engines using smart city datasets［C］// Proc of International Semantic Web Conference. Cham： Springer，2015： 374-389.