李凱 葉麟 余翔湛 胡陽

摘要： 隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)以及國家骨干網(wǎng)絡(luò)的流量規(guī)模也在不斷增長(zhǎng)，大規(guī)模的流量以及無用的惡意流量對(duì)多核處理器的負(fù)載均衡有著很大的影響，所以對(duì)于多核處理器來說，負(fù)載均衡是一個(gè)亟待解決的問題。本文提出了一種基于DPDK平臺(tái)的動(dòng)態(tài)多重Hash的技術(shù)來更好地解決在多核處理器中流量分配不均衡的問題。文章中對(duì)現(xiàn)有的RSS等相關(guān)技術(shù)進(jìn)行分析，通過采用對(duì)稱RSS技術(shù)與動(dòng)態(tài)負(fù)載相關(guān)技術(shù)相結(jié)合的方法，將捕獲的數(shù)據(jù)包發(fā)配到不同的收包隊(duì)列，實(shí)現(xiàn)處理器多核間的負(fù)載均衡。

關(guān)鍵詞： DPDK； 負(fù)載均衡； 多核處理

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：2095-2163（2017）04-0085-06

0引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)中的流量規(guī)模日益增大，傳輸速度也在不斷提高，流量的負(fù)載均衡問題成為了限制諸多網(wǎng)絡(luò)服務(wù)的瓶頸，為了應(yīng)對(duì)網(wǎng)絡(luò)中數(shù)據(jù)包的高速傳輸，Intel針對(duì)X86架構(gòu)設(shè)計(jì)了高性能的數(shù)據(jù)包處理框架DPDK，DPDK通過對(duì)大頁技術(shù)、零拷貝技術(shù)、 網(wǎng)卡隊(duì)列技術(shù)以及CPU的親和性等成熟技術(shù)的開發(fā)運(yùn)用，以及對(duì)數(shù)據(jù)包處理的過程引入了效能優(yōu)化，相比Linux系統(tǒng)的數(shù)據(jù)包處理性能提高了數(shù)倍。DPDK框架主要應(yīng)用在多核處理器系統(tǒng)對(duì)數(shù)據(jù)包的處理流程中，在多核處理器的負(fù)載均衡方面，傳統(tǒng)的負(fù)載均衡算法主要有輪詢、哈希散列、響應(yīng)速度等，DPDK框架在負(fù)載均衡上采用了RSS技術(shù)，但是單純地采用RSS技術(shù)對(duì)于高性能會(huì)話連接的處理以及特殊情況出現(xiàn)Hash碰撞這些問題在技術(shù)探討中卻仍然呈現(xiàn)出一定的缺陷與不足?；诖?，本文即研究提出了一種基于DPDK平臺(tái)的動(dòng)態(tài)多重Hash的技術(shù)，通過對(duì)原有的RSS進(jìn)行修改以及結(jié)合動(dòng)態(tài)調(diào)整的方法來更好地解決在多核處理器中流量分配不均衡的問題。

1相關(guān)工作

1.1RSS技術(shù)

RSS（Receive Side Scaling）是與底層硬件相關(guān)聯(lián)，在多核處理器收到數(shù)據(jù)報(bào)文后能夠在多核之間進(jìn)行高速轉(zhuǎn)發(fā)的網(wǎng)卡驅(qū)動(dòng)技術(shù)。該技術(shù)需要通過相關(guān)的硬件網(wǎng)卡支持展開哈希值的計(jì)算，根據(jù)哈希值的不同將收到的數(shù)據(jù)報(bào)文發(fā)送到不同的收發(fā)隊(duì)列當(dāng)中，由于CPU的親核性，Linux內(nèi)核將不同隊(duì)列的報(bào)文映射到不同的處理器核中。同時(shí)，考慮到DPDK支持網(wǎng)卡的多隊(duì)列功能，因而可以比較容易地給特定應(yīng)用指定接收（RX）或發(fā)送（TX）隊(duì)列。

