改進(jìn)的一致性哈希算法及應(yīng)用

方 堃武小年,2

（1.桂林電子科技大學(xué)信息與通信學(xué)院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

改進(jìn)的一致性哈希算法及應(yīng)用

方 堃1武小年1,2

（1.桂林電子科技大學(xué)信息與通信學(xué)院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

針對分布式入侵檢測中的數(shù)據(jù)分割問題，給出一種改進(jìn)的一致性哈希算法。該算法針對采集的數(shù)據(jù)包，通過TCP流重組建立TCP數(shù)據(jù)鏈，保證數(shù)據(jù)流的完整性；再通過結(jié)點(diǎn)的分組對一致性哈希算法進(jìn)行改進(jìn)，并實(shí)現(xiàn)組間和組內(nèi)的數(shù)據(jù)分配，減少虛擬結(jié)點(diǎn)數(shù)量；對結(jié)點(diǎn)的負(fù)載均衡檢測和調(diào)整策略，改善了系統(tǒng)的負(fù)載均衡性。仿真測試結(jié)果表明該算法具有較好的負(fù)載均衡性。

分布式入侵檢測；TCP流重組；一致性哈希算法；負(fù)載均衡

1 引言

隨著網(wǎng)絡(luò)帶寬的不斷增大，網(wǎng)絡(luò)速度的不斷提高，傳統(tǒng)的基于單主機(jī)的入侵檢測系統(tǒng)已經(jīng)很難滿足大規(guī)模網(wǎng)絡(luò)高效檢測的需求。分布式入侵檢測系統(tǒng)是解決高速網(wǎng)絡(luò)環(huán)境下入侵檢測效率低下問題的解決方案之一。現(xiàn)今，提升分布式入侵檢測系統(tǒng)的性能面對許多難題。首先，數(shù)據(jù)的完整性對入侵檢測系統(tǒng)檢測準(zhǔn)確率的提升至關(guān)重要，因此如何保持?jǐn)?shù)據(jù)的完整性是對分布式系統(tǒng)中數(shù)據(jù)分割算法提出的重大挑戰(zhàn)；其次，分布式系統(tǒng)中可能會產(chǎn)生添加或刪除結(jié)點(diǎn)的情況，此時(shí)若采用傳統(tǒng)求模運(yùn)算的哈希函數(shù)，則必須重新分配數(shù)據(jù)，然而在入侵檢測中有時(shí)需要與歷史信息結(jié)合來準(zhǔn)確判斷出攻擊行為，此時(shí)將產(chǎn)生大量的數(shù)據(jù)遷移，降低整個(gè)系統(tǒng)性能；最后，均衡的保持每個(gè)結(jié)點(diǎn)的負(fù)載，使各個(gè)結(jié)點(diǎn)發(fā)揮出最大性能，也是提升分布式入侵檢測系統(tǒng)的關(guān)鍵。因此，實(shí)現(xiàn)分布式入侵檢測的關(guān)鍵在于數(shù)據(jù)分割算法。

一個(gè)良好的面向分布式入侵檢測的數(shù)據(jù)分割算法應(yīng)當(dāng)滿足以下三個(gè)特征：（1）有效性，即每個(gè)數(shù)據(jù)分片應(yīng)能準(zhǔn)確檢測出攻擊行為；（2）均衡性，即每一個(gè)分片應(yīng)使各分布式結(jié)點(diǎn)負(fù)載均衡；（3）簡單性，即分割算法簡單、高效。文獻(xiàn)[1]提出動態(tài)最小負(fù)載優(yōu)先算法，將數(shù)據(jù)優(yōu)先分配給負(fù)載最輕的結(jié)點(diǎn)。文獻(xiàn)[2]中加入了數(shù)據(jù)預(yù)過濾和緩沖聚類，將檢測結(jié)點(diǎn)的一部分功能轉(zhuǎn)移到分割模塊中，降低了后續(xù)模塊的處理壓力。文獻(xiàn)[3]提出的隨意分割集中學(xué)習(xí)的方法，此種算法滿足了分割算法的簡單性和負(fù)載均衡性，但后續(xù)的檢測較為復(fù)雜，不利于實(shí)時(shí)網(wǎng)絡(luò)入侵檢測的實(shí)施。文獻(xiàn)[4]綜合考慮了影響各結(jié)點(diǎn)負(fù)載均衡性的因素，優(yōu)先將數(shù)據(jù)分配給負(fù)載最輕的結(jié)點(diǎn)，實(shí)現(xiàn)了負(fù)載均衡性，然而并沒有考慮到數(shù)據(jù)包之間的聯(lián)系，破壞了數(shù)據(jù)的完整性。文獻(xiàn)[5]提出基于流粒度的負(fù)載均衡算法，以會話流為單位分發(fā)數(shù)據(jù)包，保持?jǐn)?shù)據(jù)的完整性。

