一種多核環(huán)境中無鎖的多進(jìn)程負(fù)載均衡會話保持方案

吳和生 王崇駿 謝俊元

①(南京大學(xué)軟件學(xué)院 南京 210093)

②(計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 南京 210093)

③(南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 南京 210093)

1 引言

負(fù)載均衡是云計(jì)算的重要組成部分，是服務(wù)器集群化中最為重要的環(huán)節(jié)[1]。與發(fā)展早期相比，現(xiàn)代負(fù)載均衡所面臨的外部環(huán)境發(fā)生了許多變化，其中最為重要的變化之一是計(jì)算機(jī)處理器從單核變?yōu)槎嗪?。相較于傳統(tǒng)的單進(jìn)程負(fù)載均衡架構(gòu)，在多核環(huán)境中多進(jìn)程架構(gòu)可以充分利用處理器的并行處理能力以提高系統(tǒng)的整體性能。因此，多核環(huán)境中多進(jìn)程負(fù)載均衡成為現(xiàn)階段云計(jì)算中的研究熱點(diǎn)[2,3]。

在多核環(huán)境中如果采用多進(jìn)程架構(gòu)，讓費(fèi)時(shí)的包解析工作能夠并發(fā)進(jìn)行，就能顯著提升系統(tǒng)的整體性能。但與現(xiàn)有單進(jìn)程負(fù)載均衡架構(gòu)相比，多進(jìn)程負(fù)載均衡架構(gòu)需要解決一些新的問題，其中一個(gè)尤為重要的問題是會話保持問題。

單核環(huán)境中負(fù)載均衡會話保持的研究已經(jīng)積累了豐碩的成果，常用的方法有：簡單會話保持(源地址會話保持)、基于 SSL Session ID的會話保持、I-Rules會話保持、HTTP Header會話保持、HTTP Cookie會話保持、基于SIP ID以及Cache設(shè)備的會話保持等。這些方法適用于單進(jìn)程負(fù)載均衡架構(gòu)，但應(yīng)用在多核多進(jìn)程負(fù)載均衡架構(gòu)中會出現(xiàn)問題。以HTTP協(xié)議為例，應(yīng)用這些方法造成多核多進(jìn)程負(fù)載均衡會話保持難以實(shí)現(xiàn)的原因是：第 1個(gè)HTTP 數(shù)據(jù)包到達(dá)進(jìn)程A時(shí)新建的會話項(xiàng)被存儲在進(jìn)程A的會話表中，而第2個(gè)HTTP 數(shù)據(jù)包到達(dá)進(jìn)程B時(shí)進(jìn)程B在自己的會話表中無法找到存儲于進(jìn)程A會話表中的對應(yīng)會話項(xiàng)。解決這個(gè)問題的常見方法是使所有的負(fù)載均衡進(jìn)程以共享內(nèi)存的方式共享一個(gè)會話表。著名的負(fù)載均衡廠商F5, Array與 A10均采用這一方式來實(shí)現(xiàn)多核多進(jìn)程會話保持。這種方式將使會話表成為多進(jìn)程并發(fā)訪問的臨界區(qū)，所以必須設(shè)計(jì)適當(dāng)?shù)逆i機(jī)制來管理會話表的并發(fā)訪問。鎖機(jī)制的設(shè)計(jì)與使用的會話表數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，不管鎖機(jī)制的設(shè)計(jì)如何精妙，都會或多或少地造成系統(tǒng)性能的降低；此外，使用共享內(nèi)存的多進(jìn)程負(fù)載均衡會話保持方案需要對原有單進(jìn)程負(fù)載均衡程序進(jìn)行大量結(jié)構(gòu)上的修改。

本文針對多核環(huán)境中多進(jìn)程負(fù)載均衡會話保持問題，面向Linux內(nèi)核，基于Hash化管理內(nèi)核網(wǎng)絡(luò)數(shù)據(jù)包傳遞的思想，通過修改Linux內(nèi)核實(shí)現(xiàn)了Socket level hash特性，在此基礎(chǔ)上，提出并實(shí)現(xiàn)了一種無鎖的多進(jìn)程負(fù)載均衡會話保持方案。該方案避免了鎖的使用，而且不需要對原有單進(jìn)程負(fù)載均衡程序進(jìn)行結(jié)構(gòu)上的修改，能夠快速地將現(xiàn)有單進(jìn)程負(fù)載均衡程序轉(zhuǎn)變?yōu)槎噙M(jìn)程架構(gòu)。理論分析和實(shí)驗(yàn)表明，該方案提高了多核環(huán)境中負(fù)載均衡系統(tǒng)的效率。相較于傳統(tǒng)的共享內(nèi)存解決方案，本文提出的方法性能更好、適用性更強(qiáng)。

