多事件模式并行CEP處理研究

荊 心，張 璟

（1.西安工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，西安710021；2.西安理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，西安710048）

物聯(lián)網(wǎng)技術(shù)的發(fā)展，促生了大量的分布式應(yīng)用，其以事件通知作為系統(tǒng)運行的數(shù)據(jù)來源，這些數(shù)據(jù)源將始終持續(xù)地發(fā)送出海量的原子事件.這些簡單的原子事件需要被解釋、組合成高級的具有一定抽象含義的復(fù)雜事件后才能被高層應(yīng)用正確理解與使用.此類高層應(yīng)用以事件驅(qū)動為核心，目標(biāo)在于發(fā)現(xiàn)現(xiàn)在正在發(fā)生著什么，其與以往的目標(biāo)在于發(fā)現(xiàn)過去發(fā)生了什么的基于數(shù)據(jù)庫的應(yīng)用存在本質(zhì)差別.由于信息的價值與時效性有較大關(guān)系，因此這類應(yīng)用更具實用價值［1］.基于事件驅(qū)動應(yīng)用的一般架構(gòu)通常由發(fā)生器、接收器、CEP引擎三部分組成［2］.CEP引擎類似人類的大腦，是架構(gòu)中最復(fù)雜、最核心的部分，其負(fù)責(zé)對原子事件流進(jìn)行模式識別，發(fā)現(xiàn)蘊含其中的因果、時序、邏輯等關(guān)系，并產(chǎn)生出新的復(fù)雜輸出事件.

近期，CEP技術(shù)在學(xué)術(shù)及業(yè)界都得到了廣泛的關(guān)注，以SASE［3］為代表的大量的CEP系統(tǒng)被提出.雖然這些CEP系統(tǒng)已經(jīng)具備了表達(dá)能力強大的規(guī)則語言，以及高效的實現(xiàn)模型和優(yōu)化算法.但是其仍然面臨著復(fù)雜的問題，即數(shù)據(jù)源的并行處理與多事件模式的有效共享與關(guān)聯(lián).目前CEP處理引擎多采用集中處理方式，來自多個數(shù)據(jù)源的事件流合并后才能進(jìn)入，引擎隨后對每個已注冊的事件模式逐一匹配，由此事件流及事件模式均被線性化了.因此CEP引擎的工作方式完全是串行的.而在現(xiàn)實情況下，數(shù)據(jù)的接收與每個模式匹配的過程都應(yīng)該是并行的.引擎接收到的事件不應(yīng)經(jīng)歷排隊等待的過程，而應(yīng)直接路由給對應(yīng)的事件模式，同樣待匹配的模式也不應(yīng)等待其他模式的完成，而應(yīng)并行對同一輸入進(jìn)行處理.此外，相互關(guān)聯(lián)或模式相似的多個模式間的有效共享，以及共享后可能存在的沖突問題（即共享節(jié)點可同時參與每個父模式的匹配，或一次僅允許參與某一個父模式的匹配，詳細(xì)見第三小節(jié)），在現(xiàn)有的CEP引擎中還未曾提及.僅通過增強規(guī)則語言的表達(dá)能力是無法解決這些問題的，這是目前CEP引擎面臨的最大的挑戰(zhàn).

由此，文中針對以往CEP研究在上述方面的不足，結(jié)合文獻(xiàn)［4］中Petri網(wǎng)的并行處理能力，對其庫所和變遷計算進(jìn)行了時間擴(kuò)展（使其能夠支持時間窗口及時序檢測的要求），綜合了有色Petri網(wǎng)的化簡能力，提出了一個11元組的復(fù)雜事件檢測模型CEP-PN（CEP Petri Net），該模型能夠?qū)崿F(xiàn)多數(shù)據(jù)流的并行接收與處理.給出了該模型可構(gòu)造的基礎(chǔ)網(wǎng)結(jié)構(gòu)，以及由這些網(wǎng)結(jié)構(gòu)構(gòu)造出事件模式的一般方法.通過Petri網(wǎng)基本性質(zhì)證明了合并計算網(wǎng)能夠得到與獨立計算網(wǎng)完全相同的計算結(jié)果，并給出了多個事件模式的合并算法.

1 有色Petri網(wǎng)事件檢測模型

