◆谷曉鵬 張凡石 王 葉

?

發(fā)布/訂閱中間件中基于過(guò)濾器的信息選擇機(jī)制

◆谷曉鵬1張凡石2王 葉1

（1.海軍指揮所 北京 100841；2.中國(guó)電科集團(tuán)28所 江蘇 210007）

發(fā)布訂閱中間件因其松耦合的特性得到廣泛的關(guān)注和應(yīng)用。在某些應(yīng)用場(chǎng)景中訂閱方僅對(duì)所訂閱主題中的部分信息感興趣，因此需要提供信息選擇機(jī)制以滿足這種應(yīng)用需求。本文提出了一種發(fā)布訂閱中間件中基于過(guò)濾器的信息選擇機(jī)制，并在發(fā)布訂閱中間件原型系統(tǒng)中實(shí)現(xiàn)了該機(jī)制。該機(jī)制遵循OMG DDS規(guī)范，采用Flex&Bison工具生成編譯器，將遵循類SQL語(yǔ)法的訂閱表達(dá)式解析生成過(guò)濾語(yǔ)法樹(shù)，通過(guò)對(duì)接收數(shù)據(jù)的解析和對(duì)過(guò)濾語(yǔ)法樹(shù)的遍歷作出是否過(guò)濾接收數(shù)據(jù)的決定。對(duì)原型系統(tǒng)的測(cè)試驗(yàn)證了該信息選擇機(jī)制的正確性和合理性。

信息過(guò)濾；發(fā)布訂閱中間件；數(shù)據(jù)分發(fā)服務(wù)；過(guò)濾器

0 引言

發(fā)布訂閱系統(tǒng)是一種以發(fā)布訂閱機(jī)制實(shí)現(xiàn)參與者之間交互的分布式系統(tǒng)，該系統(tǒng)參與者之間松耦合的特性正使其獲得越來(lái)越多的關(guān)注[1]。在發(fā)布訂閱機(jī)制中，訂閱者專注于獲取信息，發(fā)布者專注于發(fā)布信息，系統(tǒng)通過(guò)一定的方法完成相互的匹配，從而進(jìn)行信息傳輸。這樣的處理方式使得發(fā)布者和訂閱者在時(shí)間、空間、同步方面實(shí)現(xiàn)了解耦，大大增加相關(guān)應(yīng)用程序的靈活性和可擴(kuò)展性[2,3]。OMG組織制定了實(shí)時(shí)系統(tǒng)數(shù)據(jù)分發(fā)服務(wù)規(guī)范（Data Distribution Service for Real-time Systems, DDS），已成為信息分發(fā)發(fā)布訂閱系統(tǒng)的工業(yè)標(biāo)準(zhǔn)， RTI DDS等業(yè)界領(lǐng)先的發(fā)布訂閱系統(tǒng)均遵循該規(guī)范[4,5,6,7]。

在基于主題的發(fā)布訂閱系統(tǒng)的實(shí)際應(yīng)用中，訂閱者往往只對(duì)該主題下的部分信息感興趣，如何使得這些訂閱者更好，更快地“捕捉到”自己感興趣的信息就成為了發(fā)布訂閱中間件系統(tǒng)提高服務(wù)質(zhì)量的一大重點(diǎn)。例如：一個(gè)股票信息集成管理系統(tǒng)中發(fā)布和訂閱的信息為股票名稱及其價(jià)格，而訂閱者往往只關(guān)心某幾只股票的情況。如果不加過(guò)濾地將全部幾千只股票的信息全部提交給用戶，那么無(wú)關(guān)信息將占用用戶大量的處理時(shí)間，因此發(fā)布訂閱中間件需要向用戶提供信息過(guò)濾的功能。OMG DDS規(guī)范中提出了ContentFilteredTopic機(jī)制以提供該功能[2]，目前主要的發(fā)布訂閱中間件產(chǎn)品中均實(shí)現(xiàn)了這種功能[4,5]。本文在現(xiàn)有信息集成管理軟件（基于OMG DDS規(guī)范的發(fā)布訂閱原型系統(tǒng)）的基礎(chǔ)上，遵循OMG DDS規(guī)范中ContentFilteredTopic機(jī)制的相關(guān)接口，通過(guò)應(yīng)用Flex&Bison等工具構(gòu)建過(guò)濾語(yǔ)法樹(shù)，并與信息發(fā)布訂閱處理流程相集成實(shí)現(xiàn)了信息過(guò)濾功能。