2 多核多進(jìn)程負(fù)載均衡會話保持方案分析

2.1 多進(jìn)程負(fù)載均衡在多核環(huán)境中的會話保持問題

為了實(shí)現(xiàn)會話保持，負(fù)載均衡程序需要維護(hù)一個(gè)會話表。在多核多進(jìn)程架構(gòu)中，由于多個(gè)進(jìn)程監(jiān)聽在同一組Socket集上，當(dāng)客戶請求來到時(shí)，操作系統(tǒng)可能將該請求發(fā)往這些負(fù)載均衡進(jìn)程中的任意一個(gè)，即屬于同一個(gè)會話的多個(gè)請求很可能被發(fā)往不同的負(fù)載均衡進(jìn)程進(jìn)行處理。在這種情況下，不能像單進(jìn)程架構(gòu)那樣維護(hù)局限于進(jìn)程的會話表，而需要維護(hù)一個(gè)共享的全局會話表，每個(gè)進(jìn)程都去訪問該表，該表成為臨界區(qū)。解決全局會話表的互斥訪問問題的通用方案是用共享內(nèi)存存儲會話表，用鎖來維護(hù)該表的一致性。

2.2 多核多進(jìn)程負(fù)載均衡共享內(nèi)存式鎖機(jī)制分析

著名的負(fù)載均衡廠商F5, Array與A10普遍采用多進(jìn)程共享內(nèi)存式鎖機(jī)制來解決多核環(huán)境中多進(jìn)程會話保持問題。鎖機(jī)制的設(shè)計(jì)與使用的會話表數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，在這里以開源軟件Haproxy使用的會話表結(jié)構(gòu)為例，對鎖機(jī)制的設(shè)計(jì)作必要的分析。

Haproxy中的會話表是一種散列表，用鏈表來解決Hash的沖突問題。每個(gè)會話項(xiàng)由會話ID、后端服務(wù)器ID、超時(shí)時(shí)間以及用來將會話項(xiàng)串入鏈表的hash_list結(jié)構(gòu)組成。其中會話ID表示HTTP數(shù)據(jù)包中用來表示會話信息的內(nèi)容，Haproxy根據(jù)會話 ID計(jì)算 Hash值以決定將會話項(xiàng)放入哪個(gè)隊(duì)列中；后端服務(wù)器ID表示該會話對應(yīng)的后端服務(wù)器；超時(shí)時(shí)間表示該會話何時(shí)超時(shí)。

Haproxy中對會話表的訪問主要包括：

(1)當(dāng)接收到HTTP數(shù)據(jù)包時(shí)，查詢會話表，查找是否有對應(yīng)的會話項(xiàng)，如果找到對應(yīng)項(xiàng)，更新會話項(xiàng)的超時(shí)時(shí)間，否則生成新會話項(xiàng)并插入會話表。

(2)定期掃描會話表，刪除超時(shí)會話項(xiàng)。

這些操作都需要用鎖機(jī)制進(jìn)行同步，針對Haproxy的會話表結(jié)構(gòu)，鎖設(shè)計(jì)方案有以下幾種：

(a)只用一個(gè)鎖來控制整個(gè)會話表的訪問，進(jìn)程在訪問會話表前需要獲得這個(gè)鎖。毫無疑問這種設(shè)計(jì)的鎖粒度太大，鎖的爭用將會非常嚴(yán)重，會造成系統(tǒng)性能的嚴(yán)重降低。

(b)每個(gè)Hash隊(duì)列用一個(gè)鎖控制訪問。這種設(shè)計(jì)中使用同一個(gè)鎖的范圍減小到被 Hash到同一隊(duì)列的會話項(xiàng)的操作(查找、更新和插入)加上掃描并刪除超時(shí)會話的操作(查找和刪除)。鎖的爭用情況有所緩解，但當(dāng)處理大量連接時(shí)，被Hash到同一隊(duì)列的會話數(shù)目將會很大，系統(tǒng)性能依然可能因?yàn)榈却i而造成較為嚴(yán)重的損失。這種設(shè)計(jì)的鎖粒度依然過大。

