赛题介绍

赛题网址：https://competition.huaweicloud.com/advance/1000041380/circumstance

本次赛题来源于云计算-资源调度管理的真实业务场景，自2000年以来，国外众多互联网公司如Amazon、Google、Microsoft等纷纷创立云计算中心，作为一种方便、低成本的公共服务，得以快速发展。华为云成立于2005年，作为后进者快速发展到目前的Issa全球市场前列。

在云市场发展壮大的同时，云提供商们关注云数据中心硬件成本花费和资源利用率对成本降低的巨大作用。通过优化算法对物理服务器上的虚拟机资源进行规划和调度能够为云运营商节省上亿的成本。

赛题简化

本次赛题的主要任务可以分为：服务器选型、虚拟机放置规划和虚拟机调度。

其中虚拟机放置问题可以看做是一种多维装箱问题（Vector Bin Packing），学术界对装箱问题的研究精彩纷呈，主要有：近似算法（首次适应（First Fit）、最佳适应（Best Fit）、下降最佳适应（Best Fit Descending）），随机算法（模拟退火法（Simulated annealing）、粒子群算法、蚁群算法、元启发式算法（metaheuristic）），和最优解算法（分支定界算法）。其中近似算法在一维装箱问题中不会超过最优解的11/9，随机算法就真的是随机，最优解算法能够得到最优解却是依赖牺牲时间换取的。

本次赛题的装箱问题是服务器和虚拟机的两个维度 cpu 和 mem 加上单双节点分类，从而使得问题成为三维装箱问题，因此各种算法的结果近似，基本等同于最基本的下降贪心算法结果。

虚拟机调度有两种可行方案：1.直观理解就是将未放满服务器上的虚拟机迁移至较满服务器（最基本的方法），2.也可以对不同服务器上的虚拟机进行重排（重难点）。可参考Google在ROADEF\EURO 2012上举办了名为Machine Reassignment的竞赛，其中大部分高级组（非doctor学历或非在校学生）队伍都采用了局部搜索（Neiborhood search）的随机算法，由于此次比赛要求单个数据集低于90s，实际线下不能超过20s，所以这些对此次赛题几乎没有参考性。其中方案1中影响最大的因素为待迁移服务器和目标服务器排序逻辑，由于该方法只能将剩余资源较大服务器上的虚拟机迁移至剩余资源较小的服务器上，而如果剩余资源较小的服务器出现碎片化剩余空间，如 A[0, 45] [126, 127]，即cpu=126，mem=127的剩余资源为cpu=0，mem=45，则无法继续放置。所以我们的观点是必须采用第二种方案弥补该问题。

数据分析

Input：

server: (host0Y6DP, 300, 830, 141730, 176)

server_type	cpu	ram	hard_cost	energy_cost
host0Y6DP	300	830	141730	176

visual machine：(vmMRUNJ, 60, 2, 1) 0代表单节点部署，1代表双节点部署

vm_type	cpu	ram	single or double
vmMRUNJ	60	2	1

request：(add, vmUQ9E5, 971449032) (del, 720035579)

request_type	vm_type	vm_single number
add（del）	vmUQ9E5	971449032

在输出前系统会通过标准输入给出一些信息，包括N种服务器类型数据，M中虚拟机类型数据，以及接下来N天的用户请求（删除和添加虚拟机）。

我们调度需要满足一些限制条件：1. 容纳服务器的虚拟机cpu && ram都不能超过其容量上限，特别的，对于单节点虚拟机只用放在server的一个节点即可（A或B节点），双节点虚拟机的cpu && ram需要均分放在server的两个节点（A和B节点）。

Output：

1.首先输出购买服务器信息，判题器根据购买信息按读入顺序为每台服务器设置从0开始的唯一编号。

2.根据前一天不超过存量虚拟机5/1000的限制将已有虚拟机从一台服务器迁移至能够容纳它的其他服务器上。

3.按Input顺序输出对添加虚拟机的部署信息，如果是单双节点还需指明部署在服务器的A节点还是B节点。

Constraint：

