經(jīng) 成，謝 軍

(南昌大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，江西 南昌 330031)

隨著互聯(lián)網(wǎng)急速發(fā)展，IT行業(yè)日新月異，系統(tǒng)架構(gòu)的發(fā)展也在與時(shí)俱進(jìn)，當(dāng)用戶量以幾何指數(shù)飛速增長，曾經(jīng)流行很久的單體架構(gòu)[1]已經(jīng)很難應(yīng)對和處理日益增長的軟件復(fù)雜性。傳統(tǒng)的單體架構(gòu)也很難支撐如今龐大的數(shù)據(jù)量，當(dāng)同時(shí)訪問人數(shù)達(dá)到一定數(shù)額，服務(wù)器就會出現(xiàn)響應(yīng)緩慢，交互失敗等問題，甚至可能會出現(xiàn)服務(wù)器宕機(jī)等情況?；谶@種現(xiàn)狀，微服務(wù)架構(gòu)風(fēng)格應(yīng)運(yùn)而生，微服務(wù)架構(gòu)核心是面向服務(wù)，重點(diǎn)是模塊劃分，服務(wù)之間正確高效調(diào)用。微服務(wù)架構(gòu)通常都是集群的形式，但當(dāng)服務(wù)端機(jī)器從一臺提升為集群形式，其承載的訪問量得到很大程度的提升時(shí)，系統(tǒng)的復(fù)雜程度也隨之提升，此時(shí)產(chǎn)生了一個(gè)新的問題，客戶端帶著請求訪問服務(wù)端，由于服務(wù)端是一個(gè)大的集群組，請求需要知道自己該到哪個(gè)具體的機(jī)器上調(diào)取服務(wù)，這就需要讓系統(tǒng)設(shè)計(jì)者設(shè)計(jì)一套可用合理的負(fù)載均衡算法，負(fù)載均衡存在的意義就是讓請求基于該算法能夠知道去哪臺機(jī)器獲取資源。如果負(fù)載均衡算法高效可用，就可以大幅度提升系統(tǒng)提供服務(wù)的能力。

傳統(tǒng)負(fù)載均衡算法包括靜態(tài)負(fù)載均衡算法和動態(tài)負(fù)載均衡算法，靜態(tài)負(fù)載均衡有無法獲取服務(wù)器實(shí)時(shí)負(fù)載的不足，動態(tài)負(fù)載均衡算法會給服務(wù)器端帶來負(fù)擔(dān)。本文針對傳統(tǒng)負(fù)載均衡算法存在的不足，設(shè)計(jì)了基于最低并發(fā)負(fù)載算法的動態(tài)權(quán)重負(fù)載算法。最低并發(fā)負(fù)載算法[2]面對瞬時(shí)的流量沖擊時(shí)會出現(xiàn)算法降級演變?yōu)檩喸兯惴◤亩鴮?dǎo)致算法失效的情況。本算法通過計(jì)算磁盤利用率的方差來衡量系統(tǒng)整體負(fù)載的穩(wěn)定度，當(dāng)磁盤利用率的方差在一個(gè)合適的范圍，算法根據(jù)服務(wù)器節(jié)點(diǎn)的性能計(jì)算得出系統(tǒng)節(jié)點(diǎn)的權(quán)重，當(dāng)最低并發(fā)算法失效，算法升級為動態(tài)權(quán)重算法，權(quán)重大的節(jié)點(diǎn)被選中的概率也會更大。

1 負(fù)載均衡優(yōu)化策略和實(shí)現(xiàn)方式

負(fù)載均衡算法有很多種，從系統(tǒng)角度可以分為同構(gòu)系統(tǒng)下的負(fù)載均衡算法和異構(gòu)系統(tǒng)下的負(fù)載均衡算法；從算法種類角度可以分為靜態(tài)負(fù)載均衡算法和動態(tài)負(fù)載均衡算法。其中靜態(tài)負(fù)載均衡算法實(shí)現(xiàn)簡單，系統(tǒng)資源消耗小，很適合同構(gòu)系統(tǒng)集群的環(huán)境。

隨機(jī)算法負(fù)載均衡器通過隨機(jī)函數(shù)生成一個(gè)隨機(jī)數(shù)用于選擇后臺的集群節(jié)點(diǎn)，選擇的機(jī)器無法預(yù)測，即滿載服務(wù)器還是存在被選中的可能性，所以這種算法的負(fù)載效果比較差。