(c)每個(gè)會話項(xiàng)用一個(gè)鎖來控制寫操作，每個(gè)Hash隊(duì)列用一個(gè)讀寫鎖來控制。這種設(shè)計(jì)方案將鎖的粒度進(jìn)一步細(xì)化，并且改用讀寫鎖來控制 Hash隊(duì)列的訪問。這種設(shè)計(jì)方案較前兩種方案更好地避免了鎖的爭用，但由于需要對每個(gè)會話項(xiàng)維護(hù)一個(gè)鎖，對系統(tǒng)資源的消耗較大。

可見，不管鎖機(jī)制如何設(shè)計(jì)，由于需要頻繁查詢、修改會話表，都會或多或少降低系統(tǒng)性能；何況使用共享內(nèi)存的多進(jìn)程負(fù)載均衡會話保持方案需要對原有單進(jìn)程負(fù)載均衡程序進(jìn)行大量結(jié)構(gòu)上的修改。

3 無鎖的多核多進(jìn)程負(fù)載均衡會話保持方案

使用共享內(nèi)存和鎖機(jī)制的多進(jìn)程負(fù)載均衡架構(gòu)會造成系統(tǒng)性能的損失，而且現(xiàn)有單進(jìn)程負(fù)載均衡程序需要大量結(jié)構(gòu)上的修改才能適用這種架構(gòu)。為了避免這些問題，本文通過修改Linux socket層的實(shí)現(xiàn)，使得Linux中處于TCP_LISTEN態(tài)的Socket能夠提供一種稱為Socket level hash的屬性，該屬性能保證當(dāng)有多個(gè)用戶進(jìn)程嘗試從該Socket獲取新建TCP連接時(shí)，所有來自同一IP的連接請求都會發(fā)往同一個(gè)用戶進(jìn)程，進(jìn)而保證所有屬于同一用戶會話的數(shù)據(jù)包都被發(fā)往同樣的用戶進(jìn)程。

由于內(nèi)核做了這樣的保證，各個(gè)負(fù)載均衡進(jìn)程只需要維護(hù)進(jìn)程內(nèi)部的會話表(正如單進(jìn)程負(fù)載均衡程序所做的那樣)而不需要將會話表放到共享內(nèi)存中被所有進(jìn)程共享，從而避免了鎖的使用以及使用鎖機(jī)制帶來的性能損失。

3.1 Socket level hash特性

從Linux內(nèi)核[4]Socket層實(shí)現(xiàn)中可以看到，對一個(gè)處于 TCP_LISTEN 態(tài)的 Socket，每當(dāng)一個(gè)TCP連接建立完成時(shí)，內(nèi)核構(gòu)造一個(gè)request_sock結(jié)構(gòu)并將該結(jié)構(gòu)放入該 Socket對應(yīng) inet_connection_sock結(jié)構(gòu)的 icsk_accept_queue隊(duì)列中；當(dāng)一個(gè)進(jìn)程對指向該Socket 的打開文件描述符調(diào)用 accept()函數(shù)時(shí)，內(nèi)核就從該 icsk_accept_queue隊(duì)列中取出(如果有)一個(gè) request_sock結(jié)構(gòu)，并根據(jù)該結(jié)構(gòu)生成新的Socket，最終返回給用戶一個(gè)指向新建Socket的打開文件描述符。內(nèi)核對新建TCP連接并不區(qū)別對待，對嘗試取request_sock結(jié)構(gòu)的用戶進(jìn)程也不區(qū)別對待，任何進(jìn)程都可能取得任何的request_sock結(jié)構(gòu)。

本文通過給TCP_LISTEN態(tài)的Socket增兩選項(xiàng) ：SO_SOCKLEVELHASH與 SO_SOCKADDLSPH來實(shí)現(xiàn)Socket level hash，其內(nèi)核數(shù)據(jù)結(jié)構(gòu)如圖1所示。當(dāng)一個(gè)處于TCP_LISTEN態(tài)的Socket 設(shè)置了SO_SOCKLEVELHASH選項(xiàng)后，在內(nèi)核中該Socket對應(yīng)inet_connection_sock結(jié)構(gòu)的 icsk_accept_queue 結(jié)構(gòu)除了維護(hù)原有的request_sock 隊(duì)列外，還將額外維護(hù) NR_CPUS個(gè)高優(yōu)先級隊(duì)列(NR_CPUS常量為系統(tǒng)中CPU的數(shù)目)。當(dāng)某用戶進(jìn)程對一個(gè)處于TCP_LISTEN 態(tài)并設(shè)置了 SO_SOCKLEVELHASH選項(xiàng)的 Socket設(shè)置SO_SOCKADDLSPH選項(xiàng)時(shí)，其進(jìn)程ID將被注冊到對應(yīng)icsk_accept_queue結(jié)構(gòu)的某個(gè)高優(yōu)先級隊(duì)列中，表示該用戶進(jìn)程將優(yōu)先接收該隊(duì)列中的request_sock結(jié)構(gòu)。

