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

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

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

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

1.計算資源調度及在線策略

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

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

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

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

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

2.在線調度模型

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

最優調度策略可表示為：

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

3.群體增強學習 SwarmRL

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

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

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

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

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

4.算法應用

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

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

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

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

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

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

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

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

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

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

5.總結與展望

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

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