在隨機(jī)算法中，如果每臺機(jī)器的性能差異較大，則會嚴(yán)重影響負(fù)載均衡效率和集群提供服務(wù)的能力，因此在隨機(jī)算法的基礎(chǔ)上，負(fù)載均衡器為每個(gè)可用的服務(wù)器節(jié)點(diǎn)加上了權(quán)重，權(quán)重大的節(jié)點(diǎn)更大概率被選中，在這種算法中，可以很好地應(yīng)對機(jī)器性能不會大幅度改變的異構(gòu)系統(tǒng)，但是若是節(jié)點(diǎn)性能受到負(fù)載狀況的影響，則這種算法效果也不理想。

在同構(gòu)系統(tǒng)中，靜態(tài)負(fù)載均衡算法[3]有著很好的負(fù)載效果，但是若是需要實(shí)時(shí)監(jiān)測機(jī)器負(fù)載的異構(gòu)系統(tǒng)下，由于靜態(tài)負(fù)載均衡算法無法自適應(yīng)動態(tài)調(diào)整，所以靜態(tài)負(fù)載均衡算法有很大的局限性。此時(shí)異構(gòu)系統(tǒng)下的區(qū)域分解算法和動態(tài)負(fù)載均衡算法就能滿足異構(gòu)系統(tǒng)對于負(fù)載性能的要求。

異構(gòu)系統(tǒng)下的簡易化區(qū)域分解算法是將計(jì)算域分解為若干子域，分別求解再進(jìn)行綜合的一種計(jì)算方法。此種方法分解了計(jì)算過程，加快了計(jì)算速度，使總體解更符合實(shí)際，并有利于采用并行計(jì)算，加快運(yùn)算速度。在異構(gòu)系統(tǒng)下，由于每個(gè)系統(tǒng)的獨(dú)特性，因此我們不能歸一化處理機(jī)器狀態(tài)，假設(shè)系統(tǒng)有N個(gè)處理機(jī)，這N個(gè)處理機(jī)完成一個(gè)時(shí)間步的時(shí)間為Ti，則處理機(jī)平均計(jì)算時(shí)間Ta，Ta的計(jì)算公式如1.1所示。

(1.1)

集群系統(tǒng)所有機(jī)器最大處理時(shí)間為Tmax，即為處理機(jī)并行處理一個(gè)任務(wù)所要耗費(fèi)的時(shí)間，計(jì)算公式如1.2所示。

Tmax=max{Ti}(0≤i≤N-1)

(1.2)

由以上步驟可得負(fù)載均衡函數(shù)，IB為負(fù)載均衡臨界值，計(jì)算公式如1.3所示。

(1.3)

公式1.3為簡易化的負(fù)載均衡平衡函數(shù)，顯然，IB等于零時(shí)系統(tǒng)負(fù)載近似達(dá)到平衡，大于零時(shí)，系統(tǒng)負(fù)載處于失衡狀態(tài)。

在上文中我們簡單討論了區(qū)域分解算法下的系統(tǒng)負(fù)載狀況，由于粒度較粗再加上現(xiàn)實(shí)環(huán)境中，系統(tǒng)負(fù)載還要受各種因素的干擾。因此在實(shí)際環(huán)境中，這種算法的應(yīng)用場景極其有限。所以在實(shí)際環(huán)境中，我們往往選擇動態(tài)負(fù)載均衡算法。下面是常見的動態(tài)負(fù)載均衡算法。

1.最短預(yù)期延時(shí)算法是期望最小化每個(gè)任務(wù)的預(yù)期延時(shí)直到任務(wù)完成的算法，服務(wù)器Si的預(yù)期延時(shí)公式如1.4。

(1.4)

其中，C(Si)表示服務(wù)器Si的當(dāng)前連接數(shù)，W(Si)表示服務(wù)器Si的權(quán)重。當(dāng)服務(wù)器Sm滿足公式1.5時(shí)，新的連接請求將會被調(diào)度到Sm上。

(C(Sm)+1)/W(Sm))=min{(C(Si)+1)/W(Si)}(i=0,1,2,…,n-1)