打開Socket level hash選項(xiàng)的TCP_LISTEN態(tài)Socket處理新建TCP連接的方法與普通Socket不同，當(dāng)一個(gè)TCP連接建立完成后，代表該TCP連接的 request_sock結(jié)構(gòu)被生成，內(nèi)核首先調(diào)用Hash算法將該 request_sock結(jié)構(gòu)映射到 NR_CPUS個(gè)高優(yōu)先級隊(duì)列中的一個(gè)中，如果該高優(yōu)先級隊(duì)列上已經(jīng)有用戶進(jìn)程注冊，則該 request_sock結(jié)構(gòu)被放入該隊(duì)列中，否則，表示沒有用戶程序打算優(yōu)先接收這個(gè)request_sock結(jié)構(gòu)，內(nèi)核將其放入默認(rèn)隊(duì)列中。

圖1 Socket level hash內(nèi)核數(shù)據(jù)結(jié)構(gòu)

Linux IO操作有BLOCK_IO和NOBLOCK_IO兩類。對 NOBLOCK_IO，當(dāng)用戶進(jìn)程調(diào)用accept()函數(shù)(最終調(diào)用sys_accept()內(nèi)核函數(shù))從打開Socket level hash選項(xiàng)的Socket中嘗試獲得新建TCP連接時(shí)，如果該用戶進(jìn)程已經(jīng)將自己注冊到某個(gè)高優(yōu)先級隊(duì)列中，則會首先從該隊(duì)列取request_sock結(jié)構(gòu)。對BLOCK_IO, Linux原來的邏輯是當(dāng)用戶進(jìn)程調(diào)用 accept()函數(shù)而不能取得request_sock結(jié)構(gòu)時(shí)，進(jìn)程將互斥地加入sock結(jié)構(gòu)的sk_sleep等待隊(duì)列并進(jìn)入阻塞狀態(tài)，當(dāng)TCP 連接建立，新的request_sock 結(jié)構(gòu)生成時(shí)，喚醒sk_sleep 隊(duì)列的一個(gè)進(jìn)程，該進(jìn)程將獲得新建的request_sock結(jié)構(gòu)。當(dāng)TCP_LISTEN態(tài)Socket開啟Socket level hash選項(xiàng)時(shí)，由于新建的request_sock不一定能映射給被喚醒的進(jìn)程，原有處理BLOCK_IO的邏輯需要修改。修改方法有兩種，一種方法是進(jìn)程不再互斥地加入 sk_sleep等待隊(duì)列，每次request_sock生成時(shí)將sk_sleep 上的所有進(jìn)程都喚醒，這樣該request_sock映射到的進(jìn)程繼續(xù)運(yùn)行，其余進(jìn)程繼續(xù)阻塞在sk_sleep 等待隊(duì)列上。另一種方法是在sock結(jié)構(gòu)中也相應(yīng)地維護(hù)NR_CPUS個(gè)等待隊(duì)列，用戶進(jìn)程根據(jù)自己所在 icsk_accept_queue的哪個(gè)隊(duì)列上注冊來決定自己加入哪個(gè)等待隊(duì)列，當(dāng)一個(gè)request_sock 結(jié)構(gòu)生成時(shí)，也根據(jù)該結(jié)構(gòu)被放入icsk_accept_queue的哪個(gè)隊(duì)列來在對應(yīng)等待隊(duì)列上喚醒一個(gè)進(jìn)程。

從以上討論中可以看到，只要使用客戶端IP地址作為Hash算法的輸入，就可以保證所有來自同一客戶端的連接請求都被發(fā)往同一個(gè)用戶進(jìn)程，從而保證所有屬于同一用戶會話的HTTP數(shù)據(jù)包都被發(fā)往同一個(gè)負(fù)載均衡進(jìn)程；Hash算法的分配均衡性和效率直接影響到Socket level hash的性能。

3.2 Socket level hash常用Hash算法

Hash算法的種類很多，適應(yīng)Socket level hash的Hash算法應(yīng)該具有如下特征：

