Algorithm Powers Innovation

作为北斗第七星，瑶光自古就可用来判断四季更迭、引向定时。而作为全新发布的智能云操作系统，瑶光智慧云脑又是如何做到统领云上各类资源、实现租户需求与资源供应之间最佳匹配的呢？在华为云瑶光实验室、华为云算法创新实验室里，我们找到了答案。

#初识资源调度# 云OS：我太“南”了

依托虚拟化技术，我们得以将数据中心海量的计算、存储资源以云服务的形式对外提供。而随着数据中心规模扩展、边缘计算带来的算力延伸，承担着高效、精准资源调度的云操作系统面临着三大挑战：

第一个挑战是云计算的资源消耗/售卖模式带来的。云计算的资源申请通常随机到达、按需计费、用完即释放，无法依据恒定指标构建目标函数求解；

第二个挑战是华为云快速增长带来的。根据Frost & Sullivan对于中国公有云市场的调查研究结果显示，2019年Q3华为云IaaS市场份额排名上升至第三，成为增速最快的Top厂商。高速增长使得用户资源请求的分布随时间变化，而传统的研究多是针对稳定的请求分布来设计解决方案的；

第三个挑战是服务器本身架构带来的。不同服务器体系架构的不同组合方式会导致性能差异，所以这些不同架构设计就像装箱问题中箱子之间加了很多不同隔板，使得放置资源的同时还要考虑性能约束。

#致敬经典# 传统装箱模型为何行不通

装箱问题最早可以追溯到1831年高斯（Gauss）开始研究的布局问题，其本质与装箱一样，都是希望将尽可能多的货物装进箱中。云端虚拟机的部署是把具有多种资源需求的虚拟机向物理机分配的过程，如下图，云操作系统时刻收到虚拟机的资源创建请求，它需要决策将资源部署到哪台物理机上才能保证碎片率最低。

图1 当装箱算法遇到云上资源调度

从过程中可以发现，相比经典装箱问题，云上资源调度有了新的约束：

（1）实时云环境下，虚拟机是动态、依次部署到物理机上的，事先虚拟机的创删申请和资源需求信息具有不确定性；

（2）过高的物理机资源利用率可能会导致业务负载发生波动，故资源调度时要充分考虑物理机的资源和性能约束，并处理可能出现的性能突发诉求；

（3）根据业务不同的在线/离线属性，调度过程也需考虑同物理机上不同虚拟机之间，因资源抢占可能发生的“扰邻”现象，并尽可能降低影响。

沿着经典装箱问题思路，瑶光背后的专家们尝试了如FirstFit、BestFit等运筹学方法，以一台物理机为例，通过比对“请求资源量”和“可用资源量”的匹配程度，即其向量的余弦夹角值来判断对可用资源量的利用情况，如下图所示。

图2 利用余弦夹角方法求解调度

而站在资源池全局的角度看，当发生随机请求与资源池扩缩容时，目标函数也会随即改变。此时，瑶光引入了具有强大搜索能力的强化学习算法，通过预模拟来尝试各种策略，并反复强化最终收益最大的方案。强化学习以数据为基础，其思路我们可以通过迷宫游戏来理解：

图3 通过强化学习算法模拟求解最优调度

熊猫在寻找出口处竹子的过程中，“上下左右”每一步决策都可能“碰壁”、“通过”或“吃到竹子”，这些都算是不同经验值的“奖励”。通过反复的模拟，尝试在不同位置（即“状态”）选取不同行动（即“决策”）所分得的奖励，此时“状态State”与“奖励Reward”的关系就是资源池选择哪台机器来满足请求的决策依据。

更进一步，不同体系架构的云服务器、不同租户间的QoS要求，意味着强化学习算法应对的环境在不停变化，就像上图不断复杂变换的迷宫。而强化学习训练用的历史数据不具有概括性与对抗性，这时瑶光开始基于历史数据完成自学习与进化，以应对快速规模发展下的资源调度问题。

图4 基于瑶光调度算法实现自学习调度策略调优

为了验证方案的可行性，瑶光实验室基于随机请求序列（基于华为云现网数据随机打散生成）对专家经验与模型数据双驱动的“瑶光资源调度算法”进行了仿真测试：

表1 仿真测试场景一

表2 仿真测试场景二

测试结果表明，采用瑶光资源调度算法后平均碎片率优化效果提升30%、同一仿真序列下节省服务器数量约6%、资源池碎片整理触发周期延长约50%。