摘  要： 目前基于內(nèi)容的發(fā)布/訂閱系統(tǒng)得到了廣泛的應(yīng)用,，而事件和訂閱的匹配算法是其中的一個(gè)關(guān)鍵問(wèn)題。提出了一種高效的匹配算法,，首先根據(jù)謂詞類型和名稱的不同建立若干訂閱樹(shù),，建立一個(gè)索引結(jié)構(gòu)管理這些樹(shù)。匹配時(shí),，根據(jù)事件的類型和名稱在對(duì)應(yīng)的樹(shù)中進(jìn)行搜索,。實(shí)驗(yàn)證明該算法具有較好的匹配性能。
關(guān)鍵詞： 發(fā)布/訂閱,；匹配算法；多維索引

    發(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)中,，信息由事件來(lái)表示,，訂閱者可以通過(guò)訂閱事件來(lái)獲取信息。一個(gè)事件可以表示為一些屬性的集合,，而訂閱則可以表示為一些謂詞的集合,。訂閱者可以通過(guò)指定其感興趣的謂詞來(lái)靈活地訂閱事件。相對(duì)于基于主題的發(fā)布/訂閱系統(tǒng),，基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中訂閱的表達(dá)能力得到了很大的提高,，但是同時(shí)系統(tǒng)中的訂閱數(shù)目也大大增加，匹配的復(fù)雜度大大提高,，必須有一個(gè)高效的算法來(lái)實(shí)現(xiàn)訂閱和事件的快速匹配[1],。匹配算法的基本思想是盡量?jī)?yōu)化訂閱結(jié)構(gòu),，減少匹配時(shí)訂閱條件中重復(fù)部分的判斷，提高匹配效率,。
1 相關(guān)研究
    目前相關(guān)的研究已經(jīng)提出了很多比較有代表性的算法[2-6],。Aguilera等提出了基于搜索樹(shù)的算法[4]，這種方法建立一棵搜索樹(shù),，每個(gè)非葉子節(jié)點(diǎn)表示一個(gè)對(duì)訂閱條件的測(cè)試,，每條邊代表測(cè)試結(jié)果，每個(gè)葉子節(jié)點(diǎn)表示一個(gè)訂閱條件,。當(dāng)匹配一個(gè)事件時(shí),，如果按照樹(shù)的某一路徑可以從樹(shù)根到達(dá)一個(gè)葉子節(jié)點(diǎn)，說(shuō)明該葉子節(jié)點(diǎn)代表的訂閱與這個(gè)事件相匹配,。這種方法中相同的訂閱條件只需要測(cè)試一次,，但是節(jié)點(diǎn)間的耦合性較高，相應(yīng)地,，維護(hù)樹(shù)的代價(jià)也比較高,。
    計(jì)數(shù)法的思想是測(cè)試所有謂詞，建立一個(gè)表保存謂詞和訂閱的映射關(guān)系,，即謂詞被哪些訂閱滿足,。匹配時(shí)，遍歷這個(gè)表找出滿足一個(gè)訂閱的謂詞數(shù)目,，將之與這個(gè)訂閱包含的謂詞數(shù)目進(jìn)行比較,，如果相等，則說(shuō)明事件與訂閱相匹配,。計(jì)數(shù)法雖然避免了一個(gè)謂詞被多次測(cè)試,，但是它總會(huì)對(duì)訂閱中所有的謂詞進(jìn)行測(cè)試，而實(shí)際上當(dāng)一個(gè)謂詞無(wú)法匹配時(shí),，其他的測(cè)試都不需要繼續(xù)進(jìn)行,。
2 匹配算法
    本文提出的方法借鑒了基于搜索樹(shù)的方法，學(xué)習(xí)了其中的優(yōu)點(diǎn),，并針對(duì)其中存在的缺點(diǎn)進(jìn)行了改進(jìn),。搜索樹(shù)的方法將所有謂詞添加到一棵樹(shù)中，樹(shù)的深度和耦合度比較大,，不利于訂閱樹(shù)的維護(hù),。所以本文方法中修改了構(gòu)造訂閱樹(shù)的方法，按照謂詞類型和名稱的不同創(chuàng)建若干訂閱樹(shù),，將不同的謂詞放到不同的樹(shù)中,，減少了耦合度。為了便于管理這些搜索樹(shù),，建立了一個(gè)索引結(jié)構(gòu),，根據(jù)謂詞類型和名稱的不同可以快速找到對(duì)應(yīng)的訂閱樹(shù),。
