網(wǎng)絡(luò)競價系統(tǒng)中負載均衡技術(shù)優(yōu)化

孫建崗, 張樹東

(首都師范大學 信息工程學院,北京 100048)

?

網(wǎng)絡(luò)競價系統(tǒng)中負載均衡技術(shù)優(yōu)化

孫建崗, 張樹東

(首都師范大學 信息工程學院,北京 100048)

在網(wǎng)絡(luò)系統(tǒng)正常運行中，如何確保數(shù)據(jù)準確實時高效的傳輸變得越來越重要，在一些高并發(fā)、高吞吐的服務(wù)中，確保每個事務(wù)功能正常運轉(zhuǎn)越來越重要；系統(tǒng)的負載是否均衡是確保整個系統(tǒng)能否完整工作的關(guān)鍵，現(xiàn)在有很多負載均衡算法旨在使得每個服務(wù)器的負載趨于相等，可以歸納為靜態(tài)均衡方法和動態(tài)均衡方法；考慮到影響服務(wù)器的負載有多重因數(shù)，結(jié)合貪心算法作出相對合理的負載均衡策略，應(yīng)用到本次競價系統(tǒng)中對比以前的平衡策略，通過比較可以得出多衡量指標的綜合考慮會提高負載均衡的性能，對網(wǎng)絡(luò)競價系統(tǒng)能夠起到更優(yōu)化的作用。

確保數(shù)據(jù)準確實時高效的傳輸；高并發(fā)、高吞吐；負載均衡策略；多衡量指標；網(wǎng)絡(luò)競價系統(tǒng)

0 引言

在用戶高訪問量、高并發(fā)和服務(wù)資源不斷膨脹的情況下，Web服務(wù)器的響應(yīng)緩慢遲延等問題[1]已成為了網(wǎng)絡(luò)服務(wù)質(zhì)量的主要表現(xiàn)之一。網(wǎng)絡(luò)集群服務(wù)器以其良好的可擴展性、高可靠性、高性價比的特點，為Web服務(wù)器系統(tǒng)帶來了新的解決方案[2]。負載均衡技術(shù)是解決這類問題的核心技術(shù)，其應(yīng)用保護了多臺服務(wù)器負載的均衡性，實現(xiàn)了對用戶請求進行公平合理的分配和調(diào)度，提高了系統(tǒng)自身的反應(yīng)效率和穩(wěn)定性[3]。如何確定一個合適的用戶并發(fā)量能使的系統(tǒng)的吞吐量達到最佳值是我們的一個目標[4]。在不考慮服務(wù)器執(zhí)行時間和網(wǎng)絡(luò)延時，如何確定在合適的并發(fā)量下，系統(tǒng)交易相應(yīng)時間最優(yōu)。如何確定在適應(yīng)的用戶并發(fā)量下使各個服務(wù)器的網(wǎng)絡(luò)使用情況基本平衡[5]。如何確定在適應(yīng)的用戶并發(fā)量下，使得每個數(shù)據(jù)庫服務(wù)器資源CPU利用率基本平衡。這些問題都與整個系統(tǒng)的負載均衡策略有直接的關(guān)系[6]，所以如何確定一個合適本系統(tǒng)的負載均衡是我們本次論文的最終目的。

1 一般服務(wù)器的負載均衡

當用戶通過終端進入報價系統(tǒng)時，需要的服務(wù)類型是千差萬別的，比如查看標的列表頁面，進入報價現(xiàn)場頁面，進入報價提交頁面，進入個人競價室等，這些服務(wù)對服務(wù)器的操作造成一定的壓力。如何能確定一個可靠的負載平衡策略是關(guān)鍵[7]。以前經(jīng)常用的的負載均衡的方法有靜態(tài)負載均衡技術(shù)和動態(tài)負載均衡技術(shù)兩種，靜態(tài)調(diào)度方法往往將URL依次映射成系統(tǒng)中服務(wù)器的IP，如DNS的輪詢法，但缺點明顯，隨著服務(wù)器數(shù)量和規(guī)模的增大，還有服務(wù)器類別的復(fù)雜化，很容易造成服務(wù)器的不平衡。而動態(tài)方法則是周期性采集負載信息并根據(jù)相應(yīng)的負載均衡算法轉(zhuǎn)發(fā)到有請求的服務(wù)器上處理請求信息，也會遇到明顯問題，在周期性采集負載信息的時候，如果請求太多，負載信息不能及時更新也會使得服務(wù)器的負載不均。