(1)對多種Hash輸入類型都能產(chǎn)生較為均勻的Hash分布。這些 Hash輸入類型主要包括 TCP/IPV4, TCP/IPV6, IPV4, IPV6協(xié)議數(shù)據(jù)包。

(2)在進(jìn)程數(shù)目較少(如2個(gè))或較多(如64個(gè))的情況下都能將輸入較為均勻地散列到各個(gè)進(jìn)程中。

(3)Hash函數(shù)的耗時(shí)要少。因?yàn)閷γ總€(gè)新建連接都需要進(jìn)行Hash運(yùn)算，該Hash算法必須能計(jì)算得非常快，否則會成為系統(tǒng)性能的瓶頸。

根據(jù)上述特征分析表明，適用Socket level hash的Hash算法主要有5種(見算法1～算法5)。文獻(xiàn)[5,6]討論了前4種Hash算法的性質(zhì)，文獻(xiàn)[7]討論了第5種Hash算法的性質(zhì)。

算法1使用源IP地址進(jìn)行Hash

這是最簡單的Hash方法，直接用源IP地址模進(jìn)程數(shù)N即可。該Hash函數(shù)表示為：H=SrcIP%N。當(dāng)N=2k時(shí)，只需要取源IP地址的最后kbit，就是Hash 函數(shù)的結(jié)果。

算法2使用源IP的異或折疊(XOR Folding)

使用源 IP地址的異或折疊 Hash算法可表示成：H=(D1?D2?D3?D4)%N，其中Di表示源IP地址的第i個(gè)字節(jié)。

算法3使用源IP與目的IP的異或折疊

對算法2的簡單改進(jìn)是，將目的IP地址也作為Hash 算法的參數(shù)，即將源IP地址與目的IP地址一起做異或折疊。該 Hash 算法表示為：H=(S1?S2?S3?S4?D1?D2?D3?D4) %N。

算法4CRC16 (16 bit循環(huán)冗余檢查)

CRC16算法已經(jīng)被證實(shí)可用于負(fù)載均衡中。本文用網(wǎng)絡(luò)數(shù)據(jù)包中的five-tuple(源IP、目標(biāo)IP、源端口、目標(biāo)端口、協(xié)議號)作為CRC16 算法的輸入，再對結(jié)果取模以構(gòu)造Hash 函數(shù)，算法描述為：H=CRC16(five-tuple)%N。

算法5Toeplitz hash

Toeplitz hash是一種使用 Toeplitz矩陣計(jì)算Hash值的Hash算法，Toeplitz矩陣的特征是矩陣中處于同一對角線上的元素具有相同的值。更為精確地說，對n行m列的Toeplitz矩陣A，對任意1￡i,，如果k-i=l-j，則Ai,j=Ak,l。

Free BSD內(nèi)核源碼中提供了一個(gè)用于實(shí)現(xiàn)Receive-Side Scaling功能的Toeplitz矩陣[8]，本文使用該矩陣計(jì)算request_sock的Hash值。

4 理論分析及實(shí)驗(yàn)評估

4.1 理論分析

4.1.1 5種Hash算法的比較分析 對于一個(gè)Hash算法，評價(jià)其優(yōu)劣的重要標(biāo)準(zhǔn)應(yīng)為分配均衡性和時(shí)間消耗。

Hash算法的分配均衡性，即對任意一組樣本，進(jìn)入Hash表每一個(gè)單元之概率的平均程度。因?yàn)檫@個(gè)概率越平均，數(shù)據(jù)在表中的分布就越平均，表的空間利用率就越高。

現(xiàn)有研究表明，比特之間異或運(yùn)算和位移運(yùn)算能夠提高哈希值的隨機(jī)特性[9]。這5種Hash算法本質(zhì)上都是位移和異或操作的組合，因此都具有較好的分配均衡性。

Hash算法的時(shí)間消耗也直接影響著系統(tǒng)性能。不難計(jì)算，這5種Hash算法時(shí)間復(fù)雜度均為O(1)。究竟哪種Hash算法計(jì)算最快，留待4.2節(jié)實(shí)驗(yàn)驗(yàn)證。