2.1 訂閱模型和事件模型
    在基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中，為了能讓訂閱者快速,、準(zhǔn)確地指定所需信息,，訂閱者要通過(guò)一定的訂閱模型來(lái)訂閱信息，發(fā)布者也要通過(guò)一定的事件模型來(lái)發(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è)屬性的測(cè)試結(jié)果,，可以表示為一個(gè)數(shù)據(jù)類型,、屬性名稱、測(cè)試操作符和匹配值組成的四元組,，即Predicate：=(type,，name，operator,，value),。謂詞的測(cè)試操作符(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 訂閱樹(shù)的構(gòu)造
    在構(gòu)造訂閱樹(shù)之前,，增加一個(gè)對(duì)訂閱集合預(yù)處理的步驟,。這是因?yàn)樵谝粋€(gè)訂閱中可能存在著沖突和重復(fù)的謂詞，在訂閱和匹配開(kāi)始前就進(jìn)行處理可以付出最小的代價(jià),。進(jìn)行預(yù)處理時(shí)要遍歷所有訂閱,，對(duì)于謂詞存在沖突的訂閱，由于一定不存在事件能與之匹配,，所以不需要將之添加到訂閱樹(shù)中,；對(duì)于謂詞間存在覆蓋關(guān)系的訂閱，只保留最大的謂詞,，這樣可以減少訂閱中謂詞的重復(fù),。
    接下來(lái)根據(jù)上一步經(jīng)過(guò)預(yù)處理的訂閱集合來(lái)創(chuàng)建若干訂閱樹(shù)，將類型和名稱相同的謂詞生成的節(jié)點(diǎn)添加到一棵訂閱樹(shù)中,。訂閱樹(shù)中的每個(gè)節(jié)點(diǎn)存儲(chǔ)了一個(gè)謂詞和包含這個(gè)謂詞的訂閱的集合,。為了便于在訂閱樹(shù)中進(jìn)行匹配，分別以謂詞的類型,、名稱和操作符為鍵建立一個(gè)多級(jí)索引結(jié)構(gòu)來(lái)管理所有的訂閱樹(shù),，如圖1所示，將指向每棵訂閱樹(shù)根節(jié)點(diǎn)的指針對(duì)應(yīng)存儲(chǔ)在索引結(jié)構(gòu)中,，這樣當(dāng)需要匹配一個(gè)事件的屬性時(shí)就能根據(jù)屬性的類型和名稱進(jìn)行快速定位,。

    構(gòu)建訂閱樹(shù)時(shí)要考慮到謂詞間的覆蓋關(guān)系，讓父節(jié)點(diǎn)的謂詞覆蓋子節(jié)點(diǎn)的謂詞,，這樣進(jìn)行事件匹配時(shí),，如果父節(jié)點(diǎn)的謂詞與事件的對(duì)應(yīng)屬性不匹配，則屬性與子節(jié)點(diǎn)的謂詞也一定不匹配,，加快了匹配的速度,。
    在訂閱樹(shù)中增加節(jié)點(diǎn)時(shí),，先通過(guò)索引結(jié)構(gòu)找到對(duì)應(yīng)的樹(shù),，然后在樹(shù)中查找這樣一個(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)的訂閱者。
    在訂閱樹(shù)中刪除節(jié)點(diǎn)時(shí),，先通過(guò)索引結(jié)構(gòu)找到對(duì)應(yīng)的樹(shù),，從根節(jié)點(diǎn)遍歷樹(shù),，如果找到一個(gè)節(jié)點(diǎn)被要?jiǎng)h除的節(jié)點(diǎn)覆蓋，則將對(duì)應(yīng)的訂閱者從以這個(gè)節(jié)點(diǎn)為根的樹(shù)中的所有節(jié)點(diǎn)的訂閱集合中刪除,，如果刪除后某個(gè)節(jié)點(diǎn)的訂閱集合為空,，則刪除該節(jié)點(diǎn)。
    下面給出了構(gòu)建訂閱樹(shù)的算法偽代碼：
    ADD-SUBSCRIPTION (sub)
      for each predicate Pi in sub
        do find root node of the corresponding tree by the