Petri網(wǎng)是一種直觀的圖形化并行系統(tǒng)建模工具［5］.由于使用Petri網(wǎng)中的庫所表示事件，變遷表示操作符，可以很輕易的構(gòu)造出事件模式，因此用其對于復(fù)雜事件檢測進(jìn)行建模具有天然的優(yōu)勢［6－7］.標(biāo)準(zhǔn)的有色Petri網(wǎng)能實現(xiàn)對大多數(shù)操作符的建模，但是還無法對時間約束、選擇與消耗策略、非事件等CEP具有的特殊方面進(jìn)行建模，因此文中對標(biāo)準(zhǔn)網(wǎng)進(jìn)行了時間擴(kuò)展，提出了如下的Petri網(wǎng)模型（CEP-PN），用于形式化描述復(fù)雜事件的檢測過程.

定義1 CEP-PN是一個11元組：CEP-PN＝（P，T，A，C，W ，M，U，G，E，Pin，Pout），且滿足以下條件為

① 其中（P，T，A）是一個網(wǎng)，P、T、A分別表示庫所、變遷和弧的有限集，且滿足下列條件：

P∪T≠Φ∧P∩T＝Φ∧A?×T）∪（T×P）；

②C是顏色的一個有限集合C＝｛c1，c2…cn｝，代表事件類型，可包括原子與復(fù)合事件類型；

③W：A→L（C）＋，W描述弧上消耗或產(chǎn)生的托肯數(shù)和顏色；

M：P→L（C），M描述庫所上托肯的顏色及數(shù)量，是CEP-PN的標(biāo)識；

L（C）表示定義在顏色集C上的一個非負(fù)整數(shù)系數(shù)線性函數(shù)，L（C）＋表示系數(shù)不全為0的L（C），即L（C）＋＝b1c1＋b2c2＋……＋bkck，bi（i＝1，2，…，k）均為非負(fù)整數(shù)，且b1＋b2＋……＋bk≠0；

④U：P→L（C），表示庫所中各托肯的失效時間，U與M 形式相同但作業(yè)不同，其中bi為零則表示不失效.M中的ci為托肯顏色，而bi為托肯數(shù)量，U與之不同的是ci為托肯顏色，而bi表示時間窗口單元；

⑤G表示守衛(wèi)函數(shù)，描述了事件屬性的約束條件，是與輸入庫所顏色相關(guān)的布爾表達(dá)式.

⑥E表示變遷操作表達(dá)式，描述了如何計算輸出事件的屬性值.

⑦Pin?P，Pout?P，且滿足Pin≠Φ∧Pout≠Φ∧Pin＝P－Pout∧｛?∈Pout｜p·＝Φ｝，是網(wǎng)的輸入庫所與輸出庫所，除去輸入庫所外的其他庫所均可作為輸入庫所，其中：p·＝｛t｜t∈P∪T∧（p，t）∈A｝；

⑧ 對t∈T，如果p∈·t→M（p）≥W（p，t）∧G（t）＝ture，那么變遷t在標(biāo)識M 有發(fā)生權(quán)（M［t＞），在標(biāo)識M下發(fā)生變遷t，產(chǎn)生一個新的標(biāo)識 M’（M［t＞ M’）

定義中①～⑦描述了CEP-PN的靜態(tài)結(jié)構(gòu)，而⑧描述了網(wǎng)運行的動態(tài)行為.

2 基本Petri網(wǎng)結(jié)構(gòu)

由于CEP中事件模式的基本構(gòu)件是事件操作符，因此使用CEP-PN對其進(jìn)行建模，從而構(gòu)造出來的基本網(wǎng)結(jié)構(gòu)，可作為構(gòu)造事件模式Petri計算網(wǎng)實例的原子部件.如果按照操作數(shù)的數(shù)目對事件操作符進(jìn)行分類，其可以被自然劃分為雙操作數(shù)與單操作數(shù)兩類.因此CEP-PN對事件操作符的建模也可分為兩類，即雙輸入變遷與單輸入變遷結(jié)構(gòu)（分別如圖1（a）～ （b）所示）.基本網(wǎng)的輸出可作為另一個基本網(wǎng)的輸入，由此可以將基本網(wǎng)關(guān)聯(lián)起來，從而形成目標(biāo)計算網(wǎng)（如圖1（e）所示）.