本文基于一致性哈希算法，給出一種改進(jìn)的算法，并用于分布式入侵檢測的數(shù)據(jù)分割，該算法針對采集的數(shù)據(jù)包，通過維護(hù)TCP連接記錄并重組TCP數(shù)據(jù)鏈，保持?jǐn)?shù)據(jù)流的完整性；再通過改進(jìn)的一致性哈希算法，減小結(jié)點(diǎn)間數(shù)據(jù)的遷移量，同時(shí)通過負(fù)載均衡策略維持結(jié)點(diǎn)間的負(fù)載均衡。

2 改進(jìn)的一致性哈希數(shù)據(jù)分割方法

在分布式入侵檢測中，數(shù)據(jù)分割的優(yōu)劣一直是制約分布式入侵檢測系統(tǒng)性能的瓶頸。首先，若以單一數(shù)據(jù)包為最小檢測單元，不關(guān)心數(shù)據(jù)包的狀態(tài)信息，將相互關(guān)聯(lián)的數(shù)據(jù)包分配到結(jié)點(diǎn)，會導(dǎo)致許多攻擊行為無法檢測出；其次，為了準(zhǔn)確檢測出攻擊行為，有時(shí)還需獲取歷史告警記錄。若采用傳統(tǒng)哈希函數(shù)，當(dāng)分布式系統(tǒng)中有結(jié)點(diǎn)的添加和刪除時(shí)，將導(dǎo)致整個(gè)哈希函數(shù)重新分布，為了保證歷史記錄的準(zhǔn)確性，需要遷移大量的歷史告警信息，為系統(tǒng)增加負(fù)擔(dān)；最后，若分割算法不能實(shí)現(xiàn)負(fù)載均衡，則無法充分發(fā)揮各結(jié)點(diǎn)的計(jì)算性能，導(dǎo)致系統(tǒng)整體陷入瓶頸。

針對以上問題，本文首先采用TCP流重組技術(shù)，以會話流為最小單元保持?jǐn)?shù)據(jù)的完整性。TCP協(xié)議在網(wǎng)絡(luò)中進(jìn)行傳輸?shù)臅r(shí)候，由于經(jīng)過不同的路由，在到達(dá)的時(shí)間與順序上會產(chǎn)生混亂，因此要提取出數(shù)據(jù)流中的TCP包進(jìn)行重組才能還原成一個(gè)完整的數(shù)據(jù)鏈。為保證將海量的網(wǎng)絡(luò)數(shù)據(jù)分割成一個(gè)個(gè)完整的數(shù)據(jù)子集，在數(shù)據(jù)重組時(shí)，計(jì)算數(shù)據(jù)包的哈希值。一條TCP連接可以由四元組<源IP地址，源端口，目的IP地址，目的端口>唯一確定，因此，可以通過哈希函數(shù)計(jì)算四元組的哈希值，作為此連接的唯一標(biāo)識，結(jié)合報(bào)文中的連接序號就可以實(shí)現(xiàn)正確的 TCP流重組。針對重組形成的一個(gè)個(gè)TCP流鏈，進(jìn)一步采用改進(jìn)的一致性哈希算法，將不同的TCP流鏈分配到不同的結(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)的分割。

2.1改進(jìn)的一致性哈希算法

一致性哈希算法是實(shí)際結(jié)點(diǎn)對應(yīng)的虛擬結(jié)點(diǎn)映射到0～232的環(huán)上，數(shù)據(jù)求取哈希值后同樣映射到該環(huán)上，并按順時(shí)針方向查找與之最接近的虛擬結(jié)點(diǎn)，通過虛擬結(jié)點(diǎn)與實(shí)際結(jié)點(diǎn)之間的映射關(guān)系將數(shù)據(jù)分布到真實(shí)結(jié)點(diǎn)。當(dāng)有新結(jié)點(diǎn)加入或舊結(jié)點(diǎn)退出時(shí)，僅影響順時(shí)針方向的下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)，減少數(shù)據(jù)的遷移量。

