改進的一致性哈希算法及應用

方 堃武小年,2

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004）

改進的一致性哈希算法及應用

方 堃1武小年1,2

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004）

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

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

1 引言

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

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

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

2 改進的一致性哈希數據分割方法

在分布式入侵檢測中，數據分割的優劣一直是制約分布式入侵檢測系統性能的瓶頸。首先，若以單一數據包為最小檢測單元，不關心數據包的狀態信息，將相互關聯的數據包分配到結點，會導致許多攻擊行為無法檢測出；其次，為了準確檢測出攻擊行為，有時還需獲取歷史告警記錄。若采用傳統哈希函數，當分布式系統中有結點的添加和刪除時，將導致整個哈希函數重新分布，為了保證歷史記錄的準確性，需要遷移大量的歷史告警信息，為系統增加負擔；最后，若分割算法不能實現負載均衡，則無法充分發揮各結點的計算性能，導致系統整體陷入瓶頸。

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

2.1改進的一致性哈希算法

一致性哈希算法是實際結點對應的虛擬結點映射到0～232的環上，數據求取哈希值后同樣映射到該環上，并按順時針方向查找與之最接近的虛擬結點，通過虛擬結點與實際結點之間的映射關系將數據分布到真實結點。當有新結點加入或舊結點退出時，僅影響順時針方向的下一個結點的數據，減少數據的遷移量。

然而傳統一致性哈希算法主要針對同構主機，當兩個結點的性能相差過大時，需要引入大量的虛擬結點，從而導致虛擬結點需要的存儲空間增加和查找速度的降低。假設結點i的計算能力為 ai，由文獻[6]得知，每臺主機引入的虛擬設備為klog|N|，其中k為常數，N為設備總數。若結點i的計算能力為ai，計算能力最低結點的計算能力為amin，則傳統一致性哈希函數所需要分配的虛擬結點個數為:

當ai/amin的值很大時，將引入大量的虛擬結點，降低整個一致性哈希函數性能。

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

當結點計算能力相差很大時，式（1）的值遠遠大于式（2）的值。

2.2負載均衡策略

在傳統一致性哈希算法中，數據的分配是由概率決定的，因此在容易產生負載不均衡。針對該問題，本文基于上述的改進一致性哈希算法，進一步進行負載均衡調整。系統周期性進行結點負載情況檢查，并根據不同組結點數據處理能力不同，設定不同的負載均衡調整門限，當負載不均衡程度超過門限時，進行結點的負載均衡調整。

假設組i的權重為ci，表示結點的計算能力，計算能力越強的組ci的值越大，計算能力最低的一組權重為cmin，其中p為結點組的個數。組i負載均衡調整門限為Thresholdi,計算能力最低一組的負載均衡調整門限為Thresholdmin則有：

設組內負載最輕結點負載為 Lmin，負載最重結點負載為Lmax，負載居中結點為 Lmid，若類 i中Lmax-Lmid>Thresholdi，則進行負載過重調整，減少 Lmax對應結點的虛擬結點，同時將分配到該結點的數據產生的 T時間內的告警信息遷移到順時針方向的下一個結點，并清空該虛擬結點的告警信息。同理，若組i中Lmid-Lmin>Thresholdi，進行負載過輕調整，增加Lmin對應的虛擬結點個數，同時將下一結點中的T時間內部分告警信息遷移到新的結點中，并清空舊節中遷移部分的告警信息。

負載均衡調整將有效提升一致性哈希算法負載均衡性。使調整后的結點負載接近負載中間結點。同時，檢測攻擊行為并不需要太長時間的歷史記錄，因此結點告警信息的遷移量很小，并不會給系統增添過重的負擔。

3 實驗仿真

3.1實驗環境

本文采用C語言實現了網絡數據抓包、TCP流重組，以及分組一致性哈希算法和負載均衡調整算法，并對該算法進行了測試。仿真測試主要測試算法改進后的負載均衡情況。仿真測試網絡環境為實驗室局域網通過 100M 交換機連接到校園網，并連接互聯網。模擬設置了15個結點，分為3組，每組 5個結點；各組中結點計算能力分別分布在1000,3000,6000附近區間；設置計算能力最低的一組的虛擬結點數為20。

3.2實驗結果與分析

3.2.1組間負載均衡實驗

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

圖1　組間相對數據量均方誤差對比圖

由圖 1可以看出，本文改進算法中各組組間數據量均方誤差遠小于傳統一致性哈希算法，其原因在于本文算法將數據按照相對權重值的比例均勻分布到各組結點，組間負載性能良好，充分發揮結點的計算能力。

3.2.2組內負載均衡實驗

本實驗將本文算法與傳統哈希分割算法、傳統一致性哈希算法進行對比測試。對比的兩種算法將計算能力相同的結點視為一組，同時取第二組結點在不同的數據量下進行負載均衡性測試。實驗引入文獻[7]中提出的負載均衡度作為評價指標。負載均衡度越小，說明負載均衡性能越好。實驗結果如圖2所示。

圖2　負載均衡度對比圖

由上圖可以觀察到，由于傳統算法沒有加入動態調整策略，當局部流量增大時，將導致嚴重的負載不均衡現象，此種情況需要經過較長時間的調整，才能略有改善。本文算法進行負載均衡調整后，負載均衡性能良好，且波動范圍很小，基本實現組內各結點負載均衡。

4 結束語

近年來網絡安全形勢日趨嚴峻，分布式入侵檢測技術成為維護網絡安全的有效手段，分割算法又是影響分布式入侵檢測系統性能的關鍵因素。本文給出改進的一致性哈希算法，并應用于分布式入侵檢測中進行數據分割。算法基于對采集數據的TCP流重組，并采用分組方法進行結點分組并實現組間和組內的數據分配，減少虛擬結點數量，并通過對結點的負載均衡檢測和調整，改善了系統的負載均衡性。

[1] 李信滿,趙大哲,趙宏,等.基于應用的高速網絡入侵檢測系統研究[J].通信學報,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] 劉衍珩,田大新,余雪崗,等.基于分布式學習的大規模網絡入侵檢測算法[J].軟件學報,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] 高明.高速網絡入侵檢測負載均衡機制研究[D].武漢:華中科技大學,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] 陳一驕,盧錫城,時向泉,等.一種面向會話的自適應負載均衡算法[J].軟件學報,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

廣西自然科學基金(2012GXNSFAA053224)和廣西無線寬帶通信與信號處理重點實驗室2014年開放基金項目(GXKL0614110)資助。

方堃（1990-）男，湖北武漢人，桂林電子科技大學信息與通信學院碩士研究生，研究方向為信息安全。

武小年（1972-），男，湖北監利人，桂林電子科技大學副教授，研究方向為信息安全，分布式計算。