在圖1（a）中，A、B庫所上都只有一種顏色，該基本網(wǎng)實現(xiàn)簡單，但當(dāng)使用其去構(gòu)造復(fù)雜的事件模式時，將產(chǎn)生龐大的網(wǎng)結(jié)構(gòu).為精簡Petri網(wǎng)整體規(guī)模，可以對雙輸入變遷結(jié)構(gòu)中的庫所，按照CEPPN的定義進(jìn)行合并（如圖1（c）所示）.合并后的庫所具有兩種顏色，可同時接收并存儲兩類事件.圖1（d）為對圖1（e）進(jìn)行合并后的Petri網(wǎng)實例，前者與后者比較庫所數(shù)量明顯減少，且網(wǎng)結(jié)構(gòu)更加緊湊.

使用CEP-PN共享相同的庫所節(jié)點時將面臨兩種選擇，即并發(fā)與沖突（分別如圖1（f）、1（g）所示）.在并發(fā)情況下共享節(jié)點將參與每個子模式的匹配，因此在構(gòu)造時需對該節(jié)點進(jìn)行復(fù)制.而在沖突情況下，共享節(jié)點每次僅能夠參與某一個子模式的匹配，因此在構(gòu)造時需要對該節(jié)點進(jìn)行合并.需要注意的是，在合并方式中還可以存在反饋結(jié)構(gòu)，即共享節(jié)點上的事件實際上不被消耗，從而重復(fù)多次參與子模式的匹配（如圖1（g）中的圓弧線所示）.基本網(wǎng)具體采用何種構(gòu)造方式進(jìn)行聯(lián)接，將由事件模式的消耗策略決定.

圖1 基本Petri網(wǎng)結(jié)構(gòu)Fig.1 The basic structure of Petri net

3 多事件模式的合并

CEP系統(tǒng)中存在大量事件模式合并的情況.由于無法使用一條規(guī)則定義整個系統(tǒng)的運行，一個復(fù)雜的情景通常需要先由多條規(guī)則分別定義出來，然后經(jīng)過合并才能形成.另外，在一條規(guī)則內(nèi)部，同樣需要經(jīng)歷先構(gòu)造出基本網(wǎng)結(jié)構(gòu)，然后合并的過程.合并后的Petri計算網(wǎng)，能夠有效減小CEP系統(tǒng)的整體運行規(guī)模，提高系統(tǒng)運行效率.由此，以下給出事件模式合并的語義與算法.

定義2 設(shè)CEP-PN為一個網(wǎng)，如果存在t∈T，使M［t＞M′，則稱M′為從M直接可達(dá)的.如果存在變遷序列t1，t2，…tn（記為σ）和標(biāo)識序列 M1，M2，…Mn使得 M［t1＞ M1［t2＞ M2…Mn－1［tn＞Mn（記為M［σ＞Mn），則稱Mn為從M 可達(dá)的.從M可達(dá)的一切標(biāo)識的集合記為R（M），規(guī)定M∈R（M）.

定義3 設(shè)CEP-PN為一個網(wǎng)，M1和M2是網(wǎng)的兩個標(biāo)識.如果 ?p∈P 都有M1（p）≤M2（p），則稱M1被M2覆蓋，記作M1≤M2.

定義4 設(shè)CEP-PN為一個網(wǎng)，M為網(wǎng)的一個標(biāo)識.若 ?M′∈R（M0），使得M≤M′，則稱M 為CEP-PN的一個可覆蓋標(biāo)識.

根據(jù)以上定義可以很容易的證明多模式合并后的可達(dá)性.例如：可將如圖1（a）所示的網(wǎng)記為＜a；b＞→ab，則＜a；b；d＞→abd事件模式，可視為＜a；b＞→ab與＜ab；d＞→abd兩個基本網(wǎng)連接形成的合并網(wǎng).記其初始狀態(tài)為M0，a；b發(fā)生為M1，ab；d發(fā)生為M2，由于M1∈R（M0），且M2∈R（M1）：M2∈R（M0），因此R（M1）R（M0）.即如果變遷序列σ1導(dǎo)致M0→M1可達(dá)，σ2導(dǎo)致M1→M2可達(dá)，則一定存在σ＝σ1＋σ2導(dǎo)致M0→M2可達(dá)，其中M1是合并網(wǎng)的一個可覆蓋標(biāo)識.

