面向?qū)崟r事件流的復雜事件處理方法

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

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

摘 要：

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

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

中圖分類號：TP315"" 文獻標志碼：A"" 文章編號：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 引言

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

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

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

綜上所述，本文的主要貢獻如下：

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

b）設計了一個臨時匹配鏈式分區(qū)存儲結(jié)構(gòu)，通過該結(jié)構(gòu)避免了臨時匹配的集中式存儲及使用，同時該結(jié)構(gòu)也作為復雜事件實例覆蓋的載體，構(gòu)建了臨時匹配之間的關(guān)聯(lián)。

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2 預備工作

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

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

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

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

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

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

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

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

PATTERN" 〈sequence pattern〉

［WHERE〈qualification〉］

［AND〈other qualifications〉］

［WITHIN〈time window〉］

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

為了解釋SASE事件描述語言結(jié)構(gòu)的含義，現(xiàn)在使用一個基于道路交通場景構(gòu)造的例子來說明。在這個例子中，事件類型TrafficInfo為道路地點所收集到該地點的交通數(shù)據(jù)報告，一個報告對應一個事件實例。假設報告內(nèi)容包含該地點的位置，以及某一時刻的車流量、平均車速等。所構(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

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

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

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

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

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

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

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

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

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

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

WHEREskip-till-any-match

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

WITHIN50

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

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

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

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

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

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

3.2 減少冗余計算

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

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

定義4 復雜事件實例覆蓋。對于兩個匹配結(jié)果M1和M2來說，如果M1中的每一個事件實例，都相等于M2中對應的事件實例或是M2中對應事件實例的事件實例覆蓋，則稱M1是M2的一個復雜事件實例覆蓋。

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

很多場景都能夠應用復雜事件實例覆蓋，因為復雜事件實例覆蓋能運用在匹配距離當前事件最近的復雜事件上，例如在股票事件流上尋找某一只股票最近的一次價格反彈事件、在交通數(shù)據(jù)事件流上尋找某地點最新的擁堵事件等。

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

3.2.1 臨時匹配鏈式分區(qū)存儲結(jié)構(gòu)

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

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

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

算法1 基于鏈式分區(qū)存儲結(jié)構(gòu)的匹配算法CoverMatch

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

輸出：復雜事件實例覆蓋集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在上一個分區(qū)中遍歷暴露的匹配節(jié)點，將能夠進行更新的節(jié)點拷貝，進行更新，然后再進入到當前分區(qū)進行復雜事件實例覆蓋的檢查，如果不是某個節(jié)點的復雜事件實例覆蓋，就單獨成鏈（第17行），否則成為某個鏈的鏈尾節(jié)點（第15行）。最后返回最終的復雜事件實例覆蓋。由于采用的數(shù)據(jù)結(jié)構(gòu)是雙向環(huán)形鏈式結(jié)構(gòu)，所以第19行使用prev可以直接定位到鏈尾節(jié)點從而得到最終復雜事件實例覆蓋。

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

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

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

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

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

本文進一步地完善了匹配結(jié)果的生成。當用戶指定需要獲取全部匹配結(jié)果時，則需要使用算法1所得到的結(jié)果來進行反向的匹配結(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é)果以及鏈式分區(qū)結(jié)構(gòu)來得到全部的匹配結(jié)果。

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

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

輸入：復雜事件實例覆蓋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中，通過傳入鏈表頂點R，能夠獲取上一個分區(qū)中R的傳遞節(jié)點。第9行使用了遞歸的形式來獲取最終的聯(lián)結(jié)結(jié)果，其中doCombine方法進行了聯(lián)結(jié)操作。

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

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

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

4 實驗

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

4.1 實驗設置

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

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

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

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

4.2 實驗分析

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

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

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

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

實驗2 測試在不同時間窗口下的匹配性能。使用查詢1中的查詢組，更改查詢的時間窗口為50 s、100 s、150 s、200 s、300 s，對應的值為該組查詢的平均匹配時間。

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

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

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

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

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

5 結(jié)束語

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

復雜事件處理技術(shù)具有廣闊的應用空間，未來的研究工作將主要圍繞多個復雜事件之間進行查詢優(yōu)化來展開。首先在多個查詢上，設計一種算法來利用本文提出的臨時匹配鏈式分區(qū)存儲結(jié)構(gòu)來共享復雜事件實例覆蓋鏈，探索并設計出一種適用于多查詢進行結(jié)果共享的監(jiā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)院東，郭喬進，梁中巖，等. 規(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］趙會群，李會峰，劉金鑾. RFID物聯(lián)網(wǎng)復雜事件模式聚類算法研究 ［J］. 計算機應用研究，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)境中多依賴復雜事件處理研究［J］. 計算機應用研究，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：一種復雜事件流處理語言［J］. 計算機科學，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］盧莉萍，張曉倩.復雜環(huán)境下多傳感器目標識別的數(shù)據(jù)融合方法［J］.西安電子科技大學學報，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.