Algorithm Powers Innovation

“兵者，国之大事，死生之地，存亡之道，不可不察也”。 《孙子兵法》历来被奉为兵家经典，诞生已有2500年历史，匠心独具，巧夺天工，是一部教科书式的兵书典范，历代都有研究。李世民说“观诸兵书，无出孙武”。而《孙子兵法》中研究和阐述如何“运筹帷幄之中，决胜千里之外”的兵法谋略，可以说是我国古代运筹思想最早的典籍。孙子在《孙子兵法》中灵活地运用整体性原则研究军事问题，采用定量分析方法谋划战争，运用优化原则进行科学决策，无一不是运筹思想的体现。例如，孙子在《计算》篇指出：“多算胜，少算不胜，而况于无算乎！”在《作战篇》中，以十万军队出征为例，估算了战争所消耗的财力，“百姓之费，十去其七”，“丘牛大车，十去其六”。在计算运输粮草成本时指出：“食敌一钟，当吾二十钟；  杆一石，当吾二十石。”又例如，对于决策方案，在《谋攻篇》中他指出：“凡用兵之法，全国为上，破国次之；全军为上，破军次之；全旅为上，破旅次之；全卒为上，破卒次之；全伍为上，破伍次之。是故百战百胜，非善之善者也；不战而屈人之兵，善之善者也。”这些充分体现和蕴含了运筹学的思想。

除此之外，宋朝沈括在《梦溪笔谈》中有“营复宫室暠”的记载：“宋祥符年间，皇宫失火。当时由丁谓主持营建恢复宫室，他怕取土的地方太远，于是下令凿开一条大路来取土，不多时日大路都成了巨大的壕沟，于是引汴水流入渠道中，引进各地的竹筏木排以及用船运送的各类建筑材料，全都从壕沟中径直运送到宫门外。这件工事完毕后，却又把废弃的瓦片碎石尘土填实在壕沟中，这样又成为了街道。这一举措的实施三件事情都办成了，总计下来竟然省下了费用可以用亿万来计算。 

以上事例体现了运筹安排的重要性。简单一句话，善用运筹优化的思想就是能达到少花钱，多办事；花小钱，办大事的效果。欣不欣喜、高不高兴：）

之所以提到这么多运筹优化的故事，是和我们云计算瑶光项目中涉及的基础资源调度算法的研究息息相关的。技术创新部算法创新Lab团队承担了IaaS在线调度和离线调度中大量的算法研究工作。在调度算法中大量应用了运筹优化的数学思想。通过这些思想和数学手段进行调度问题的分析、建模和算法优化工作。首先我们就来看一看当前研究的重中之重，分配率调度算法。

1    容量测算

华为云的弹性计算服务提供多种具有不同资源配比、增强特性的实例类型（flavor），而每种flavor都需要根据当前资源情况、包周期订单以及未来订单信息来预测它的售卖趋势，从而决定是否需要调整按需售罄水位线、调配不同的资源池，以及扩充对应资源池。这就是我们这里要介绍的容量测算要解决的问题。

前一期我们介绍过容量预测，侧重从历史数据来预估未来的需求量，而容量测算则更侧重从flavor调度需要考虑的细化约束条件来预估flavor的售卖情况。

如果仅从资源数量角度来看，最简单的就是直接用主机剩余资源除以flavor配置资源，来得到未来还可以容纳多少该flavor的实例。而且还可以使用矢量化并行算法加速计算，适用于超大规模资源池。但真实的资源调度远非如此简单，需要考虑异构资源、NUMA约束、Flavor对称/不对称放置等因素，这些都不是简单的除法计算能解决的。既然需要考虑如此复杂的调度约束，那么会想到直接对flavor进行逐个调度，直到再无法放置，就可以得到还能容纳下多少该flavor请求。这也是当前采用的手段，称为Dry-Run方式。这种方式可以最精准的测算出flavor的容量，但问题也很明显，计算效率非常低，无法支持大规模计算。因此，需要探索一种既能保证测算准确度又能支持大规模多flavor并行计算的容量测算算法。

2    分配率调度算法

根据用户实时VM请求，选择最佳可用服务器来满足这个请求，由于请求具有随机性，不同请求考虑的限制条件不同，导致匹配放置的时候不可能做到全过程的最优放置，导致一定的资源剩余无法分配。

匹配放置算法希望能尽量减少在线资源发放过程中产生的碎片资源。由于碎片无法避免，我们希望通过二次调整的方式来整理这些碎片，使得资源分配最优。

2.1 匹配放置

用户的VM请求随机到达，按需完成任务后会释放资源，后续的用户请求规格和时间未知，而当前的VM放置又会影响到未来请求的放置。所以从最终目标来看，我们每一步的决策都需要考虑到当前VM请求的满足（即时收益）和对未来的影响。

技术研究方案会引入未来收益的考量和调度策略参数的算法调优，设计不同场景不同评估指标来衡量算法效果。技术点包括未来用户请求数据的可预测性，如何预测，未来收益如何量化，评估体系如何构建，指标如何制定，丰富多维度优化的放置策略，策略间如何调优等等。

2.2 强化学习算法

强化学习适合VM请求来自随机序列，可用资源池稳定的调度问题。在这种问题中，强化学习将用于分配请求主机的可用资源量看成状态，在状态与分配行为所产生的价值之间建立映射关系。状态价值关系是调度决策的依据。对每个请求选择价值最大的分配方式，最终有限的主机资源可处理的请求数量越有可能最多。

3    二次调整（离线调度）

在线调度是要求在VM请求到来时实时做出放置决策，这就决定了这个决策只能基于当前时刻的资源情况而做出最佳判断。但当前的最佳决定，随着后续VM请求的不断到来，并不一定在未来也是最佳的。而且每次在线调度又是基于之前放置决策的结果之上，导致最终放置效果相比全局最优已经偏差甚远了。这就需要通过离线调度来对资源分配进行二次调整。

二次调整这里包含了两个关键问题：一是以当前时刻的资源和请求状态计算得到当前全局最优解，采用的调度算法基本与前面介绍的在线调度算法类似；二是需要给如何从当前实际的放置结果调整到最接近这个计算出来的全局最优解的结果。为什么说是最接近而不是直接调整到最优解呢？因为这个调整，首先约束条件多：异构性的对称/非对称多NUMA、不产生热点、亲和/反亲和性等调度约束一个不少；其次优化目标多：各资源维度碎片率不能增加、迁移成本低等。

二次调整虽然包含了两个关键问题，但这两个问题相互制约和影响，因此需要权衡迁移成本与碎片整理收益（碎片率下降比例）之间的关系，需要统一建模。当前分析了虚拟机并行迁移的可行性及迁移序列，并通过多目标优化建模来寻找Pareto前沿面，求解办法包括分支定界、进化算法等。