2021華為軟體精英挑戰賽總結

本屆挑戰賽賽題來源於華為公司實際面對的一個生產場景，即雲上資源規劃、調度的優化，而優秀的優化演算法不僅能為雲運營商節約上億的運營成本，更能為客戶提供更穩定、更流暢的雲端體驗。該賽題要求參賽者依據不同伺服器、虛擬機以及某個時間段的訂單需求，設計出購買伺服器、放置虛擬機以及定價博弈等完善的調度策略，力圖降低雲運營商成本，提升盈利。因此我覺得這個題目是十分有趣而且有意義的，可以一窺雲上資源調度的問題。我們的成績是粵港澳賽區複賽第7，差一些進決賽，有點遺憾，但是也拿到了華為的面試直通卡。【附上沒有整理的程式碼//github.com/MiaoMiaoGarden/Huawei-CodeCraft-2021】

賽題解讀

題目中描述了一些名詞。

伺服器

伺服器類型：在公有雲的運營場景中，我們的數據中心可以選購的伺服器類型有多種。伺服器使用NUMA架構，有單節點和雙節點之分。雙節點伺服器可以分為A和B兩個節點，伺服器擁有的資源（CPU 和記憶體）均勻分布在這兩個節點上，虛擬機不能橫跨兩個節點。
伺服器成本：數據中心使用每台伺服器的成本由兩部分構成：硬體成本和能耗成本。硬體成本是在採購伺服器時的一次性支出，用戶可以根據自己的需求來自由選購。能耗成本是後續伺服器使用過程中的持續支出，只要某一天這台伺服器上放置了虛擬機，那麼這一天就要計算能耗成本。

虛擬機

虛擬機類型：我們面向用戶提供了多種類型的虛擬機售賣服務，用戶可以根據自己的需求來自由選購。不同的虛擬機類型，有不同的CPU、記憶體需求。
單節點/雙節點部署：由於伺服器存在兩個節點，對應的虛擬機也存在兩種部署方式：單節點部署或雙節點部署。單節點部署指的是一台虛擬機所需的資源（CPU和記憶體）完全由主機上的一個節點提供；雙節點部署指的是一台虛擬機所需的資源（CPU 和記憶體）必須由一台伺服器的兩個節點同時提供，並且每個節點提供總需求資源的一半。

資源規劃與調度

  • 容量約束：伺服器可以用來容納用戶的虛擬機，但是伺服器上的任意一個節點(A和B)上的資源負載(CPU 和記憶體)均不能超過其容量上限。
  • 請求類型：用戶的請求共分為兩種類型：創建請求和刪除請求。
  • 請求序列：由一系列請求構成的序列。題目會給出接下來若干天中每一天用戶的請求序列，根據每天的請求序列，你需要進行相應的資源規劃和調度。
  • 數據中心擴容：在得知了一天的請求序列後，你可以在實際進行調度前進行一次數據中心擴容。即購買一些新的伺服器來容納後續用戶請求的虛擬機，同時你需要付出所購買伺服器相應的硬體成本。
  • 虛擬機遷移：在完成擴容後，在處理每一天的新請求之前，你還可以對當前存量虛擬機進行一次遷移，即把虛擬機從一台伺服器遷移至另一台伺服器。遷移的虛擬機總量不超過當前存量虛擬機數量的百分之三。即假設當前有n 台存量虛擬機，每天你可以遷移的虛擬機總量不得超過3n/100 向下取整。
  • 部署虛擬機：在完成擴容和遷移之後，你需要按順序處理當天所有的新請求。對於每一個創建虛擬機的新請求，你要為虛擬機指定一台伺服器進行部署。若虛擬機是單節點部署的，你還需要指明部署在伺服器的A 節點還是B 節點。處理請求的過程中，任意一台伺服器上每個節點容納的虛擬機資源總和都不能超出節點本身的資源容量（指CPU 和記憶體兩個維度）。
  • 未知請求序列：在初賽中，我們面對的是提前知曉了未來所有用戶請求序列的場景，這在實際中是很難作到的。現實場景中，我們往往只能預測後續較短的一段時間內用戶可能的請求序列。所以在複賽中，你需要面對這種存在未知的場景，進行雲上的資源規劃和調度。