為了更好的選擇負載均衡策略，可以選擇一個多衡量指標的研究方案，通過各個對服務(wù)器負載有影響的因數(shù)，提出服務(wù)器負載多屬性的量化函數(shù)[8]。通過這個函數(shù)來提高系統(tǒng)中服務(wù)器的負載情況從而提高系統(tǒng)的效率和性能。首先考慮到影響服務(wù)器負載的因數(shù)有CPU的使用率，內(nèi)存的使用率，磁盤I/O的訪問率，網(wǎng)絡(luò)帶寬的使用率和存儲空間的使用大小，有人對這5個因數(shù)進行了研究，但是隨著網(wǎng)絡(luò)的發(fā)展，人們對網(wǎng)絡(luò)質(zhì)量的提高，尤其是有很多網(wǎng)絡(luò)是針對動態(tài)網(wǎng)頁和靜態(tài)網(wǎng)頁的時候，服務(wù)器其的處理數(shù)據(jù)量是大不相同的，這兩方面的多少會直接影響到服務(wù)器的響應(yīng)速度，所以本文也將服務(wù)器處理動態(tài)網(wǎng)頁的能力大小和服務(wù)器處理靜態(tài)網(wǎng)頁能力的大小作為參考的因數(shù)，重新算出一個更合理的權(quán)向量函數(shù)。

2 多衡量屬性負載均衡方法

2.1 建立衡量函數(shù)模型

對于集群中如何建立服務(wù)器的工作負載數(shù)學模型，Watts和Taylor在他們的研究中心已經(jīng)證明了線性加權(quán)法來定量描述服務(wù)器負載的有效性和準確性[9]，而且后來又有相當多的人對相關(guān)領(lǐng)域做了大量的研究工作，并且取得了很多新的進展，所以我們這次也要用這種思路來建立改進算法的數(shù)學模型。

線性輪詢的理論思路如下：各個衡量指標在總目標數(shù)值中所占的重要程度是不相同的，那么就可以根據(jù)其各自的重要性分別設(shè)定他們的系數(shù)，并將這些帶有系數(shù)的衡量指標相加，最后得到的目標總值[10]。這樣就是多衡量指標在不同情況下共同作用的結(jié)果，得到的結(jié)果能更好的反映實際情況。

因此改進后的多衡量指標負載均衡衡量的函數(shù)可以用以下公式代替：

L=K1*L(band)+K2*L(Storage)+K3*L(io)+K4*

L(cpu)+K5*L(mem)+K6*L(Static)+

K7*L(Dynamic)

(1)

此公式(1)中，L(band)表示網(wǎng)絡(luò)帶寬使用率的大小，L(Storate)表示存儲空間使用率的大小，L(io)則表示磁盤I/O訪問率的大小，L(cpu)表示CPU使用率的大小，L(mem)表示內(nèi)存使用用率的大小，L(Static)表示服務(wù)器處理靜態(tài)網(wǎng)頁能力的大小，L(Dynamic)表示服務(wù)器處理動態(tài)能力的大小，K1，K2，K3，K4，K5，K6和K7分別表示這七個變量的權(quán)值系數(shù)(并滿足K1+K2+K3+K4+K5+K6+K7=1)，用以表示各個負載度量指標對服務(wù)器負載量大小影響的強弱程度。該函數(shù)的權(quán)向量則為ω=(K1，K2，K3，K4，K5，K6，K7)。通過這個改進的方法計算每個服務(wù)器負載能力大小，由于這個方法是從多衡量指標考慮，所以相對來說更具有科學依據(jù)。

