基于內(nèi)容的發(fā)布訂閱系統(tǒng)的一種快速匹配算法

陳 娛，劉健波

（四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065）

發(fā)布/訂閱系統(tǒng)是一種用于信息交互的中間件系統(tǒng)，它將信息的發(fā)布者與訂閱者聯(lián)系在一起。發(fā)布者只負(fù)責(zé)發(fā)布信息給中間件，訂閱者也只向中間件訂閱自己感興趣的信息，信息具體的發(fā)布和傳送則由發(fā)布/訂閱系統(tǒng)負(fù)責(zé)，這樣大大降低了系統(tǒng)的耦合性，使通信更加靈活，符合分布式系統(tǒng)的需求，所以在分布式系統(tǒng)中得到了廣泛的應(yīng)用。

在基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中，信息由事件來表示，訂閱者可以通過訂閱事件來獲取信息。一個(gè)事件可以表示為一些屬性的集合，而訂閱則可以表示為一些謂詞的集合。訂閱者可以通過指定其感興趣的謂詞來靈活地訂閱事件。相對(duì)于基于主題的發(fā)布/訂閱系統(tǒng)，基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中訂閱的表達(dá)能力得到了很大的提高，但是同時(shí)系統(tǒng)中的訂閱數(shù)目也大大增加，匹配的復(fù)雜度大大提高，必須有一個(gè)高效的算法來實(shí)現(xiàn)訂閱和事件的快速匹配[1]。匹配算法的基本思想是盡量優(yōu)化訂閱結(jié)構(gòu)，減少匹配時(shí)訂閱條件中重復(fù)部分的判斷，提高匹配效率。

1 相關(guān)研究

目前相關(guān)的研究已經(jīng)提出了很多比較有代表性的算法[2-6]。Aguilera等提出了基于搜索樹的算法[4]，這種方法建立一棵搜索樹，每個(gè)非葉子節(jié)點(diǎn)表示一個(gè)對(duì)訂閱條件的測試，每條邊代表測試結(jié)果，每個(gè)葉子節(jié)點(diǎn)表示一個(gè)訂閱條件。當(dāng)匹配一個(gè)事件時(shí)，如果按照樹的某一路徑可以從樹根到達(dá)一個(gè)葉子節(jié)點(diǎn)，說明該葉子節(jié)點(diǎn)代表的訂閱與這個(gè)事件相匹配。這種方法中相同的訂閱條件只需要測試一次，但是節(jié)點(diǎn)間的耦合性較高，相應(yīng)地，維護(hù)樹的代價(jià)也比較高。

計(jì)數(shù)法的思想是測試所有謂詞，建立一個(gè)表保存謂詞和訂閱的映射關(guān)系，即謂詞被哪些訂閱滿足。匹配時(shí)，遍歷這個(gè)表找出滿足一個(gè)訂閱的謂詞數(shù)目，將之與這個(gè)訂閱包含的謂詞數(shù)目進(jìn)行比較，如果相等，則說明事件與訂閱相匹配。計(jì)數(shù)法雖然避免了一個(gè)謂詞被多次測試，但是它總會(huì)對(duì)訂閱中所有的謂詞進(jìn)行測試，而實(shí)際上當(dāng)一個(gè)謂詞無法匹配時(shí)，其他的測試都不需要繼續(xù)進(jìn)行。

2 匹配算法

本文提出的方法借鑒了基于搜索樹的方法，學(xué)習(xí)了其中的優(yōu)點(diǎn)，并針對(duì)其中存在的缺點(diǎn)進(jìn)行了改進(jìn)。搜索樹的方法將所有謂詞添加到一棵樹中，樹的深度和耦合度比較大，不利于訂閱樹的維護(hù)。所以本文方法中修改了構(gòu)造訂閱樹的方法，按照謂詞類型和名稱的不同創(chuàng)建若干訂閱樹，將不同的謂詞放到不同的樹中，減少了耦合度。為了便于管理這些搜索樹，建立了一個(gè)索引結(jié)構(gòu)，根據(jù)謂詞類型和名稱的不同可以快速找到對(duì)應(yīng)的訂閱樹。

2.1 訂閱模型和事件模型

在基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中，為了能讓訂閱者快速、準(zhǔn)確地指定所需信息，訂閱者要通過一定的訂閱模型來訂閱信息，發(fā)布者也要通過一定的事件模型來發(fā)布數(shù)據(jù)，所以在提出匹配算法之前，首先定義如下的訂閱模型和事件模型：

(1)事件

事件包含了一些發(fā)布者發(fā)布的數(shù)據(jù)，可以定義為一些屬性的集合。屬性是最小的數(shù)據(jù)，可以表示為一個(gè)數(shù)據(jù)類型、屬性名稱和屬性值組成的三元組，即 Attribute：=。屬性的數(shù)據(jù)類型定義有數(shù)值類型和字符串型。事件可以表示為{A1，A2，…，An}，即 Event：=∪Attribute。

例如事件 E1={(int，x，10)，(string，s，“teacher”)}包含兩個(gè)屬性 A1=(int，x，10)和 A2=(string，s，“teacher”)。