方案

設計伺服器、虛擬機的數據結構自然不必多說，直接討論解決方案。從問題的定義來看，我們扮演的是雲服務運營商的角色。保證用戶的虛擬機請求得以滿足的情況下，盡量降低自己的成本，這是首要目標（次要目標是決策速度，速度不能超過一定時限）。整體解決方案需要考慮三種行為的策略：購買伺服器、放置虛擬機和虛擬機遷移。

購買伺服器

成本分為硬體成本和能耗成本，購買伺服器的策略優化主要目的是降低硬體成本。降低硬體成本要求我們購買伺服器的花銷儘可能少，儘可能少買並且儘可能買價格便宜的機器。我們查看給定的伺服器資源和價格的關係，發現一些伺服器的價格高，可能是因為cpu資源比較多，一些伺服器的價格低，可能是因為mem資源比較多，當然也有兩種資源都比較多的機器。總體來說，貴的機器基本上是有貴的理由的。買伺服器有四種容易想到的策略：

  • 買貴的伺服器（或者資源多的伺服器）：貴的伺服器意味著一台伺服器上的資源可能比較充足，一則可以放置大的虛擬機，二則由於虛擬機的聚集放置，可以減少」內部碎片「。缺點是貴的伺服器通常能耗比較大，如果用戶需求的機器量比較少，一味地購買貴的機器將不得不負擔不必要的大能耗成本。
  • 買便宜的伺服器（或者資源少的伺服器）：便宜的機器與貴的機器恰好相反，一位地購買便宜的機器可能不足以放置大的虛擬機，且容易產生」內部碎片「。但能耗也許可以降低。

從上面的考量中我們發現，伺服器的購買與用戶請求的虛擬機類型相關。我們的方案是在每次伺服器不足以滿足一台虛擬機請求的時候，就新購買一台。購買伺服器的型號根據這個虛擬機請求來決定。我們設計了一個weight函數，這個函數比較複雜，因為權衡了很多因素。

  • left_Day是剩餘天數，life是這台虛擬機的生命天數。

  • p0和p1是今天所有請求放置的虛擬機的cpu資源佔總資源比例和mem資源佔總資源比例。這決定了今天的虛擬機請求要求的主要是cpu還是mem資源。

  • last_cpu和last_mem是這個型號的伺服器放置完這台虛擬機之後剩餘的cpu和mem資源。這決定了這台伺服器的剩餘碎片大小，是否物盡其用，是否能供給其他虛擬機請求。

  • q0和q1是伺服器上的cpu佔總資源比例和mem佔總資源比例。這說明了這台伺服器資源主要是cpu還是mem，與p0和p1是供需關係。

  • 設計了一個交叉熵函數來求得(p0, p1)和(q0, q1)之間的相似程度。js_1表示的是這台伺服器放置了虛擬機之後的供需相似程度，js_new表示放置之前的供需相似程度。

  • 用一個線性組合來求得一台伺服器的得分。這台伺服器的能提供的資源與需求資源的匹配程度的影響遍布剩餘的天數，因此js_1以left_Day為權重，js_new類似。money是伺服器的價格，money與資源的商表示伺服器的性價比。如果這一天有大量的虛擬機插入請求，那麼購買伺服器的時候可以不用考慮太多的放置之前的供需相似程度。這個線性組合彙集了眾多影響因素，通過調整參數可以增加對場景的適應性。（在歷史數據量足夠大、足夠典型的情況下，根據歷史數據調整參數應該是可以適應未來的虛擬機請求的。）

最後遍歷所有可選的伺服器型號，找到能放置這台虛擬機的得分最高的伺服器購買一台。