(1.5)

最短預(yù)期延時(shí)算法[4]考慮了連接的預(yù)期成本，不是以當(dāng)前連接數(shù)作為成本，而是以當(dāng)前連接數(shù)加1作為成本，這樣就極大提高了算法的效率。最短預(yù)期延時(shí)調(diào)度算法希望在請求少的時(shí)候?qū)⒄埱蟊M可能轉(zhuǎn)發(fā)到性能高的服務(wù)器上，這種調(diào)度算法不再考慮非活動連接。這種算法有一定缺陷，在請求量比較少的時(shí)候，某個(gè)權(quán)重下的節(jié)點(diǎn)可能一個(gè)請求都沒有輪到。而權(quán)重大的節(jié)點(diǎn)卻輪到了比較多的請求。

2.最低并發(fā)策略(BestAvailableRule)是一種動態(tài)、智能的負(fù)載均衡算法，主要是根據(jù)節(jié)點(diǎn)的當(dāng)前連接數(shù)來決定將請求發(fā)送至哪個(gè)節(jié)點(diǎn)。當(dāng)服務(wù)器集群性能平均，每臺服務(wù)器提供服務(wù)的能力相差不大時(shí)，我們往往采用RoundRobinRule負(fù)載策略，即輪詢策略，但是現(xiàn)實(shí)情況中，服務(wù)器性能有好有壞，性能不均勻，輪詢算法就顯得極其不合理，不合理的負(fù)載均衡算法會極大影響服務(wù)端提供服務(wù)的效率和能力。最低并發(fā)策略就很好地考慮服務(wù)器端性能，并發(fā)數(shù)是其衡量的重要指標(biāo)，該策略會將請求轉(zhuǎn)發(fā)至并發(fā)數(shù)最小的服務(wù)器，這種策略對服務(wù)器有很好的保護(hù)功能。

2 加入動態(tài)權(quán)重的BestAvailableRule改進(jìn)算法

上文提及的BestAvailableRule[5]算法可以一定程度上解決因服務(wù)器性能不均導(dǎo)致負(fù)載不平衡的問題。但是當(dāng)并發(fā)高到一種程度，服務(wù)器可能會出現(xiàn)服務(wù)降級，服務(wù)響應(yīng)時(shí)間延長等問題，BestAvailableRule策略一定程度地維護(hù)了服務(wù)器集群的整體性能，該策略的流程圖如下所示：

圖1 BestAvailableRule負(fù)載策略流程圖Figure 1 Flow chart of BestAvailableRule load policy

通過上述BestAvailableRule負(fù)載策略流程圖和源碼可知，BestAvailableRule策略關(guān)鍵在于找取并發(fā)數(shù)最小的服務(wù)器，這種算法性能會隨著并發(fā)量極速升高而降低，當(dāng)并發(fā)量很高時(shí)，BestAvailableRule算法策略性能將會下降，慢慢趨近于輪詢算法[6]，該算法策略平均響應(yīng)時(shí)間隨著并發(fā)量的提升如下圖所示，歸納該圖數(shù)據(jù)我們可以知道，當(dāng)我們定義的并發(fā)連接數(shù)小于全部的服務(wù)器并發(fā)連接數(shù)時(shí)，此時(shí)就沒有最優(yōu)的可用服務(wù)，這個(gè)時(shí)候該算法會發(fā)生性能下滑，并演變成輪詢負(fù)載均衡算法。因此本文在最小并發(fā)策略的基礎(chǔ)上加入了權(quán)重，改進(jìn)了該算法，利用動態(tài)權(quán)重來讓負(fù)載均衡策略在高并發(fā)場景下仍然可以高效平穩(wěn)地運(yùn)行。

開發(fā)用戶量/個(gè)圖2 BestAvailableRule性能圖Figure 2 BestAvailabilityRule performance diagram

一般來說，磁盤空間使用率是反映負(fù)載節(jié)點(diǎn)存儲空間剩余容納量的最直觀表現(xiàn)，也是提供服務(wù)的子節(jié)點(diǎn)負(fù)載能力的關(guān)鍵衡量標(biāo)準(zhǔn)。通過磁盤利用率，我們可以分析出節(jié)點(diǎn)的空間使用情況和當(dāng)前存儲空間下的負(fù)載能力。磁盤空間利用率是影響負(fù)載均衡的重要因素?？梢杂霉?.1表示磁盤空間利用率，其中Pi表示編號為i的節(jié)點(diǎn)的磁盤利用率。

