“兵者，國之大事，死生之地，存亡之道，不可不察也”。 《孫子兵法》歷來被奉為兵家經(jīng)典，誕生已有2500年歷史，匠心獨具，巧奪天工，是一部教科書式的兵書典范，歷代都有研究。李世民說“觀諸兵書，無出孫武”。而《孫子兵法》中研究和闡述如何“運籌帷幄之中，決勝千里之外”的兵法謀略，可以說是我國古代運籌思想最早的典籍。孫子在《孫子兵法》中靈活地運用整體性原則研究軍事問題，采用定量分析方法謀劃戰(zhàn)爭，運用優(yōu)化原則進行科學決策，無一不是運籌思想的體現(xiàn)。例如，孫子在《計算》篇指出：“多算勝，少算不勝，而況于無算乎！”在《作戰(zhàn)篇》中，以十萬軍隊出征為例，估算了戰(zhàn)爭所消耗的財力，“百姓之費，十去其七”，“丘牛大車，十去其六”。在計算運輸糧草成本時指出：“食敵一鐘，當吾二十鐘；  桿一石，當吾二十石?！庇掷纾瑢τ跊Q策方案，在《謀攻篇》中他指出：“凡用兵之法，全國為上，破國次之；全軍為上，破軍次之；全旅為上，破旅次之；全卒為上，破卒次之；全伍為上，破伍次之。是故百戰(zhàn)百勝，非善之善者也；不戰(zhàn)而屈人之兵，善之善者也。”這些充分體現(xiàn)和蘊含了運籌學的思想。

除此之外，宋朝沈括在《夢溪筆談》中有“營復宮室暠”的記載：“宋祥符年間，皇宮失火。當時由丁謂主持營建恢復宮室，他怕取土的地方太遠，于是下令鑿開一條大路來取土，不多時日大路都成了巨大的壕溝，于是引汴水流入渠道中，引進各地的竹筏木排以及用船運送的各類建筑材料，全都從壕溝中徑直運送到宮門外。這件工事完畢后，卻又把廢棄的瓦片碎石塵土填實在壕溝中，這樣又成為了街道。這一舉措的實施三件事情都辦成了，總計下來竟然省下了費用可以用億萬來計算。 

以上事例體現(xiàn)了運籌安排的重要性。簡單一句話，善用運籌優(yōu)化的思想就是能達到少花錢，多辦事；花小錢，辦大事的效果。欣不欣喜、高不高興：）

之所以提到這么多運籌優(yōu)化的故事，是和我們云計算瑤光項目中涉及的基礎資源調(diào)度算法的研究息息相關的。技術創(chuàng)新部算法創(chuàng)新Lab團隊承擔了IaaS在線調(diào)度和離線調(diào)度中大量的算法研究工作。在調(diào)度算法中大量應用了運籌優(yōu)化的數(shù)學思想。通過這些思想和數(shù)學手段進行調(diào)度問題的分析、建模和算法優(yōu)化工作。首先我們就來看一看當前研究的重中之重，分配率調(diào)度算法。

1    容量測算

華為云的彈性計算服務提供多種具有不同資源配比、增強特性的實例類型（flavor），而每種flavor都需要根據(jù)當前資源情況、包周期訂單以及未來訂單信息來預測它的售賣趨勢，從而決定是否需要調(diào)整按需售罄水位線、調(diào)配不同的資源池，以及擴充對應資源池。這就是我們這里要介紹的容量測算要解決的問題。

前一期我們介紹過容量預測，側(cè)重從歷史數(shù)據(jù)來預估未來的需求量，而容量測算則更側(cè)重從flavor調(diào)度需要考慮的細化約束條件來預估flavor的售賣情況。