放置虛擬機

以單節點虛擬機的放置為例子。server.fit()函數返回一個bool值，表示這個節點的剩餘資源是否足夠放置虛擬機，如果足夠放置，才可能被選擇。在能放得下的節點中選擇代價最小的。我們用這兩點計算代價：

  • 最好的情況下是這台虛擬機放置完了之後，這個節點直接滿了，物盡其用，否則的話，越放置剩餘的資源越可能是不可利用的碎片。因此，如果放置完了這台虛擬機之後，該節點剩餘資源越多，那麼代價越大。

  • 如果這台伺服器還沒開機，虛擬機的放置導致能耗成本要計算了，那麼代價就更大了。

虛擬機遷移

遷移這塊兒其實不是我實現的，但是我參與了方案的設計，簡單說說吧。遷移的目的是將虛擬機重新排布，需要重新排布的原因是這一天可能有許多虛擬機被刪除了，因此空出了一些資源，那麼可以把剩下的虛擬機歸攏。遷移的好處有兩個，一是空出了資源，類似OS記憶體管理的記憶體回收，會減少內部碎片，為以後放置大的虛擬機提供了空間；二是可以減少開機機器的數量，從而減少能耗成本。有了這兩個目的驅動，加上遷移次數的限制（小於3n/100向下取整，n是正在運行的虛擬機總數），遷移的策略基本上就出來了：從比較空的機器遷移到比較滿的機器。

  • 首先把現有的伺服器排序，按照剩餘資源的多少。（這裡程式碼沒有整理，留下了實驗的痕迹。）
  • 從空的機器到滿的機器逐一遍歷，對機器上的每個虛擬機，找到可放置的最滿的機器，遷移過去。直到沒有可以遷移的機器，或者已經達到最大遷移次數。

這個遷移策略看似很容易想到，也十分自然，考慮的因素比較少，但卻是經過了一番實驗才選擇的。如果伺服器排序遍歷的順序不合適，可能出現不夠好的遷移策略：例如按照利用率，伺服器的排序是A<B<C<D，一台虛擬機V原本放置在A，如果C不能放置，它可能被遷移到B，然後C上的虛擬機遷移到了D，空出了位置給V，但V卻再也不會被遷移了。這也是為什麼我們的from_server和to_server的排序是按照不同的策略來進行，並且嘗試了多種策略才選擇到一個比較優的排序方案。

速度優化

除了縮減成本之外，程式碼運行速度也曾經掣肘我們，因為程式碼要求必須在120s之內處理完所有的請求並給出決策。尤其是遷移程式碼，其實對速度來說十分關鍵，假如用m和n分別表示虛擬機和伺服器節點數量，那麼遷移會是O(mn)的複雜度，m和n輕易可以達到三位數的量。速度的優化基本上是和程式碼實現有關：

  • 初始化數據結構時指定初始大小，減少擴容耗時
  • 將除法改為位移
  • 將不必要放在for循環內的操作，移到循環外
  • 多執行緒排序（機器是雙核的其實多執行緒用處不大）
  • log運算其實很耗時間，複賽現場數據量大了超時，直接把log去掉了，成本相差不大
  • 剪枝，遷移的時候如果源伺服器的資源利用率已經很高了就不考慮遷移了

總結

這比賽整挺好，就是考慮的東西太多，很考驗分析問題的能力和工程能力，還有團隊協作的能力。比賽過程為了找思路我也翻了一些雲資源分配策略的論文，有一些方法比較高級：用上了蟻群演算法和模擬退火這種運籌學上的優化演算法，但這些方法既不好實現，又需要較大的計算量。還有一些論文預測未來的虛擬機請求，以此來幫助當下做決策。複賽的時候要求輸出一天的結果之後才能得到下一天的請求輸入，因此我們是直接用歷史情況當作未來情況的預測，這種時序數據預測是假設數據是平穩的，其實準確率應該不高。

VirMach 便宜 VPS

QNews

QNews