張 穎，高申勇，曾 虹

（1.浙江水利水電?？茖W(xué)校計(jì)算機(jī)與信息工程系，浙江 杭州310018；2.杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州310018）

0 引 言

隨著網(wǎng)絡(luò)快速發(fā)展，生活當(dāng)中出現(xiàn)越來越多的分布式計(jì)算環(huán)境，傳統(tǒng)的客戶/服務(wù)器模式難以適應(yīng)這種環(huán)境。發(fā)布/訂閱系統(tǒng)是一種基于事件的通信范型，具有異步、多點(diǎn)通信等優(yōu)點(diǎn)，可廣泛應(yīng)用分布式計(jì)算及移動(dòng)環(huán)境［1］。因此近年來，發(fā)布/訂閱系統(tǒng)成為研究熱點(diǎn)，特別是基于內(nèi)容的發(fā)布訂閱系統(tǒng)，典型系統(tǒng)如SIENA［2］等。其中，系統(tǒng)中必須解決事件與訂閱間高效匹配問題，匹配算法的性能直接影響到系統(tǒng)性能。匹配算法分為兩類：基于計(jì)數(shù)法和基于搜索樹匹配［3］。目前算法都未能解決訂閱與事件重復(fù)匹配問題，如主流算法Carzaniga［4］只支持訂閱覆蓋，沒有考慮多個(gè)訂閱可能存在謂詞間的覆蓋關(guān)系，引發(fā)較嚴(yán)重重復(fù)匹配，從而影響匹配效率，導(dǎo)致系統(tǒng)整體性能低。針對(duì)上述問題，本文提出改進(jìn)算法，它能同時(shí)支持訂閱覆蓋和謂詞覆蓋，實(shí)驗(yàn)表明與Carzaniga相比，本算法能進(jìn)一步減少重復(fù)匹配，提高匹配效率，也提高系統(tǒng)整體性能，更適合應(yīng)用于大規(guī)模的發(fā)布訂閱系統(tǒng)。

1 PPSMTBOAD算法描述

已有的較有影響的原型系統(tǒng)SIENA采用Carzaniga算法，它利用訂閱間的覆蓋關(guān)系以及合并訂閱思想，減少和事件進(jìn)行匹配的訂閱數(shù)目。算法的基礎(chǔ)思想如下，以樹結(jié)構(gòu)組織所有訂閱，以覆蓋與被覆蓋方式組織樹中的結(jié)點(diǎn)。事件e從樹的根結(jié)點(diǎn)向下逐級(jí)匹配，當(dāng)且僅當(dāng)e通過所有的中間結(jié)點(diǎn)到達(dá)葉結(jié)點(diǎn)時(shí)匹配結(jié)束，被匹配到的訂閱條件就是葉結(jié)點(diǎn)所指代的訂閱條件。

但是Carzaniga算法［5］僅考慮訂閱間的覆蓋關(guān)系，沒有考慮多個(gè)訂閱可能存在相同謂詞及謂詞間的覆蓋關(guān)系，若相同謂詞被多次存儲(chǔ)和判定，將產(chǎn)生時(shí)間和空間上的冗余。在其基礎(chǔ)上，充分吸收覆蓋思想，提出一種改進(jìn)算法，稱為基于屬性劃分的并行謂詞集匹配樹算法（Parallel Predicate Set Matching Tree Based on Attribute Division，PPSMTBOAD）。

PPSMTBOAD算法結(jié)合基于計(jì)數(shù)法和基于搜索樹匹配策略，充分兼顧多個(gè)訂閱間可能存在相同謂詞和謂詞間覆蓋關(guān)系，并且通過構(gòu)造多個(gè)并行謂詞集匹配樹加速匹配，以及利用謂詞間的覆蓋關(guān)系減少不必要重復(fù)匹配進(jìn)行優(yōu)化。

1.1 訂閱語言和事件模型

設(shè)計(jì)合理的事件模型和訂閱語言能降低系統(tǒng)的事件匹配復(fù)雜度，提高系統(tǒng)性能。本算法采用的策略是：發(fā)布者通過事件模型發(fā)布事件，訂閱同時(shí)支持合取和析取操作。

（1）謂詞或約束：謂詞是一個(gè)含有命名變?cè)拿}，4個(gè)命名變?cè)獮椋╰ype，attribute，operator，value）的四元組。

（2）過濾：Filterp=constraintp，q謂詞合取關(guān)系的復(fù)合命題。

（3）訂閱：subscriptioni=Filteri，p過濾上使用析取關(guān)系的復(fù)合命題，表明有一個(gè)過濾為真，該訂閱就為真。

（4）事件或通知：事件是發(fā)布者發(fā)送到發(fā)布/訂閱系統(tǒng)的具體信息，事件采用屬性集合來描述，Notifications=attributes，t，attributet=（typeα，nameα，valueα）。

1.2 匹配和覆蓋規(guī)則