如果僅從資源數(shù)量角度來看，最簡單的就是直接用主機剩余資源除以flavor配置資源，來得到未來還可以容納多少該flavor的實例。而且還可以使用矢量化并行算法加速計算，適用于超大規(guī)模資源池。但真實的資源調(diào)度遠非如此簡單，需要考慮異構(gòu)資源、NUMA約束、Flavor對稱/不對稱放置等因素，這些都不是簡單的除法計算能解決的。既然需要考慮如此復雜的調(diào)度約束，那么會想到直接對flavor進行逐個調(diào)度，直到再無法放置，就可以得到還能容納下多少該flavor請求。這也是當前采用的手段，稱為Dry-Run方式。這種方式可以最精準的測算出flavor的容量，但問題也很明顯，計算效率非常低，無法支持大規(guī)模計算。因此，需要探索一種既能保證測算準確度又能支持大規(guī)模多flavor并行計算的容量測算算法。

2    分配率調(diào)度算法

根據(jù)用戶實時VM請求，選擇最佳可用服務器來滿足這個請求，由于請求具有隨機性，不同請求考慮的限制條件不同，導致匹配放置的時候不可能做到全過程的最優(yōu)放置，導致一定的資源剩余無法分配。

匹配放置算法希望能盡量減少在線資源發(fā)放過程中產(chǎn)生的碎片資源。由于碎片無法避免，我們希望通過二次調(diào)整的方式來整理這些碎片，使得資源分配最優(yōu)。

2.1 匹配放置

用戶的VM請求隨機到達，按需完成任務后會釋放資源，后續(xù)的用戶請求規(guī)格和時間未知，而當前的VM放置又會影響到未來請求的放置。所以從最終目標來看，我們每一步的決策都需要考慮到當前VM請求的滿足（即時收益）和對未來的影響。

技術研究方案會引入未來收益的考量和調(diào)度策略參數(shù)的算法調(diào)優(yōu)，設計不同場景不同評估指標來衡量算法效果。技術點包括未來用戶請求數(shù)據(jù)的可預測性，如何預測，未來收益如何量化，評估體系如何構(gòu)建，指標如何制定，豐富多維度優(yōu)化的放置策略，策略間如何調(diào)優(yōu)等等。

2.2 強化學習算法

強化學習適合VM請求來自隨機序列，可用資源池穩(wěn)定的調(diào)度問題。在這種問題中，強化學習將用于分配請求主機的可用資源量看成狀態(tài)，在狀態(tài)與分配行為所產(chǎn)生的價值之間建立映射關系。狀態(tài)價值關系是調(diào)度決策的依據(jù)。對每個請求選擇價值最大的分配方式，最終有限的主機資源可處理的請求數(shù)量越有可能最多。

3    二次調(diào)整（離線調(diào)度）

在線調(diào)度是要求在VM請求到來時實時做出放置決策，這就決定了這個決策只能基于當前時刻的資源情況而做出最佳判斷。但當前的最佳決定，隨著后續(xù)VM請求的不斷到來，并不一定在未來也是最佳的。而且每次在線調(diào)度又是基于之前放置決策的結(jié)果之上，導致最終放置效果相比全局最優(yōu)已經(jīng)偏差甚遠了。這就需要通過離線調(diào)度來對資源分配進行二次調(diào)整。

二次調(diào)整這里包含了兩個關鍵問題：一是以當前時刻的資源和請求狀態(tài)計算得到當前全局最優(yōu)解，采用的調(diào)度算法基本與前面介紹的在線調(diào)度算法類似；二是需要給如何從當前實際的放置結(jié)果調(diào)整到最接近這個計算出來的全局最優(yōu)解的結(jié)果。為什么說是最接近而不是直接調(diào)整到最優(yōu)解呢？因為這個調(diào)整，首先約束條件多：異構(gòu)性的對稱/非對稱多NUMA、不產(chǎn)生熱點、親和/反親和性等調(diào)度約束一個不少；其次優(yōu)化目標多：各資源維度碎片率不能增加、遷移成本低等。

二次調(diào)整雖然包含了兩個關鍵問題，但這兩個問題相互制約和影響，因此需要權衡遷移成本與碎片整理收益（碎片率下降比例）之間的關系，需要統(tǒng)一建模。當前分析了虛擬機并行遷移的可行性及遷移序列，并通過多目標優(yōu)化建模來尋找Pareto前沿面，求解辦法包括分支定界、進化算法等。