(2.1)

其中，Pi是第i個(gè)節(jié)點(diǎn)的磁盤使用率[7]，DUi是第i個(gè)節(jié)點(diǎn)磁盤已經(jīng)使用的內(nèi)存空間，單位通常是GB，DTi是第i個(gè)節(jié)點(diǎn)磁盤的總?cè)萘?，單位通常也是GB，在同構(gòu)型分布式系統(tǒng)下，每個(gè)磁盤的DT即磁盤總?cè)萘恳话銇碚f是一樣的，但是在異構(gòu)系統(tǒng)下，DT一般來說是不一樣的，因此，不能把機(jī)器的磁盤總?cè)萘孔鳛楹饬繖C(jī)器負(fù)載能力的標(biāo)準(zhǔn)。

可以由公式2.1得出的磁盤利用率作為基準(zhǔn)計(jì)算出節(jié)點(diǎn)磁盤利用率的方差DX，計(jì)算公式如2.2所示。

(2.2)

其中，DX是磁盤利用率的方差，Pa是集群系統(tǒng)下機(jī)器的平均磁盤利用率，系統(tǒng)有N臺服務(wù)器。DX可以衡量系統(tǒng)整體負(fù)載的穩(wěn)定度，當(dāng)DX值越大，系統(tǒng)子節(jié)點(diǎn)磁盤利用率的離散程度就越大，此時(shí)系統(tǒng)整體處于失衡狀態(tài)，當(dāng)DX值越小，系統(tǒng)子節(jié)點(diǎn)磁盤利用率的離散程度[8]就越小，此時(shí)系統(tǒng)穩(wěn)定性相對而言就較強(qiáng)。系統(tǒng)磁盤平均利用率Pa計(jì)算公式如2.3所示。

(2.3)

系統(tǒng)磁盤平均利用率Pa可以大概衡量系統(tǒng)磁盤空間的使用狀況，但是可能會出現(xiàn)系統(tǒng)機(jī)器性能不平均[9]這種狀況，因此磁盤平均利用率只能作為參考因子而不能作為影響系統(tǒng)負(fù)載的關(guān)鍵因素。dm是系統(tǒng)各節(jié)點(diǎn)相對于磁盤平均利用率的最大差值即最大相對偏差值，當(dāng)最大相對偏差值在一個(gè)合理的范圍內(nèi)，平均磁盤利用率才具有較強(qiáng)的可參考性[10]，最大相對偏差dm計(jì)算公式如公式2.4所示。

dm=max{|pi-pa|i=0，1，2，…,N}

(2.4)

除了服務(wù)器的磁盤空間使用離散度外，服務(wù)器的其他性能指標(biāo)也是重要衡量標(biāo)準(zhǔn)。

若是要計(jì)算出服務(wù)器端的權(quán)重，服務(wù)器的性能指標(biāo)是其重要參考依據(jù)[11]，當(dāng)上文中的磁盤利用率的方差在正常范圍內(nèi)，即系統(tǒng)處于相對平衡狀態(tài)[12]。當(dāng)系統(tǒng)失衡時(shí)，斷路器被觸發(fā)。已知系統(tǒng)有N臺服務(wù)器，令Si表示服務(wù)器集群中第i個(gè)服務(wù)器，A表示服務(wù)器的CPU主頻，B表示內(nèi)存，C表示帶寬，計(jì)算第i個(gè)性能的服務(wù)器的性能指標(biāo)X(Si)為：

(2.5)

下面Au，Bu，Cu分別表示目標(biāo)服務(wù)器上的CPU利用率，內(nèi)存利用率和帶寬利用率，計(jì)算第i個(gè)服務(wù)器的負(fù)載為L(Si)：

L(Si)=αAui+βBui+γCui

(2.6)

其中α，β，γ是影響因子系數(shù)且滿足α+β+γ=1。

由以上推導(dǎo)過程，我們得出權(quán)重計(jì)算公式，T表示總連接數(shù)，ti表示第i個(gè)服務(wù)器的連接數(shù)，計(jì)算得出的權(quán)重為W(Si)為