規(guī)則 1 如果屬性α=（typeα，nameα，valueα）與屬性β=（typeβ，nameβ，operatorβ，valueβ）約束之間滿足（typeα=typeβ）∧（nameα=nameβ）∧（operatorβ=valueβ）?（operatorα=valueα），則稱約束β包含屬性α，或記為α＜β。

規(guī)則 2 判定約束β1和β2具有覆蓋關(guān)系則β1和β2必須滿足（typeβ1=typeβ2）∧（nameβ1=nameβ2）∧（operatorβ1=valueβ1）?（operatorβ2=valueβ2），則稱β1覆蓋β2，或記為β2＜β1。

規(guī)則3 如果對(duì)于訂閱中的每個(gè)屬性約束φ，事件中至少存在一個(gè)屬性α，使得α＜φ，則稱事件與訂閱匹配，記為 n＜s??β∈s：?α∈n：α＜β。

1.3 算法數(shù)據(jù)結(jié)構(gòu)

算法數(shù)據(jù)結(jié)構(gòu)如圖1所示，首先處理訂閱集，將訂閱分解為謂詞集合，剔除重復(fù)謂詞，將謂詞按照屬性名分為若干個(gè)謂詞集，利用規(guī)則2，即以覆蓋與被覆蓋方式組織樹中的結(jié)點(diǎn)、前驅(qū)結(jié)點(diǎn)后繼結(jié)點(diǎn)組建多個(gè)匹配樹，結(jié)點(diǎn)代表謂詞，稱為謂詞集匹配樹。從覆蓋范圍最廣的第一級(jí)謂詞結(jié)點(diǎn)開始匹配，采用深度優(yōu)先搜索逐級(jí)往下級(jí)匹配，當(dāng)某一級(jí)謂詞不滿足匹配，表明從該級(jí)直至最后一級(jí)謂詞都不滿足匹配，因此立即停止匹配。

給定事件e，根據(jù)屬性名快速定位，并從根結(jié)點(diǎn)開始查找滿足匹配的謂詞，如事件與某個(gè)謂詞集匹配樹中的謂詞不匹配，則該謂詞以后直至謂詞集匹配樹的葉子結(jié)點(diǎn)都不滿足該事件，無需再逐個(gè)進(jìn)行比較。另外，在謂詞集匹配樹中，為了保持謂詞和訂閱之間的隸屬關(guān)系，采用了謂詞-訂閱者的鏈表結(jié)構(gòu)，每個(gè)謂詞指向一個(gè)鏈表結(jié)構(gòu)，該鏈表存儲(chǔ)了所有包含該謂詞的訂閱者標(biāo)識(shí)，為了區(qū)別同一訂閱者的不同訂閱消息，又建立了訂閱者-訂閱消息的鏈表結(jié)構(gòu)，存儲(chǔ)了訂閱消息標(biāo)識(shí)符。

為了將匹配謂詞集求交集，建立了一個(gè)謂詞集匹配表，如圖2所示，以屬性名作為鍵，存儲(chǔ)每個(gè)成功匹配謂詞所包含訂閱者標(biāo)識(shí)和訂閱消息標(biāo)識(shí)。當(dāng)一個(gè)訂閱條件所有的謂詞都匹配時(shí)，說明該訂閱匹配成功。

1.4 算法步驟

描述PPSMT算法。為了形式化描述該算法，定義如下符號(hào)：保存與事件中的某個(gè)三元組匹配的謂詞標(biāo)識(shí)matching-predicater（cj.sk）；保存與某事件匹配的訂閱標(biāo)識(shí)matching-subscriptionr（cj.sk）：

圖1 謂詞集并行匹配樹結(jié)構(gòu)

圖2 謂詞集匹配表

（1）以單個(gè)三元組 attributet=（typet，α，namet，α，valuet，α）為匹配單位，并行遍歷謂詞集匹配樹，遍歷至某個(gè)謂詞時(shí)，三元組與之進(jìn)行匹配，若滿足規(guī)則1匹配成功，保存謂詞標(biāo)識(shí)cj.sk至matching-predicater（cj.sk），若存在與之不匹配的謂詞，不繼續(xù)進(jìn)行匹配，匹配結(jié)束。之后判斷matching-predicater（cj.sk）是否為空，如果為空，即不存在與事件相匹配的訂閱，算法結(jié)束，go to Step3；

（2）對(duì)所有matching-predicater（cj.sk）鏈表中的元素求交集，保存結(jié)果至匹配集matching-subscriptionr（cj.sk），該結(jié)果集就是與事件匹配的訂閱；

（3）算法結(jié)束。

2 算法性能