2.2 多衡量指標權(quán)向量的確定

在以往的研究中，確定權(quán)向量一般是先賦初始值，然后再根據(jù)實際情況不斷地修改來確定權(quán)向量，但是這種方法可靠性和信賴度比較低，所以本文是借鑒國外關(guān)于多屬性決策相關(guān)理論中的層次分析法來計算權(quán)向量的初始值。

層次分析法(analytic hierarchy process, AHP)是美國著名運籌學家Saaty教授于20世紀70年代末期提出的一種新的系統(tǒng)分析方法[11]。層次分析決策方法最大的優(yōu)點是可以處理定性和定量相結(jié)合的問題，可以將決策者的判斷與經(jīng)驗引入到模型中，并加以量化處理。層次分析法的出現(xiàn)給決策者解決那些難以定量描述的決策問你帶來了極大的方便，因而他是一種可以將定性和定量分析相結(jié)合的多目標決策分析方法。

它的基本思想是在分析復(fù)雜系統(tǒng)所包含的因素及相關(guān)關(guān)系的基礎(chǔ)上，把一個復(fù)雜的系統(tǒng)按支配關(guān)系分組，從而分解成各個組成因數(shù)，形成含有若干層次的有序的遞階層次結(jié)構(gòu)。層次分析法按表1的梯度理論，對每一層次的各要素兩兩比較，獲得了對應(yīng)的判斷矩陣。通過計算判斷矩陣的最大特征值以及屬于該特征值相應(yīng)的特征向量。再對特征向量進行歸一化處理，獲得了權(quán)重向量，依據(jù)此權(quán)重向量，可得到各層次中若干要素的重要性次序。同時需要確定層次中若干準則的相對重要性，然后綜合人的判斷來確定決策中各因素相對重要的排名。

在網(wǎng)絡(luò)競價系統(tǒng)中，我們列出了當用戶量增多時，在系統(tǒng)中每個服務(wù)器的負載情況各不相同，負載情況還和用戶選擇不同的服務(wù)有關(guān)系，比如提交訂單服務(wù)、修改報價服務(wù)等，但是我們羅列出了對服務(wù)器負載影響的各個因數(shù)，然后用數(shù)學的方法計算反映每一個元素的相對重要性的權(quán)重，從多個要素考慮來確定出本系統(tǒng)使用層次分析法求來的權(quán)向量[15]。對于任何復(fù)雜的衡量權(quán)重問題，都可以選擇構(gòu)造層次結(jié)構(gòu)模型，然后形成判斷矩陣，通過線性代數(shù)中的相關(guān)特征值的方法便能得到所有方案重要性的次序與權(quán)值大小，以下是重要的定義及相關(guān)定理。

定義1：若矩陣A=(aij)n×n滿足:

非負性：aij>0,?i,j∈N;

互反性：aij=1/aji，aii=1,?i,j∈N。

則稱A=(aij)n×n是n階正互反判斷矩陣。

定義2:若?i,j,k∈N，有aikakj=aij成立，則稱A=(aij)n×n為完全一致性正反判斷矩陣。

定義3:一致性指標C.I可以定義為：

(2)

其中:λmax為互反判斷矩陣A=(aij)n×n的最大特征值。

定義4:令

(3)

則陳C.R為一致性比率。其中R.I為隨機一致性指標，Saaty教授給出隨機一致性指標R.I的數(shù)值列表見表1。

表1 R.I不同階的平均隨機一致性指標

定義5：計算最大特征向量λmax：

(4)

定義6:判斷矩陣歸一化處理公式：

(5)

在定義1中，aij的值如何確定是關(guān)鍵。Saaty等人用大量實驗的方法比較了在各種不同標度下人們判斷結(jié)果的正確性，經(jīng)過無數(shù)實驗的驗證，aij的值按照1-9標度進行確定，如表2。