然而傳統(tǒng)一致性哈希算法主要針對同構(gòu)主機(jī)，當(dāng)兩個(gè)結(jié)點(diǎn)的性能相差過大時(shí)，需要引入大量的虛擬結(jié)點(diǎn)，從而導(dǎo)致虛擬結(jié)點(diǎn)需要的存儲空間增加和查找速度的降低。假設(shè)結(jié)點(diǎn)i的計(jì)算能力為 ai，由文獻(xiàn)[6]得知，每臺主機(jī)引入的虛擬設(shè)備為klog|N|，其中k為常數(shù)，N為設(shè)備總數(shù)。若結(jié)點(diǎn)i的計(jì)算能力為ai，計(jì)算能力最低結(jié)點(diǎn)的計(jì)算能力為amin，則傳統(tǒng)一致性哈希函數(shù)所需要分配的虛擬結(jié)點(diǎn)個(gè)數(shù)為:

當(dāng)ai/amin的值很大時(shí)，將引入大量的虛擬結(jié)點(diǎn)，降低整個(gè)一致性哈希函數(shù)性能。

本文改進(jìn)算法中，將計(jì)算能力相差不大的結(jié)點(diǎn)分為一組，組間按照各組結(jié)點(diǎn)計(jì)算能力的大小比例分割整個(gè)哈希值的值域，數(shù)據(jù)先分配到不同的組中，在組內(nèi)采用一致性哈希算法，再將數(shù)據(jù)分配到不同的結(jié)點(diǎn)上。由于組內(nèi)結(jié)點(diǎn)計(jì)算能力相差不大，因此可以采用均勻分配的方式。采用此方法可以解決異構(gòu)主機(jī)引入虛擬結(jié)點(diǎn)過多的問題。假設(shè)結(jié)點(diǎn)共分為 p組，組i中有ni個(gè)結(jié)點(diǎn)，由于結(jié)點(diǎn)計(jì)算能力相差不大，則每組中引入的虛擬結(jié)點(diǎn)總數(shù)為niklog|N|，整個(gè)分割系統(tǒng)引入總結(jié)點(diǎn)數(shù)為：

當(dāng)結(jié)點(diǎn)計(jì)算能力相差很大時(shí)，式（1）的值遠(yuǎn)遠(yuǎn)大于式（2）的值。

2.2負(fù)載均衡策略

在傳統(tǒng)一致性哈希算法中，數(shù)據(jù)的分配是由概率決定的，因此在容易產(chǎn)生負(fù)載不均衡。針對該問題，本文基于上述的改進(jìn)一致性哈希算法，進(jìn)一步進(jìn)行負(fù)載均衡調(diào)整。系統(tǒng)周期性進(jìn)行結(jié)點(diǎn)負(fù)載情況檢查，并根據(jù)不同組結(jié)點(diǎn)數(shù)據(jù)處理能力不同，設(shè)定不同的負(fù)載均衡調(diào)整門限，當(dāng)負(fù)載不均衡程度超過門限時(shí)，進(jìn)行結(jié)點(diǎn)的負(fù)載均衡調(diào)整。

假設(shè)組i的權(quán)重為ci，表示結(jié)點(diǎn)的計(jì)算能力，計(jì)算能力越強(qiáng)的組ci的值越大，計(jì)算能力最低的一組權(quán)重為cmin，其中p為結(jié)點(diǎn)組的個(gè)數(shù)。組i負(fù)載均衡調(diào)整門限為Thresholdi,計(jì)算能力最低一組的負(fù)載均衡調(diào)整門限為Thresholdmin則有：

