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

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

0 引 言

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

1 技術(shù)背景

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

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

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

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

2.1 簽名算法

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

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

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

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

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

2.3 算法描述

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

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

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

圖2 查找會(huì)話的過(guò)程

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

2.3.1 裝填因子

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

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

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

(1)

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

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

2.3.2 誤判率

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

(2)

1-k(k-1)/2n

(3)

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

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

(4)

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

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

3.1 單核性能

在開(kāi)源TCP/IP協(xié)議棧中，文中使用優(yōu)化后的TCB查找算法代替了原來(lái)的TCP查找協(xié)議，并對(duì)查找性能進(jìn)行了評(píng)估。

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

表1 跟蹤文件的特性

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

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

3.2 并行性能

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

圖4 TCB查找性能

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

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

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

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

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