4.1.2 多核多進(jìn)程負(fù)載均衡會話保持方案比較分析多核環(huán)境中多進(jìn)程負(fù)載均衡共享內(nèi)存式鎖機(jī)制會話保持解決方案(簡稱方案 1)需要精心設(shè)計(jì)鎖來保護(hù)共享的會話表，對會話表的訪問需要首先獲得對應(yīng)的鎖，當(dāng)鎖被其他進(jìn)程占用時(shí)，當(dāng)前獲取鎖的進(jìn)程必須等待鎖的釋放。當(dāng)多核中同時(shí)有多個(gè)進(jìn)程試圖獲得同一個(gè)鎖時(shí)會產(chǎn)生爭用，相關(guān)進(jìn)程越多爭用就越頻繁，因而系統(tǒng)需要維護(hù)多個(gè)就緒隊(duì)列和阻塞隊(duì)列，開銷將變得非常大。

不難計(jì)算，就緒隊(duì)列和阻塞隊(duì)列的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(n)，而鎖爭用過程中頻繁地等待資源，導(dǎo)致開銷進(jìn)一步加大。Etsion等人[10]使用內(nèi)核探測程序來測試內(nèi)核鎖的爭用情況，統(tǒng)計(jì)結(jié)果顯示，在32個(gè)進(jìn)程時(shí)，內(nèi)核鎖競爭的開銷多達(dá)20%。袁清波等人[11]用Sysbench測試程序?qū)inux操作系統(tǒng)的文件系統(tǒng)部分進(jìn)行了詳細(xì)測試，結(jié)果顯示，在1024個(gè)線程時(shí)，內(nèi)核中對鎖的等待時(shí)間已經(jīng)超過對鎖的占有時(shí)間，而且線程數(shù)越多這種現(xiàn)象越明顯。顯而易見，方案1鎖的爭用較內(nèi)核鎖爭用的開銷更大。

采用基于Socket level hash特性的無鎖多核多進(jìn)程負(fù)載均衡會話保持方案(簡稱方案2)，需要額外維護(hù)多個(gè)優(yōu)先級隊(duì)列?；凇岸选?內(nèi)嵌雙向鏈表)實(shí)現(xiàn)的優(yōu)先級隊(duì)列的時(shí)間復(fù)雜度為O(log2n)，空間復(fù)雜度為O(1)。與方案1的比較見表1。

從表1可以看出，無論是在內(nèi)存需求增量方面，還是在性能損耗方面，方案2都明顯優(yōu)于方案1。

表1 方案1與方案2的性能比較

4.2 實(shí)驗(yàn)1 5種Hash算法的實(shí)驗(yàn)比較及評估

4.2.1 實(shí)驗(yàn)設(shè)置 本實(shí)驗(yàn)所使用數(shù)據(jù)集由美國麻省大學(xué)(Umass)[12]網(wǎng)絡(luò)中心收集，該數(shù)據(jù)集記錄了麻省大學(xué)從2007年6月9日到2007年6月22日期間每天上午 9:30～10:30 通過學(xué)校網(wǎng)關(guān)的數(shù)據(jù)包，共包括654795條記錄。本實(shí)驗(yàn)使用3.2節(jié)提到的5種Hash算法計(jì)算這些包的Hash值，測試當(dāng)存在2, 4, 8, 16,32, 64個(gè)負(fù)載均衡進(jìn)程的情況下Hash算法的分配均衡性，同時(shí)對這些過程計(jì)時(shí)，以考察Hash算法的時(shí)間消耗。

4.2.2 實(shí)驗(yàn)結(jié)果及評估 5種Hash算法耗費(fèi)時(shí)間分別為0.031 s, 0.089 s, 0.162 s, 3.910 s, 0.153 s。

實(shí)驗(yàn)表明，算法1產(chǎn)生實(shí)驗(yàn)結(jié)果的不均衡性明顯高于其他4種算法。

對其余4種算法產(chǎn)生的實(shí)驗(yàn)結(jié)果求標(biāo)準(zhǔn)差，結(jié)果如圖2所示。

從圖2中可以看到，當(dāng)Hash目標(biāo)數(shù)量較小時(shí)(如2或4個(gè))，算法2，算法3的均衡性嚴(yán)重降低；算法4，算法5的均衡性幾乎不受Hash目標(biāo)數(shù)量多少的影響，具有很好的穩(wěn)定性，而且無論 Hash 目標(biāo)的多少，這兩種算法的實(shí)驗(yàn)結(jié)果都具有最小的標(biāo)準(zhǔn)差，提供最均衡的Hash分配。但算法4的時(shí)間消耗是算法5的25.6倍，在Socket level hash的實(shí)現(xiàn)中，每個(gè)request_sock結(jié)構(gòu)都需要進(jìn)行一次Hash運(yùn)算，該 Hash算法的時(shí)間消耗直接影響著系統(tǒng)的整體性能，從這個(gè)角度來看，算法5優(yōu)于算法4。