設(shè)組內(nèi)負(fù)載最輕結(jié)點(diǎn)負(fù)載為 Lmin，負(fù)載最重結(jié)點(diǎn)負(fù)載為Lmax，負(fù)載居中結(jié)點(diǎn)為 Lmid，若類 i中Lmax-Lmid>Thresholdi，則進(jìn)行負(fù)載過重調(diào)整，減少 Lmax對應(yīng)結(jié)點(diǎn)的虛擬結(jié)點(diǎn)，同時(shí)將分配到該結(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生的 T時(shí)間內(nèi)的告警信息遷移到順時(shí)針方向的下一個(gè)結(jié)點(diǎn)，并清空該虛擬結(jié)點(diǎn)的告警信息。同理，若組i中Lmid-Lmin>Thresholdi，進(jìn)行負(fù)載過輕調(diào)整，增加Lmin對應(yīng)的虛擬結(jié)點(diǎn)個(gè)數(shù)，同時(shí)將下一結(jié)點(diǎn)中的T時(shí)間內(nèi)部分告警信息遷移到新的結(jié)點(diǎn)中，并清空舊節(jié)中遷移部分的告警信息。

負(fù)載均衡調(diào)整將有效提升一致性哈希算法負(fù)載均衡性。使調(diào)整后的結(jié)點(diǎn)負(fù)載接近負(fù)載中間結(jié)點(diǎn)。同時(shí)，檢測攻擊行為并不需要太長時(shí)間的歷史記錄，因此結(jié)點(diǎn)告警信息的遷移量很小，并不會給系統(tǒng)增添過重的負(fù)擔(dān)。

3 實(shí)驗(yàn)仿真

3.1實(shí)驗(yàn)環(huán)境

本文采用C語言實(shí)現(xiàn)了網(wǎng)絡(luò)數(shù)據(jù)抓包、TCP流重組，以及分組一致性哈希算法和負(fù)載均衡調(diào)整算法，并對該算法進(jìn)行了測試。仿真測試主要測試算法改進(jìn)后的負(fù)載均衡情況。仿真測試網(wǎng)絡(luò)環(huán)境為實(shí)驗(yàn)室局域網(wǎng)通過 100M 交換機(jī)連接到校園網(wǎng)，并連接互聯(lián)網(wǎng)。模擬設(shè)置了15個(gè)結(jié)點(diǎn)，分為3組，每組 5個(gè)結(jié)點(diǎn)；各組中結(jié)點(diǎn)計(jì)算能力分別分布在1000,3000,6000附近區(qū)間；設(shè)置計(jì)算能力最低的一組的虛擬結(jié)點(diǎn)數(shù)為20。

3.2實(shí)驗(yàn)結(jié)果與分析

3.2.1組間負(fù)載均衡實(shí)驗(yàn)

由于各組分配的數(shù)據(jù)量與各組計(jì)算能力成正比，若各組負(fù)載均衡則該組中處理數(shù)據(jù)的總量比該組計(jì)算能力的值應(yīng)大致相同。這個(gè)值定義為組間相對數(shù)據(jù)量。各組組間相對數(shù)據(jù)量差值越小，說明組間負(fù)載均衡性越好。均方誤差能較好的反應(yīng)數(shù)據(jù)之間的離散程度，均方誤差越小說明數(shù)據(jù)之間的離散程度越低。因此本文采用組間相對數(shù)據(jù)量的均方誤差作為評價(jià)組間負(fù)載均衡的評價(jià)指標(biāo)，并將本文改進(jìn)算法與傳統(tǒng)一致性哈希函數(shù)進(jìn)行對比測試。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1　組間相對數(shù)據(jù)量均方誤差對比圖

由圖 1可以看出，本文改進(jìn)算法中各組組間數(shù)據(jù)量均方誤差遠(yuǎn)小于傳統(tǒng)一致性哈希算法，其原因在于本文算法將數(shù)據(jù)按照相對權(quán)重值的比例均勻分布到各組結(jié)點(diǎn)，組間負(fù)載性能良好，充分發(fā)揮結(jié)點(diǎn)的計(jì)算能力。

3.2.2組內(nèi)負(fù)載均衡實(shí)驗(yàn)

本實(shí)驗(yàn)將本文算法與傳統(tǒng)哈希分割算法、傳統(tǒng)一致性哈希算法進(jìn)行對比測試。對比的兩種算法將計(jì)算能力相同的結(jié)點(diǎn)視為一組，同時(shí)取第二組結(jié)點(diǎn)在不同的數(shù)據(jù)量下進(jìn)行負(fù)載均衡性測試。實(shí)驗(yàn)引入文獻(xiàn)[7]中提出的負(fù)載均衡度作為評價(jià)指標(biāo)。負(fù)載均衡度越小，說明負(fù)載均衡性能越好。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2　負(fù)載均衡度對比圖

由上圖可以觀察到，由于傳統(tǒng)算法沒有加入動態(tài)調(diào)整策略，當(dāng)局部流量增大時(shí)，將導(dǎo)致嚴(yán)重的負(fù)載不均衡現(xiàn)象，此種情況需要經(jīng)過較長時(shí)間的調(diào)整，才能略有改善。本文算法進(jìn)行負(fù)載均衡調(diào)整后，負(fù)載均衡性能良好，且波動范圍很小，基本實(shí)現(xiàn)組內(nèi)各結(jié)點(diǎn)負(fù)載均衡。

4 結(jié)束語

近年來網(wǎng)絡(luò)安全形勢日趨嚴(yán)峻，分布式入侵檢測技術(shù)成為維護(hù)網(wǎng)絡(luò)安全的有效手段，分割算法又是影響分布式入侵檢測系統(tǒng)性能的關(guān)鍵因素。本文給出改進(jìn)的一致性哈希算法，并應(yīng)用于分布式入侵檢測中進(jìn)行數(shù)據(jù)分割。算法基于對采集數(shù)據(jù)的TCP流重組，并采用分組方法進(jìn)行結(jié)點(diǎn)分組并實(shí)現(xiàn)組間和組內(nèi)的數(shù)據(jù)分配，減少虛擬結(jié)點(diǎn)數(shù)量，并通過對結(jié)點(diǎn)的負(fù)載均衡檢測和調(diào)整，改善了系統(tǒng)的負(fù)載均衡性。

[1] 李信滿,趙大哲,趙宏,等.基于應(yīng)用的高速網(wǎng)絡(luò)入侵檢測系統(tǒng)研究[J].通信學(xué)報(bào),2002,23(9):1-7.

[2] Xinidis K,Charitakis I,Antonatos S, et al. An active splitter architecture for intrusion detection and prevention[J]. Dependable and Secure Computing, IEEE Transactions on,2006, 3(1): 31-44.

[3] 劉衍珩,田大新,余雪崗,等.基于分布式學(xué)習(xí)的大規(guī)模網(wǎng)絡(luò)入侵檢測算法[J].軟件學(xué)報(bào),2008,19(4): 993-1003.

[4] Jiang W, Song H, Dai Y. Real-time intrusion detection for high-speed networks[J].Computers & security,2005,24(4): 287-294.

[5] 高明.高速網(wǎng)絡(luò)入侵檢測負(fù)載均衡機(jī)制研究[D].武漢:華中科技大學(xué),2009.

[6] Karger D,Lehman E, Leighton T, et al. Consistent hashing and random trees:Distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM,1997: 654-663.

[7] 陳一驕,盧錫城,時(shí)向泉,等.一種面向會話的自適應(yīng)負(fù)載均衡算法[J].軟件學(xué)報(bào),2008,19(7):1828-1836.

Improved consistent hash algorithm and application

Aiming at data segmentation problem in distributed intrusion detection, this paper proposes an improved consistent hash algorithm to solve this problem. The algorithm uses TCP stream reassembly technology to rebuild TCP links to ensure data integrity; then divided nodes into different group to improve the consistent hash algorithm. Through the improved consistent hash algorithm, the data can be divided in node and the number of required virtual node is reduced; Load balancing detection of node and adjustment strategy to improve the load balance of the system. The simulation results show that the algorithm has better load balance.

Distributed Intrusion Detection;TCP stream reassembly;Consistent hash;Load balancing

TP393

A

1008-1151(2015)04-0005-03

2015-02-10

廣西自然科學(xué)基金(2012GXNSFAA053224)和廣西無線寬帶通信與信號處理重點(diǎn)實(shí)驗(yàn)室2014年開放基金項(xiàng)目(GXKL0614110)資助。

方堃（1990-）男，湖北武漢人，桂林電子科技大學(xué)信息與通信學(xué)院碩士研究生，研究方向?yàn)樾畔踩?/p>

武小年（1972-），男，湖北監(jiān)利人，桂林電子科技大學(xué)副教授，研究方向?yàn)樾畔踩植际接?jì)算。