一種高性能計算網絡下的TCP查找哈希算法

張立武，馮 寶，周建華，李 洋，茅天奇

(1.南瑞集團有限公司(國網電力科學研究院有限公司),江蘇 南京 211000； 2.國網江蘇省電力有限公司電力科學研究院，江蘇 南京 211103； 3.南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著計算機技術和電力行業的迅猛發展，智能電網與高性能計算機集群的聯系越來越密切。由于電力系統本身對數據實時性及計算性能的高要求，智能電網中的數據處理主要由計算機集群提供的高性能計算服務完成，其中的數據傳輸主要由計算機集群之間的高性能計算網絡完成，高性能計算網絡就是指能夠在集群主機之間提供極高通信性能的網絡[1]。由于通信機制越來越難設計,所以通信往往成為開發的瓶頸,如何使高性能計算機集群運行得更快、更高效一直是研究的熱點[2]。事實上，高性能計算已被公認為是繼理論科學和實驗科學之后,人類認識世界改造世界的第三大科學研究方法,是科技創新的重要手段[3]。因此這就對計算機集群的計算性能提出了更高要求。目前，高性能計算網絡在廣域網中主要依賴于TCP來實現[4]，但隨著高性能計算網絡中TCP會話數量的快速增長，傳統TCP會話的查找算法很難在查找速率和查找時所占用的計算機處理器的緩存大小之間達到平衡。TCB(傳輸控制塊)是一種用于維持每個TCP會話狀態的數據結構。一般來說，TCB的大小為280～1 300字節。在如今的高性能計算網絡中，TCP會話的數量一般可以達到一百萬個，也就是說TCB將占用280 MB～1.3 GB的儲存空間，而主流的計算機處理器的最后一級高速緩存(LLC)的規模通常為10 MB，這就使得TCB的存儲器占用空間是LLC的大小的幾十萬倍。對于這種巨大的工作量，幾乎每個沿鏈表的搜索步驟都會導致查找TCP會話時計算機的緩存不夠。已有研究[5-7]表明，TCP會話的查找時間主要是由主存儲器訪問的CPU性能決定的，而不是由指令的執行時間決定的。因此，即使只是次要的存儲器訪問也會顯著增加TCP查找的時間，也就是說，傳統的TCP查找算法中哈希表的數據結構已經不能滿足查找高性能計算網絡中大量TCP會話的要求，且會對計算機的處理器緩存造成極大負擔。為了解決這些問題，必須提出一種適合現代計算機處理器的TCP會話的哈希查找算法。

1 技術背景

哈希表是在當前TCP過程中計算機查找TCB最廣泛使用的方法。當TCP會話到達時，計算機按照哈希函數將TCP會話標識符映射為哈希值，然后使用哈希值定位哈希桶，最后在發生哈希沖突時對沖突鏈表進行搜索。只有當裝填因子較低時，哈希表才有較好的性能。在數百萬個TCP會話并行的情況下，如果裝填因子仍要保持較低水平，則TCB哈希表將變得特別大，這就會占用計算機極大的存儲空間，然而，限制哈希表大小又會大大增加發生哈希沖突的可能性，這就使哈希表的優點不再存在。

文獻[8]介紹了目前的算法會導致計算機查找TCP會話時因TCP會話過多而產生性能急劇惡化的現象，這是因為哈希表的大小與會話數量成比例增長會導致計算機占用的內存空間增加。此外，由于對TCB的訪問缺乏規律，當有大量的TCP會話需要處理時，增加計算機緩存大小并不能帶來較大的性能優化。為了改善哈希表的查找瓶頸，文獻[9-13]提出了一些優化方案來減少計算機的查找時間和內存占用，然而它們都不能適應高性能計算網絡的要求，特別是不能適應在實際系統中對高性能網絡的緩存有效使用。

近年來也有許多采用硬件來優化TCB查找的方案。文獻[14]中利用網絡會話的特點設計出了服務器專用的TCB緩存硬件。文獻[15]設計了一種復雜的函數，該函數將會話簽名和TCB位置轉換為32位代碼，存儲在專用TCB緩存硬件中。由于資源有限，上述解決方案都只能用來處理少量TCP會話，且它們的擴展成本非常高，這無法滿足高性能計算網絡中百萬數量級的TCP會話的要求。除了性能和價格這對矛盾之外，硬件解決方案還需要修改現有的網絡棧結構，這是很難實現的。

2 一種基于哈希表的TCP查找優化算法

2.1 簽名算法

文中提出了一種基于哈希查找的簽名算法，它不再使用TCP會話的4元組，即源IP地址、目的地IP地址、源端口、目的端口來生成哈希值，而是使用32位的短簽名來標記TCP會話。由于不需要將完整的TCB標識符存儲在哈希表中，而只需要存儲短簽名，哈希表的大小大大減少，查找時需要的緩存也大大減少。簽名算法的主要作用是數據壓縮，這就有可能產生匹配沖突的現象，即不同的TCP會話恰好具有相同的簽名。因此，每當在哈希表中匹配到對應的TCP會話的簽名時，應訪問相應的TCB，并比較4元組，對實際匹配的TCP會話進行確認。由于簽名匹配出錯會導致額外的存儲器訪問，低匹配出錯率是簽名算法最重要的特性。另外，簽名算法必須對每個TCP會話執行，故其計算次數不能太多。

文中采用一種較為簡單的簽名算法，對第一個TCP會話，簡單地對其4元組執行異或來獲得簽名，即計算源IP地址⊕目的地IP地址⊕源端口⊕目的端口來得到簽名，而對于之后的TCP會話，則將該TCP會話與前一個TCP會話按上述步驟得到的兩個32位數進行異或，以作為該TCP會話的短簽名。

2.2 數據結構

圖1描述了優化后的TCB查找數據結構，一般用TCP會話標識符作為哈希函數的輸入，每個哈希桶包含16個槽，每個槽為32位長。在對TCB陣列預分配時，引入參數N表示哈希表中的槽的數量。前N個會話與每個槽一一映射，剩余元素則被保留在TCB池中用于下次分配。當沖突的TCB的數量大于哈希桶中的最大的槽的數量時，這些沖突的TCB簽名將被分配到TCB池中，它們的位置與簽名一起明確地存儲在相應的沖突列表中。另外，在這種數據結構下，TCB位置并不是明確地存儲在查找表中，而是通過它們對應的槽的位置計算得出。TCB會話與槽的映射關系是將陣列中的序號為(i-1)×16+j的TCB會話映射到第i個哈希桶中的第j個槽。

圖1 優化后的哈希算法的數據結構

2.3 算法描述

(1)查找會話：如圖2所示,當接收到TCP分組時，用TCP的會話標識符計算該TCP會話的TCP簽名。從第一個槽開始向桶的末端進行搜索簽名匹配時，訪問相應的TCB，并且進一步比較完整的4元組。如果發現誤判，則繼續進行搜索。若在哈希桶中找不到匹配，則檢查相應的沖突列表，這個過程的最終返回值為相應的TCB位置或NOT FOUND。

(2)添加會話：添加會話的過程與查找會話類似，其區別在于添加會話是要在哈希桶找到一個空的槽。當在哈希桶中找到空槽時，新的會話簽名被存儲在其中，并且返回與之對應的TCB。如果在哈希桶中沒有找到空槽，則將包含會話簽名和TCB位置的新元素添加到沖突列表。

(3)刪除會話：當會話關閉時，需要清除TCB簽名。若能在表中找到匹配的TCB簽名，則可以通過將該槽清零來刪除該會話。如果在沖突列表中找到該TCB會話簽名，則首先將該TCB放回到TCB池中，然后再刪除沖突列表中的TCB。

圖2 查找會話的過程

文中提出的哈希表的結構可等效為一種兩級哈希表結構，其中第一級表含有N個哈希桶，每個第二級表含有2b個哈希桶。在采用優化后的基于哈希算法的TCP查找算法時，采取簽名算法來生成作為哈希索引的b個比特的TCB簽名的第二級哈希函數。然而，在優化算法下哈希索引并不用于定位哈希桶，而是通過記錄哈希索引來標識對象，這能很好地解決與開放尋址法的沖突。因此，在優化后的算法中，每個桶的TCB簽名的誤判率等于第二級哈希表的沖突率。

2.3.1 裝填因子

哈希表的性能很大程度上取決于哈希表的裝填因子。文中研究的優化后的TCB查找算法等效哈希表見圖3中表B，兩者的裝填因子相等。圖中N表示哈希表中的哈希桶數，b表示TCB簽名的32位位數。

當哈希表均勻裝填了M個TCP會話時，裝填因子可以計算為(M/N)×(1/2b)。在該優化算法中，設定b=32，且一般M/N不超過16，則有：

(M/N)×(1/2b)≤3.72×10-9

(1)

由此可見，優化后算法實現了一種具有極地裝填因子的哈希表結構，這種結構大大減少了哈希表占用的存儲空間。例如，當有1 000 000個TCP會話到達且裝填因子為3.72×10-9時，傳統的哈希表在64位系統中需要占用2 000 TB的容量，而優化后的算法僅僅需要占用4.5 MB的容量。

圖3 優化后哈希算法的識別率和裝填因子

2.3.2 誤判率

如前所述，優化后算法中每個哈希桶的誤判率等于圖3中表A中第二級哈希表的沖突率。表A中每個第二級哈希表含有n=232個桶，包含在該表中TCP會話的簽名的平均數量不大于16。假設在第二級哈希表中均勻存儲了k個TCP會話簽名，并且定義Ek為k個會話在表中不沖突的事件，則其概率為：

(2)

1-k(k-1)/2n

(3)

根據概率知識可知，至少兩個會話沖突的概率等于1減去沒有會話沖突的概率，從而在優化后的算法中每個哈希桶的預期誤判率為：

1-Pr{Ek}≈k(k-1)/2n≤2.79×10-8

(4)

也就是說，與傳統的哈希表相比，優化后的哈希算法具有很低的誤判率和裝填因子，且占用了更少的計算機內存空間。

3 仿真結果與分析

3.1 單核性能

在開源TCP/IP協議棧中，文中使用優化后的TCB查找算法代替了原來的TCP查找協議，并對查找性能進行了評估。

生成了三種不同大小的跟蹤文件，如表1所示。

表1 跟蹤文件的特性

針對三種不同的跟蹤文件，將優化后的算法與原來的算法進行了對比。優化后的哈希算法的平均查找時間如圖4所示，其中原始算法(N桶-M寄存器)表示以N個區段占用了M個存儲器空間的原始算法。

仿真結果表明，原始算法的性能受TCP會話數的變化而顯著變化，而優化后算法的表現非常穩定，更加可靠。

3.2 并行性能

不同哈希表大小的優化算法和傳統TCP查找算法的性能對比如圖5所示。

圖4 TCB查找性能

圖5 優化算法與原始TCP查找算法的性能對比

設置150萬桶為閾值，在此情況下采用文中簽名算法，僅有11 257個TCP會話的簽名發生沖突，另一方面，在使用傳統算法時，系統性能會隨著哈希表大小的增加而增加，直到達到閾值。而在10 Gbps的以太網下，采用150萬個哈希桶(約12 MB)的傳統算法的端口吞吐量不能高于14.88 Mpps，而優化后的算法能在同等條件下用六個內核實現15.2 Mpps的吞吐量，在七個內核上實現16.5 Mpps的吞吐量，且其查找表和沖突列表只占用7.5 MB的內存空間。顯然，優化后的哈希表查找算法的系統性能更加優越。

4 結束語

哈希表是目前計算機查找TCP會話中最廣泛使用的方法，但其并不能很好地處理國家電網中廣域高性能計算網絡中大量的TCP會話，且會導致計算機查找TCP會話的時間和占用的內存較大。為了解決這一問題，對傳統的哈希查找算法進行了優化。首先設計了一種簽名算法用查找表中的較短的會話簽名來替換完整的TCB標識符，減少了計算機的內存占用。其次使用順序訪問替代隨機訪問，以增加計算機的存儲器訪問效率，降低了誤判率。仿真結果表明，優化后的哈希查找算法的系統性能更加優越。

參考文獻:

[1] 劉 穎,陳 煜，林 林，等.高性能計算集群中的網絡技術研究與實踐[J].中國水利水電科學研究院學報,2016,14(2):90-95.

[2] 岳菲菲,王海軍,王 新,等.高性能計算通信機制分析與研究[J].計算機工程與科學,2009,31(A1):27-30.

[3] 李根國,桂亞東,劉 欣.淺談高性能計算的地位及應用[J].計算機應用與軟件,2006,23(9):3-4.

[4] 熊 兵,李 峰,姜臘林,等.面向高速網絡連接記錄管理的高效哈希表[J].華中科技大學學報:自然科學版,2011,39(2):19-22.

[5] CLARK D D,JACOBSON V,ROMKEY J,et al.An analysis of TCP processing overhead[J].IEEE Communications Magazine,2002,40(5):94-101.

[6] CHIANG M L,LI Y C.LyraNET:a zero-copy TCP/IP protocol stack for embedded systems[J].Real-Time Systems,2006,34(1):5-18.

[7] LI Z,MAKINENI S,ILLIKKAL R,et al.Efficient caching techniques for server network acceleration[C]//Advanced networking & communications hardware.[s.l.]:[s.n.],2004.

[8] MAKINENI S,BHUYAN L.TCP/IP cache characterization in commercial server workloads[C]//Proceedings of seventh workshop on computer architecture evaluation using commercial workloads.[s.l.]:[s.n.],2004.

[9] 馬如林,蔣 華,張慶霞.一種哈希表快速查找的改進方法[J].計算機工程與科學,2008,30(9):66-68.

[10] 王 果,徐仁佐.結合哈希過濾的一種改進多連接查詢優化算法[J].計算機工程,2004,30(7):57-59.

[11] SONG H,DHARMAPURIKAR S,TURNER J,et al.Fast hash table lookup using extended bloom filter:an aid to network processing[C]//Proceedings of the 2005 conference on applications,technologies,architectures,and protocols for computer communications.New York,NY,USA:ACM,2005:181-192.

[12] KUMAR S,CROWLEY P.Segmented hash:an efficient hash table implementation for high performance networking subsystems[C]//Proceedings of 2005 ACM symposium on architecture for networking and communications systems.New York,NY,USA:ACM,2005:91-103.

[13] HASAN J,CADAMBI S,JAKKULA V,et al.Chisel:a storage efficient,collision-free hash-based network processing architecture[C]//Proceedings of the 33rd annual international symposium on computer architecture.Washington,DC,USA:IEEE Computer Society,2006:203-215.

[14] LIAO G,BHUYAN L N,WU W,et al.A new TCB cache to efficiently manage TCP sessions for web servers[C]//ACM/IEEE symposium on architectures for networking and communications systems,New York,NY,USA:ACM,2010.

[15] PONG F.Fast and robust TCP session lookup by digest hash[C]//Proceedings of the 12rd IEEE international conference on parallel and distributed systems.[s.l.]:IEEE,2006.