綜合考慮Hash算法的分配均衡性、時(shí)間消耗等各方面因素，可見Toeplitz hash最適合作為Socket level hash的Hash算法。

4.3 實(shí)驗(yàn)2 方案的實(shí)驗(yàn)比較及評估

4.3.1 實(shí)驗(yàn)設(shè)置 本實(shí)驗(yàn)使用以下工具：

(1)Haproxy Haproxy是著名的開源 TCP/HTTP負(fù)載均衡項(xiàng)目，提供了豐富的7層負(fù)載均衡功能[13]。Haproxy使用單進(jìn)程架構(gòu)，正如本文中提到的問題，這款軟件無法支持多進(jìn)程負(fù)載均衡架構(gòu)。

(2)Siege Siege是一款網(wǎng)絡(luò)性能測試工具，它以可配置的并發(fā)度在一段由用戶配置的時(shí)間內(nèi)不斷地向目標(biāo)服務(wù)器請求服務(wù)以測試目標(biāo)服務(wù)器的性能，這個(gè)過程稱為一次轟擊(Hit)；在每次轟擊之后Siege都會計(jì)算目標(biāo)服務(wù)器的性能參數(shù)，包括目標(biāo)服務(wù)器的連接率、吞吐量和并發(fā)連接數(shù)等[14]。

(3)VMware VMware是一款虛擬化平臺[15]，本實(shí)驗(yàn)使用 VMware 來生成虛擬機(jī)作為負(fù)載均衡器。本實(shí)驗(yàn)用到2臺配置完全相同的虛擬機(jī)，虛擬機(jī)具有2個(gè)CPU。其中虛擬機(jī)1運(yùn)行原版2.6.18內(nèi)核；虛擬機(jī)2運(yùn)行修改過的支持Socket level hash的內(nèi)核。兩臺虛擬機(jī)都運(yùn)行Haproxy負(fù)載均衡程序，其中虛擬機(jī)1只有一個(gè)Haproxy進(jìn)程，虛擬機(jī)2使用Socket level hash選項(xiàng)，運(yùn)行著2個(gè)Haproxy進(jìn)程。兩臺虛擬機(jī)都使用本機(jī)的Redhat自帶Http服務(wù)器Httpd作為后端服務(wù)器。

4.3.2 實(shí)驗(yàn)結(jié)果及評估 實(shí)驗(yàn)步驟如下：

步驟.1 用 Siege 轟擊虛擬機(jī) 1，記錄性能參數(shù)。

步驟2 選擇2個(gè)具有會被Socket level hash分配給同一負(fù)載均衡進(jìn)程的IP地址的機(jī)器，在這2臺機(jī)器上分別用 Siege 轟擊虛擬機(jī) 2，記錄性能參數(shù)。

步驟3 選擇2個(gè)具有會被Socket level hash分配給不同負(fù)載均衡進(jìn)程的IP地址的機(jī)器，在這2臺上分別用Siege 轟擊虛擬機(jī)2，記錄性能參數(shù)。

以上每次轟擊都持續(xù)30 s，重復(fù)10次，最后得到的性能參數(shù)如圖3 所示。

圖2 Hash算法2～算法5實(shí)驗(yàn)結(jié)果標(biāo)準(zhǔn)差

圖3 吞吐量和連接數(shù)

從圖3中可以計(jì)算得到，步驟3相對于步驟1的吞吐量平均提高107%，連接數(shù)平均提高168%；步驟2相對于步驟1的吞吐量平均提高8%，連接數(shù)平均提高36%。

步驟3得到的服務(wù)器性能參數(shù)(無論是吞吐量還是連接率)遠(yuǎn)好于步驟1，這說明相對于單進(jìn)程架構(gòu)而言，多核環(huán)境中多進(jìn)程負(fù)載均衡架構(gòu)能充分利用并行處理的好處，提高系統(tǒng)的整體性能。

值得注意的是，步驟2的性能參數(shù)遠(yuǎn)遜于步驟3，與步驟1相比提高不多。步驟2模擬了一種極端的情況，即用在Socket level hash 中的Hash算法產(chǎn)生極不均衡的分配時(shí)(步驟2中所有的連接都被發(fā)往同一個(gè)負(fù)載均衡進(jìn)程)，系統(tǒng)的整體性能將急劇地降低；只有當(dāng)Socket level hash產(chǎn)生較為均衡的分配時(shí)，使用Socket level hash 的多進(jìn)程負(fù)載均衡系統(tǒng)才能獲得最大的性能提升。

