一種高性能計算網(wǎng)絡(luò)下的TCP查找哈希算法

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

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

0 引 言

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

1 技術(shù)背景

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

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

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

2 一種基于哈希表的TCP查找優(yōu)化算法

2.1 簽名算法

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

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

2.2 數(shù)據(jù)結(jié)構(gòu)

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

圖1 優(yōu)化后的哈希算法的數(shù)據(jù)結(jié)構(gòu)

2.3 算法描述

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

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

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

圖2 查找會話的過程

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

2.3.1 裝填因子

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

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

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

(1)

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

圖3 優(yōu)化后哈希算法的識別率和裝填因子

2.3.2 誤判率

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

(2)

1-k(k-1)/2n

(3)

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

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

(4)

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

3 仿真結(jié)果與分析

3.1 單核性能

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

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

表1 跟蹤文件的特性

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

仿真結(jié)果表明，原始算法的性能受TCP會話數(shù)的變化而顯著變化，而優(yōu)化后算法的表現(xiàn)非常穩(wěn)定，更加可靠。

3.2 并行性能

不同哈希表大小的優(yōu)化算法和傳統(tǒng)TCP查找算法的性能對比如圖5所示。

圖4 TCB查找性能

圖5 優(yōu)化算法與原始TCP查找算法的性能對比

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

4 結(jié)束語

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

參考文獻:

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

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

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

[4] 熊 兵,李 峰,姜臘林,等.面向高速網(wǎng)絡(luò)連接記錄管理的高效哈希表[J].華中科技大學(xué)學(xué)報:自然科學(xué)版,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].計算機工程與科學(xué),2008,30(9):66-68.

[10] 王 果,徐仁佐.結(jié)合哈希過濾的一種改進多連接查詢優(yōu)化算法[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.