[JP2]通俗地講，RSS是利用特定的報(bào)文字段值進(jìn)行哈希計(jì)算得出哈希值，再通過得出的哈希值將數(shù)據(jù)報(bào)文送往不同的隊(duì)列，網(wǎng)卡會(huì)根據(jù)數(shù)據(jù)包的不同類型確定其特定的字段信息，如表1所示。例如IPV4 TCP的特定字段是由（S-IP、D-IP、S-Port、D-port）四元組構(gòu)成，此外，DPDK還可以根據(jù)需要采用數(shù)據(jù)包中的其他特定字段滿足不同的需求。并且圖1還進(jìn)一步闡釋了通過Hash計(jì)算得到的哈希值與隊(duì)列索引之間的關(guān)系。

1.2對(duì)稱RSS技術(shù)

對(duì)稱RSS是指在網(wǎng)卡驅(qū)動(dòng)開啟RSS功能后相同連接的雙向數(shù)據(jù)報(bào)文能夠分配到多核處理器的同一個(gè)核中，因?yàn)樵诓煌酥泄蚕磉B接信息會(huì)產(chǎn)生死鎖的現(xiàn)象，即使得對(duì)稱RSS對(duì)于保存連接信息的網(wǎng)絡(luò)應(yīng)用在減少性能開銷上獲得了大幅提升。

[JP2]RSS采用的是Toeplitz Hash算法，此算法需要2個(gè)輸入變量：數(shù)據(jù)報(bào)文中的五元組信息以及默認(rèn)的Hash key。DPDK網(wǎng)卡驅(qū)動(dòng)層采用的Hash key是Microsoft推薦的，對(duì)于相同連接的雙向數(shù)據(jù)報(bào)文經(jīng)過哈希后得到的Hash值是不同的，Hash值的不同會(huì)出現(xiàn)2個(gè)方向的數(shù)據(jù)報(bào)文分配到不同的接收隊(duì)列，通過不同的處理器核心進(jìn)行處理。對(duì)于如何生成對(duì)稱的RSS，文獻(xiàn)[1]對(duì)RSS原有的Hash key融入了一定的修改，并證明這組Hash key可以用來實(shí)現(xiàn)對(duì)稱RSS。原有的Hash key以及論文中提到的Hash key值分別如圖2和圖3所示。

1.3技術(shù)分析

研究分析可得，RSS技術(shù)的缺點(diǎn)是一些網(wǎng)絡(luò)應(yīng)用處理的設(shè)備中，僅僅使用RSS技術(shù)會(huì)影響處理性能，例如電信轉(zhuǎn)發(fā)設(shè)備，對(duì)一個(gè)網(wǎng)絡(luò)連接的雙向流處理的方式是相近的，所以希望在多核處理器的同一個(gè)核上對(duì)存在對(duì)稱信息的數(shù)據(jù)報(bào)文進(jìn)行處理，比較有代表性的應(yīng)用有網(wǎng)絡(luò)防火墻、服務(wù)質(zhì)量保證。若在不同的核上處理同一個(gè)流上的雙向信息，就會(huì)出現(xiàn)不同核研發(fā)設(shè)定數(shù)據(jù)同步的問題，這就會(huì)產(chǎn)生處理器的多余開銷，降低處理器的性能。

相對(duì)DPDK平臺(tái)的RSS技術(shù)改進(jìn)的對(duì)稱RSS技術(shù)雖然解決了同一個(gè)流的對(duì)向數(shù)據(jù)報(bào)文在不同核上有效處理的問題，但是對(duì)于出現(xiàn)Hash碰撞的情況以及大規(guī)模相同連接的流量時(shí)，還是會(huì)出現(xiàn)多核處理器某一個(gè)核上的負(fù)載過重，甚或負(fù)載不均衡的情況。

