基于微服務架構的負載均衡優化算法及實現

經 成，謝 軍

(南昌大學數學與計算機學院，江西 南昌 330031)

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

傳統負載均衡算法包括靜態負載均衡算法和動態負載均衡算法，靜態負載均衡有無法獲取服務器實時負載的不足，動態負載均衡算法會給服務器端帶來負擔。本文針對傳統負載均衡算法存在的不足，設計了基于最低并發負載算法的動態權重負載算法。最低并發負載算法[2]面對瞬時的流量沖擊時會出現算法降級演變為輪詢算法從而導致算法失效的情況。本算法通過計算磁盤利用率的方差來衡量系統整體負載的穩定度，當磁盤利用率的方差在一個合適的范圍，算法根據服務器節點的性能計算得出系統節點的權重，當最低并發算法失效，算法升級為動態權重算法，權重大的節點被選中的概率也會更大。

1 負載均衡優化策略和實現方式

負載均衡算法有很多種，從系統角度可以分為同構系統下的負載均衡算法和異構系統下的負載均衡算法；從算法種類角度可以分為靜態負載均衡算法和動態負載均衡算法。其中靜態負載均衡算法實現簡單，系統資源消耗小，很適合同構系統集群的環境。

隨機算法負載均衡器通過隨機函數生成一個隨機數用于選擇后臺的集群節點，選擇的機器無法預測，即滿載服務器還是存在被選中的可能性，所以這種算法的負載效果比較差。

在隨機算法中，如果每臺機器的性能差異較大，則會嚴重影響負載均衡效率和集群提供服務的能力，因此在隨機算法的基礎上，負載均衡器為每個可用的服務器節點加上了權重，權重大的節點更大概率被選中，在這種算法中，可以很好地應對機器性能不會大幅度改變的異構系統，但是若是節點性能受到負載狀況的影響，則這種算法效果也不理想。

在同構系統中，靜態負載均衡算法[3]有著很好的負載效果，但是若是需要實時監測機器負載的異構系統下，由于靜態負載均衡算法無法自適應動態調整，所以靜態負載均衡算法有很大的局限性。此時異構系統下的區域分解算法和動態負載均衡算法就能滿足異構系統對于負載性能的要求。

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

(1.1)

集群系統所有機器最大處理時間為Tmax，即為處理機并行處理一個任務所要耗費的時間，計算公式如1.2所示。

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

(1.2)

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

(1.3)

公式1.3為簡易化的負載均衡平衡函數，顯然，IB等于零時系統負載近似達到平衡，大于零時，系統負載處于失衡狀態。

在上文中我們簡單討論了區域分解算法下的系統負載狀況，由于粒度較粗再加上現實環境中，系統負載還要受各種因素的干擾。因此在實際環境中，這種算法的應用場景極其有限。所以在實際環境中，我們往往選擇動態負載均衡算法。下面是常見的動態負載均衡算法。

1.最短預期延時算法是期望最小化每個任務的預期延時直到任務完成的算法，服務器Si的預期延時公式如1.4。

(1.4)

其中，C(Si)表示服務器Si的當前連接數，W(Si)表示服務器Si的權重。當服務器Sm滿足公式1.5時，新的連接請求將會被調度到Sm上。

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

(1.5)

最短預期延時算法[4]考慮了連接的預期成本，不是以當前連接數作為成本，而是以當前連接數加1作為成本，這樣就極大提高了算法的效率。最短預期延時調度算法希望在請求少的時候將請求盡可能轉發到性能高的服務器上，這種調度算法不再考慮非活動連接。這種算法有一定缺陷，在請求量比較少的時候，某個權重下的節點可能一個請求都沒有輪到。而權重大的節點卻輪到了比較多的請求。

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

2 加入動態權重的BestAvailableRule改進算法

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

圖1 BestAvailableRule負載策略流程圖Figure 1 Flow chart of BestAvailableRule load policy

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

開發用戶量/個圖2 BestAvailableRule性能圖Figure 2 BestAvailabilityRule performance diagram

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

(2.1)

其中，Pi是第i個節點的磁盤使用率[7]，DUi是第i個節點磁盤已經使用的內存空間，單位通常是GB，DTi是第i個節點磁盤的總容量，單位通常也是GB，在同構型分布式系統下，每個磁盤的DT即磁盤總容量一般來說是一樣的，但是在異構系統下，DT一般來說是不一樣的，因此，不能把機器的磁盤總容量作為衡量機器負載能力的標準。

可以由公式2.1得出的磁盤利用率作為基準計算出節點磁盤利用率的方差DX，計算公式如2.2所示。

(2.2)

其中，DX是磁盤利用率的方差，Pa是集群系統下機器的平均磁盤利用率，系統有N臺服務器。DX可以衡量系統整體負載的穩定度，當DX值越大，系統子節點磁盤利用率的離散程度就越大，此時系統整體處于失衡狀態，當DX值越小，系統子節點磁盤利用率的離散程度[8]就越小，此時系統穩定性相對而言就較強。系統磁盤平均利用率Pa計算公式如2.3所示。