表2 標度取值參考表

在根據(jù)競價系統(tǒng)中現(xiàn)場的操作和回饋，我們總結(jié)出了影響性能的一些要素，并根據(jù)這些要素間的重要性，并結(jié)合Saaty教授層次分析法的理論，得到一個判斷矩陣，用a1、a2、a3、a4、a5、a6、a7分別表示網(wǎng)絡(luò)帶寬使用率、存儲空間使用率、磁盤I/O訪問率、CPU使用率、內(nèi)存使用用率、服務(wù)器處理靜態(tài)網(wǎng)頁能力和服務(wù)器處理動態(tài)能力，并更具這7個變量作為判斷矩陣的行和列，則判斷矩陣為：

由表1可知，根據(jù)值法可以得出判斷矩陣A如下：

矩陣A根據(jù)公式(5)做歸一化處理，將矩陣A轉(zhuǎn)化為A′：

矩陣經(jīng)歸一化處理后的判斷矩陣A′再按行相加得到的列向量W=(0.2,0.77,0.77,0.44,0.38,1.5,2.7)T然后對該列向量進一步對每個分量做歸一化處理，就可以得到權(quán)重向量W=(0.03,0.11,0.11,0.07,0.06,0.22,0.4)T。再結(jié)合矩陣A和公式(4)可以得出λmax=7.6，又根據(jù)表一可以查表知道一直想R.I=1.32，由公式(2)得知C.I=0.1，最后再有公式(3)可知C.R=0.07<0.1，證明判斷矩陣A滿足一致性條件，因此前面計算出來的權(quán)重向量就是能夠在競價系統(tǒng)中最終定量決定負載均衡的分量指標。

由前面公式(1)可知，對于每個服務(wù)器負載能力大小的評測就可以結(jié)合計算出來的權(quán)重向量來表示，所以最終決定服務(wù)器如何進行負載分配的表達式為：

L=0.03L(band)+0.11L(Storage)+0.11L(io)+

0.07L(cpu)+0.06L(mem)+0.22L(Static)+

0.4L(Dynamic)

由上面得到的負載量衡量函數(shù)是比較合理的，整個競價系統(tǒng)可以在實際競報價過程中通過監(jiān)測整個系統(tǒng)的運行狀態(tài)來對權(quán)向量進行微調(diào)，來提高整個系統(tǒng)的性能。

3 負載性能測試

在本次試驗中，我們針對的環(huán)境是實際應(yīng)用的競報價系統(tǒng)，在實際操作應(yīng)用過程中我們得到了一些實際數(shù)據(jù)，就是當系統(tǒng)的并發(fā)量達到1 000左右的時候，CPU的利用率會達到一個較高的使用率，用戶響應(yīng)時間拖延比較嚴重，系統(tǒng)幾乎面臨癱瘓的邊緣，而一些內(nèi)存使用率還有存儲空間的使用不是特別高。還有就是在靜態(tài)頁面和動態(tài)頁面的一些測試中，系統(tǒng)在高并發(fā)的時候，監(jiān)測到系統(tǒng)都不能達到理想的效果。出于這些原因的考慮我們得出了多衡量指標的負載均衡設(shè)計，希望可以在配置系統(tǒng)過程中，依照得出的權(quán)向量表達式去分配管理服務(wù)器負載能力。

我們通過比較的方式來對比哪一種方式會對我們的競報價系統(tǒng)更有利，在使用了多衡量指標的負載和未使用多衡量指標負載的相比較。

由圖1可知，在競價系統(tǒng)中，該改進的負載均衡算法起到了很好的效果，在相同響應(yīng)時間的情況下，使用權(quán)衡向量的服務(wù)器更能多的提高用戶并發(fā)量。

圖1 報價系統(tǒng)測試