[JP2]綜上可得，當(dāng)網(wǎng)絡(luò)流量出現(xiàn)比較單一極端的情況下，僅僅利用靜態(tài)的哈希技術(shù)是無法滿足對(duì)數(shù)據(jù)報(bào)文處理的需求的，也就是將出現(xiàn)單核負(fù)載過重的情形，從而降低CPU的處理效率。[JP]

2框架設(shè)計(jì)及實(shí)驗(yàn)分析

2.1負(fù)載均衡框架

DPDK 對(duì)于數(shù)據(jù)包的處理主要設(shè)計(jì)推出了2種框架，分別是： run-to-completion（運(yùn)行至終結(jié)，簡(jiǎn)稱RTC）模型和Pipeline（流水線）模型。在此，將給出各自研究闡釋如下。

[JP2]首先，Pipeline模型能夠?qū)⑻幚砥髅芗牟僮骷性谝粋€(gè)核上執(zhí)行，將I/O密集的操作配置在另一個(gè)核上執(zhí)行，將不同的操作利用過濾器分配到不同的線程中。具體來說，Pipeline 模型把整個(gè)框架分為3部分：輸入端口、輸出端口和工作核（worker Lcore）， ring 隊(duì)列將端口與工作核相連。[JP3]通過這種方式，從一個(gè)端口收到的數(shù)據(jù)報(bào)文能夠依據(jù)應(yīng)用需求而分配至任一指定的工作核上處理，處理后工作核將數(shù)據(jù)包發(fā)送到輸出端口。[JP]endprint

其次，run-to-completion模型主要是DPDK平臺(tái)對(duì)于一般程序的運(yùn)行方法， run-to-completion通過網(wǎng)卡的多隊(duì)列的功能，將接收的數(shù)據(jù)報(bào)文分配給多個(gè)CPU核上處理，對(duì)于CPU的每個(gè)核，都是獨(dú)立處理到達(dá)該隊(duì)列的數(shù)據(jù)報(bào)文，硬件資源分配也比較固定，降低了數(shù)據(jù)報(bào)文在核間的傳遞的開銷，能夠隨著核的數(shù)目較為靈活地?cái)U(kuò)展處理能力。

基于前文研究可知，run-to-completion 模型確實(shí)能夠減少CPU核心間通信的開銷，但對(duì)于負(fù)載均衡是不合適的，對(duì)于同屬于一個(gè)鏈接的不同數(shù)據(jù)包會(huì)出現(xiàn)被分配到CPU的不同核上進(jìn)行處理，這樣保持會(huì)話連接就比較困難，而Pipeline能夠通過自定義規(guī)則選出特定的核心來處理數(shù)據(jù)報(bào)文，為此在負(fù)載均衡框架的設(shè)計(jì)上采用了Pipeline模型。負(fù)載均衡的實(shí)現(xiàn)框架則如圖4所示。

在該負(fù)載框架中用于處理來自不同網(wǎng)卡端口報(bào)文的邏輯核稱I/O邏輯核（I/O Lcore），其余被指定執(zhí)行應(yīng)用處理的邏輯核稱為工作邏輯核（Worker Lcore）。圖4即建立展示了2個(gè)特定的RX I/O邏輯核和2個(gè)特定TX I/O邏輯核用于處理來自網(wǎng)卡端口的報(bào)文收發(fā)的過程。下面則針對(duì)各關(guān)鍵核的工作內(nèi)容研究得到如下設(shè)計(jì)表述。[FL）]

1）I/O 接收邏輯核（I/O RX Lcore）。每個(gè)I/O接收邏輯核從指定的網(wǎng)卡環(huán)形隊(duì)列接收?qǐng)?bào)文，然后分發(fā)到工作線程（Worker Thread）。該框架允許每個(gè)I/O接收邏輯核與任何一個(gè)工作線程進(jìn)行通信，因此每個(gè)（I/O RX Lcore，Worker Lcore）對(duì)之間就可以通過專用的“生產(chǎn)者—消費(fèi)者”Ring環(huán)形隊(duì)列而展開連接。

