一種可應用于大流量環境的雙層散列算法研究

張智江，王志軍，張 尼

（中國聯合網絡通信有限公司 北京 100033）

1 引言

散列是信息存儲和查詢所用的一項基本技術，雖然發明于50年前，其間也有過不少非常系統、完整的研究工作，但近年仍然有新的工作進展。散列技術的基礎性及其在許多領域的可應用性是其不斷被人們研究的源泉。目前，散列算法已經廣泛應用于大流量環境下的工程實踐中，典型的場景如骨干網群發郵件過濾[1]、互聯網冗余流量清除[2]、移動網絡中的短消息過濾[3]等。

一般地，應用于大流量環境下的實時處理系統會面臨兩個問題：系統需要保留一定數量的歷史數據，因此對存儲空間有一定的需求（涉及算法的空間性能，如果需要的存儲空間過大，系統將難以投入使用）；系統需要對流量數據進行實時查找、比較、修改等操作，因此對操作時間有一定要求（涉及算法的時間性能，如果算法實時性能差，系統難以投入使用）。

直觀、常識性的做法是對大流量數據實施散列算法，并將產生的散列值集合存入數據存儲結構，便于后續操作。大流量環境下的實時處理系統是否有效、實用，關鍵就在于如何設計散列算法和對應的數據存儲結構以滿足系統的時間和空間性能。

[1,2]均希望通過設計一個合理的散列算法同時滿足系統的時間和空間性能，但效果卻并不理想。本文認為時間與空間性能的需求，可轉化成如下兩個問題。

·選取合適的散列下標算法（即鍵值在散列表中的存儲位置）。合理的散列下標算法使得鍵值均勻分布于散列表內各槽中；否則，在槽中查詢或添加一個元素會帶來較大開銷，失去散列表的優越性。

·選取合適的鍵值。散列表中往往保留原始輸入作為鍵值，以區分槽中存儲位置沖突的元素。但是，如果原始鍵值較長，則不應直接存儲和比較，否則必將占用極大的內存空間且耗費時間。

這兩種需求是有區別的。前者追求時間性能，要求散列值的分布盡量均勻，查詢、比較、修改操作速度快；后者追求算法的空間性能，要求散列表中存儲占用空間較小，但能代表原始輸入。因此，很難通過一種散列算法同時滿足上述需求，參考文獻[1,2]只解決了選取鍵值的問題，使系統具有較好的空間性能，但系統的時間性能較差。

針對上述情況，本文提出一種雙層散列算法。兩個散列函數均直接作用于原始輸入，鍵值散列函數用于產生可惟一表征原始輸入的鍵值，下標散列函數用于產生鍵值在數據結構中的存儲地址。針對上述兩種需求給出了相應的算法評估測度，并通過實驗從若干候選算法中選出較優的算法。

2 雙層散列算法

2.1 算法思路與數據結構設計

下面以互聯網垃圾郵件過濾為例，具體介紹雙層散列算法。

將全體郵件集合記作M={M1,M2,…,Mn}，每封郵件的正文部分看成是字節序列的集合{b1,b2,…,bs}。作為研究郵件聚類性質的一個方面，給定k封郵件M1,…,Mk，分析是否存在內容相似性，從而可以聚成同一郵件類，進而識別具有相似內容的群發垃圾郵件。為此，將郵件表示為：

即將每封郵件看成是由連續n個長度為l byte（一般取較大的值，如100 byte）的子序列構成的集合。如果k封郵件M1,…,Mk的交集不為空，則可認為這些郵件內容相似。

一種可行的方法是依次比較郵件中各字節序列是否相同，為提高比較效率，要用數據結構T保存訪問過的字節序列Bi。遇到一個元素Bi，先與T中的元素比較，若不在其中，則將它加入T中，否則丟棄此元素，并記錄郵件相似情況。顯然將T組織成一個散列表是較好的選擇。

設雙層散列算法中的鍵值函數為Unique_hash，下標函數為Uniform_hash，hi為原始輸入Bi在數據結構中的存儲地址，因此有：

為節省空間，在數據結構中不存儲Bi，而是存儲可惟一表征 Bi的指紋值 fi，有：

雙層散列算法的關鍵在于選取合適的鍵值函數及下標函數，以滿足實時系統時、空性能。

此外，在處理數據過程中，散列算法需要頻繁對內存中存儲的大量指紋信息進行檢索、比較，為支持上述操作，設計了一套數據結構，由郵件庫(MD)和模式庫(PD)兩部分組成，如圖1所示。

圖1 雙層散列函數對應的數據結構

· 郵件庫以散列表形式組織，保存全部郵件類的描述信息，用于全局統計。描述信息包括所屬郵件類的容量、郵件類第一封郵件和最后(即最近)一封郵件的ID、類中郵件指紋信息在模式庫中的散列槽地址。

· 模式庫以散列表形式組織，負責指紋的保存、檢索和組織工作。每個單元對應一個槽，槽內每個元素由一個指紋和該指紋對應的郵件類在郵件庫中的入口地址組成。

2.2 算法選擇

2.2.1 評估測度

為了比較不同的散列函數的優劣，需要有與應用背景相關的評估測度。對于§1第 1種需求，關心對散列后散列值的平均查詢時間；對于第2種需求，關心散列值的沖突情況，保證形成的散列槽中最多只能有一個元素。為此，有下面兩種對應的測度定義。

（1）鍵值函數測度