在圖2中我們可以看出，在競價系統(tǒng)中，控制相同的響應(yīng)時間，使用權(quán)衡向量的服務(wù)器能夠提高用戶的并發(fā)量。通過實驗進行比較我們發(fā)現(xiàn)，在整個競報價系統(tǒng)中，應(yīng)用本次多衡量指標算法不僅能夠提高用戶的并能發(fā)量，同樣還可以系統(tǒng)響應(yīng)的時間，同時在軟件檢測中可以發(fā)現(xiàn)各個硬件機能都處在一個優(yōu)越的位置，性能達到最大化。

4 結(jié)言

目前，在一個實際運行的系統(tǒng)中制約系統(tǒng)有效運行的因數(shù)有很多，如何讓系統(tǒng)達到最好的性能，是我們追求的目標。查看文獻會看到有很多關(guān)于改善系統(tǒng)性能的文章，可以去分析討論相關(guān)的技術(shù)，本文也不例外，在面對競報價系統(tǒng)的缺陷，利用所學知識，得出一個系統(tǒng)而有效的科學方法來提高系統(tǒng)的性能。

本次系統(tǒng)在運行過程中我們發(fā)現(xiàn)，并發(fā)量不高，響應(yīng)時間遲緩的關(guān)鍵，是系統(tǒng)中沒有很好的對服務(wù)器那一塊做負載均衡處理。負載均衡技術(shù)又有很多種，本次文章大膽假設(shè)利用多衡量指標的方法來提高服務(wù)器的負載能力，就其中服務(wù)器處理靜態(tài)數(shù)據(jù)的能力和處理動態(tài)數(shù)據(jù)的能力加入考慮，現(xiàn)在隨著硬件技術(shù)的飛速成長，制約一個系統(tǒng)性能的瓶頸越來越推向軟件方向，所以本次的重點就是從負載決策上找到一個更合理的方法，結(jié)合國外教授的先進理論我們得出服務(wù)器基于多衡量指標的算法，從而優(yōu)化系統(tǒng)的性能。

[1] 桂勇哲，張進宇.基于覆蓋網(wǎng)絡(luò)多路徑與并行TCP的傳輸技術(shù)[J].計算機應(yīng)用，2010，30(5):1171-1175.

[2] 杜文峰，吳 真，賴力潛. 傳輸延遲感知的多路徑并發(fā)差異化路徑數(shù)據(jù)分配算法[J].通信學報，2013，34(4):149-157.

[3] 趙先明，朱伏生，唐 宏，等.TD-LTE系統(tǒng)動態(tài)資源分配算法研究[J].重慶郵電大學學報:自然科學版，2013，25(2):226-230.

[4] 楊際祥,譚國真,王榮生.并行與分布式計算動態(tài)負載均衡策略綜述[J].電子學報, 2010, 38(5): 1122-1130.

[5] 王榮生，楊際祥，王 凡. 負載均衡策略研究綜述[J]. 小型微型計算機系統(tǒng)，2010，31(8):1681-1686.

[6] 王春娟，董麗麗，賈 麗.Web集群系統(tǒng)的負載均衡算法[J].計算機工程，2010，36(2):102-104.

[7] 張玉芳，魏欽磊，趙 膺.基于負載權(quán)值的負載均衡算法[J].計算機應(yīng)用研究，2012，29(12):4711-4713.

[8] 李 新，黎文偉.一種改進的動態(tài)告警負載均衡算法[J].小型微型計算機系統(tǒng)，2013，34(7):1585-1589.

[9] 許少華，夏智偉.基于輪轉(zhuǎn)周期的動態(tài)反饋負載均衡算法[J].計算機技術(shù)與發(fā)展(ISTIC)，013，23(6):63-66.

[10] 孫峻文，周 良，丁秋林.基于退火算法的動態(tài)負載均衡研究[J].計算機科學，2013，40(5):89-92.

[11] 楊 錦，李肯立，吳 帆.異構(gòu)分布式系統(tǒng)的負載均衡調(diào)度算法[J].計算機工程，2012，38(2):166-168.

