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

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

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

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

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