(2)訂閱

一個(gè)訂閱表示了一個(gè)訂閱者所感興趣的數(shù)據(jù)，可以定義為一些謂詞的集合。謂詞是對(duì)一個(gè)屬性的測試結(jié)果，可以表示為一個(gè)數(shù)據(jù)類型、屬性名稱、測試操作符和匹配值組成的四元組，即 Predicate：=(type，name，operator，value)。謂詞的測試操作符(operator)對(duì)應(yīng)的數(shù)值型定義有=、＞、<、＞=、<=和!=，對(duì)應(yīng)字符串型定義有=、!=和 *=(包含)。 訂閱可以表示為{P1，P2，…，Pn}，即 Subscription：=∪Predicate。

例 如 訂 閱 S1={(int，x， ＞ ，10)，(string，s，!= ， “student”)}，包含兩個(gè)謂詞 P1=(int，x，＞，10)和 P2=(string，s，=，“student”)。

定義 1.屬性 a(typea，namea，valuea)與謂詞 p(typep，namep，operatorp，valuep)匹配，則要滿 足(typea=typep)∧(namea=namep)∧(operatorp(valuea，valuep)=true)。

定義2.事件e與訂閱s匹配，則對(duì)于 s中的每個(gè)謂詞p，e中至少存在一個(gè)屬性a與p匹配。

定義3.謂詞p1與謂詞p2間存在覆蓋關(guān)系，則對(duì)任意一個(gè)屬性a，如果它和p2匹配，則它也一定和p1匹配。

定義4.謂詞p1與謂詞p2沖突，則當(dāng)p1成立時(shí)，p2一定不成立。

2.2 訂閱樹的構(gòu)造

在構(gòu)造訂閱樹之前，增加一個(gè)對(duì)訂閱集合預(yù)處理的步驟。這是因?yàn)樵谝粋€(gè)訂閱中可能存在著沖突和重復(fù)的謂詞，在訂閱和匹配開始前就進(jìn)行處理可以付出最小的代價(jià)。進(jìn)行預(yù)處理時(shí)要遍歷所有訂閱，對(duì)于謂詞存在沖突的訂閱，由于一定不存在事件能與之匹配，所以不需要將之添加到訂閱樹中；對(duì)于謂詞間存在覆蓋關(guān)系的訂閱，只保留最大的謂詞，這樣可以減少訂閱中謂詞的重復(fù)。

接下來根據(jù)上一步經(jīng)過預(yù)處理的訂閱集合來創(chuàng)建若干訂閱樹，將類型和名稱相同的謂詞生成的節(jié)點(diǎn)添加到一棵訂閱樹中。訂閱樹中的每個(gè)節(jié)點(diǎn)存儲(chǔ)了一個(gè)謂詞和包含這個(gè)謂詞的訂閱的集合。為了便于在訂閱樹中進(jìn)行匹配，分別以謂詞的類型、名稱和操作符為鍵建立一個(gè)多級(jí)索引結(jié)構(gòu)來管理所有的訂閱樹，如圖1所示，將指向每棵訂閱樹根節(jié)點(diǎn)的指針對(duì)應(yīng)存儲(chǔ)在索引結(jié)構(gòu)中，這樣當(dāng)需要匹配一個(gè)事件的屬性時(shí)就能根據(jù)屬性的類型和名稱進(jìn)行快速定位。

構(gòu)建訂閱樹時(shí)要考慮到謂詞間的覆蓋關(guān)系，讓父節(jié)點(diǎn)的謂詞覆蓋子節(jié)點(diǎn)的謂詞，這樣進(jìn)行事件匹配時(shí)，如果父節(jié)點(diǎn)的謂詞與事件的對(duì)應(yīng)屬性不匹配，則屬性與子節(jié)點(diǎn)的謂詞也一定不匹配，加快了匹配的速度。

在訂閱樹中增加節(jié)點(diǎn)時(shí)，先通過索引結(jié)構(gòu)找到對(duì)應(yīng)的樹，然后在樹中查找這樣一個(gè)節(jié)點(diǎn)：這個(gè)節(jié)點(diǎn)覆蓋了新增加的節(jié)點(diǎn)，而它的子節(jié)點(diǎn)都不覆蓋新節(jié)點(diǎn)，然后將新節(jié)點(diǎn)插入到這個(gè)節(jié)點(diǎn)和它的子節(jié)點(diǎn)之間，新節(jié)點(diǎn)的訂閱集合也要添加相應(yīng)的訂閱者。

在訂閱樹中刪除節(jié)點(diǎn)時(shí)，先通過索引結(jié)構(gòu)找到對(duì)應(yīng)的樹，從根節(jié)點(diǎn)遍歷樹，如果找到一個(gè)節(jié)點(diǎn)被要?jiǎng)h除的節(jié)點(diǎn)覆蓋，則將對(duì)應(yīng)的訂閱者從以這個(gè)節(jié)點(diǎn)為根的樹中的所有節(jié)點(diǎn)的訂閱集合中刪除，如果刪除后某個(gè)節(jié)點(diǎn)的訂閱集合為空，則刪除該節(jié)點(diǎn)。