[12] 張聰萍，尹建偉.分布式文件系統(tǒng)的動態(tài)負載均衡算法[J].小型微型計算機系統(tǒng)，2011，32(7):1424-1426.

[13]DemestichasP,GeorgakopoulosA,KarvounasD,etal. 5Gonthehorizon:keychallengesfortheradio-accessnetwork[J].IEEEVehicularTechnologyMagazine, 2013,8(3).

[14]DamnjanovicA,MontojoJ,WeiYB,etal.Asurveyon3GPPheterogeneousnetworks[J].IEEEWirelessCommunications,2011,18(3).

[15]PengMG,LiangD,WeiY,etal.Self-configurationandself-optimizationinLTE-advancedheterogeneousnetworks[J].IEEECommunicationsMagazine, 2013,51(5).

[16]AndrewsJ,SinghS,YeQY,etal.AnoverviewofloadbalancinginHetNets:oldmythsandopenproblems[J].IEEEWirelessCommunications, 2014,21(2).

[17]AndroneC,PaladeT,PuschitaE,etal.Studyofco-channelcross-layerinterferenceforthedownlinkcommunicationinfemtocellnetworks[A].ProceedingsofISSCS[C].Lasi, 2011.

[18]LiZH,WangH,PanZW,etal.Jointoptimizationonloadbalancingandnetworkloadin3GPPLTEmulti-cellnetworks[A].Proceedingsof2011InternationalConferenceonWirelessCommunicationsandSignalProcessing(WCSP)[C].Nanjing,China, 2011.

[19]ShengJ,YangZ,TangLR.Anovelloadbalancingalgorithmbasedonutilityfunctionsandfuzzylogicinheterogeneouswirelessnetworks[A].ProceedingsofFSKD[C].Sichuan,China, 2012.

[20]MuozP,BarcoR,Ruiz-AviléJM,etal.Fuzzyrule-basedreinforcementlearningforloadbalancingtechniquesinenterpriseLTEfemtocells[J].IEEETransactionsonVehicularTechnology, 2013,62(5).

[21]KyuhoSon,SongC.DynamicassociationforloadbalancingandinterferenceavoIDanceinmulti-cellNetworks[J].IEEETransactionsonWirelessCommunications, 2009,8(7).

Optimization of Load Balancing Technology in Network Bidding System

Sun Jiangang, Zhang Shudong

(College of information engineering, Capital Normal University, Beijing 100048, China)

In the normal operation of network systems, how to ensure accurate data transmission in real time with high efficiency is becoming more and more important. In some high concurrency and high throughput of the service, to ensure the normal operation of each transaction function more and more important. The load balancing of the system is the key to ensure the whole system can complete the work, there are now many load balancing algorithm is designed to make each server load tends to be equal, can be divided into static load balancing method and the dynamic load balancing method. Considering the influence of server load multiple factor, combining greedy algorithm made relatively reasonable load balancing strategy, application to the bidding system in contrast to previous balance strategy, through the comparison, it can be that multi measurement index comprehensive consideration can improve the load balance of performance, the network bidding system can play a more optimal function.

To ensure accurate data transmission in real time with high efficiency; high concurrency and high throughput; load balancing strategy; multi measurement index; network bidding system

2016-04-07；

2016-05-18。

國家自然科學基金(31571563);國家科技支撐計劃項目、北京市屬高等學校創(chuàng)新團隊建設(shè)與教師職業(yè)發(fā)展計劃項目、高可靠嵌入式系統(tǒng)技術(shù)北京市工程研究中心(2013BAH19F01);國外訪學項目(067145301400)。

孫建崗(1989-)，男，山西忻州人，首都師范大學碩士研究生，主要從事數(shù)據(jù)庫系統(tǒng)及計算機應(yīng)用方向的研究。

張樹東(1969-),男，教授，博士，主要從事計算機網(wǎng)絡(luò)、分布式計算方向的研究。

1671-4598(2016)09-0237-03DOI：10.16526/j.cnki.11-4762/tp

TP

A