完爆 Best Fit，看阿里如何優(yōu)化 Sigma 在線(xiàn)調(diào)度策略節(jié)約億級(jí)成本

摘要：
2018 年“雙 11”的交易額又達(dá)到了一個(gè)歷史新高度 2135 億。相比十年前，我們的交易額增長(zhǎng)了 360 多倍，而交易峰值增長(zhǎng)了 1200 多倍。相對(duì)應(yīng)的，系統(tǒng)數(shù)呈現(xiàn)爆發(fā)式增長(zhǎng)。系統(tǒng)在支撐“雙 11”過(guò)程中的復(fù)雜度和難度呈現(xiàn)指數(shù)級(jí)形式上升趨勢(shì)。

作為阿里巴巴全集團(tuán)范圍的容器調(diào)度系統(tǒng)，Sigma 在“雙11”期間成功支撐了全集團(tuán)所有容器（交易線(xiàn)中間件、數(shù)據(jù)庫(kù)、廣告等 20 多個(gè)業(yè)務(wù)）的調(diào)配，是阿?巴巴運(yùn)維系統(tǒng)重要的底層基礎(chǔ)設(shè)施。Sigma 已經(jīng)是阿里全網(wǎng)所有機(jī)房在線(xiàn)服務(wù)管控的核心角色，管控的宿主機(jī)資源達(dá)到百萬(wàn)級(jí)，重要程度不言而喻，其算法的優(yōu)劣程度影響了集團(tuán)整體的業(yè)務(wù)穩(wěn)定性，資源利用率。

當(dāng)用戶(hù)向調(diào)度系統(tǒng)申請(qǐng)容器所需的計(jì)算資源(如 CPU 、 內(nèi)存、磁盤(pán))時(shí)，調(diào)度器負(fù)責(zé)挑選出滿(mǎn)足各項(xiàng)規(guī)格要求的物理機(jī)來(lái)部署這些容器。在相同的資源需求下，調(diào)度策略的優(yōu)劣決定著集群計(jì)算資源利用的水平。本文將簡(jiǎn)要介紹群體增強(qiáng)學(xué)習(xí)算法在調(diào)度策略?xún)?yōu)化中的應(yīng)用。

作者：
王孟昌 達(dá)摩院機(jī)器智能技術(shù)算法專(zhuān)家
韓堂 阿里巴巴集團(tuán)技術(shù)專(zhuān)家

1.計(jì)算資源調(diào)度及在線(xiàn)策略

當(dāng)用戶(hù)向 Sigma 申請(qǐng)容器所需的計(jì)算資源（如 CPU、Memory、磁盤(pán)等）時(shí)，調(diào)度器負(fù)責(zé)挑選出滿(mǎn)足各項(xiàng)規(guī)格要求的物理機(jī)來(lái)部署這些容器。通常，滿(mǎn)足各項(xiàng)要求的物理機(jī)并非唯一，且水位各不相同，不同的分配方式最終得到的分配率存在差異，因此，調(diào)度器的一項(xiàng)核心任務(wù)就是按照某一策略從眾多候選機(jī)器中挑出最合適的物理機(jī)。

在文獻(xiàn)中，計(jì)算資源調(diào)度一般被表述為矢量裝箱問(wèn)題(vector bin packing problem)，如果各應(yīng)用的容器數(shù)量事先已知（如大促場(chǎng)景），調(diào)度器可一次性為所有容器生成優(yōu)化的排布方案，此時(shí)問(wèn)題可以表述為整數(shù)規(guī)劃，可使用通用求解器或?qū)ｉT(mén)開(kāi)發(fā)的算法來(lái)求解；如果各應(yīng)用的請(qǐng)求陸續(xù)到達(dá) Sigma （如日常場(chǎng)景），調(diào)度器需要在每次請(qǐng)求到達(dá)時(shí)即時(shí)（在線(xiàn)）生成部署決策，此時(shí)問(wèn)題可表述為馬爾可夫決策過(guò)程 (Markov Decision Process, MDP)，原則上可以通過(guò)值迭代或策略迭代求得最優(yōu)策略。