1 過(guò)濾規(guī)則語(yǔ)法定義

過(guò)濾規(guī)則也稱為訂閱表達(dá)式，用于描述對(duì)信息相關(guān)數(shù)據(jù)的要求，表示用戶的“興趣”。OMG DDS規(guī)范中采用類SQL語(yǔ)法作為其語(yǔ)法定義。類SQL語(yǔ)法具體是指SQL語(yǔ)句中where從句部分的語(yǔ)法，該從句用于描述所查詢數(shù)據(jù)應(yīng)滿足的條件[2,6]。

該語(yǔ)法所支持的條件表達(dá)式有：

1.簡(jiǎn)單比較運(yùn)算

用于比較主題信息中某個(gè)字段的值是否等于（不等于、大于、小于）某個(gè)設(shè)定值，或者落在某個(gè)設(shè)定的取值區(qū)間，例如：key=10，key>20，key between 10 and 20等。

2.復(fù)雜邏輯運(yùn)算

對(duì)簡(jiǎn)單比較運(yùn)算表達(dá)式的與、或、非操作。例如：key<10 and key>20。

理論上該語(yǔ)法可以描述足夠復(fù)雜的訂閱表達(dá)式。

除OMG DDS規(guī)范定義的語(yǔ)法規(guī)則外，本文還加入了支持字符串型數(shù)據(jù)模糊過(guò)濾的strlike運(yùn)算符，該運(yùn)算符根據(jù)編輯距離的概念（即將一個(gè)字符串修改為另一個(gè)字符串所需改動(dòng)的字符個(gè)數(shù)），判斷兩個(gè)字符串是否相似。

2 基于過(guò)濾器的信息選擇機(jī)制

2.1 信息選擇機(jī)制的框架

圖1 信息選擇機(jī)制框架圖

圖1所示為信息選擇機(jī)制的框架和處理流程，其核心部分為過(guò)濾規(guī)則編譯器和過(guò)濾器。

過(guò)濾規(guī)則編譯器由通用的編譯器生成工具Flex&Bison離線生成。以過(guò)濾規(guī)則語(yǔ)法及其對(duì)應(yīng)的動(dòng)作代碼為輸入，生成過(guò)濾規(guī)則編譯器源代碼，該源代碼連編到發(fā)布訂閱中間件系統(tǒng)庫(kù)文件中，供發(fā)布訂閱系統(tǒng)運(yùn)行過(guò)程中在線使用[8]。

其中，動(dòng)作代碼是指當(dāng)生成的編譯器發(fā)現(xiàn)其輸入滿足某條語(yǔ)法規(guī)則時(shí)需要執(zhí)行的相應(yīng)語(yǔ)句，在本文中，用戶的訂閱表達(dá)式通過(guò)編譯器被表示成相應(yīng)的過(guò)濾語(yǔ)法樹(shù)，因此，此處的動(dòng)作代碼對(duì)應(yīng)著過(guò)濾語(yǔ)法樹(shù)中相應(yīng)節(jié)點(diǎn)的添加[8]。

當(dāng)訂閱者想要訂閱相關(guān)主題信息時(shí)，首先需要向系統(tǒng)注冊(cè)，此時(shí)，訂閱者應(yīng)提供訂閱表達(dá)式（過(guò)濾規(guī)則）以表示其訂閱興趣，過(guò)濾規(guī)則編譯器接受該輸入編譯生成相應(yīng)的過(guò)濾語(yǔ)法樹(shù)。

在數(shù)據(jù)發(fā)布訂閱階段，當(dāng)訂閱端接收到發(fā)布者發(fā)布的數(shù)據(jù)時(shí)，訂閱者的過(guò)濾器將獲取該數(shù)據(jù)，并根據(jù)該數(shù)據(jù)中各分量的值遍歷過(guò)濾語(yǔ)法樹(shù)，計(jì)算出當(dāng)前數(shù)據(jù)是否應(yīng)該過(guò)濾，如需要過(guò)濾則丟棄，否則向上提交給用戶。

2.2 過(guò)濾語(yǔ)法樹(shù)的生成

