基于單哈希多維布隆過濾器的DDS自動發現算法

樊智勇 騰 達 劉哲旭

1(中國民航大學工程技術訓練中心 天津 300300) 2(中國民航大學電子信息與自動化學院 天津 300300)

0 引 言

數據分發服務DDS是一種高性能的中間件，能夠以較小的開銷實現可預測的數據分發。對象管理組織(Object Management Group, OMG)先后頒布了Version1.0、Version1.1和Version1.2規范[1-3]。該規范定義了一個與用戶具體使用的平臺、語言、所處位置都不相關且可擴展的基礎服務模型[4]。DDS采用以數據為中心的發布/訂閱通信模式，使分布式系統能夠實現數據高效、可靠的發布與訂閱[5]。目前，DDS已經被成功應用于海軍作戰管理、空中交通管制和船舶等系統[6]。

針對DDS自動發現過程，RTI(Real-time Innovations)提出了基于簡單發現協議的自動發現算法SDP_ADA(Simple discovery protocol automatic discovery algorithm)[7]。該算法在中小型實時系統中取得了良好的效果，但當系統的規模增大時，大量的數據需要頻繁地交換，會產生網絡數據傳輸量和內存消耗較高的問題。文獻[8]將DDS簡單發現協議和標準布隆過濾器Bloom結合，提出了一種自動發現算法SDPBloom。在自動發現過程中，SDPBloom通過Bloom存儲端點描述信息，有效地解決了 SDP_ADA中存在的高內存消耗和高網絡數據傳輸量等問題，增強了DDS的可拓展性。但是SDPBloom的實現需要大量的哈希函數運算，導致CPU資源消耗過多，并在分布式系統中產生了一定的延遲。為解決這一問題，本文提出了一種基于單哈希多維布隆過濾器的自動發現算法。該算法中的OMBF通過一個哈希函數和取模運算代替SDPBloom中多個哈希函數，降低了參與者端點匹配過程的計算量。

1 DDS簡單發現協議

域是一個虛擬網絡概念，它有助于隔離和優化分布式應用程序之間的通信。只有同一個域中的域參與者才能相互通信[10]。域參與者由發布者和訂閱者組成，每個發布者和訂閱者分別管理一個或多個數據寫入者和數據讀取者。本文將數據寫入者和數據讀取者統稱為端點。只有數據寫入者和數據讀取者具有相同的主題時，域參與者才能建立通信。域參與者之間的數據傳輸通過自動發現協議完成。

DDS簡單發現協議可以分為簡單參與者發現階段和端點發現階段[11]，兩個階段的發布/訂閱關系如圖2所示。

圖2 SDP自動發現過程

簡單參與者發現階段：域參與者之間進行相互發現。本地域參與者通過數據寫入者向其他域參與者發送數據包，同時也會通過數據讀取者讀取其他域參與者發送的數據包。

簡單端點發現階段：本地域參與者與其他域參與者進行相互匹配。它們相互交換包含主題名稱、主題類型和服務質量策略等信息的數據包。

在DDS簡單發現協議中，每個本地域參與者需要將自己所有的端點信息發送給其他域參與者，同時也會接收其他域參與者發送的所有的端點信息，這會產生大量的內存消耗和網絡傳輸量。事實上，每個域參與者只關心與自己訂閱主題相關的端點信息。因此，本文提出了基于單哈希多維布隆過濾器的自動發現算法。

2 算法設計

為降低標準Bloom的哈希計算量，本文提出了一種新型布隆過濾器OMBF。為降低DDS自動發現過程中的內存消耗和數據傳輸，本文將OMBF與DDS簡單發現協議結合，提出了自動發現算法SDP_OMBF。

2015年9月，沙特阿拉伯和巴林簽署價值約3億美元的新輸油管道鋪設合同。該管道由沙特阿美石油公司和巴林石油公司共同管理，將把原油從沙特阿美公司位于沙特東部的布蓋格煉油廠輸送到巴林石油公司煉油廠。

2.1 OMBF

OMBF是一種高效率的空間隨機數據結構，它用位數組簡潔地表示一個集合，并可以判斷一個元素是否屬于這個集合。OMBF是一個多維向量，每一維向量分為k個分區且初始值為0。向量維數用t表示，每一維向量分區i的大小用mi(1≤i≤k)表示。

OMBF的哈希函數計算過程分為以下三個階段：

(1) 哈希階段：A→B。A是將要存儲或查詢的集合中的元素，B是經過哈希函數映射之后的機器字。

(2) 選維階段：B→C。C是OMBF向量某一維，通過對B取模得到，即|B|(h(x)modt)。每次取模的結果選中OMBF向量某一維。

(3) 取模階段：B→D。D是OMBF向量某一維中的位置，通過對B取模得到，即|B|(h(x)modmi)。每次取模的結果使OMBF向量某一分區中某一位置為1。

如果每維向量中每個分區大小為互質，那么OMBF中這種不均勻的分區方法將會產生相互獨立的取模結果。更確切地，如果gi(x)=h(x) modmi，每個分區滿足條件(mi,mj)=1,1≤i≤j≤k，即mi、mj為相對素數，那么g1(x)、g2(x)、…、gk(x)相互獨立。

圖3表示OMBF的結構，其中假設k=3，集合S{x1，x2}中的元素通過一個哈希函數h(x)和取模運算存儲在OMBF中。