type and name of Pi
            if the tree doesn’t exist
               create a new tree
            ADD-PREDICATE (rooti,Pi)
    ADD-PREDICATE (node, p)
      if the predicate of node covers p
      for each child of node childi
        do if the predicate of childi covers p
            then ADD-PREDICATE (childi, p)
            else if p covers the predicate of childi
                then insert p between node and childi
            else save p as a child of node
2.3 事件匹配
    由于訂閱樹(shù)的構(gòu)造方法的改變,，事件匹配的方法也有所不同,，采用了先找出所有不匹配的訂閱，然后得到匹配的訂閱方法,。匹配一個(gè)事件時(shí),，先對(duì)所有謂詞進(jìn)行測(cè)試，對(duì)事件中的每個(gè)屬性,，依次查找類型和名稱對(duì)應(yīng)的訂閱樹(shù),。如果找到了相應(yīng)的訂閱樹(shù)，則用這個(gè)屬性測(cè)試訂閱樹(shù)中所有的節(jié)點(diǎn),。在測(cè)試的過(guò)程中,，如果一個(gè)節(jié)點(diǎn)測(cè)試失敗，則記錄下這個(gè)節(jié)點(diǎn)的訂閱者和以這個(gè)節(jié)點(diǎn)為根的子樹(shù)中所有節(jié)點(diǎn)的訂閱者,。測(cè)試完成后,，在訂閱集合中剔除所有不匹配的訂閱，就能找出所有與當(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++語(yǔ)言,。編寫了一個(gè)訂閱產(chǎn)生器和事件產(chǎn)生器來(lái)產(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)一 測(cè)試訂閱數(shù)量對(duì)匹配速度的影響,。首先向系統(tǒng)中添加訂閱,，訂閱數(shù)目變化范圍為1 000～10 000個(gè)，每個(gè)訂閱包含5～10個(gè)謂詞；然后隨機(jī)生成一個(gè)事件,，這個(gè)事件包含的屬性個(gè)數(shù)為20,，測(cè)試匹配這個(gè)事件所需的時(shí)間。實(shí)驗(yàn)結(jié)果如圖2所示,。

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

    從上面的實(shí)驗(yàn)結(jié)果可以看出，本文提出的算法在匹配效率上相對(duì)于計(jì)數(shù)法和基于匹配樹(shù)的算法有了較大的提高,。當(dāng)事件的屬性個(gè)數(shù)相同而系統(tǒng)訂閱數(shù)不斷增加時(shí),，和系統(tǒng)中訂閱數(shù)目相同而事件包含的屬性個(gè)數(shù)不斷增長(zhǎng)時(shí)，這種算法明顯表現(xiàn)出了它的高效性,。
    近年來(lái)基于內(nèi)容的發(fā)布/訂閱系統(tǒng)逐漸獲得了越來(lái)越廣泛的應(yīng)用,。本文針對(duì)基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中的事件與訂閱的匹配，提出了一種匹配算法,。這種算法利用一個(gè)多級(jí)索引結(jié)構(gòu)來(lái)管理不同類型和名稱謂詞,，提高了謂詞的匹配速度，而且充分考慮了謂詞間的覆蓋關(guān)系,，減少了匹配次數(shù),。最后通過(guò)實(shí)驗(yàn)證明了這種算法的正確性和高效性。未來(lái)可以對(duì)算法的覆蓋關(guān)系,、訂閱樹(shù)的結(jié)構(gòu)等進(jìn)行更一步的改進(jìn),。
參考文獻(xià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.