最常用的調(diào)度策略包括 First-Fit (FF) 和 Best-Fit (BF)。如果使用 First-Fit算法，調(diào)度器會(huì)將容器部署到遍歷中碰到的第一個(gè)滿(mǎn)足所有要求的物理機(jī)上；而B(niǎo)est-Fit算法則會(huì)在滿(mǎn)足要求的物理機(jī)中挑選分配水位最高的機(jī)器來(lái)部署容器。對(duì)于經(jīng)典的 bin packing 問(wèn)題（即一維矢量裝箱問(wèn)題），F(xiàn)irst-Fit 和 Best-Fit 的近似比均為1.7，即二者都可保證所使用的機(jī)器數(shù)不超出最優(yōu)方案的170%；對(duì)于2維及以上的矢量裝箱問(wèn)題，理論上不存在有著明確近似比保證的多項(xiàng)式算法。當(dāng)物理機(jī)的某個(gè)資源維度明顯為瓶頸而導(dǎo)致其它資源維度普遍有剩余時(shí)，其有效維度可視為1，使用 First-Fit 或 Best-Fit 一般可以取得不錯(cuò)的分配率；而一旦瓶頸并未集中體現(xiàn)在同一維度，兩種策略的效果就要大打問(wèn)號(hào)了。

除了資源維度上的要求，實(shí)際調(diào)度中還有容災(zāi)和干擾隔離上的考慮：比如同一應(yīng)用的容器不允許全部部署到同一臺(tái)物理機(jī)上，很多應(yīng)用甚至每臺(tái)機(jī)器上只允許有一個(gè)實(shí)例；某些應(yīng)用之間還存在互斥關(guān)系（如資源爭(zhēng)搶?zhuān)?，?yán)重影響應(yīng)用的性能，因此也不允許它們被部署到同一物理機(jī)上。這些限制條件的引入，使得常用策略越發(fā)水土不服了。通過(guò)人肉反復(fù)試錯(cuò)，勉強(qiáng)扛住了多次大促建站的壓力。然而，隨著各業(yè)務(wù)的擴(kuò)張，線(xiàn)上容器的規(guī)模越來(lái)越大，資源變得越來(lái)越緊張，人肉調(diào)參的效率漸漸力不從心。

為了把調(diào)度同學(xué)從調(diào)參中解放出來(lái)，讓有限的資源扛住更大的壓力，達(dá)摩院機(jī)器智能技術(shù)實(shí)驗(yàn)室（M.I.T.）的決策智能算法團(tuán)隊(duì)和Sigma調(diào)度團(tuán)隊(duì)展開(kāi)了緊密合作，對(duì)在線(xiàn)調(diào)度策略問(wèn)題進(jìn)行了研究，并開(kāi)發(fā)了基于群體增強(qiáng)學(xué)習(xí)（SwarmRL）的算法。

2.在線(xiàn)調(diào)度模型

記當(dāng)前待部署容器的規(guī)格為向量?p∈P，為其分配資源時(shí)集群狀態(tài)為向量?s∈S?, 候選物理機(jī)的集合為?A?A，策略可表示為函數(shù)?π:S×P→A（π∈Π）。當(dāng)按策略?π 選擇物理機(jī)?a=π(s,p)來(lái)部署該容器時(shí)，該選擇的即時(shí)成本為?r(a)，集群的新?tīng)顟B(tài)?s′ 由狀態(tài)量?s?、p?以及動(dòng)作?a?共同決定，記為?s′=L(s,p,a)?；記后續(xù)到達(dá)的容器規(guī)格?p′， 對(duì)于在線(xiàn)調(diào)度，p′ 為隨機(jī)量。引入折扣系數(shù)?γ∈[0,1]，系統(tǒng)的 Bellman 方程為：

最優(yōu)調(diào)度策略可表示為：