(2.3)

系統磁盤平均利用率Pa可以大概衡量系統磁盤空間的使用狀況，但是可能會出現系統機器性能不平均[9]這種狀況，因此磁盤平均利用率只能作為參考因子而不能作為影響系統負載的關鍵因素。dm是系統各節點相對于磁盤平均利用率的最大差值即最大相對偏差值，當最大相對偏差值在一個合理的范圍內，平均磁盤利用率才具有較強的可參考性[10]，最大相對偏差dm計算公式如公式2.4所示。

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

(2.4)

除了服務器的磁盤空間使用離散度外，服務器的其他性能指標也是重要衡量標準。

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

(2.5)

下面Au，Bu，Cu分別表示目標服務器上的CPU利用率，內存利用率和帶寬利用率，計算第i個服務器的負載為L(Si)：

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

(2.6)

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

由以上推導過程，我們得出權重計算公式，T表示總連接數，ti表示第i個服務器的連接數，計算得出的權重為W(Si)為

(2.7)

前文介紹的最小并發算法會有很大的瓶頸，本文為服務器列表加入動態權重，讓客戶端更加智能的選取最符合性能的服務器。

在BestAvailableRule算法中，當設定的并發數小于每一個服務器的請求數時，算法策略失效，本算法的核心是當BestAvailableRule算法失效時，算法升級到動態權重負載均衡算法，動態權重負載均衡算法的核心是在客戶端中引入權重，將權重作為選擇服務器的標準。

由上述計算得出的權重公式，我們可得集群中N臺服務器的權重之和Wt，使用式2.8計算。

(2.8)

經過上述計算得到了服務器的權重之和，相加之后相當于各機器在總權重上各占了相應的一段比例。由權重和可得隨機權重Wr，使用式2.9計算。

Wr=σWt(0<σ<1)

(2.9)

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

W(Si)

(2.10)

其中i=0時權重為0，即W(S0)=0。

算法示意圖如圖3：

圖3 動態權重負載均衡算法示意圖Figure 3 Schematic diagram of dynamic weight load balancing algorithm

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

圖4 動態權重算法流程圖Figure 4 Flow chart of dynamic weight algorithm

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

3 實驗設計

本次測試目的將驗證本文所提出的負載均衡算法的可用性，為了驗證這個算法，本實驗將在高并發的實驗環境下分別測試輪詢算法，隨機選取算法，最小連接算法和本文提出的DWLB算法下系統的性能指標。

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

這里以DWLB算法在500次請求下的失敗次數為例，經過測試工具Postman設置請求數量進行測試，測試結果如下圖所示，總共發起了500次請求，請求失敗的次數為0，這可以初步驗證本算法的高穩定性。

圖5 DWLB算法在500次下失敗次數實驗結果Figure 5 Experimental results of failure times of DWLB algorithm under 500 times

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

表1 各個算法在不同并發量下的性能指標Table 1 Performance indexes of each algorithm under different concurrency

將上述數據以圖表展現出來，如圖6、圖7、圖8所示分別表示吞吐率、響應時間和失敗次數的折線圖：

并發數圖6 吞吐率對比Figure 6 Comparison of throughput rates

并發數圖7 請求響應時間對比Figure 7 Comparison of request response time

并發數圖8 請求失敗次數對比Figure 8 Comparison of number of failed requests

4 結語

以上實驗從系統吞吐率、請求響應時間、請求失敗次數三個性能指標得出了不同算法在不同請求數量級下的響應情況。

吞吐率是指服務器在單位時間內可以處理并發請求數量[15]，從圖6中可以看出這4種算法浮動比較平穩，沒有一個比較穩定的吞吐率峰值點，但是DWLB算法因為獲取了不同服務器實時的健康狀況[16]，因此在吞吐率這個性能指標，DWLB算法明顯比其他算法表現優秀。

請求響應時間是指服務器對處理請求花費的時間[17]，從圖7可以看出，輪詢算法和隨機算法因為其算法復雜度較為簡單，所以響應時間很短，DWLB算法因為其算法復雜，運算量大，所以響應時間比其他算法久點，但是差距不大，在可接受范圍之內，這說明DWLB算法不會給服務器帶來過多額外的負擔。

失敗次數是指服務器端沒有給出正確響應的請求的次數[18]，由圖8可知，輪詢算法下的失敗次數比較均衡[19]，因為每個服務器得到請求的機會都是一致的，隨機選取算法因為帶有一定的偶然性，所以造成折線圖波動較大[20]，最小連接算法因為優先把請求給空閑服務器，響應時間較短，DWLB算法因為從多個維度計算了服務器的性能，能夠最大程度地提高請求的處理正確度，所以失敗次數顯著優于其他算法，這也驗證了本文提出算法的高性能。

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