對于任意兩個網(wǎng)A、B，如果存在一個公共可覆蓋標(biāo)識M，使得M ∈RA（M0），且M ∈RB（M0），則A與B是可以合并的，其中RA（RB）為A（B）初始標(biāo)識的可達(dá)標(biāo)識集合.根據(jù)以上結(jié)論可知，＜a；b；c；d，a；b；c；e＞ 兩個網(wǎng)是可以直接合并的（稱為前結(jié)合模式），＜a；b；c；d，b；c；e＞ 亦是可以合并的（稱為中間結(jié)合模式，后者網(wǎng)b；c可視為前者網(wǎng)a；b；c的特殊子模式），而 ＜a；b；c，e；b；c＞ 是不能直接合并的（稱為后結(jié)合模式），由于a；b的變遷t1與e；b的變遷t2不是同一個變遷，因此不存在共同的可覆蓋標(biāo)識，但該類情況可采用后面先合并的方式，即將模式重寫為 ＜a；（b；c），e；（b；c）＞ 的形式，以（b；c）為模式起始進(jìn)行網(wǎng)合并，而后才將前面的庫所與由合并形成的結(jié)果庫所輸入到一個變遷上去.后結(jié)合模式面臨一定的風(fēng)險，即當(dāng)前事件不滿足條件時，后事件的檢測將浪費計算資源.

兩個獨立的網(wǎng)合并時會面臨兩種情況：并發(fā)與沖突（如圖1（f）與1（g）所示）.并發(fā)情況下，合并庫所采用復(fù)制模式產(chǎn)生出多個中間結(jié)果，同時用于每個事件模式的匹配.而沖突情況下，合并庫所采用共享模式，僅參與多個事件模式匹配中的一條.系統(tǒng)使用模式的策略如下：對位于一條規(guī)則中的基本網(wǎng)結(jié)構(gòu)和串聯(lián)結(jié)構(gòu)，采用連接模式合并，前結(jié)合與中間結(jié)合采用共享模式合并，后結(jié)合采用復(fù)制模式合并，對位于多條規(guī)則中的網(wǎng)則均采用復(fù)制模式合并.多事件模式合并算法為

①將預(yù)加入CEP引擎運行Petri網(wǎng)中的用戶事件模式分解為多個（FirstPlace，Transition，Second Place，Out put Place）四元組，根據(jù)其中的操作符類型生成相應(yīng)的基本網(wǎng)結(jié)構(gòu)；

②將該事件模式產(chǎn)生基本網(wǎng)結(jié)構(gòu)單元，依次采用連接模式進(jìn)行合并，直到最后；

③采用從頭比對的方法，將該事件模式與運行Petri網(wǎng)中事件模式列表中的其他模式進(jìn)行逐一比較，如果未發(fā)現(xiàn)同類庫所存在，則將其直接加入到運行Petri網(wǎng)中；

④ 如果發(fā)現(xiàn)新事件模式的首庫所與某運行事件模式從首庫所開始匹配，則采用前結(jié)合方式合并相同的子模式部分；

⑤ 如果發(fā)現(xiàn)新事件模式的首庫所與某運行事件模式從其中間某庫所開始匹配，則采用中間結(jié)合方式合并相同的子模式部分；

⑥ 如果發(fā)現(xiàn)新事件模式與某運行事件模式存在中間部分匹配，則采用后結(jié)合方式合并；

⑦直到與運行事件模式列表全部匹配完畢.

4 實驗與分析

由于目前沒有開源的以有色Pertri網(wǎng)為模型的CEP引擎，因此選擇以自動機(jī)為模型的SASE原型系統(tǒng)進(jìn)行比較.與SASE進(jìn)行比較的其他重要原因在于，自動機(jī)模型是CEP社區(qū)最為流行的模式匹配方法，因此通過兩者的比較能夠清楚的發(fā)現(xiàn)兩種基礎(chǔ)實現(xiàn)思想的優(yōu)缺點.為確保準(zhǔn)確測試兩者的性能，文中構(gòu)造了相同的環(huán)境.首先事件模式采用了SASE提供的檢測三支價格相等的股票序列的示例，然后讓兩個系統(tǒng)使用同一個事件發(fā)生器作為輸入，并檢查兩者具有完全相同的輸出.顯然在輸入、輸出相同的情況下，占用越少時間、空間的系統(tǒng)性能越好，系統(tǒng)吞吐量則越大.

