◆谷曉鵬 張凡石 王 葉

?

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

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

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

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

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

0 引言

發(fā)布訂閱系統(tǒng)是一種以發(fā)布訂閱機(jī)制實現(xiàn)參與者之間交互的分布式系統(tǒng)，該系統(tǒng)參與者之間松耦合的特性正使其獲得越來越多的關(guān)注[1]。在發(fā)布訂閱機(jī)制中，訂閱者專注于獲取信息，發(fā)布者專注于發(fā)布信息，系統(tǒng)通過一定的方法完成相互的匹配，從而進(jìn)行信息傳輸。這樣的處理方式使得發(fā)布者和訂閱者在時間、空間、同步方面實現(xiàn)了解耦，大大增加相關(guān)應(yīng)用程序的靈活性和可擴(kuò)展性[2,3]。OMG組織制定了實時系統(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)的實際應(yīng)用中，訂閱者往往只對該主題下的部分信息感興趣，如何使得這些訂閱者更好，更快地“捕捉到”自己感興趣的信息就成為了發(fā)布訂閱中間件系統(tǒng)提高服務(wù)質(zhì)量的一大重點。例如：一個股票信息集成管理系統(tǒng)中發(fā)布和訂閱的信息為股票名稱及其價格，而訂閱者往往只關(guān)心某幾只股票的情況。如果不加過濾地將全部幾千只股票的信息全部提交給用戶，那么無關(guān)信息將占用用戶大量的處理時間，因此發(fā)布訂閱中間件需要向用戶提供信息過濾的功能。OMG DDS規(guī)范中提出了ContentFilteredTopic機(jī)制以提供該功能[2]，目前主要的發(fā)布訂閱中間件產(chǎn)品中均實現(xiàn)了這種功能[4,5]。本文在現(xiàn)有信息集成管理軟件（基于OMG DDS規(guī)范的發(fā)布訂閱原型系統(tǒng)）的基礎(chǔ)上，遵循OMG DDS規(guī)范中ContentFilteredTopic機(jī)制的相關(guān)接口，通過應(yīng)用Flex&Bison等工具構(gòu)建過濾語法樹，并與信息發(fā)布訂閱處理流程相集成實現(xiàn)了信息過濾功能。

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

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

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

1.簡單比較運算

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 過濾語法樹的生成

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

圖 2a StockCode=AAPL

圖2b StockCode=MSFT

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

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

2.3 發(fā)布訂閱過程的過濾計算

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

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

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

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

圖3 過濾計算過程示意圖

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

3 實驗結(jié)果及分析

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

表 1 性能測試測試用例

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

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

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

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

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

4 總結(jié)

本文采用Flex&Bison工具，提出了一個發(fā)布訂閱中間件系統(tǒng)中基于過濾語法樹的過濾器實現(xiàn)方案，以實現(xiàn)發(fā)布訂閱系統(tǒng)中的信息選擇機(jī)制，并在一個已有的發(fā)布訂閱中間件原型系統(tǒng)——信息集成管理軟件的基礎(chǔ)上實現(xiàn)了該方案。測試結(jié)果表明該實現(xiàn)方案遵循OMG DDS規(guī)范，較好地實現(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.

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