在現(xiàn)代分布式應(yīng)用中，服務(wù)請求是由物理機或虛擬機組成的 server 池進行處理的。 通常，server 池規(guī)模巨大且服務(wù)容量各不相同，受網(wǎng)絡(luò)、內(nèi)存、CPU、下游服務(wù)等各種因素影響，一個 server 的服務(wù)容量始終處于動態(tài)變動和趨于穩(wěn)定的狀態(tài)，如何設(shè)計和實現(xiàn)這種系統(tǒng)的負載均衡算法是一個極具挑戰(zhàn)的難題。

自適應(yīng)負載均衡的需求背景

負載均衡有兩個主要目標：

• 保持較短的請求響應(yīng)時間和較小的請求阻塞概率；

• 負載均衡算法的 overhead 在可控級別，不占用過多的 CPU 、網(wǎng)絡(luò)等資源。

自適應(yīng)負載均衡是指無論系統(tǒng)處于空閑、穩(wěn)定還是繁忙狀態(tài)，負載均衡算法都會自動評估系統(tǒng)的服務(wù)能力，進行合理的流量分配，使整個系統(tǒng)始終保持較好的性能，不產(chǎn)生饑餓或者過載、宕機。

這種算法對于現(xiàn)在的電商系統(tǒng)、數(shù)據(jù)中心、云計算等領(lǐng)域都很有必要，使用自適應(yīng)負載均衡能夠更合理的利用資源，提高性能。

為了避免這種情況發(fā)生，我們可能會想到一種常用的辦法：在服務(wù)上線前提前進行壓測，使用壓測的容量作為限流值，當線上服務(wù)的請求速率大于限流值的時候，服務(wù)拒絕新到的服務(wù)，從而保障服務(wù)始終可用。但是這種方式也存在問題：壓測時測試的容量進行限流通常會趨于保守，不能充分發(fā)揮異構(gòu)系統(tǒng)的全部性能；也無法智能地應(yīng)對由于網(wǎng)絡(luò)、下游服務(wù)變化而導(dǎo)致的容量下降等問題，系統(tǒng)仍然存在宕機風(fēng)險。

因此，我們需要具備自適應(yīng)能力的負載均衡算法，來更好地進行流量分配調(diào)度以及穩(wěn)定性保障，追求極致性能，挑戰(zhàn)大促等場景下的流量洪峰。

結(jié)合中間件性能挑戰(zhàn)賽的賽題

我們結(jié)合「第五屆中間件性能挑戰(zhàn)賽」中的初賽場景，來一起探討一下設(shè)計和實現(xiàn)一個自適應(yīng)的負載均衡的基本思路。

本次挑戰(zhàn)賽的場景由施壓程序(阿里云性能測試PTS)、服務(wù)調(diào)用方(Consumer)和三個規(guī)格不同的服務(wù)提供方(Provider) 組成。在評測過程中，每個程序都部署在不同的物理機上，以避免因 CPU、網(wǎng)絡(luò)資源的競爭，導(dǎo)致評測程序抖動，影響最終評測成績。

Becnhmarker 負責請求 Consumer, Consumer 收到請求后，從三臺物理規(guī)格不同、服務(wù)響應(yīng)時間和最大并發(fā)都不同的 Provider 中選擇一個進行調(diào)用并返回結(jié)果。選擇哪一個 Provider 進行調(diào)用的流程就是本次挑戰(zhàn)賽需要實現(xiàn)的負載均衡算法。

為了簡化環(huán)境部署和提升性能，本次挑戰(zhàn)賽沒有使用服務(wù)注冊和發(fā)現(xiàn)機制。三個 Provider 對應(yīng)的 URL 都已經(jīng)被直接配置在了 Consumer 中，選手在開發(fā)和測試時可直接通過 Provider-small 等 hostname 訪問相應(yīng)的 Provider。

賽題分析

題目描述很簡單，不考慮 Consumer 直接拒絕的情況下，場景可以簡化為 3 選 1 的問題，但如何進行這個決策則是本次挑戰(zhàn)賽考察的難點和重點。