文中選擇樹(shù)形數(shù)據(jù)結(jié)構(gòu)作為訂閱表達(dá)式的表示方式，該結(jié)構(gòu)能夠比較直觀地表達(dá)訂閱表達(dá)式各部分之間的邏輯關(guān)系，并且便于過(guò)濾計(jì)算過(guò)程中的使用，例如：對(duì)于股票信息訂閱表達(dá)式StockCode=AAPL（蘋(píng)果股票） OR StockCode=MSFT（微軟股票）解析過(guò)程如圖2所示。當(dāng)過(guò)濾規(guī)則編譯器對(duì)一個(gè)滿足規(guī)約條件的表達(dá)式進(jìn)行規(guī)約時(shí)，會(huì)生成和這個(gè)表達(dá)式對(duì)應(yīng)的語(yǔ)法樹(shù)，圖2中首先是對(duì)于子式StockCode=AAPL進(jìn)行規(guī)約，然后是對(duì)子式StockCode=MSFT進(jìn)行規(guī)約，完成前面兩個(gè)規(guī)約之后，此時(shí)滿足了OR連詞表達(dá)式的規(guī)約條件，通過(guò)規(guī)約的相應(yīng)動(dòng)作將剛才生成的兩棵子樹(shù)以O(shè)R操作符對(duì)應(yīng)的節(jié)點(diǎn)為根節(jié)點(diǎn)，形成一棵新的語(yǔ)法樹(shù)。

圖 2a StockCode=AAPL

圖2b StockCode=MSFT

圖2 StockCode=AAPLOR StockCode=MSFT對(duì)應(yīng)樹(shù)形結(jié)構(gòu)示意圖

編譯器生成過(guò)程中所需要的動(dòng)作代碼[7]就是基于Flex&Bison提供的規(guī)則規(guī)約處理機(jī)制，在相關(guān)語(yǔ)法規(guī)則之后添加當(dāng)輸入滿足該規(guī)則進(jìn)行規(guī)約時(shí)需要進(jìn)行的處理。以圖2a為例，子式StockCode=AAPL對(duì)應(yīng)的規(guī)則的動(dòng)作代碼就是圖2a中樹(shù)節(jié)點(diǎn)的聲明以及節(jié)點(diǎn)間關(guān)系建立。

2.3 發(fā)布訂閱過(guò)程的過(guò)濾計(jì)算

過(guò)濾計(jì)算是過(guò)濾器根據(jù)過(guò)濾語(yǔ)法樹(shù)，提取出數(shù)據(jù)中與規(guī)則相關(guān)的數(shù)據(jù)分量，根據(jù)規(guī)則的邏輯關(guān)系進(jìn)行計(jì)算以判斷對(duì)于該數(shù)據(jù)的取舍。

在語(yǔ)義樹(shù)中主要存在三類與數(shù)據(jù)有關(guān)的節(jié)點(diǎn)：（1）確定值對(duì)應(yīng)的節(jié)點(diǎn)。該類節(jié)點(diǎn)是由用戶定義規(guī)則中明確的數(shù)值經(jīng)過(guò)編譯生成的，數(shù)據(jù)的類型以及值的信息均存儲(chǔ)于節(jié)點(diǎn)結(jié)構(gòu)中。（2）參數(shù)對(duì)應(yīng)的節(jié)點(diǎn)，該類節(jié)點(diǎn)由輸入規(guī)則中‘%n’形式表示的參數(shù)編譯生成，其中n表示該參數(shù)對(duì)應(yīng)參數(shù)值在參數(shù)存儲(chǔ)隊(duì)列中的索引位置,在過(guò)濾計(jì)算過(guò)程中根據(jù)索引信息查詢到對(duì)應(yīng)數(shù)值，參數(shù)的設(shè)計(jì)主要是為了提供過(guò)濾的靈活性，通過(guò)修改參數(shù)值就可以影響過(guò)濾的結(jié)果，不必重構(gòu)過(guò)濾表達(dá)式。（3）變量對(duì)應(yīng)的節(jié)點(diǎn)，該類節(jié)點(diǎn)需要過(guò)濾器在原始數(shù)據(jù)中查詢到變量對(duì)應(yīng)的實(shí)際值。

過(guò)濾計(jì)算過(guò)程中，首先將數(shù)據(jù)相應(yīng)分量的值代入到過(guò)濾語(yǔ)法樹(shù)中相應(yīng)節(jié)點(diǎn)，然后對(duì)過(guò)濾語(yǔ)法樹(shù)進(jìn)行自葉節(jié)點(diǎn)向根的遍歷計(jì)算，遍歷完整棵樹(shù)后的計(jì)算結(jié)果即表示是否過(guò)濾。

