谈谈2018华为精英挑战赛

落日映苍穹つ 2022-05-27 08:19 201阅读 0赞

背景介绍云平台为了满足不同租户的需求，提供了一种可随时自助获取、可弹性伸缩的云服务器，即弹性云服务器（Elastic Cloud Server，ECS）。为容纳更多的租户请求、并尽可能提高资源利用率、降低成本，自动化、智能化的资源调度管理系统非常关键。由于租户对ECS实例（虚拟机，VM）请求的行为具有一定规律，可以通过对历史ECS实例请求的分析，预测到未来一段时间的ECS实例请求，然后对预测的请求分配资源（如图1所示），这样可以找到一个接近最优的分配策略，实现资源最大化利用，同时也能参考预测的结果制定云数据中心的建设计划。  
![这里写图片描述][70]  
    赛题更加详细的信息请参考2018华为软件精英挑战赛官网（[http://codecraft.devcloud.huaweicloud.com/home/detail][http_codecraft.devcloud.huaweicloud.com_home_detail]）代码介绍比赛赛题主要可以分成两个步骤：**1. 根据历史虚拟机请求数量预测接下来几天的各类虚拟机请求数量**（主要通过机器学习方法）**2. 将预测出来的虚拟机放置进规定规格的物理服务器中，使得物理服务器的资源（CPU或者内存）利用率最高**  
1）第一个步骤需要先对数据进行预处理，比如去除节假日期间的异常请求值等等，然后应用机器学习的方法使用历史数据**训练预测模型**，最后使用训练出来的预测模型进行预测，不知道是测试用例原因还是我们使用的模型的原因，这一步骤做出来效果并不是太好，所以这部分暂时就先不放出来了，以免误导大家。  
2）第二个步骤是寻找最优放置虚拟机方式，在上一步预测出来各种虚拟机数量之后，实际资源使用情况就已经确定了（一共多少CPU，多少内存），每个服务器的资源又是确定的，所以最终的资源使用率就只跟服务器数量有关，于是问题便转化为了：如何放置虚拟机可以使得使用的服务器数量最少？因为每次放置都要考虑虚拟机的CPU和内存两个维度，所以放置问题可以看作一个**二维装箱问题**（Bin packing），人们对二维装箱问题的研究一直在进行。第一种最简单的方法（也是官方文档示例方法）是**首次适应法**（FFD算法），即将所有的虚拟机按次序放入物理服务器中，对于每个虚拟机，检查服务器资源是否足够放下该虚拟机，如果可以放下就将其放在这台服务器上，如果服务器剩余资源不足以放下该虚拟机，则新建一台服务器，将虚拟机放入新建的服务器……直到最后放置完所有的虚拟机，将每个服务器放置的虚拟机输出即可。首次适应方法有个弊端，可能会造成每个服务器都有挺多资源剩余，但是却无法被后来的虚拟机利用。由于在采用首次适应法的前提下，虚拟机放置方式只与虚拟机初始排列顺序有关，所以我们可以用智能算法对初始排列顺序进行优化，求得接近最优解的解。我们可以采用模拟退火算法进行最优解的寻找，模拟退火算法（Simulated Annealing Algorithm）用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性，关于该算法的详细介绍，请参考维基百科（[https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB][https_zh.wikipedia.org_wiki_E6_A8_A1_E6_8B_9F_E9_80_80_E7_81_AB]）。使用模拟退火算法， 每次随机交换两个虚拟机的顺序，使用首次适应法将虚拟机放入服务器，并计算出服务器使用数目最少的一组，模拟退火算法收敛过后，我们即可得到一个最优解或者接近最优解的解，将其作为最终结果输出即可。  
[参考文献][Link 1]

[70]: /images/20220527/97978a046b0e4a26a55d642624750072.png
[http_codecraft.devcloud.huaweicloud.com_home_detail]: http://codecraft.devcloud.huaweicloud.com/home/detail
[https_zh.wikipedia.org_wiki_E6_A8_A1_E6_8B_9F_E9_80_80_E7_81_AB]: https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB
[Link 1]: https://www.zhihu.com/question/268448695