官方題目組提供了 Random 算法作為默認實現(xiàn)：從 3 個 Provider 中隨機取任意一個。對于單 dispatcher （在本次賽題中是 Consumer) 同構(gòu)系統(tǒng)的場景，Random可以達到漸近負載均衡， 每個 Provider 接收到的總請求數(shù)接近。但是對于多 dispatcher 或異構(gòu)系統(tǒng)而言，Random 算法由于缺少全局狀態(tài)，無法保證全局隨機，極端條件下，多個 dispatcher 可能將請求同時分配到一臺 Provider 上，導(dǎo)致系統(tǒng)存在服務(wù)過載和宕機的風(fēng)險；異構(gòu)系統(tǒng)中，不同 Provider 服務(wù)容量實際是不同的，即使每個 Provider 請求速率相同也會產(chǎn)生空閑、穩(wěn)定、過載等不同的服務(wù)狀態(tài)，無法實現(xiàn)最優(yōu)流量分配，更不能做到響應(yīng)時間最小。顯而易見，Random 并不是符合賽題要求的自適應(yīng)算法。

那么，如何實現(xiàn)自適應(yīng)負載均衡呢？接下來我們將利用題目給出的條件由淺入深的描述這個算法的設(shè)計過程。

自適應(yīng)算法首先要解決如何對服務(wù)進行容量評估的問題。

本次比賽按照硬件規(guī)格不同，Provider 被分為 small、medium、和 large 三種，CPU 和內(nèi)存對應(yīng)的比例為 1:2:3 。在評測過程中，每個 Provider 的處理能力都會動態(tài)變化，主要體現(xiàn)在單次響應(yīng)時間的變化和允許的最大的并發(fā)數(shù)上。來自 Consumer 的請求速率過快時， Provider 端新到的請求會排隊等待處理，當排隊線程數(shù)和工作線程數(shù)量之和達到最大線程數(shù)時，Provider 返回線程池用盡異常。在算法的實現(xiàn)和調(diào)優(yōu)過程中，應(yīng)該盡量避免產(chǎn)生線程池異常，減少排隊。如何結(jié)合好程序和硬件的限制，區(qū)分出不同階段的瓶頸，做出符合實際的容量評估是賽題的第一個難點。對于本次題目所采用的參數(shù)和變化過程，僅憑現(xiàn)有的理論和實踐很難達到最優(yōu)，所以需要選手充分理解題意和各參數(shù)配置，設(shè)計出更適合實際場景的算法。

第二個需要考慮的問題是如何應(yīng)用容量評估結(jié)果，即如何維護代表 Provider 服務(wù)能力的狀態(tài)，又如何在選擇 Provider 階段根據(jù)這些狀態(tài)進行決策？

傳統(tǒng)的單 Dispatcher 負載均衡模型由一個 Dispatcher 維護所有 Provider 的狀態(tài)，在同構(gòu)系統(tǒng)中，這種方式能夠達到漸進最優(yōu)負載均衡。但是它存在的問題也很明顯：單 Dispatcher 性能存在天然瓶頸，可擴容性較差，當 Provider 數(shù)量成倍上升時，Dispatcher 需要維護的狀態(tài)也在成倍上升，通信成本也在上升。本次挑戰(zhàn)賽中為了降低難度，沒有基于多 Dispatcher 模型構(gòu)建題目，但多 Dispatcher 、多 Provider 才是 Dubbo 等微服務(wù)框架在實際生產(chǎn)環(huán)境中最常見的情況。因此，若能實現(xiàn)高性能且可擴展性良好的均衡算法，會是一個不錯的加分項。

第三點是輔助接口的使用。為了不限制算法設(shè)計思路，賽題提供了多個可能用到的輔助接口，包括雙向通信、Provider 限流等支持。但是這些接口都是非必選項，是否使用這些接口取決于算法實現(xiàn)的需要。

在評測環(huán)境中，任意一個 Provider 服務(wù)處理速率都小于評測程序的請求速率。三個 Provider 總的處理速率會在請求速率上下浮動。最終成績由請求成功數(shù)和最大 TPS 組成，失敗的請求不計入成績。對于這個限制，可以有兩種解讀方式，一是為了保證服務(wù)不嚴重過載，可以適當拒絕請求。第二點是需要充分利用每個 Provider 的服務(wù)容量，保證性能最優(yōu)的 Provider 請求數(shù)合理，適當?shù)倪^載也是允許的。

以上僅作為一個主要的算法設(shè)計思路，優(yōu)秀的負載均衡算法在工程上的實現(xiàn)也是很關(guān)鍵的一點，需要選取合適的數(shù)據(jù)結(jié)構(gòu)，充分利用好內(nèi)存和 CPU，壓榨出比賽環(huán)境的每一點性能。當然，評測成績并不代表一切，良好的代碼結(jié)構(gòu)、編碼風(fēng)格以及通用性，也在最終初賽成績中占據(jù)很大比例。