(2.7)

前文介紹的最小并發(fā)算法會有很大的瓶頸，本文為服務(wù)器列表加入動態(tài)權(quán)重，讓客戶端更加智能的選取最符合性能的服務(wù)器。

在BestAvailableRule算法中，當(dāng)設(shè)定的并發(fā)數(shù)小于每一個(gè)服務(wù)器的請求數(shù)時(shí)，算法策略失效，本算法的核心是當(dāng)BestAvailableRule算法失效時(shí)，算法升級到動態(tài)權(quán)重負(fù)載均衡算法，動態(tài)權(quán)重負(fù)載均衡算法的核心是在客戶端中引入權(quán)重，將權(quán)重作為選擇服務(wù)器的標(biāo)準(zhǔn)。

由上述計(jì)算得出的權(quán)重公式，我們可得集群中N臺服務(wù)器的權(quán)重之和Wt，使用式2.8計(jì)算。

(2.8)

經(jīng)過上述計(jì)算得到了服務(wù)器的權(quán)重之和，相加之后相當(dāng)于各機(jī)器在總權(quán)重上各占了相應(yīng)的一段比例。由權(quán)重和可得隨機(jī)權(quán)重Wr，使用式2.9計(jì)算。

Wr=σWt(0<σ<1)

(2.9)

其中σ是隨機(jī)系數(shù)。若隨機(jī)權(quán)重滿足式2.10，說明第(i+1)臺機(jī)器被選中。

W(Si)

(2.10)

其中i=0時(shí)權(quán)重為0，即W(S0)=0。

算法示意圖如圖3：

圖3 動態(tài)權(quán)重負(fù)載均衡算法示意圖Figure 3 Schematic diagram of dynamic weight load balancing algorithm

由上圖可知，服務(wù)器權(quán)重越高，在線段上的占的長度越長，被隨機(jī)數(shù)選中的概率越大。該算法完整的流程圖如下圖所示：

圖4 動態(tài)權(quán)重算法流程圖Figure 4 Flow chart of dynamic weight algorithm

通過以上流程圖可知，優(yōu)化后的算法首先接收到用戶的請求，根據(jù)用戶請求內(nèi)容分析出功能所屬的微服務(wù)鏈，根據(jù)微服務(wù)鏈確定該鏈上的微服務(wù)類型以及他們的依賴關(guān)系，再借助微服務(wù)鏈中的數(shù)據(jù)傳輸信息[13]，負(fù)載均衡器對系統(tǒng)中的實(shí)例進(jìn)行遍歷計(jì)算，尋找出所得代價(jià)最小的實(shí)例組合。當(dāng)并發(fā)量在一定范圍內(nèi)，算法的邏輯是選取最小并發(fā)處理機(jī)，當(dāng)并發(fā)量提高時(shí)，算法智能的提升為動態(tài)權(quán)重負(fù)載均衡算法[14]。算法維持了邏輯的完整性和嚴(yán)謹(jǐn)性，當(dāng)遇到請求的大量沖擊時(shí)，本算法也能維持其高可用性。

3 實(shí)驗(yàn)設(shè)計(jì)

本次測試目的將驗(yàn)證本文所提出的負(fù)載均衡算法的可用性，為了驗(yàn)證這個(gè)算法，本實(shí)驗(yàn)將在高并發(fā)的實(shí)驗(yàn)環(huán)境下分別測試輪詢算法，隨機(jī)選取算法，最小連接算法和本文提出的DWLB算法下系統(tǒng)的性能指標(biāo)。

本實(shí)驗(yàn)利用壓力測試工具siege和Postman模擬了100，500，1000，1500，2000，3000，4000，5000等不同請求數(shù)量的并發(fā)場景，分別對比了Ribbon自帶的輪詢調(diào)度算法、隨機(jī)選取算法、最小連接算法以及本文提出的DWLB算法，選擇了平均響應(yīng)時(shí)間、吞吐率和失敗次數(shù)這三個(gè)指標(biāo)作為算法評估指標(biāo)。

這里以DWLB算法在500次請求下的失敗次數(shù)為例，經(jīng)過測試工具Postman設(shè)置請求數(shù)量進(jìn)行測試，測試結(jié)果如下圖所示，總共發(fā)起了500次請求，請求失敗的次數(shù)為0，這可以初步驗(yàn)證本算法的高穩(wěn)定性。

