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