赛题解析

首届云原生编程挑战赛正在报名中，初赛共有三个赛道，题目如下：

赛道一：实现一个分布式统计和过滤的链路追踪
赛道二：实现规模化容器静态布局和动态迁移
赛道三：服务网格控制面分治体系构建

立即报名（报名时间即日起至07/01）：https://tianchi.aliyun.com/specials/promotion/cloudnative#problem-definition

本文主要针对赛道2题目做出剖析，帮助选手更高效的解题。

背景

阿里每年双11不断的创造奇迹的背后，是巨大的资源成本投入，用以支撑峰值流量。每年各种大促、基础设施的升级都有可能会涉及到中心、单元机房站点变化，而这些站点的迁移、变化，我们可能会短时间借助离线、云上资源等，也可能会评估采购物理机，但无论是采用哪种方式，我们都期望控制成本用尽可能少的资源成本满足当下站点需求。
日常态，我们使用较少的资源满足业务流量需求，但备战各种大促，尤其是双11，容器平台会承担数十万容器扩容诉求，支撑0点峰值流量，满足用户买买买的需求，同时也使得机器资源成本大幅度提升。
在大促规模化场景下，我们希望通过合理容器静态布局及动态迁移能力，在保证业务稳定性前提下，用尽可能少的机器资源来满足大促资源成本的节省，因而集群规模化容器布局成为了我们的关注点。

赛题描述

参赛者需要实现两个功能，一个用于实现规模化的容器静态布局功能，一个用于实现规模化的容器动态迁移功能。
首届云原生编程挑战赛2：实现规模化容器静态布局和动态迁移

赛题主要由源数据、规则两部分组成。在满足规则的前提下，通过队列、循环等one-by-one的方式调度容器，赛题场景将会得到极大的简化。但one-by-one的调度方式不过多感知后续数据，那么如何利用全局视角进行决策则是挑战赛考察的难点和重点。
官方为赛题提供了简单实现，通过宿主机、容器排序，然后在满足规则情况下循环决策容器的安置，采用贪心的这种实现方式来满足尽可能少的使用宿主机，在一些特殊数据情况下，对于调度规则约束约松弛、宿主机数据约宽松，可以趋近于最优解。但对于调度约束越多、宿主机多规格约束约大的情况下，打分循环的贪心方式由于缺乏全局视角，每次容器循环安置，寻求的是当前的局部最优解。显而易见，这种贪心的方式并不适合在规模化场景下寻求资源的节省，不是符合赛题要求最好的算法。
业界多数调度器均通过队列使用不同打分策略以one-by-one的方式调度容器，设计上并不感知后续待调度容器信息，串行扩容顺序会左右调度结果，进而极大的可能会导致资源浪费。下面通过三个容器实例、三台宿主机举例:
静态布局

动态迁移

那么，如何去寻求更好的实现呢？接下来我们将利用题目给出来的条件来描述这个算法设计问题。

1、首先正确理解赛题目的

赛题需要根据约束规则实现两个功能。较通俗的描述来理解赛题如下:
①静态布局：给定一堆箱子，需要按照规则将给定的物品装到这些箱子中，希望在符合规则的情况下尽可能少的使用箱子。
② 动态迁移：给定一堆箱子，已经零零散散的放置了给定的物品，现在需要迁移物品，且每次迁移不能违背规则的情况下规整箱子。
③约束规则: 物品装箱过程中，可能期望衣物与衣物、鞋类与鞋、零食与零食放在一起。因而赛题中容器分布我们也需要满足一些彼此之间的规则约束。

上述描述中箱子可以有不同的容量，对应于赛题中的机器(node)数据；上述描述中物品可以有不同的种类，对应于赛题中不同应用分组(group)的容器(pod)数据。
赛题所属领域为容器调度领域，考察对规模化的容器部署进行决策，优化一个容器集群的整体资源。赛题优化的角度如下:

①调度结果满足设定的约束，并尽可能的降低约束。
② 最小化资源碎片，每个宿主机节点的资源尽量用完。
③最少化机器使用量，节省机器成本。

碎片多少与机器使用量在不同的集群环境下其实是两个不冲突的考点，首先资源碎片是多个维度的，其次碎片少但机器价格成本高、碎片多但机器使用量少，因而需要根据不同机型的资源权重进行决策。
应用容器的性能在容器调度时一般主要受制于三方面规则约束影响。

①亲和性约束，尽可能的部署在一起，如使得应用容器之间减少响应时延。
②反亲和约束，尽可能的不要部署在一起，如使得应用容器之间减少彼此干扰。
③ 折中的自定义约束。赛题规则约束考点。

