Huawei-Codecraft2021

1.说明

2021华为软件精英挑战赛-内个小队

京津东北赛区 初赛第二 复赛第一 总决赛八强（三等奖）

因为有程序运行时间的要求，所以采用C++

仅用作学习交流，不得用于商业用途

2. 目录

1. Match_Information: 赛题信息
2. References： 比较有帮助的参考文献
3. Huawei_Final： 代码工程
   • 各个阶段的代码需要查看分枝树的提交记录
   • 时间有限，维持比赛阶段的原状
4. 2021HWAutoGrader (by B1ACK917): 开源的初赛判题器
5. 2021HWAutoGrader-2nd-Stage： 修改为复赛判题器
   • 复赛训练阶段题目要求改动不大，仅需要修改输入部分的可读天数，以及5%。的迁移限制改为3%
   • 不兼容复赛现场的题目改动
6. Huawei_PK： 决赛的PK模拟器和日志分析器
   • 决赛题目改动较大，初赛和复赛的判题器已不兼容
   • 最终的commit为决赛现场修改的兼容现场题目变更要求的版本，训练阶段的版本可以查看git分枝树

3. 代码库

• 工程懒得整理了，列举下各个最终版本的提交ID号

  • 初赛：776f26f9b0b982aafaa9835b450fbef7f192c34a (位于cyt分支上)
  • 复赛现场：8a7298b2fdda9a75e3a5d4e31a81b53ca2dd5a8f (位于moreIters分支上)
  • 决赛现场：361e802c97b615a6dd19c95e53cae6a5d320fc81 (binding分支最新提交)

• 下文只是大概理一下思路，不涉及很多细节。

4.初赛

• 实现功能：服务器的购买，虚机的迁移和部署

• 因为初赛可以读取所有天数的用户请求，而官方训练集给出了两种不同的用户请求分布，所以猜测最终比赛阶段的两个训练集包含这两种请求分布的各一种，或者是两个分布的混合结果。

  • 第一件事就是读了数据之后统计用户请求的分布，分析属于那种分布，然后可以给出不同的处理
  • 为了简单高效，我们只是分别计算了add请求和del请求的方差，给出一个阈值来区分
  • 后来通过分析发现del请求的分布对性能硬性更大；
  • del请求比较平稳的时候服务器容易装满，此时迁移就迁移不动，对购买和部署的要求较高
  • del请求存在突发情况的时候服务器大量服务器会空闲，这种情况下的迁移就非常重要，但是迁移的复杂度是明显高于购买和部署的，复杂的算法就容易超时，所以必须要降低购买和部署的复杂度，来把大量的运行时间留给迁移。
  • 后来发现对于初赛赛题来说，90s是相当够用的，不用特意降低复杂度（一定要记得把CMakeLists的debug->release）

• 购买和部署

  • 当时担心程序超时，所以写了两个版本，一个方案目前就叫做SSP (SSP分支)，另一个方案就叫做GraphFit (cyt分支)；最终合并代码时候都合并到cyt分支上去了
  • SSP是复杂度高一点，性能相比GraphFit好的办法；各自也都有自己的参数控制复杂度和性能的折中；
  • SSP复杂度最低的参数配置和GraphFit复杂度最高的参数配置是同一个方案。
  • 方案思路来自于参考文献："Heuristics for the variable sized bin-packing problem"，SSP起源于其中的”Heuristic SSP1“方案，GraphFit起源于其中的"A genetic algorithm"方案（只是随便给出一个排序，然后借鉴了最短路径方法求解没有用遗传算法，所以是次优的）
  • SSP和GraphFit的主要区别在于处理那些需要购买新服务器的请求，对于可以装进已有服务器的请求，我们使用的是bestFit的方法，并做了些修改，参考文献:"More than bin packing: Dynamic resource allocation strategies in cloud data centers", "Heuristics for Vector Bin Packing"

• 迁移

  • 有关迁移的文献里常常用到局部搜索的方法，我们觉着局部搜索可能不适合这个比赛，所有没有采用。
  • 我们的办法就是对所有的服务器排序，然后按顺序拿出来一个虚机，找一个更合适的服务器放进去。这个过程可以迭代多次，但是我们初赛时候只迭代一次。
  • 其中有两个关键点。第一，搜索迁入服务器的时候，如果遍历所有的服务器，那复杂度大约就是O(Days*VMs*Sers)，这个数已经上亿了，是没法在短时间内运行完的。所以我们就用了一个嵌套四层的红黑树（STL中的map），每一层的key分别为aIdleCPU, aIdleRAM, bIdleCPU, bIdleRAM，value是一个vector，保存所有的server信息。这样可以较快搜索到可以装入这个虚机并且空闲资源最少的那台服务器。
  • 第二，因为成本是每天部署结束后来计算的，就会出现一种情况是，本来一个服务器已经清理的很空了，部署的时候又给部署进去了，或者是部署的时候又用了很多的空闲服务器，导致服务器功耗变大。所以，我们的办法是把迁移放到部署之后去执行，暂时称它为后迁移，后迁移和先迁移的不同在于两点。
    • 如果迁入服务器当日有删除，必须把被删除虚机占用的资源考虑在内，不然先迁移是有可能迁移不进去的。
    • 如果迁移的是当日部署的虚拟机，那我就可以等效为部署的时候直接放到了目标服务器，这个方法因为时间关系初赛时候没写，后来才加上。