理論上，通過(guò)隨機(jī)梯度下降，我們可以在策略空間?Π 中搜索較優(yōu)的策略，但相要更進(jìn)一步的優(yōu)化，甚至得到全局最優(yōu)策略，則需要借助其它方法，特別是當(dāng)最優(yōu)策略可能是 multi-modal 形式。

3.群體增強(qiáng)學(xué)習(xí) SwarmRL

為防止策略的優(yōu)化陷入較差的局部最優(yōu)解，同時(shí)擁有較快的收斂速度，我們基于群體增加學(xué)習(xí)的框架來(lái)設(shè)計(jì)算法。與傳統(tǒng)的增強(qiáng)學(xué)習(xí)方法相比，算法使用多個(gè) agent 來(lái)探索問(wèn)題的策略空間，且多個(gè) agent 之間存在互相學(xué)習(xí)機(jī)制，這使得算法有了跳出局部陷阱的能力。為獲取各狀態(tài)值（V^π^）的估計(jì)，一個(gè)準(zhǔn)確的 Sigma 模擬器必不可少，團(tuán)隊(duì)內(nèi)部同學(xué)基于 Sigma 的調(diào)度器開(kāi)發(fā)了“完全保真”的模擬器 Cerebro 。

算法首先隨機(jī)初始化一群 agent 的策略，針對(duì)每個(gè)策略，通過(guò)模擬器獲取相應(yīng)的的狀態(tài)值估計(jì)，記錄當(dāng)前全局最佳策略。在后續(xù)的每次迭代中，各個(gè) agent 不斷更新自身的局部最佳策略，并參照局部最佳策略與群體當(dāng)前全局最佳策略，對(duì) agent 自身的當(dāng)前策略進(jìn)行更新，再進(jìn)行模擬，獲取新策略的狀態(tài)值估計(jì)，更新全局最佳策略。如此循環(huán)，直到滿(mǎn)足收斂條件。

在各個(gè) agent 狀態(tài)值的估計(jì)中，樣本（多個(gè)隨機(jī)抽取的集群快照和擴(kuò)容請(qǐng)求序列）和各 agent 的當(dāng)前策略被輸入模擬器 Cerebro，追蹤模擬時(shí)集群狀態(tài)的軌跡，即可得到該軌跡的總成本；基于多個(gè)樣本的軌跡總成本求平均，即得到相應(yīng)策略下的狀態(tài)估計(jì)值。

在 SwarmRL 中，策略的演進(jìn)方向與步長(zhǎng)用“速度” (v) 來(lái)表示，速度的變化涉及局部最佳策略 (πL) 和群體全局最佳策略 (πG?) 與 agent 當(dāng)前策略 (π) 的差異，并受策略慣性因子?w、本地學(xué)習(xí)因子C~1~（self-learning）、群體學(xué)習(xí)因子?C~2~?(social-learning) 等參數(shù)的調(diào)控：

其中?ξ1,ξ2∈[0,1]?為隨機(jī)量，Φ為可行性保持映射，用于將逸出可行域的 agent 重新“拉回”可行域。在迭代中，局部最佳策略 (πL) 和群體全局最佳策略 (πG?) 不斷更新：

4.算法應(yīng)用

下面我們先用一個(gè)隨機(jī)生成的小算例來(lái)對(duì)比一下算法的效果。算例中涉及 30 個(gè)應(yīng)用（見(jiàn)下表），其容器規(guī)格主要為 4c8g 與 8c16g，所用宿主機(jī)的規(guī)格均為 96c512g。

若在調(diào)度時(shí)，請(qǐng)求的順序和數(shù)量均為已知（“上帝視角”），即進(jìn)行事后排布，使用整數(shù)規(guī)劃求得的最優(yōu)解對(duì)應(yīng)的分配率為 94.44 % （這也是所有調(diào)度策略在該算例上所得分配率的上界），共啟用 15 臺(tái)宿主機(jī)，具體排布方案為：