2）I/O 發(fā)送邏輯核（I/O TX Lcore）。針對(duì)多個(gè)已預(yù)先定義的網(wǎng)卡端口，每個(gè)I/O邏輯核擁有報(bào)文發(fā)送能力。為啟動(dòng)每個(gè)工作線程發(fā)送報(bào)文到任何TX端口，框架為每個(gè)（Worker Lcore ，NIC_TX_Port）創(chuàng)建了一個(gè)Ring環(huán)形隊(duì)列，而每個(gè)I/O發(fā)送邏輯核就可以處理這些網(wǎng)卡端口上的環(huán)形隊(duì)列。

3）工作邏輯核（Worker Lcore）。每個(gè)工作邏輯核從一系列的Ring環(huán)形隊(duì)列讀取報(bào)文，通過將這些報(bào)文拆分到輸出軟件環(huán)，報(bào)文被轉(zhuǎn)發(fā)到網(wǎng)卡口。轉(zhuǎn)發(fā)邏輯是基于DPDK提供的LPM查表轉(zhuǎn)發(fā)的，所有的工作線程共享同樣的LPM規(guī)則。

2.2多重Hash算法

主要思想是采用2種哈希的方法解決負(fù)載不均衡的問題。首先建立2張Hash表，用來存儲(chǔ)一個(gè)連接與CPU不同核之間的映射關(guān)系，在網(wǎng)卡接收到報(bào)文后，對(duì)包頭的四元組設(shè)定2次不同的Hash計(jì)算，為了保證相同連接需要送到同一個(gè)核而統(tǒng)一處理的大原則，即使在CPU過載情況也要遵循這一原則，根據(jù)計(jì)算來研究轉(zhuǎn)入哈希表查詢：若查到映射關(guān)系說明收到的數(shù)據(jù)包是已有連接中的數(shù)據(jù)包，將數(shù)據(jù)包送到相應(yīng)CPU核心進(jìn)行處理；若在查表過程中沒有查詢到映射關(guān)系，說明收到的數(shù)據(jù)包屬于新連接，在負(fù)載正常的情況下，收到的新連接數(shù)據(jù)包進(jìn)行對(duì)稱RSS處理，將映射關(guān)系存在哈希表1中并將數(shù)據(jù)包送到相應(yīng)CPU實(shí)現(xiàn)后續(xù)處理，若系統(tǒng)出現(xiàn)負(fù)載不均導(dǎo)致某些CPU核心過載的情況下則剔除負(fù)載過重的核，收到的新連接數(shù)據(jù)包即加載第2套哈希算法，將映射關(guān)系存在哈希表2中并將數(shù)據(jù)包送到相應(yīng)CPU實(shí)現(xiàn)定制處理，通過這種方式能夠?qū)⑹盏降男逻B接中的數(shù)據(jù)包分散到負(fù)載較輕的CPU核心中去，從而能夠達(dá)到將負(fù)載均勻分配的目的。

采用多重Hash方法的好處是進(jìn)一步分離不同流的數(shù)據(jù)包，因?yàn)閱未蜨ash可能會(huì)出現(xiàn)Hash碰撞的可能。相對(duì)多核匹配，優(yōu)點(diǎn)在于能有更多的核參與到均衡流量。圖5即例示說明了在硬件層面對(duì)算法的支持。

過程中，需要在何種情況下對(duì)處理器的負(fù)載配置優(yōu)化調(diào)整，算法即在本節(jié)內(nèi)容中研究提出了采用負(fù)載均衡度[2]對(duì)多核的負(fù)載進(jìn)行評(píng)估，負(fù)載均衡度表示了接收的數(shù)據(jù)包在CPU多核處理器之間的分配比例與多核之間的處理能力比例的差異程度。負(fù)載均衡度的值越小，表明各處理節(jié)點(diǎn)的負(fù)載程度就越均勻。而考慮到對(duì)于多核處理器各核的處理性能均相同，為此這里的負(fù)載均衡度就是CPU多核之間負(fù)載量的差異程度 。具體的公式表述如下：

