發布/訂閱中間件中基于過濾器的信息選擇機制

◆谷曉鵬 張凡石 王 葉

?

發布/訂閱中間件中基于過濾器的信息選擇機制

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

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

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

信息過濾；發布訂閱中間件；數據分發服務；過濾器

0 引言

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

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

1 過濾規則語法定義

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

該語法所支持的條件表達式有：

1.簡單比較運算

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

2.復雜邏輯運算

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

理論上該語法可以描述足夠復雜的訂閱表達式。

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

2 基于過濾器的信息選擇機制

2.1 信息選擇機制的框架

圖1 信息選擇機制框架圖

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

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

其中，動作代碼是指當生成的編譯器發現其輸入滿足某條語法規則時需要執行的相應語句，在本文中，用戶的訂閱表達式通過編譯器被表示成相應的過濾語法樹，因此，此處的動作代碼對應著過濾語法樹中相應節點的添加[8]。

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

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

2.2 過濾語法樹的生成

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

圖 2a StockCode=AAPL

圖2b StockCode=MSFT

圖2 StockCode=AAPLOR StockCode=MSFT對應樹形結構示意圖

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

2.3 發布訂閱過程的過濾計算

過濾計算是過濾器根據過濾語法樹，提取出數據中與規則相關的數據分量，根據規則的邏輯關系進行計算以判斷對于該數據的取舍。

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

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

如圖3所示，當到達的數據中StockCode變量的實際值為IBM（IBM股票代碼）時，圖2中過濾語法樹中StockCode節點的值被替換成IBM，過濾計算最終結果為False，表示這個數據不符合訂閱表達式，將會被過濾掉。

圖3 過濾計算過程示意圖

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

3 實驗結果及分析

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

表 1 性能測試測試用例

圖4 時延指標測試結果

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

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

圖5 吞吐量指標測試結果

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

4 總結

本文采用Flex&Bison工具，提出了一個發布訂閱中間件系統中基于過濾語法樹的過濾器實現方案，以實現發布訂閱系統中的信息選擇機制，并在一個已有的發布訂閱中間件原型系統——信息集成管理軟件的基礎上實現了該方案。測試結果表明該實現方案遵循OMG DDS規范，較好地實現了信息選擇機制，其性能也與預期相符。

[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.陸軍譯.南京：東南大學出版社.2011.

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