發(fā)布訂閱系統(tǒng)中Carzaniga匹配算法優(yōu)化

張 穎，高申勇，曾 虹

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

0 引 言

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

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

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

1.1 訂閱語言和事件模型

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

（1）謂詞或約束：謂詞是一個含有命名變元的命題，4個命名變元為（type，attribute，operator，value）的四元組。

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

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

（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 如果對于訂閱中的每個屬性約束φ，事件中至少存在一個屬性α，使得α＜φ，則稱事件與訂閱匹配，記為 n＜s??β∈s：?α∈n：α＜β。

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

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

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

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

1.4 算法步驟

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

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

圖2 謂詞集匹配表

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

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

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

2 算法性能

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

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

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

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

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

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

圖3 不同屬性取值范圍的匹配時間

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

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

3 結(jié)束語

在Carzaniga算法基礎(chǔ)上提出了PPSMTBOAD，建立了訂閱模型和事件模型，定義了匹配和覆蓋規(guī)則，該算法充分挖掘謂詞間的覆蓋關(guān)系，同時支持訂閱和謂詞覆蓋，進(jìn)一步減少了重復(fù)匹配。在基于SINEA的原型系統(tǒng)進(jì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ī)模分布式計算發(fā)布訂閱系統(tǒng)核心技術(shù)［J］.軟件學(xué)報，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.