5 結(jié)束語

多核環(huán)境中無鎖的多進(jìn)程負(fù)載均衡架構(gòu)在TeraScaler(作者參與研發(fā)的國家自然科學(xué)基金資助項(xiàng)目成果)負(fù)載均衡器中得以成功應(yīng)用。TeraScaler運(yùn)行于充分定制的內(nèi)核中，包括 Socket level hash在內(nèi)的定制內(nèi)核功能極大地提高了產(chǎn)品的性能；彈性負(fù)載均衡資源管理功能的加入使得相較于普通負(fù)載均衡產(chǎn)品，TeraScaler負(fù)載均衡器更適合應(yīng)用于云計(jì)算環(huán)境中。當(dāng)網(wǎng)絡(luò)負(fù)載非常大時(shí)，負(fù)載均衡器本身可能成為整個(gè)系統(tǒng)的瓶頸，這時(shí)負(fù)載均衡的集群化就變得很有必要，這也是一個(gè)本文未能深入研究，但是未來值得研究的方向。

[1] Chiang M L, Yang C Y, and Lien S L. Kernel support for fine-grained load balancing in a web cluster providing streaming service[C]. Lecture Notes in Computer Science Volume 7439/2012: Algorithms and Architectures for Parallel Processing - 12th International Conference, Fukuoka, Japan,2012: 458-472.

[2] Yang P J. Load balancing mechanism for QoS-aware cloud computing using eucalyptus platform[OL]. http://140.118.33.1/ETD-db/ETD-search/view_etd?URN=etd-061211 1-175517, 2012.3.

[3] Hu J H, Gu J H, Sun G F,et al.. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C]. 3rd International Symposium on Parallel Architectures, Algorithms and Programming (PAAP 2010), Dalian, China, 2010: 89-96.

[4] Torvalds L,et al.. The linux kernel archives[OL]. http://www.kernel.org/, 2012.4.

[5] Cao Z, Wang Z, and Zegura E. Performance of hashing-based schemes for Internet load balancing[C]. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies(Proceedings IEEE INFOCOM 2000), Tel Aviv, Israel, 2000: 332-341.

[6] Mansour Y, Nisan N, and Tiwari P. The computational complexity of universal hashing[C]. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing,Baltimore, USA, 1990: 235-243.

[7] Microsoft Corporation. Receive-side scaling enhancements in Windows Server 2008 [OL]. http://www.microsoft.com/whdc/device/network/ndis_rss.mspx, 2012.8.

[8] Ziehau S. FreeBSD/linux kernel cross reference: sys/net/toeplitz.c[OL].http://fxr.watson.org/fxr/source/net/toeplitz.c?v=DFBSD, 2012.7.

[9] 程光, 龔儉, 丁偉, 等. 面向IP流測量的哈希算法研究[J]. 軟件學(xué)報(bào), 2005, 16(5): 652-658.Cheng Guang, Gong Jian, Ding Wei,et al.. A hash algorithm for IP flow measurement[J].Journal of Software, 2005, 16(5):652-658.

[10] Etsion Y, Tsafrir D, Kirkpatrick S,et al.. Fine grained kernel logging with KLogger: experience and insights[C].Proceedings of the 2007 EuroSys Conference,Lisbon,Portugal, 2007: 259-272.

[11] 袁清波, 趙健博, 陳明宇, 等. 多核平臺共享內(nèi)存操作系統(tǒng)性能瓶頸分析及解決[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(12):2268-2276.Yuan Qing-bo, Zhao Jian-bo, Chen Ming-yu,et al..Performance bottleneck analysis and solution of shared memory operating system on a multi-core platform[J].Journal of Computer Research and Development, 2011, 48(12):2268-2276.

[12] Umass. YouTube traces from the campus network[OL]. http://traces.cs.umass.edu/index.php/Network/Network, 2012.6.

[13] Tarreau W. Haproxy: the reliable, high performance TCP/HTTP load balancer[OL]. http://haproxy.1wt.eu/, 2012.9.

[14] Fulmer J. Siege home[OL]. http://www.joedog.org/ index/siege-home, 2012.9.

[15] VMware. Application platform[OL]. http://www.vmware.com/, 2012.9.