在一臺(tái)CPU為Intel Pentium IV 3.00 GHz，內(nèi)存為1.00GB普通臺(tái)式電腦上，對(duì)SINEA原型系統(tǒng)進(jìn)行了模擬實(shí)驗(yàn)。SINEA是科羅拉多大學(xué)一個(gè)開放源碼基于內(nèi)容的分布式發(fā)布訂閱系統(tǒng)，提供了標(biāo)準(zhǔn)的publish、subscribe和unsubscribe API等接口，具有良好的性能。實(shí)驗(yàn)結(jié)果中的每個(gè)數(shù)據(jù)點(diǎn)都是以同樣的參數(shù)運(yùn)行了15次求得的平均值。實(shí)驗(yàn)中包括一個(gè)數(shù)據(jù)產(chǎn)生器，按照自動(dòng)配置產(chǎn)生相應(yīng)的事件與訂閱，產(chǎn)生規(guī)則如下：

（1）屬性類型，使用四種基本數(shù)據(jù)類型Int、Float、String、Bool；其中Int類型占40%，其余各占20%；

（2）屬性名稱，定義一個(gè)長度為n的字符數(shù)組，稱為屬性名表，表中的每個(gè)字符是從24個(gè)英文字母表中隨機(jī)選取5個(gè)字母組成，屬性名是從屬性名表中隨機(jī)選??；

（3）操作符，包括＞，＜，=，!，"5種操作符，在測試中的比例各占20%；

（4）屬性值，對(duì)于Int/Float類型，在0-1 000之間取值；對(duì)于String類型，從屬性名表隨機(jī)選?。粚?duì)于Bool類型，隨機(jī)取“真”或“假”。

本實(shí)驗(yàn)將比較最原始基于計(jì)數(shù)法的匹配算法Naive、Carzaniga算法和PPSMTBOAD算法，從以下方面來進(jìn)行比較。屬性取值范圍對(duì)匹配時(shí)間的影響：取屬性表的長度變化范圍為50～500，對(duì)每個(gè)屬性表隨機(jī)生成5 000個(gè)訂閱，各訂閱的謂詞個(gè)數(shù)在515平均分配，測得的匹配計(jì)算耗時(shí)如圖3所示。訂閱數(shù)量對(duì)算法匹配時(shí)間的影響：生成一個(gè)長度為600的屬性表，隨機(jī)生成包含25個(gè)屬性的事件，隨機(jī)生成若干組訂閱，訂閱個(gè)數(shù)的變化范圍為1 000～100 000，各訂閱的謂詞個(gè)數(shù)在5～20平均分配，測得的匹配計(jì)算耗時(shí)如圖4所示。

圖3 不同屬性取值范圍的匹配時(shí)間

圖4 不同訂閱數(shù)量的匹配時(shí)間

由圖3可知，屬性取值范圍變化對(duì)Naive基本沒有影響，對(duì)Carzaniga算法，由于它支持訂閱覆蓋，當(dāng)屬性種類越多，取值范圍擴(kuò)大，那么覆蓋范圍越分散，匹配效率有所提高。PPSMTBOAD除支持訂閱覆蓋，還支持謂詞覆蓋，劃分并行謂詞集匹配樹可減少搜索樹的節(jié)點(diǎn)數(shù)，降低對(duì)存儲(chǔ)空間的需求，并潛在地縮短事件匹配時(shí)間，尤其適合于節(jié)點(diǎn)分支數(shù)多而匹配分支少時(shí)的情況，當(dāng)屬性種類越多，謂詞集匹配樹越多，覆蓋范圍更加分散，進(jìn)一步減少了重復(fù)匹配提高，匹配效率顯著提高。由圖4可知，隨著訂閱數(shù)量增加，本算法的降幅小于其他兩種算法，系統(tǒng)可擴(kuò)展性提高，更適合應(yīng)用于大規(guī)模的發(fā)布訂閱系統(tǒng)。

3 結(jié)束語

在Carzaniga算法基礎(chǔ)上提出了PPSMTBOAD，建立了訂閱模型和事件模型，定義了匹配和覆蓋規(guī)則，該算法充分挖掘謂詞間的覆蓋關(guān)系，同時(shí)支持訂閱和謂詞覆蓋，進(jìn)一步減少了重復(fù)匹配。在基于SINEA的原型系統(tǒng)進(jìn)行了模擬實(shí)驗(yàn)，結(jié)果表明，與Carzaniga算法相比，該算法的匹配效率有了一定的提高。

［1］ Carzaniga A，Wolf A L.Design and Evaluation of a Wide-Area Event Notification Service［J］.ACM Transaction on Computer Systems，2001，19（3）：332-383.

［2］ Eugster PT，F(xiàn)elber PA，Guerraoui R，et al.The Many Faces of Publish/Subscribe［J］.ACM Computing Surveys，2003，35（2）：114-213.

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

［4］ Carzaniga A，Wolf A L.Design and Evaluation of aWide2Ar2ea Event Notification Service［J］.ACM Trans on Computer Systems，2001，19（3）：322-383.

［5］ 苑洪亮.基于內(nèi)容的“發(fā)布/訂閱”若干關(guān)鍵技術(shù)研究［D］.長沙：國防科學(xué)技術(shù)大學(xué)，2006.