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

張智江，王志軍，張 尼

（中國聯(lián)合網(wǎng)絡通信有限公司 北京 100033）

1 引言

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

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

直觀、常識性的做法是對大流量數(shù)據(jù)實施散列算法，并將產(chǎn)生的散列值集合存入數(shù)據(jù)存儲結(jié)構(gòu)，便于后續(xù)操作。大流量環(huán)境下的實時處理系統(tǒng)是否有效、實用，關(guān)鍵就在于如何設計散列算法和對應的數(shù)據(jù)存儲結(jié)構(gòu)以滿足系統(tǒng)的時間和空間性能。

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

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

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

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

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

2 雙層散列算法

2.1 算法思路與數(shù)據(jù)結(jié)構(gòu)設計

下面以互聯(lián)網(wǎng)垃圾郵件過濾為例，具體介紹雙層散列算法。

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

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

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

設雙層散列算法中的鍵值函數(shù)為Unique_hash，下標函數(shù)為Uniform_hash，hi為原始輸入Bi在數(shù)據(jù)結(jié)構(gòu)中的存儲地址，因此有：

為節(jié)省空間，在數(shù)據(jù)結(jié)構(gòu)中不存儲Bi，而是存儲可惟一表征 Bi的指紋值 fi，有：

雙層散列算法的關(guān)鍵在于選取合適的鍵值函數(shù)及下標函數(shù)，以滿足實時系統(tǒng)時、空性能。

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

圖1 雙層散列函數(shù)對應的數(shù)據(jù)結(jié)構(gòu)

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

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

2.2 算法選擇

2.2.1 評估測度

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

（1）鍵值函數(shù)測度

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

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

（2）下標函數(shù)測度

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

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

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

2.2.2 待評估的散列函數(shù)

（1）用于生成鍵值的候選函數(shù)

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

圖2 Rabin指紋算法實現(xiàn)

（2）用于生成下標的候選函數(shù)

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

2.3 實驗驗證

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

圖3 下標候選函數(shù)算法實現(xiàn)

圖4 鍵值性能

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

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

圖5 下標函數(shù)性能比較

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

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

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

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

3 結(jié)束語

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

參考文獻

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 黃文良,張尼,董玉濤.基于移動終端位置和發(fā)送內(nèi)容的垃圾短信監(jiān)控方案.移動通信,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散列效果很好的函數(shù).軟件學報,2004,15(2):179～184