在迁移和部署过程中均需满足服务器的容量限制条件

Evaluation function：

服务器购买 get_value = hard_cost + (T - today) * energy_cost | 其中T为总的天数，T-today为剩余天数。

解题思路和结果分析

其实今年赛题很简单，很容易写出baseline，我在初赛练习赛（2021/3/10）放出赛题很快写出了最简单的方法，贪心方法和按利用率排序。贪心方法就是确定每天买一种类型的服务器，先买一台放得下当前虚拟机就放，放不下就买新的服务器，每次放置都从先买的服务器开始尝试，最后根据购买服务器目标函数比较每种服务器的总价选择最小的。然后尝试过使用随机算法（如模拟退火，博哥成电校内赛时讲了一堆元启发，难道这就是其他赛区派来的间谍，Emmm），但是由于时间限制和效果放弃了。线上单个集合90s的限制实际上线下不能超过20s。

大佬搞得python判题器https://github.com/B1ACK917/2021HWAutoGrader，主要功能其实只有圆形图看服务器类型数据，哈哈哈哈。

后来我google找了几十篇文献，研读了10多篇文献，然后找到了两个字“废话”！可能是这次赛题结合实际，是三维以及以上的multichoice vector bin packing，导致国内外的研究都成了无用功。只好自研算法，然后根据贪心算法和迁移的骚操作（题目让每天先迁移再购买最后部署，我们先购买和部署，然后再将那些删除操作后剩余的vm迁移至其他较满服务器上），后来据我所知，没有其他人这样搞。但是在得到较好成绩后没有继续优化这个点。购买服务器也换成了买最便宜的，导致的结果就是超过50%的服务器都是最小最便宜的那一款，所以迁移反而负优化。

接下来我们被困在11e的关头一直没有找到问题关键，然后我又回头去找文献去了！哎！果然是太年轻。后来根据图形化和分析，我们在正式赛封榜前两天找到了一个主要问题：由于购买时买到了较小的服务器，而迁移没有只考虑了利用率，所以当空余空余服务器很多时（i.e. total servers：3000，empty servers：1000），大部分大容量服务器已经被放满了。在超量请求（>1000条add请求）到来时，一旦包含很多最小服务器放不下的vm类型时，便会直接购买大容量服务器，直接导致大量小服务器（1000台）都空着，而又购买了很多新的服务器，所以硬件成本直接涨了几千万，也就在11e关头徘徊。

我们后来发现这个问题后，先是通过强制迁移限制：同样类型只能迁移至同样类型上，避免小的vm把大的server填满，而大的vm找不到server只好买新的情况，直接突破11e的关头。但是队友想出一个magic方法，购买时强行限制server剩余部分容量，这样就让买的服务器偏大，不会出现放不下的尴尬情况。由于该方法让我们到达有了较大进步，加上骚迁移直接到达10e9000w，也就挤进32强的席位，然后我们便忽略了对这个购买方法深层次的逻辑分析，间接导致后来复赛的滑铁卢。

重点

1. 其实从初赛开始你的算法就大致决定了复赛的结果，因为可以分为每天调度（总共1000天）和每天迁移，而非迁移的结果与迁移结果成正相关。初赛训练赛通过比较西北赛区rank1大佬非迁移结果，10e800w，而大部分队伍都是11e4000w。所以复赛训练集大部分队伍不迁移都在20e左右，而前几大佬都是19.7e，我们有个购买模型在19.85e，但是后来一直没有找到适应的迁移策略。

2. 数学验证。由于赛题理解简单，所以实际操作的时候构思了许多策略，但是都没有将其转换成抽象的数学模型，而是简单地通过实现结果来判断好坏。因此我们根本没有完全确定那几个策略是普适性的。

3. 对于想到且通过可视化确认的点一定要认真分析，不要抛弃，其中最主要的就是购买模型和迁移方法。因为赛题同样是数据类型非常大，所以部分观察看不出具体的问题。

4. 没有数学逻辑的优化是个极大地陷阱，如果没有认真分析而是直接采用，后期会因为没法分析而无法继续优化。