如果一個原子事件未參與復(fù)合而被過濾掉了，那么其顯然不會充分占用計算時間.為最大限度的估算系統(tǒng)的計算能力，本實驗的事件發(fā)生器產(chǎn)生三支股票事件各3，000個，并使得其全部參與計算，最終復(fù)合出3，000個匹配結(jié)果.為研究多模式在并發(fā)數(shù)據(jù)環(huán)境下的性能，復(fù)制事件模式從10倍至50倍.復(fù)制模式可以保證兩個系統(tǒng)使用同一輸入，同時輸出一致的結(jié)果.例如：50個事件模式時，兩者均輸出150，000個復(fù)雜事件.如圖2所示，當(dāng)同時運行的模式數(shù)量小于20時，SASE運行較快，但隨著模式數(shù)量的增加，SASE處理時長的增長速度明顯高于CEP系統(tǒng).其主要原因在于，隨著注冊模式的增加，在SASE中活動的自動機(jī)數(shù)量快速增長，使得用于檢索活動狀態(tài)的索引的效率持續(xù)降低，而Petri網(wǎng)系統(tǒng)可以通過在其庫所和變遷上創(chuàng)建更多的并發(fā)進(jìn)程有效降低處理時間.由此可知，當(dāng)并發(fā)模式數(shù)量較少時，自動機(jī)模型執(zhí)行高效.相反，Petri網(wǎng)模型則具有較好的運行效率.

圖2 與SASE系統(tǒng)的比較Fig.2 Comparison with the SASE system

5 結(jié) 論

通過對有色Petri網(wǎng)進(jìn)行時間擴(kuò)展，使其能夠較好的用于CEP事件模式的建模，以前、中、后三種結(jié)合模式進(jìn)行連接的基本網(wǎng)結(jié)構(gòu)，能夠形式化、準(zhǔn)確的表達(dá)事件模式.給出的Petri計算網(wǎng)自動合并算法，能夠?qū)崿F(xiàn)多個獨立事件模式的關(guān)聯(lián)共享，由此降低系統(tǒng)計算資源的利用，提高系統(tǒng)整體的運行效率.通過與目前流行的CEP引擎的比較與分析可知，Petri網(wǎng)系統(tǒng)在多模式并行執(zhí)行時具有更好的性能，將能夠有效應(yīng)對大量事件并行輸入與多模式并行處理的實際情況.

［1］ CUGOLA G，MARGARA A.Processing Flows of Information：From Data Stream to Complex Event Processing［J］.ACM Computing Surveys（CSUR），2012，44（3）：15.

［2］ CUGOLA G，MARGARA A.Complex Event Processing with T-Rex［J］.Journal of Systems and Software，2012，85（8）：1709.

［3］ AGRAWAL J，DIDOA Y，GYLLSTROM D，et al.Efficient Pattern Matching over Event Streams［C］／／Proceedings of the 2008ACM SIGMOD International Conference on Management of Data.Vancouver：ACM，2008：147.

［4］ 黃毅，鄭力，向晴.基于復(fù)雜事件處理的RFID輔助實時生產(chǎn)監(jiān)控［J］.清華大學(xué)學(xué)報：自然科學(xué)版，2013，53（5）：721.HUANG Yi，ZHENG Li，XIANG Qing.RFID Integrated Real－Time Manufacturing Monitoring Based on Complex Event Processing［J］.Journal of Tsinghua University：Science and Technology，2013，53（5）：721.（in Chinese）

［5］ 程蘇珺，王永劍，孟由，等.PMTree：一種高效的事件流模式匹配方法［J］.計算機(jī)研究與發(fā)展，2013，49（11）：2481.CHENG Su－Jun，WANG Yong－jian，MENG You，et al.PMTree：An Efficient Pattern Matching Method for Event Stream Processing ［J］.Journal of Computer Research and Development，2013，49（11）：2481.（in Chinese）

［6］ 葉蔚，黃雨，趙文，等.基于Petri網(wǎng)的 RFID中間件中復(fù)合事件檢 測研 究［J］.電子學(xué)報，2009，36（B12）：1.YE Wei，HUANG Yu，ZHAO Wen，et al.Research on Complex Event Detection in RFID Middleware Based on Colored Petri Net［J］.Acta Electronica Sinica，2009，36（B12）：1.（in Chinese）

［7］ 王中生，楊盛泉.Petri網(wǎng)的總線型DCS的通信機(jī)制［J］.西安工業(yè)大學(xué)學(xué)報，2010，30（3）：281.WANG Zhong－sheng，YANG Sheng－quan.Research of Communication Mechanism in Bus Topology DCS System Based on Petri Net［J］.Journal of Xi’an Technological University，2010，30（3）：281.（in Chinese）