下面給出了構(gòu)建訂閱樹的算法偽代碼：

2.3 事件匹配

由于訂閱樹的構(gòu)造方法的改變，事件匹配的方法也有所不同，采用了先找出所有不匹配的訂閱，然后得到匹配的訂閱方法。匹配一個(gè)事件時(shí)，先對(duì)所有謂詞進(jìn)行測試，對(duì)事件中的每個(gè)屬性，依次查找類型和名稱對(duì)應(yīng)的訂閱樹。如果找到了相應(yīng)的訂閱樹，則用這個(gè)屬性測試訂閱樹中所有的節(jié)點(diǎn)。在測試的過程中，如果一個(gè)節(jié)點(diǎn)測試失敗，則記錄下這個(gè)節(jié)點(diǎn)的訂閱者和以這個(gè)節(jié)點(diǎn)為根的子樹中所有節(jié)點(diǎn)的訂閱者。測試完成后，在訂閱集合中剔除所有不匹配的訂閱，就能找出所有與當(dāng)前事件匹配的訂閱。

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

實(shí)驗(yàn)采用的計(jì)算機(jī)采用雙核Core2、主頻為1.6 GHz的CPU，2 GB的DDR2內(nèi)存，Windows XP系統(tǒng)，算法的實(shí)現(xiàn)采用Visual Studio 2008平臺(tái)，C++語言。編寫了一個(gè)訂閱產(chǎn)生器和事件產(chǎn)生器來產(chǎn)生實(shí)驗(yàn)樣本，每個(gè)實(shí)驗(yàn)結(jié)果為10次運(yùn)行的平均值。每個(gè)訂閱的形式如（numeric1＞10，numeric2!=8，string1*=“student”）， 每個(gè)事件的形式如（int1=12，int3=200，string2=“teacher”）。

實(shí)驗(yàn)一 測試訂閱數(shù)量對(duì)匹配速度的影響。首先向系統(tǒng)中添加訂閱，訂閱數(shù)目變化范圍為1 000～10 000個(gè)，每個(gè)訂閱包含5～10個(gè)謂詞；然后隨機(jī)生成一個(gè)事件，這個(gè)事件包含的屬性個(gè)數(shù)為20，測試匹配這個(gè)事件所需的時(shí)間。實(shí)驗(yàn)結(jié)果如圖2所示。

實(shí)驗(yàn)二 測試事件屬性個(gè)數(shù)對(duì)匹配速度的影響。向系統(tǒng)中添加5 000個(gè)訂閱，每個(gè)訂閱包含5～10個(gè)謂詞，隨機(jī)生成事件，事件的屬性個(gè)數(shù)變化范圍為5～20個(gè)，測試匹配事件所需的時(shí)間。實(shí)驗(yàn)結(jié)果如圖3所示。

從上面的實(shí)驗(yàn)結(jié)果可以看出，本文提出的算法在匹配效率上相對(duì)于計(jì)數(shù)法和基于匹配樹的算法有了較大的提高。當(dāng)事件的屬性個(gè)數(shù)相同而系統(tǒng)訂閱數(shù)不斷增加時(shí)，和系統(tǒng)中訂閱數(shù)目相同而事件包含的屬性個(gè)數(shù)不斷增長時(shí)，這種算法明顯表現(xiàn)出了它的高效性。

近年來基于內(nèi)容的發(fā)布/訂閱系統(tǒng)逐漸獲得了越來越廣泛的應(yīng)用。本文針對(duì)基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中的事件與訂閱的匹配，提出了一種匹配算法。這種算法利用一個(gè)多級(jí)索引結(jié)構(gòu)來管理不同類型和名稱謂詞，提高了謂詞的匹配速度，而且充分考慮了謂詞間的覆蓋關(guān)系，減少了匹配次數(shù)。最后通過實(shí)驗(yàn)證明了這種算法的正確性和高效性。未來可以對(duì)算法的覆蓋關(guān)系、訂閱樹的結(jié)構(gòu)等進(jìn)行更一步的改進(jìn)。

[1]馬建剛，黃濤.面向大規(guī)模分布式計(jì)算發(fā)布訂閱系統(tǒng)核心技術(shù)[J].軟件學(xué)報(bào)，2006，17(1)：134-147.

[2]KALE S，HAZAN E，CAO F，et al.Analysis and algorithms for content-based event matching[C].In proceedings of ICDCS Workshops，2005：363-369.

[3]FABRET F，LLIRBAT F，PEREIRA J，et al.Efficient matching for content-based publish/subscribe systems[C].In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles，2003，37(5)：29-43.

[4]AGUILERA M K，STORM R E，STURMAN D C，et al.Matching events in a content-based subscription system[C].In proceedings of the 18th ACM Symposium on Principles of Distributed Computing，1999：53-61.

[5]齊鳳亮，金蓓弘.發(fā)布/訂閱系統(tǒng)中的原子訂閱管理和匹配[J].軟件學(xué)報(bào)，2009，36(12)：111-114.

[6]薛濤，馮博琴.基于內(nèi)容的發(fā)布訂閱系統(tǒng)中快速匹配算法的研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(3)：529-535.