圖5 DWLB算法在500次下失敗次數(shù)實(shí)驗(yàn)結(jié)果Figure 5 Experimental results of failure times of DWLB algorithm under 500 times

總的實(shí)驗(yàn)結(jié)果如表1所示，展示了不同算法在不同請求數(shù)量下的性能數(shù)據(jù)。其中吞吐率單位是兆每秒(Mb/s)，響應(yīng)時(shí)間單位是秒(s)，失敗次數(shù)單位是1，為了顯示簡潔，依次用A、B、C、D代替輪詢算法、隨機(jī)選取算法、最小連接算法、DWLB算法，用1、2、3代替吞吐率、響應(yīng)時(shí)間、失敗次數(shù)，例如用B3表示最小連接算法下的失敗次數(shù)。

表1 各個(gè)算法在不同并發(fā)量下的性能指標(biāo)Table 1 Performance indexes of each algorithm under different concurrency

將上述數(shù)據(jù)以圖表展現(xiàn)出來，如圖6、圖7、圖8所示分別表示吞吐率、響應(yīng)時(shí)間和失敗次數(shù)的折線圖：

并發(fā)數(shù)圖6 吞吐率對比Figure 6 Comparison of throughput rates

并發(fā)數(shù)圖7 請求響應(yīng)時(shí)間對比Figure 7 Comparison of request response time

并發(fā)數(shù)圖8 請求失敗次數(shù)對比Figure 8 Comparison of number of failed requests

4 結(jié)語

以上實(shí)驗(yàn)從系統(tǒng)吞吐率、請求響應(yīng)時(shí)間、請求失敗次數(shù)三個(gè)性能指標(biāo)得出了不同算法在不同請求數(shù)量級下的響應(yīng)情況。

吞吐率是指服務(wù)器在單位時(shí)間內(nèi)可以處理并發(fā)請求數(shù)量[15]，從圖6中可以看出這4種算法浮動比較平穩(wěn)，沒有一個(gè)比較穩(wěn)定的吞吐率峰值點(diǎn)，但是DWLB算法因?yàn)楂@取了不同服務(wù)器實(shí)時(shí)的健康狀況[16]，因此在吞吐率這個(gè)性能指標(biāo)，DWLB算法明顯比其他算法表現(xiàn)優(yōu)秀。

請求響應(yīng)時(shí)間是指服務(wù)器對處理請求花費(fèi)的時(shí)間[17]，從圖7可以看出，輪詢算法和隨機(jī)算法因?yàn)槠渌惴◤?fù)雜度較為簡單，所以響應(yīng)時(shí)間很短，DWLB算法因?yàn)槠渌惴◤?fù)雜，運(yùn)算量大，所以響應(yīng)時(shí)間比其他算法久點(diǎn)，但是差距不大，在可接受范圍之內(nèi)，這說明DWLB算法不會給服務(wù)器帶來過多額外的負(fù)擔(dān)。

失敗次數(shù)是指服務(wù)器端沒有給出正確響應(yīng)的請求的次數(shù)[18]，由圖8可知，輪詢算法下的失敗次數(shù)比較均衡[19]，因?yàn)槊總€(gè)服務(wù)器得到請求的機(jī)會都是一致的，隨機(jī)選取算法因?yàn)閹в幸欢ǖ呐既恍裕栽斐烧劬€圖波動較大[20]，最小連接算法因?yàn)閮?yōu)先把請求給空閑服務(wù)器，響應(yīng)時(shí)間較短，DWLB算法因?yàn)閺亩鄠€(gè)維度計(jì)算了服務(wù)器的性能，能夠最大程度地提高請求的處理正確度，所以失敗次數(shù)顯著優(yōu)于其他算法，這也驗(yàn)證了本文提出算法的高性能。

DWLB算法雖然在響應(yīng)時(shí)間稍遜于其他算法，但是在吞吐率和失敗次數(shù)性能明顯優(yōu)于其他算法，并且響應(yīng)時(shí)間跟其他算法的差距也在接受范圍之內(nèi)，因此經(jīng)過實(shí)驗(yàn)證明，本文提出的負(fù)載均衡算法具有高可行性。