关联比赛: 首届云原生编程挑战赛【复赛】实现一个 Serverless 计算服务调度系统
比赛攻略—ONE PIECE团队
代码链接：
初赛：GitHub - czy-gm/containerScheduler: 2020天池首届云原生编程挑战赛亚军-初赛赛道二（实现规模化容器静态布局和动态迁移）方案
复赛：GitHub - czy-gm/serverlessScheduler: 2020天池首届云原生编程挑战赛亚军-复赛（实现一个 Serverless 计算服务调度系统）方案
初赛（赛道二，语言Java）
1 赛题背景分析及理解
1.1赛题介绍
实现规模化容器静态布局和动态迁移：
1）规模化容器静态布局场景。我们准备了确定数量多规格机器资源，使得在满足调度约束条件下，确定数量、多种类的应用容器能在这些机器资源上满足扩容诉求，保证建站的确定性(赛题中我们会给出充足的机器，但真正建站场景我们会先通过计算预估机器)。
2）规模化容器动态迁移场景。我们会准备一个集群容器静态布局数据，此时集群是一种碎片态。然后通过容器的迁移，按照规则要求尽可能腾空机器资源，并过滤空机器，使得碎片态集群现状重新成为饱满态。
1.2赛题分析
静态布局问题可以理解为多约束的多维装箱问题，约束有资源、绑核、堆叠和打散，约束条件多，判断约束条件的时间较长。
考虑在三个方面着手：
- 减少判断约束条件的时间，以扩大搜索解空间的范围
- 选择一个好的初始解，解空间很大，在比赛给出的时间内能搜索的范围很小，这时好的初始解很重要。
- node的选择，对于不同规格的容器，node的选择顺序决定了node资源的使用情况。
动态迁移问题可以从两个思路解决：
- 先将所有容器按照静态布局的方案进行放置，再通过前后位置的差异进行迁移
- 使用策略判断是否需要迁移，逐渐减少node的使用数
综上，初赛考察的是复杂的装箱问题，在有限的时间内找到较优解，动态迁移使用较少的迁移次数达到饱和态。
2 核心思路
静态布局考虑了两个方案，一是使用模拟退火，二是模拟退火+局部DP。因为使用模拟退火时，后面的node资源利用率较差，可以用DP来改进这一缺陷。首先先试验使用DP能够跑多大的数据规模，每次判断约束条件的时间大约在500ms，在调整数据结构后，时间降低至200~300ms，但DP也只能跑几个node，无法配合模拟退火。
最终方案主体采用模拟退火，pods根据cpu/ram从小到大排序，nodes根据与pod的资源不匹配分数从小到大排序。
动态迁移先将不满足约束的pod进行迁移，然后采用静态布局的方法将每个pod重新放置，根据布局前后的位置不同决定是否需要迁移。不采取任何优化时，迁移次数在8000-8300。考虑到静态布局后，PodA的原node可能存在同规格的PodB，可以交换两者位置，PodA就不用迁移，经过优化后迁移次数在4000~4200。
优化策略如图所示：
图1 优化前（PodA和PodB都需要迁移）
图2 优化后（PodA和PodB交换位置，PodA不需要迁移）
在迁移过程中，可能存在死锁情况，都在等待对方迁移空出位置，需要跳转到中转node解除死锁。方案如图所示：
图3 优化前（PodA和PodB形成死锁）
图4 优化后（根据迁移顺序，解除死锁）
复赛（语言Golang）
3 赛题背景分析及理解
3.1赛题介绍
一个简化的Faas系统分为APIServer，Scheduler，ResourceManager，NodeService，ContainerService 5个组件，本题目中APIServer，ResourceManager，NodeService，ContainerService由平台提供，Scheduler的AcquireContainer和ReturnContainer API由选手实现（gRPC服务，语言不限），Scheduler会以容器方式单实例运行，无需考虑分布式多实例问题。
其中测试函数由平台提供，可能包含但不局限于helloworld，CPU intensive，内存intensive，sleep等类型；调用模式包括稀疏调用，密集调用，周期调用等；执行时间包括时长基本固定，和因输入而异等。
选手对函数的实现无感知，可以通过Scheduler的AcquireContainer和ReturnContainer API的调用情况，以及NodeService.GetStats API获得一些信息，用于设计和实现调度策略。
3.2赛题分析
赛题需要完成AcquireContainer和ReturnContainer两个接口，根据请求函数分配相应的node和container，主要考察node的资源分配，以及请求的响应时间。
评分从两个方面，总的响应时间RT和资源使用时间ND，两者的权重都是0.5，分数是与基准分相比得出的，所以基准的实现策略对选手的策略有很大影响。
node的初始可用数只有10个，需要过一段时间才可以申请新的node，总的可用node数为20个。要规划好node的资源分配，避免前期请求申请超过初始node时出错，造成惩罚性分数。
内存密集型函数占用内存较大，同一container同时运行多个实例，可能会导致OOM，cpu密集型函数也尽量避免同一container运行多个实例，可能会造成超时，这两种情况也会有惩罚性分数。
有些函数（如helloworld、sleep等）占用资源很小，同一container同时运行多个实例，响应时间变化不大，可以减少创建容器的时间。
4 核心思路
由于赛题使用grpc，不限制语言的使用，对于比拼速度的比赛，语言的选择也是考虑的一方面，分别尝试使用c++，java，golang三种语言实现demo，经测试发现，c++与golang的速度差不多，java要比其他两个慢10%~20%。Golang对于并发开发具有天生的优势，再加上官方提供了demo，所以最终选择了golang作为开发语言。
官方前期没有提供评测系统，每次提交系统需要等待1到3小时才能得到结果，等待结果的同时并不能并行开发，效率极低。通过线上跑出的日志，自己使用java实现了一个评测demo，每个函数的调用频率、调用时间、首次调用时间都可以通过日志分析出。由于无法模拟真实环境，所以NodeService只是实现基本功能，无法根据负载情况做出相应的执行时间。评测demo可以检验程序的正确性，以及资源的使用情况，避免了线上等待很久才发现出错的情况，提升了开发效率。
程序的整体策略就是负载均衡和动态扩缩，负载均衡提升响应速度，动态扩缩应对调用压力的变化以及不同数据，避免出现大规模的调用失败的情况。分别从以下几点着手：
选取node的策略
- 如果当前请求函数的并发数大于现有的node数，且现有node不超过初始node数量（设定10个node），则获取新的node创建容器，目的是充分利用前期仅能获取的初始node，让每个node响应较少的请求，可以更快的创建容器以及更快的响应速度。
- 使函数均匀分布在每个node，首先按照node内该函数容器数量排序，优先数量少的node，如果数量相同，优先可用内存多的node。目的是资源分配更加平均，避免资源抢占。
- 当初始node数不能再满足新的请求时，申请新的node，满足高压力的请求。
选取container的策略
- 当容器数大于等于请求数，每个容器同时满足一个请求。如果容器数不够，则创建新的容器。
- 如果该函数（不包括内存密集型和cpu密集型）当前不能再创建容器，则每个容器同时满足多个请求。
函数分类
- 当使用内存高于分配内存的30%时，判定为内存密集型函数。
- 当cpu使用率大于10%时，判定为cpu密集型函数。
- 当函数执行时间小于50ms时，判定为短时间型函数，若再超过65ms的上限，取消判定为短时间型函数。
动态缩减
- 根据cpu密集型容器的数量，初步判断可以缩减的node数量，判断依据是缩减后每个node内cpu密集型容器的数量不超过一定值（更优的方案是根据cpu负载情况判断数量），防止cpu资源紧张，响应时间过长。
- 选择使用内存最少的node，先校验是否满足迁移条件。迁移条件是剩余node的可用内存是否满足该node所有容器的需求，重点是内存密集型函数。
- 当满足迁移条件后，将该node的所有容器迁移到其他node，然后释放该node。当缩减数量达到预判值或者不再满足迁移条件，则停止该轮缩减。
回收资源
- 部分函数可能会从密集调用变为稀疏调用，或者调用一段时间后就不再调用，这样会导致一些空闲容器，导致资源浪费（尤其是内存密集型会一直占用内存）。所以，当容器超过一定时间（设5分钟）没有执行函数时，则释放该容器。若node中没有容器，则释放该node。
根据以上几个策略，程序没有设定最终使用的node数，会根据实时压力动态扩缩。程序每次分配node，都是根据node的可用内存和函数的分配内存进行选择，并且内存密集型容器只会同时执行一个请求，避免发生OOM。cpu密集型容器只会同时执行一个请求，避免出现执行超时的情况。
根据基准分来看，RT相对与ND优化空间更大，所以重点优化响应时间，根据函数的分类指定多种策略：
函数执行优先级
函数：短时间型、cpu密集型（非短时间）、内存密集型（非短时间）
分析：cpu密集型和内存密集型函数一般执行时间较长，占用资源较多，与短时间型同时执行时，会存在资源竞争，导致短时间型执行时间增加至两到三倍。
策略：短时间型优先级比cpu密集型和内存密集型高，当短时间型正在执行时，cpu密集型和内存密集型等待其执行完毕或者等待超时。由于cpu密集型和内存密集型执行时间较长，等待的时间对其影响不大。
预留容器
函数：所有函数
分析：创建容器的时间在0.4~1.0s，大大增加了请求的响应时间，要尽量避免在请求到来时创建容器。部分函数由稀疏调用逐渐变为密集调用，可以在空闲时间提前创建容器。
策略：当某函数的容器满载时，则提前申请一个空闲容器，之后并发请求数增加时，省去创建容器的时间，减少了响应时间。
资源调整
函数：cpu密集型
分析：容器规格是由内存决定的，cpu和内存成比例，每1GB内存对应0.67cpu。cpu密集型执行时，可能存在cpu满载的情况，执行时间受资源限制不能再减少。
策略：当函数执行时cpu使用率高于分配的90%，则认为当前分配的cpu资源不足，先创建新容器再删除旧容器，新容器分配的内存是旧容器的200%，对应的cpu资源也是200%，减少函数的执行时间。
5 比赛经验总结和感想
初赛动态迁移部分，一开始选择直接迁移这个方案，简单实现后发现并不理想，然后就放弃了，赛后才发现这个方案要更优，应该多做一些尝试。在比赛中，学到了很多东西，也结识了很多大佬，感谢官方举办这次比赛。
查看更多内容，欢迎访问天池技术圈官方地址：首届云原生编程挑战赛总决赛亚军比赛攻略(ONE PIECE团队)_天池技术圈-阿里云天池