張智江，王志軍，張 尼

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

1 引言

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

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

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

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

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

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

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

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

2 雙層散列算法

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法選擇

2.2.1 評(píng)估測(cè)度

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

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

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

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

（2）下標(biāo)函數(shù)測(cè)度

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

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

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

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

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

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

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

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

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

2.3 實(shí)驗(yàn)驗(yàn)證

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

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

圖4 鍵值性能

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)

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 黃文良,張尼,董玉濤.基于移動(dòng)終端位置和發(fā)送內(nèi)容的垃圾短信監(jiān)控方案.移動(dòng)通信,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ù).軟件學(xué)報(bào),2004,15(2):179～184