現(xiàn)實(shí)場(chǎng)景中，每個(gè)請(qǐng)求所處順序和容器數(shù)量?jī)H在其到達(dá) Sigma 時(shí)才揭曉，若采用 Best-Fit 進(jìn)行動(dòng)態(tài)調(diào)度，所得分配率為 70.83%，共啟用 20 臺(tái)宿主機(jī)，具體排布如下：

若采用 SwarmRL 學(xué)習(xí)所得策略進(jìn)行動(dòng)態(tài)分配，分配率為 94.44%，共啟用 15 臺(tái)宿主機(jī)，最終容器排布如下：

在該算例中，SwarmRL 學(xué)習(xí)所得策略的表現(xiàn)（94.44%）與“上帝視角”下最優(yōu)排布的表現(xiàn)（上界）一致，明顯優(yōu)于 Best-Fit 的表現(xiàn)（70.83%），改進(jìn)幅度達(dá) 23.61%.

我們?cè)匐S機(jī)生成規(guī)模較大的請(qǐng)求數(shù)據(jù)：共計(jì) 3K 個(gè)請(qǐng)求，5K 個(gè)容器，其規(guī)格分布如下圖，

由于該場(chǎng)景下整數(shù)規(guī)劃模型的變量規(guī)模太大，已經(jīng)無(wú)法在短時(shí)間內(nèi)直接求取“上帝視角”的最優(yōu)解。對(duì)比 Best-Fit （以及人肉策略），算法所得新策略的效果如下：

相對(duì)于 Best-Fit，新策略節(jié)約宿主機(jī) 13 臺(tái)（4.48%），分配率提升 4.30%；相對(duì)于人肉策略，新策略節(jié)約 7 臺(tái)（2.46%）宿主機(jī)，分配率改進(jìn) 2.36%.

考慮到實(shí)際場(chǎng)景中應(yīng)用請(qǐng)求到達(dá)順序的隨機(jī)性，我們隨機(jī)打亂請(qǐng)求生成多個(gè)不同的請(qǐng)求順序，再分別應(yīng)用三個(gè)策略按不同的請(qǐng)求順序進(jìn)行動(dòng)態(tài)分配：

Best-Fit 在不同請(qǐng)求順序下宿主機(jī)數(shù)量的極差為 39 臺(tái)，相對(duì)人肉策略的 84 臺(tái)而言，表現(xiàn)相對(duì)穩(wěn)定，其波動(dòng)幅度約為人肉策略的一半；人肉策略的平均分配率低至 81.85%，對(duì)比原順序下的 93.44%，可見(jiàn)人肉策略的性能并不穩(wěn)定，表現(xiàn)出較劇烈的波動(dòng)。而學(xué)習(xí)所得新策略的表現(xiàn)則相當(dāng)穩(wěn)定，其宿主機(jī)數(shù)量的極差僅為 3 臺(tái)，波動(dòng)幅度約為人肉策略的 30 分之一；新策略的分配率平均比人肉策略的分配率高 13.78%，比 Best-Fit 的高 3.02%.

5.總結(jié)與展望

從提升分配率、節(jié)省資源的角度來(lái)看，SwarmRL 算法可以產(chǎn)生出優(yōu)于常用（以及人肉）的策略，并且有著較為穩(wěn)定的表現(xiàn)。算法部署到線(xiàn)上環(huán)境后，公共資源池的分配率峰值與之前相比有了明顯的提升。

隨著 CPU share 和混部的鋪開(kāi)，除分配率外，新的場(chǎng)景將涉及更多目標(biāo)，比如打散、負(fù)載均衡等，這些目標(biāo)甚至還有互相矛盾的地方，而 SwarmRL 的運(yùn)行機(jī)制天然適合具有多個(gè)目標(biāo)的策略?xún)?yōu)化問(wèn)題，可以十分方便地在策略空間中構(gòu)造 Pareto Front，因而，后續(xù)我們將繼續(xù)研究新場(chǎng)景下的在線(xiàn)調(diào)度策略問(wèn)題，充分挖掘 SwarmRL 的潛力，進(jìn)一步提升 Sigma 的調(diào)度能力。