RLBM（t）=1-〖SX（〗〖JB（（〗∑〖DD（〗n〖〗i=1〖DD）〗Ri（t）〖JB））〗2〖〗n∑〖DD（〗n〖〗i=1〖DD）〗R2i（t）〖SX）〗[JY]（1）

其中，R（t）表示在時(shí)刻 t 多核處理器的第i個(gè)核的利用率，n 為多核處理器核的數(shù)量。通過反復(fù)實(shí)驗(yàn)，可以得出在負(fù)載均衡度的值高于0.2時(shí)，就會(huì)對(duì)處理器的流量負(fù)載進(jìn)行動(dòng)態(tài)的多重Hash調(diào)整。在確定了動(dòng)態(tài)調(diào)整的評(píng)估方法后，整體算法的基本流程則如圖6所示。算法流程步驟詳述如下：

1）收到數(shù)據(jù)包后，分別通過Hash1（）以及Hash2（）計(jì)算得到哈希結(jié)果，并利用哈希表1以及哈希表2進(jìn)行查找，如果存在映射關(guān)系就將數(shù)據(jù)包分配到對(duì)應(yīng)的處理核心中。

2）在第1）步中如果沒有在2張哈希表中查到對(duì)應(yīng)關(guān)系，說明數(shù)據(jù)包屬于一條新連接，而后將通過對(duì)當(dāng)前CPU的整體負(fù)載均衡度的統(tǒng)籌判斷操作來決定數(shù)據(jù)包的下步操作。

3）負(fù)載均衡度沒有超過系統(tǒng)設(shè)定的閾值，說明目前系統(tǒng)負(fù)載均衡情況較好，數(shù)據(jù)包根據(jù)Hash1（）的結(jié)果在哈希表1中建立映射關(guān)系，并將數(shù)據(jù)包分配到對(duì)應(yīng)的處理核心中。

4）負(fù)載均衡超過設(shè)定閾值時(shí)，說明目前出現(xiàn)了負(fù)載均衡不良，某些處理核心存在過載嚴(yán)重的情況，需在下一步中剔除過載嚴(yán)重的處理核心，并動(dòng)態(tài)更新Hash2（）的所有計(jì)算結(jié)果與處理核心id的映射關(guān)系，采用Hash2（）進(jìn)行計(jì)算，數(shù)據(jù)包根據(jù)Hash1（）的結(jié)果在哈希表2中建立映射關(guān)系，并將數(shù)據(jù)包分配到對(duì)應(yīng)的處理核心中。

2.3實(shí)驗(yàn)分析

實(shí)驗(yàn)選擇Pktgen對(duì)單位時(shí)間內(nèi)關(guān)于處理接收數(shù)據(jù)報(bào)文的CPU核心的使用率進(jìn)行統(tǒng)計(jì)，并對(duì)一個(gè)時(shí)間段的核心使用率計(jì)算平均值，通過比較多核處理器各個(gè)處理節(jié)點(diǎn)的使用率來對(duì)負(fù)載均衡度而展開有效的衡定與測(cè)量。研究中選定的實(shí)驗(yàn)平臺(tái)的配置信息則如表2所示。endprint

2）使用多重Hash方法，各核的負(fù)載情況。也可由研究得到對(duì)應(yīng)運(yùn)行效果即如圖8所示。