亲和性、反亲和约束分别过于松弛、苛刻，且实现上也相对简单，但根据应用的特性它是很有必要的，集群内部也在大量的使用。赛题中我们结合容器绑核信息考察的是折中的自定义约束，而这些约束可以通过线上数据、特征进行离线分析获取，并通过赛题考察的两个功能点进行集群级别的容器布局、迁移。赛题经过多次降低难度，现在主要考察以下几点:

①打散约束：我们希望通过约束同一应用容器单机的部署数量，来减少宕机、同机其他容器对该应用容器的影响，且需要尽可能去优化容器堆叠数。
②绑核约束：集团大量使用x86机型、ARM机型、及开启numa特性。我们期望同一宿主机上容器部署，单一容器尽可能不要跨socket分配cpu、单一容器尽可能不要同core分配cpu、敏感应用容器之间尽可能不要同core分配cpu。不然易给业务容器带来性能上的损失。
③迁移约束：容器动态迁移无论在调度链路还是业务稳定性上都是有损的，因而我们期望在动态调整整个集群时能够尽可能少的减少迁移的容器数量。

2、其次决策赛题算法求解

①可参考kubernetes多套打分调度算法。
②可参考各类启发调度算法。
③可参考各类搜索算法。
④ 可参考线性规划类调度算法。
⑤ 可参考mesos多资源DRF算法。
⑥可参考矢量装箱算法。
⑦可参考智能粒子群算法。
⑧ 可参考机器学习训练应用、机器分数权重来优化调度打分算法。

3、最后优化赛题求解算法

评测程序会按照调度规则中的时间约束来终止程序的运行。因而部分算法在多项式时间内可能超过了规定的时间上限，因而可以考虑在寻求最优解、次优解时做少许优化。

①可考虑同规格应用合并优化。
② 可考虑一部分数据提前贪心布局，一部分数据最优求解。
③可考虑混合多算法结合，如启发、群算法。
④ 可考虑将整个数据规模切分，分治法求解。
⑤可考虑利用多核特性并发求解，取最优。

赛题提供针对调度域常用的两种语言java(如:hadoop-yarn调度)、go(如:k8s中调度器)分别实现了demo，且参赛者可以按照要求在本地环境优化自己的程序。

赛题评测

评测环境

参赛者代码程序将会运行在 1 台 4 核 4G 的容器环境中，容器会限制 CPU 和内存使用。
评测步骤
①参赛者fork demo项目，创建出自己的私有项目仓库。
• Java开发者demo地址：https://code.aliyun.com/middleware-contest-2020/django-java
• GO开发者demo地址：https://code.aliyun.com/middleware-contest-2020/django-go
②参赛者在私有项目中赋予 middleware-show 成员 reporter 权限，否则无法进行评测。
• 成员权限地址: https://code.aliyun.com/{你的账号}/{你的项目名}/project_members
③参赛者修改自己的项目代码。在允许修改模块中除实现接口外，其余代码均可修改，不允许修改模块，在程序评测编译前会被替换。
• 允许修改: 实现静态布局、动态迁移功能模块，Java中的"django-calculate"模块，Go中的"calculate"模块。
• 不允许修改: 数据模块，Java中的"django-data"模块，Go中的"data"模块。
• 不允许修改: 运行模块，Java中的"django-start"模块，Go中的"cmd"模块。
• 不允许修改: 功能模块，Java中的"django-common"模块，Go中的"pkg"模块。参赛者可以使用此模块下的公共函数，也可不使用。但若使用后，demo有更新，记得merge。
④参赛者本地调试。
• Java:模块 "django-start" 中的 CalculateLauncher.java 文件直接运行。
• Go: 模块 "cmd" 中的 calculate.go 文件直接运行。
⑤参赛者提交代码进行评测。
• 提交评测地址: https://tianchi.aliyun.com/competition/entrance/231791/submission/572
• 提交评测方式: 提交自定义的私有项目仓库https或ssh地址进行测试。
⑥ 评测系统检测到提交信息，通过git地址获取选手的代码，并进行编译。其中java项目因maven下载jar依赖会相比于go项目更加耗时。(模块替换均为替换相关demo中最新的master分支下代码)
• Java程序编译前替换模块"django-data"、"django-start"、"django-common"。
• Go程序编译前替换模块"cmd"、"data"、 "pkg"
⑦ 评测系统根据项目不同分别生成最新的Dockerfile文件，并自动构建docker镜像，然后通过kubernetes部署容器来运行程序。
⑧评测系统从容器创建开始计时，以调度规则中约束时长+1分钟做终止时间上限，结束程序执行。避免程序过长时间运行。
⑨ 评测系统收集程序最后200行执行日志，然后上传到oos服务器，并将日志下载链接和评分成绩上传到天池页面便于查看。
⑩ 清理容器环境，释放资源。