基于內(nèi)容的發(fā)布-訂閱系統(tǒng)中事件快速匹配算法研究.pdf

1、分布對(duì)象通信中間件的目標(biāo)是解決異構(gòu)網(wǎng)絡(luò)環(huán)境下分布應(yīng)用系統(tǒng)之間的互操作，它可以屏蔽網(wǎng)絡(luò)通信的實(shí)現(xiàn)細(xì)節(jié)，提高系統(tǒng)的可移植性。因而，在諸多領(lǐng)域得到了廣泛應(yīng)用，成為分布計(jì)算的主流技術(shù)之一。隨著Internet的飛速發(fā)展，軟件應(yīng)用形態(tài)逐步從相對(duì)封閉、面向熟識(shí)用戶群體和相對(duì)靜態(tài)的緊耦合形式向開放、公共可訪問(wèn)和動(dòng)態(tài)協(xié)作的松耦合模式轉(zhuǎn)變。采用RPC(Remote Procedure Call)同步機(jī)制的傳統(tǒng)分布對(duì)象中間件提供的單一同步通信機(jī)制無(wú)法適應(yīng)I

2、nternct的動(dòng)態(tài)特性，為應(yīng)對(duì)這一挑戰(zhàn)，構(gòu)建能夠?yàn)樯蠈臃植紤?yīng)用提供異步的、松耦合的通信機(jī)制變得非常必要。 發(fā)布/訂閱(Publish/Subscribe)是一種基于事件的通信范型。與異步RPC、分布共享內(nèi)存、消息隊(duì)列等異步通信范型相比，它具有能夠使通信的參與者在空間、時(shí)間和控制流上完全解耦等特點(diǎn)。因此，該范型能夠較好地滿足許多大型分布式系統(tǒng)松散耦合通信的需求，近年來(lái)受到廣泛關(guān)注和深入研究。 根據(jù)對(duì)事件通知選擇方式的不同

3、，發(fā)布/訂閱系統(tǒng)可以分為基于通道、基于主題和基于內(nèi)容等?；谕ǖ篮突谥黝}的發(fā)布/訂閱相對(duì)簡(jiǎn)單；基于內(nèi)容的發(fā)布/訂閱具有更強(qiáng)大、更靈活、適應(yīng)性更廣的特性。后者是構(gòu)建未來(lái)新型大規(guī)模分布式應(yīng)用系統(tǒng)的基礎(chǔ)設(shè)施之一。然而，相比之下，基于內(nèi)容的發(fā)布/訂閱要復(fù)雜的多。要使它成為一個(gè)真正實(shí)用的、支持大規(guī)模分布式應(yīng)用的支撐平臺(tái)，許多關(guān)鍵技術(shù)問(wèn)題仍然亟待解決。其中，制約其發(fā)展的瓶頸問(wèn)題就是事件的匹配。對(duì)于基于內(nèi)容的發(fā)布/訂閱系統(tǒng)而言，由于需要對(duì)事件的所有

4、可過(guò)濾屬性進(jìn)行匹配判斷，所以找到所有匹配的訂閱是非常具有挑戰(zhàn)的事情。大多數(shù)已有匹配算法都是基于如下的思想：對(duì)各個(gè)訂閱條中重復(fù)的約束，只需判斷一次來(lái)優(yōu)化，并充分利用訂閱的索引結(jié)構(gòu)，以縮短匹配時(shí)間。 本文分析了前人提出算法，在權(quán)衡匹配的時(shí)間效率、匹配的空間效率和訂閱維護(hù)的成本三方面因素的基礎(chǔ)上，提出了一種新的消息匹配算法-基于多維索引結(jié)構(gòu)算法(MIS/AL)。與傳統(tǒng)算法比較，MIS/AL算法具有以下優(yōu)點(diǎn)： 1)能同時(shí)支持“與