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

    構(gòu)建訂閱樹時要考慮到謂詞間的覆蓋關(guān)系，讓父節(jié)點(diǎn)的謂詞覆蓋子節(jié)點(diǎn)的謂詞，這樣進(jìn)行事件匹配時，如果父節(jié)點(diǎn)的謂詞與事件的對應(yīng)屬性不匹配，則屬性與子節(jié)點(diǎn)的謂詞也一定不匹配，加快了匹配的速度。
    在訂閱樹中增加節(jié)點(diǎn)時，先通過索引結(jié)構(gòu)找到對應(yīng)的樹，然后在樹中查找這樣一個節(jié)點(diǎn)：這個節(jié)點(diǎn)覆蓋了新增加的節(jié)點(diǎn)，而它的子節(jié)點(diǎn)都不覆蓋新節(jié)點(diǎn)，然后將新節(jié)點(diǎn)插入到這個節(jié)點(diǎn)和它的子節(jié)點(diǎn)之間，新節(jié)點(diǎn)的訂閱集合也要添加相應(yīng)的訂閱者。
    在訂閱樹中刪除節(jié)點(diǎn)時，先通過索引結(jié)構(gòu)找到對應(yīng)的樹，從根節(jié)點(diǎn)遍歷樹，如果找到一個節(jié)點(diǎn)被要刪除的節(jié)點(diǎn)覆蓋，則將對應(yīng)的訂閱者從以這個節(jié)點(diǎn)為根的樹中的所有節(jié)點(diǎn)的訂閱集合中刪除，如果刪除后某個節(jié)點(diǎn)的訂閱集合為空，則刪除該節(jié)點(diǎn)。
    下面給出了構(gòu)建訂閱樹的算法偽代碼：
    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 事件匹配
    由于訂閱樹的構(gòu)造方法的改變，事件匹配的方法也有所不同，采用了先找出所有不匹配的訂閱，然后得到匹配的訂閱方法。匹配一個事件時，先對所有謂詞進(jìn)行測試，對事件中的每個屬性，依次查找類型和名稱對應(yīng)的訂閱樹。如果找到了相應(yīng)的訂閱樹，則用這個屬性測試訂閱樹中所有的節(jié)點(diǎn)。在測試的過程中，如果一個節(jié)點(diǎn)測試失敗，則記錄下這個節(jié)點(diǎn)的訂閱者和以這個節(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平臺，C++語言。編寫了一個訂閱產(chǎn)生器和事件產(chǎn)生器來產(chǎn)生實(shí)驗(yàn)樣本，每個實(shí)驗(yàn)結(jié)果為10次運(yùn)行的平均值。每個訂閱的形式如（numeric1>10，numeric2 !=8，string1 *=“student”），每個事件的形式如（int1=12，int3=200，string2=“teacher”）。
    實(shí)驗(yàn)一 測試訂閱數(shù)量對匹配速度的影響。首先向系統(tǒng)中添加訂閱，訂閱數(shù)目變化范圍為1 000～10 000個，每個訂閱包含5～10個謂詞；然后隨機(jī)生成一個事件，這個事件包含的屬性個數(shù)為20，測試匹配這個事件所需的時間。實(shí)驗(yàn)結(jié)果如圖2所示。

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

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