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

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

當用戶向調(diào)度系統(tǒng)申請容器所需的計算資源(如 CPU 、 內(nèi)存、磁盤)時，調(diào)度器負責挑選出滿足各項規(guī)格要求的物理機來部署這些容器。在相同的資源需求下，調(diào)度策略的優(yōu)劣決定著集群計算資源利用的水平。本文將簡要介紹群體增強學習算法在調(diào)度策略優(yōu)化中的應用。

作者：
王孟昌 達摩院機器智能技術算法專家
韓堂 阿里巴巴集團技術專家

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

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

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

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

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

為了把調(diào)度同學從調(diào)參中解放出來，讓有限的資源扛住更大的壓力，達摩院機器智能技術實驗室（M.I.T.）的決策智能算法團隊和Sigma調(diào)度團隊展開了緊密合作，對在線調(diào)度策略問題進行了研究，并開發(fā)了基于群體增強學習（SwarmRL）的算法。

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

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

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

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

3.群體增強學習 SwarmRL

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

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

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

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

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

4.算法應用

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

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

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

若采用 SwarmRL 學習所得策略進行動態(tài)分配，分配率為 94.44%，共啟用 15 臺宿主機，最終容器排布如下：

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

我們再隨機生成規(guī)模較大的請求數(shù)據(jù)：共計 3K 個請求，5K 個容器，其規(guī)格分布如下圖，

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

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

考慮到實際場景中應用請求到達順序的隨機性，我們隨機打亂請求生成多個不同的請求順序，再分別應用三個策略按不同的請求順序進行動態(tài)分配：

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

5.總結與展望

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

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