如圖3所示，當(dāng)?shù)竭_(dá)的數(shù)據(jù)中StockCode變量的實(shí)際值為IBM（IBM股票代碼）時(shí)，圖2中過(guò)濾語(yǔ)法樹(shù)中StockCode節(jié)點(diǎn)的值被替換成IBM，過(guò)濾計(jì)算最終結(jié)果為False，表示這個(gè)數(shù)據(jù)不符合訂閱表達(dá)式，將會(huì)被過(guò)濾掉。

圖3 過(guò)濾計(jì)算過(guò)程示意圖

不同類型的發(fā)布訂閱系統(tǒng)，過(guò)濾器的調(diào)用方式也不相同。對(duì)于有信息代理的集中式發(fā)布訂閱系統(tǒng)，由信息代理進(jìn)行信息的過(guò)濾，因?yàn)榇碛?jì)算功能相對(duì)較強(qiáng)而且相關(guān)資源（計(jì)算能力，內(nèi)存）等也比較充裕，同時(shí)提高端點(diǎn)（發(fā)布端，訂閱端）的運(yùn)行效率。對(duì)于純分布式的系統(tǒng)，采用在訂閱端過(guò)濾，考慮到發(fā)布端計(jì)算任務(wù)相對(duì)繁重（信息的產(chǎn)生以及發(fā)布），資源相對(duì)較少（用于信息存儲(chǔ)等），所以采取訂閱端過(guò)濾的方式，在訂閱者網(wǎng)絡(luò)層接收到數(shù)據(jù)，解析線程進(jìn)行解析時(shí)過(guò)濾。但是，在某些特殊情況下，發(fā)布端過(guò)濾會(huì)有更好地收益，因?yàn)榘l(fā)布端過(guò)濾可以減少網(wǎng)絡(luò)上的數(shù)據(jù)個(gè)數(shù)，節(jié)約帶寬資源，當(dāng)網(wǎng)絡(luò)帶寬資源相對(duì)較緊缺時(shí)，或者大部分訂閱端有相同的訂閱表達(dá)式時(shí)，可以考慮采用發(fā)布端過(guò)濾，而且發(fā)布端過(guò)濾沒(méi)有必要將表示數(shù)據(jù)結(jié)構(gòu)的typecode傳遞到訂閱端。

3 實(shí)驗(yàn)結(jié)果及分析

對(duì)過(guò)濾功能實(shí)現(xiàn)的相關(guān)功能測(cè)試顯示，該實(shí)現(xiàn)遵循OMG DDS規(guī)范，能夠滿足對(duì)于信息過(guò)濾的需求且具備較好的錯(cuò)誤處理能力。為進(jìn)一步驗(yàn)證實(shí)現(xiàn)方案的合理性，本文主要針對(duì)發(fā)布訂閱中間件系統(tǒng)的兩個(gè)主要性能指標(biāo)：處理時(shí)延和數(shù)據(jù)吞吐量進(jìn)行性能測(cè)試。過(guò)濾器中對(duì)影響相關(guān)指標(biāo)的因素主要是過(guò)濾計(jì)算的處理時(shí)間，該處理時(shí)間受過(guò)濾規(guī)則復(fù)雜度和相關(guān)數(shù)據(jù)查詢時(shí)間影響。過(guò)濾規(guī)則復(fù)雜度越高時(shí)，遍歷語(yǔ)法樹(shù)所需時(shí)間越長(zhǎng)，而數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，查找其中分量對(duì)應(yīng)實(shí)際數(shù)值所需時(shí)間也越長(zhǎng)，因此，測(cè)試過(guò)程中選取簡(jiǎn)單和復(fù)雜兩類數(shù)據(jù)類型，按照無(wú)過(guò)濾、簡(jiǎn)單過(guò)濾表達(dá)式、復(fù)雜過(guò)濾表達(dá)式這三種過(guò)濾場(chǎng)景設(shè)計(jì)測(cè)試用例，測(cè)試不同用例下的時(shí)延和吞吐量。測(cè)試用例設(shè)計(jì)如表1所示。

表 1 性能測(cè)試測(cè)試用例

圖4 時(shí)延指標(biāo)測(cè)試結(jié)果