• 曾经尝试过但没采用的方法

  • bin-center分支：bestFit本来是请求虚拟机找服务器，改成了服务器找请求，低维度（只有cpu和ram两维）而且这两个维度对于虚机来说有很强的相关性，这个场景不太适用。参考文献："Heuristics for Vector Bin Packing"
  • doublemap分支：四个map嵌套太反人类了，想改成双map嵌套，只存入服务器a节点/b节点/ab节点取最小的资源，但是这个程序既难写，写出来运行速度还不快，可能有bug，时间关系放弃了。

5.复赛

• 练习阶段变更点，只能读取部分天数的数据，迁移个数上限改为3%

• 现场阶段变更点，可以选择一天，那天的迁移次数上限为100%

• 复赛显然就是在迁移上做文章，我们购买部署依旧采用SSP+bestFit的办法。

• 方案：

  • 迁移的时候要尽量把一台服务器清空才是真正的目标。所以可以考虑把服务器内的虚机看做整体去迁移，甚至是多个服务器内的虚机看做整体，一起迁移进一个服务器。复赛时，我们是允许迁入空服务器的，只要迁移之后的功耗比迁移之前的低，而初赛我们直接禁止了迁入空服务器。
  • 多次迭代，因为迁移次数放宽了，只扫描一遍所有排序后的服务器可能还没有达到迁移次数上限，所以我们可以在多搜索几遍服务器列表。
  • 空间换时间，很多虚机都是同一种型号，而这些虚机在搜索迁入服务器的时候进行的是近似相同的操作（不同之处在于搜索迁入服务器时候是不搜索自己当前这个服务器的，都是细节暂时不理解就算了），所以一旦一个型号虚机搜索结束而没有成功迁移，就可以把这个搜索结果记下来给下一个同型号虚机来用。这个办法在一个训练集上可以提速不到20秒。
  • 复杂度边界控制，现场会更换新的数据集，而为了达到良好的性能要尽量用尽所有的时间，所以必须有参数控制复杂度，我们选择只搜索迁出服务器列表一部分来控制，例如只搜索最空的95%的服务器。
  • 到了现场比赛，数据集突然变大，很多队的程序超时，我们直接调参控制迭代次数和搜索空间的大小，这就省下了很多的时间调整别的地方。
  • 现场比赛允许有一次大规模迁移，但是我们怎么使用大规模迁移都没有带来更好的收益，所以复赛我们是没有用到大规模迁移的。

• 曾经尝试过但没采用的办法：

  • 我在newssp分支上尝试了很多方法，例如，修改优化目标公式、给服务器添加锁（如果总是迁移不动那就加个锁提高速度）等，提高性能就得提高复杂度，为了不超时降低复杂度就又降低性能，所以权衡之后这两个方法没用上。

6.决赛

• 决赛直接变成了竞价博弈，而且是买方垄断的场景，赚钱是不可能的，这辈子都不可能的了，就看谁赔的少才是王道，零元购百亿补贴走起。

• 去线下比赛和他们讨论之后发现，大家的方法大致都差不多，估成本、预测对手、调价等等，可能更多的在于一些细节上，少写逻辑bug，不要编译超时，不要运行超时，还有程序是否易扩展易维护。

• 现场变更点为允许卖方每天绑定三个订单，直接和买方交易，不需要和对方博弈。这玩意对最终受益影响非常大，如果现场不把这个新内容加上，是拿不到好成绩的。就因为这个变化，我们之前写的日志分析器和pk模拟器是不兼容的，所以现场必须修改pk模拟器来给新程序debug，修改日志分析器来调参，所以这次比赛的现场压力还是有一些的。（当然这俩个都不改其实也是可以的）

• 我们的方法先估计订单的成本，已经有了所有的虚机型号的信息，就可以解几百个超定方程求出单位cpu和单位ram的硬件和功耗成本，然后就得到的订单的估计成本。（订单的虚机分布肯定不是均匀分布的，估计不准的地方就交给调参了）

• 调价，前一天订单少就就降价，订单多久涨价，当然不能低于成本。

• 分段出价，前期抢用户就能早买服务器，早买的服务器可以一直用，就等价于早期的成本低后期的成本高。虽然这个问题可以归结到成本估计上，但是成本估计不准啊，所以还是变成了调参。

• 预测对手，我后两天写了个预测对手的方法，但是我担心对手不安套路出价预测可能不如不预测，添加判断方法还太麻烦，学校事情太多写不完就放弃了。但是线下给我的感觉是，这一点非常重要，想拿更好的收益必须要预测，所以这也是我感觉我们不足的地方。

• 曾经尝试过但没采用的办法：

  • finalSSP分支：出价可以每天一部分订单给低价，一部分给高价，防止因为价格过低某一天赔本太多，某一天价格过高就拿不到订单，提高鲁棒性。但是比赛现场，这个方法越调越差，博弈一直输然后就放弃了。