通過實例說明OMBF的工作原理。假設m1=11、m2=13、m3=19。當存儲元素x1時，首先，在哈希階段通過哈希函數h(x)轉換成機器字h(x1)，設h(x1)=9 655；然后，在選維階段d=h(x1) modt，即將元素x1映射到OMBF向量中第d維；最后，在取模階段機器字h(x1)分別對各分區進行取模。g1(x1)=h(x1) modm1=8，g2(x1)=h(x1) modm2=9，g3(x1)=h(x1) modm3=3，即第d維三個分區對應第8位、第9位、第3位。當查詢某一元素是否屬于集合S時，將待查詢元素經過3個階段運算之后，檢查相應3個位置是否為1，如果是，則判定該元素屬于集合S。

2.2 OMBF性能分析

OMBF和Bloom一樣，在元素查詢過程中也會發生誤報。OMBF誤報由兩個因素導致：(1) 在哈希階段，由機器字沖突發生的誤報，用a表示；(2) 在取模階段，在機器字不發生沖突的情況下，機器字取模余數發生沖突導致的誤報，用b表示。OMBF總的誤報率用FOMBF表示，計算如下：

FOMBE=P(f)=P(f|a)P(a)+P(f|b)P(b)=

P(a)+P(f|b)(1-P(a))

(1)

(2)

同理，可以得到機器字取模余數發生沖突導致的誤報率為：

(3)

通常機器字的長度遠大于OMBF向量，所以P(a)接近于0。OMBF的誤報率可以簡化為：

(4)

由于SDPBloom中的哈希函數數量等于SDP_OMBF中每一維的分區數，即哈希函數數量為k，其誤報率FSBF為[12]：

(5)

(6)

2.3 SDP_OMBF

在OMBF和簡單發現協議SDP的基礎上，本文提出了一種新的自動發現算法SDP_OMBF。SDP和SDP_OMBF的自動發現執行過程如圖4所示。

(a) SDP執行過程

圖4用兩個節點通信的實例說明SDP和SDP_OMBF執行過程，實例中本地參與者A向遠程參與者B發送端點信息。SDP_OMBF的執行過程如圖4(b)所示。在參與者發現階段，將本地參與者端點描述信息生成OMBF向量，然后和本地參與者數據包一塊發送至遠程參與者。參與者端點描述信息使用參與者端點信息唯一標識符，本文使用主題名作為唯一標識符。在端點發現階段，遠程參與者根據自身訂閱的主題對OMBF進行查詢。如果存在訂閱主題，則向本地參與者發送訂閱信息，本地參與者將被訂閱的主題數據包及服務質量發送至遠程參與者進行下一步匹配，如果匹配成功，兩參與者建立通信。而在圖4(a)所示的SDP的執行過程中，遠程參與者將會訂閱和接收本地參與者所有的端點信息。本文提出的SDP_OMBF將大量的端點信息減少為一條OMBF向量信息，因此，可以有效地減少自動發現過程中的內存消耗和網絡傳輸量。

3 實 驗

本節通過仿真和實驗驗證SDP_OMBF的有效性。本文將SDP_OMBF與使用較廣的DDS改進自動發現算法SDPBloom進行對比，驗證SDP_OMBF網絡傳輸量和內存消耗、主題查詢時間和誤報率。實驗平臺為Intel(R)CPU Core(TM) i5-3210、12 GB DDR 3(1 600 MHz)存儲器和4核×2線程(2.5 GHz)，軟件環境為DDS分布式互聯架構平臺。

3.1 網絡傳輸量和內存消耗驗證

實驗設置了1 000個參與者，每個參與者發布100個主題，每個主題信息是6 800字節，主題關鍵字為4字節。在SDPBloom和SDP_OMBF中，存儲主題關鍵字的向量為72字節。在端點發現階段，當查詢主題關鍵字中成員元素的比例從10%到90%變化時，SDP_OMBF和SDPBloom的網絡傳輸量和內存消耗如圖5和圖6所示。

圖5 SDPBloom和SDP_OMBF的網絡傳輸量

圖6 SDPBloom和SDP_OMBF的內存消耗

可以看出，當端點匹配逐漸增大時，SDPBloom和SDP_OMBF中的網絡數據傳輸量和內存消耗也逐漸增大。無論端點匹配率如何變化，兩者網絡數據傳輸量和內存消耗都近似相等。

3.2 主題查詢時間和誤報率驗證

本文實驗中，參與者端點信息的每個主題關鍵字大小為4字節。在SDP_OMBF中，本地參與者n個主題關鍵字映射到OMBF向量中。遠程參與者查詢主題關鍵字成員元素比例在10%至90%之間變化。令m=150、n=100、k=3、t=3。SDP_OMBF中的哈希函數為MD5，SDPBloom中的哈希函數為MD5、MD2和SHA-1。

當m變化時，進行了100組實驗，實驗結果如表1、表2所示。

表1 m=561時，SDPBloom和SDP_OMBF誤報率和計算時間對比

表2 m=1 413時，SDPBloom和SDP_OMBF誤報率和計算時間對比

續表2

從表1和表2可以看出，當m較小時，SDP_OMBF的誤報率略大于SDPBloom；當m增大時，兩者誤報率近似相等。然而，SDP_OMBF的運算時間始終低于SDPBloom約3 000 ms。

4 結 語

本文對 DDS 中SDP_ADA和SDPBloom自動發現算法進行了深入研究, 在分布式仿真系統規模較大時，針對數據傳輸過程中SDPBloom自動發現算法存在哈希函數運算量大的問題，提出一種新型的自動發現算法SDP_OMBF。通過實驗驗證了該算法的有效性。與SDPBloom算法相比，該算法在保證網絡數據傳輸量和內存消耗基本不變的條件下，將哈希函數運算時間降低約78%，從而降低自動發現過程中參與者端點之間發布/訂閱信息的時間，提高了分布式仿真系統的實時性。