時(shí)延測(cè)試結(jié)果如圖4所示。由圖可知：無(wú)過(guò)濾情形在所有情形中時(shí)延最短，而復(fù)雜過(guò)濾規(guī)則下時(shí)延最長(zhǎng)；采用相同的過(guò)濾表達(dá)式時(shí)，復(fù)雜數(shù)據(jù)類型的時(shí)延高于簡(jiǎn)單數(shù)據(jù)類型。測(cè)試結(jié)果表明：數(shù)據(jù)類型的復(fù)雜性會(huì)影響發(fā)布訂閱系統(tǒng)的時(shí)延，但相比而言，訂閱表達(dá)式的復(fù)雜程度對(duì)于時(shí)延的影響更大?？紤]到本文中復(fù)雜條件情形下的規(guī)則復(fù)雜度為簡(jiǎn)單條件情形下的5倍（以過(guò)濾語(yǔ)法樹(shù)中節(jié)點(diǎn)個(gè)數(shù)計(jì)），而時(shí)延僅增長(zhǎng)15%左右，說(shuō)明過(guò)濾器在過(guò)濾規(guī)則復(fù)雜度明顯增加時(shí)，具有較好的性能。

在吞吐量測(cè)試中，由于數(shù)據(jù)大小對(duì)吞吐量測(cè)試結(jié)果有一定影響，故將簡(jiǎn)單數(shù)據(jù)類型擴(kuò)充到與復(fù)雜數(shù)據(jù)類型大小一致后再進(jìn)行測(cè)試，經(jīng)測(cè)試該擴(kuò)充不會(huì)造成原始數(shù)據(jù)獲取時(shí)間明顯增長(zhǎng)。測(cè)試結(jié)果如圖5所示。

圖5 吞吐量指標(biāo)測(cè)試結(jié)果

上圖中縱軸數(shù)據(jù)代表訂閱端每秒處理的數(shù)據(jù)個(gè)數(shù)（因?yàn)閿?shù)據(jù)大小相同，所以用個(gè)數(shù)來(lái)代表吞吐量）。由圖5可知：過(guò)濾規(guī)則的復(fù)雜程度及數(shù)據(jù)類型的復(fù)雜程度均會(huì)影響發(fā)布訂閱系統(tǒng)的吞吐量，相比較而言，過(guò)濾規(guī)則的復(fù)雜程度是影響該指標(biāo)的最主要因素。

4 總結(jié)

本文采用Flex&Bison工具，提出了一個(gè)發(fā)布訂閱中間件系統(tǒng)中基于過(guò)濾語(yǔ)法樹(shù)的過(guò)濾器實(shí)現(xiàn)方案，以實(shí)現(xiàn)發(fā)布訂閱系統(tǒng)中的信息選擇機(jī)制，并在一個(gè)已有的發(fā)布訂閱中間件原型系統(tǒng)——信息集成管理軟件的基礎(chǔ)上實(shí)現(xiàn)了該方案。測(cè)試結(jié)果表明該實(shí)現(xiàn)方案遵循OMG DDS規(guī)范，較好地實(shí)現(xiàn)了信息選擇機(jī)制，其性能也與預(yù)期相符。

[1]Patrick TH. Eugster, Pascal A. Felber,Rachid Guerraoui, Anne-Marie Kermarrec, The Many Faces of Publish/Subscribe, ACM Computing Surveys, Vol. 35, No. 2, June 2003, pp. 114–131.

[2]Object Management Group, Data Distribution Service for Real-time Systems Specification,Version1.1, Nov.2005

[3] Object Management Group, The Real-time Publish/Subs cribe Wire Protocol DDS Interoperability Wire Protocol Specification .Version 2.1 2009.

[4] Gerardo P C. OMG Data-Distribution Service (DDS): Architectural Update. 2004 IEEE Military Communications Conference, 2004.

[5] Schneider S, Farabaugh B, Using the DDS Standard for High Reliability Applications. Real-Time Innovations.Inc, 2004.

[6] Real-Time Innovations. The Real-Time Publish/Subsc ribe Middleware User's Manual. Version 4.5C. 2010

[7] Object Computing, Inc. OpenDDS Developer’s Guide. Version 2.3,2007.

[8] Jobn Levine. flex與bison.陸軍譯.南京：東南大學(xué)出版社.2011.

本文受國(guó)家自然科學(xué)基金項(xiàng)目（60903163）和航空科學(xué)基金項(xiàng)目（20101969010）資助。