設有M組內容相似的郵件，每組有Ni封郵件。將郵件中的字節序列用散列函數F形成鍵值，然后到相應的散列表中查詢，假設鍵值正確命中ni1次，錯誤命中ni2次，則每組郵件的沖突率為ni1/Ni，查全率為ni1/Ni，有：

其中，B=C+1-Q，B為鍵值函數的測度。

（2）下標函數測度

設有N個鍵值需要處理，將這些鍵值用散列函數F散列到M個槽中，對于i(1≤i≤M)號槽，散列到其中的鍵值個數為N。假設查詢每個鍵值的概率是相等的，則對N個鍵值各作一次查詢的時間算術平均值，便可當作F的查詢性能測度。按照通常散列表項的鏈表結構，對i號槽中第k個元素作查詢，需要訪問存儲k次，所以對散列在i號槽中的所有鍵值都作一次查詢，則需要訪問存儲(ni+1)Ni/2次。考慮所有的槽，可以用平均存儲訪問次數表示散列函數F的查詢性能測度，即：

S即為下標函數的測度，其值越小越好。

根據上述條件和凹函數的基本性質，當Ni=N/M時S取最小值，當只有1個Ni=N，其他Ni為0時取最大值，兩個極值分別為N/(M+1)/2、(N+1)/2。

2.2.2 待評估的散列函數

（1）用于生成鍵值的候選函數

Rabin指紋算法[4]是公認的最優鍵值函數，其鍵值長度為64位，值域范圍大，可代替原始輸入而不產生沖突，因此將Rabin指紋算法作為惟一的候選函數，算法實現如圖2所示。

圖2 Rabin指紋算法實現

（2）用于生成下標的候選函數

考慮3個候選函數：Rabin指紋算法，實現簡單且與鍵值算法聯系緊密；Unix System V中的散列函數UV5 Hash，被稱為“實際生活散列函數中的典型魔術”[5]，但對URL的處理性能不好；應用于天網搜索引擎的折疊函數Hflp[5]，被稱為處理URL的查詢速度和負載平衡效果最好的函數。下標候選函數算法實現如圖3所示。

2.3 實驗驗證

從某運營商骨干網邊界路由器的一條鏈路上采集數據，數據僅包含雙向SMTP流量，并以Tcpdump格式進行文件保存。其中郵件流量1捕獲于2009年，包含28 488封內容完全相同的郵件，已經做好標記；郵件流量2捕獲于2010年，包含郵件近100萬封，最多4 000萬個字節序列作為背景流量。實驗的目的是選取具有較優時空性能且能識別群發郵件的函數。流量1、2由于捕獲時間相隔較遠，保證內容不會發生干擾。

圖3 下標候選函數算法實現

圖4 鍵值性能

將流量1、2混合回放，首先對鍵值的惟一性進行測試。取散列表槽數M=400萬，以100萬為間隔，以N=100萬，200萬，…，4 000萬個字節序列為原始輸入，通過測度1測試Rabin函數。

鍵值性能如圖4所示，Rabin指紋算法性能穩定，實驗中始終保證為原始字節序列生成惟一的鍵值，因此可代替原始輸入保存在散列表中。

圖5 下標函數性能比較

對下標函數進行測試，分別取散列表槽數M=50、100、400、1 600(單位:萬)，以 100萬為間隔，以 N=100 萬，…，4 000萬個鍵值為輸入，通過測度2測試3個候選函數。性能對比如圖5所示。

由圖5可以看出，UV5 Hash具有絕對的優勢，在所有情況下都是最佳選擇。此外，隨著槽數減少，UV5變化不大，始終保持較好的性能。這表明，UV5表現優異而且相當穩定。槽數不變時，Rabin函數的性能在鍵值數量較少的情況下與HfIp相當；但隨著鍵值的增大，Rabin函數的性能顯著下降。

特別地，當將槽數減少到20萬時，Rabin函數查詢4 000萬鍵值用時超過20 h，已經無法使用；而UV5和Hlfp算法性能基本相當，并保持400 000鍵值/秒的處理速度。這表明UV5與Hflp均可應用于內存有限的大流量環境中，而Rabin函數不應使用。

本文結論與參考文獻[5]不同，在本文中，UV5 Hash是最優的下標散列函數，Hflp函數次之，Rabin函數不適合作下標散列函數。實驗表明，在散列表槽數較大的情況下，Hflp甚至不如Rabin函數，這個差異可能與兩者的原始輸入特點有關。

3 結束語

本文提出一種可應用于大流量環境的雙層散列算法。實驗表明，本方法實用且有效，網絡管理人員可將此算法應用于大流量環境，以減少網絡中冗余流量、過濾垃圾郵件及進行流量分析。

參考文獻

1 Zhang N,Jiang Y,Fang B X.Traffic classification-based spam filter.In:Proc of ICC’06,Istanbul,Turkey,June 2006

2 Spring N,Wetherall D.A protocol-independent technique for eliminating redundant network traffic. In:Proc of ACM SIGOCOMM,Aug 2000

3 黃文良,張尼,董玉濤.基于移動終端位置和發送內容的垃圾短信監控方案.移動通信,2008,32(13)

4 Manber U.Finding similar files in a large file system.In:Proc of USENIX Winter Technical Conference,Jan 1994

5 李曉明,鳳旺森.兩種URL散列效果很好的函數.軟件學報,2004,15(2):179～184