在此基礎(chǔ)上，又引入了柱狀圖的模式來展開研究，研究可得結(jié)果如圖9所示。通過柱狀圖的遞進(jìn)趨勢(shì)來看，相比在DPDK平臺(tái)單純使用RSS技術(shù)而言，使用多重Hash方法將負(fù)載過重的處理節(jié)點(diǎn)的后續(xù)接收的數(shù)據(jù)報(bào)文分配到其他負(fù)載較輕的負(fù)載節(jié)點(diǎn)上，從而能夠使得各個(gè)處理節(jié)點(diǎn)的使用率相對(duì)平均，充分利用了多核處理器的性能，處理器也隨即將更好地發(fā)揮可調(diào)用設(shè)計(jì)潛能，一定程度上提高了多核處理器的處理效率。

3結(jié)束語

本文圍繞高速網(wǎng)絡(luò)壞境中多核處理器關(guān)于捕獲數(shù)據(jù)包負(fù)載均衡的問題，首先對(duì)DPDK平臺(tái)提供的RSS以及對(duì)稱RSS靜態(tài)哈希的技術(shù)探討引入了可行有效分析，并進(jìn)一步論述了目前呈現(xiàn)的問題；其次是針對(duì)這些不足致力于研究改進(jìn)，由此則開發(fā)提出了靜態(tài)與動(dòng)態(tài)相結(jié)合的多重Hash負(fù)載均衡的算法；最后，基于DPDK平臺(tái)設(shè)計(jì)得出一個(gè)負(fù)載均衡的框架，并通過實(shí)驗(yàn)分析算法性能，從而全面對(duì)照比較了在DPDK平臺(tái)單純地采用RSS算法和多重Hash算法之間的差異程度。

參考文獻(xiàn)：

[1] WOO S， PARK K S. Scalable TCP session monitoring with symmetric receive-side scaling[R]. Daejeon， South Korea：KAIST， 2012.

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

[3] 趙寧， 謝淑翠. 基于dpdk的高效數(shù)據(jù)包捕獲技術(shù)分析與應(yīng)用[J]. 計(jì)算機(jī)工程與科學(xué)， 2016， 38（11）：2209-2215.

[4] 何佳偉， 江舟. 基于Intel DPDK的高性能網(wǎng)絡(luò)安全審計(jì)方案設(shè)計(jì)[J]. 電子測(cè)試， 2016（Z1）：87-91.

[5] 張瑩， 吳和生. 面向多進(jìn)程負(fù)載均衡的Hash算法比較與分析[J]. 計(jì)算機(jī)工程， 2014， 40（9）：71-76.

[6] 于洪偉. 基于多核處理器高效入侵檢測(cè)技術(shù)研究與實(shí)現(xiàn)[D]. 成都：電子科技大學(xué)， 2009.

[7] 莊卓俊. 基于多核平臺(tái)的入侵檢測(cè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 上海：上海交通大學(xué)， 2009.

[8] Shemesh O. System and method for symmetric receiveside scaling （RSS）：US，8635352[P]. 2014-01-22.

[9] BOKHARI M U， ALAM M， HASAN F. Performance analysis of dynamic load balancing algorithm for multiprocessor interconnection network[J]. Perspectives in Science， 2016， 8（C）：564-566.

[10] ZAJDA K. Evaluation of possible applications of dynamic routing protocols for load balancing in computer networks[J]. Theoretical & Applied Informatics， 2010， 22（2）：141-151.

[11]李敬喆. 多核環(huán)境下的負(fù)載均衡方法研究與設(shè)計(jì)[D]. 北京：北方工業(yè)大學(xué)， 2011.

[12]劉熙. 若干負(fù)載均衡技術(shù)的研究[D]. 南京：南京大學(xué)， 2011.

[13]李彥君， 鐘求喜， 陳誠，等. 多核平臺(tái)入侵檢測(cè)系統(tǒng)負(fù)載均衡算法設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究， 2012， 29（4）：1413-1416.

[14][JP4]HOU E S H， ANSARI N， REN H. Genetic algorithm for multiprocessor[JP] scheduling[J]. IEEE Transactions on Parallel & Distributed Systems， 1994， 5（2）：113-120.endprint