本文讲的是美团点评容器平台HULK的调度系统【编者的话】美团点评作为国内最大的O2O平台，业务热度的高峰低谷非常显著且规律，如果遇到节假日或促销活动，流量还会在短时间内出现成倍的增长。过去传统虚拟机的服务运行及部署机制在应对服务快速扩容、缩容需求中存在诸多不足：
- 资源实例创建慢，需要预先安装好运行所需的环境，比如JDK等。
- 扩容后的实例，需要经过代码部署流程，一些情况下还需要修改配置后才能承接流量。
- 资源申请容易回收难，促销活动后做相关资源的回收下线会比较漫长。
- 由于业务存在典型的高峰低谷，为保障业务稳定，资源实例数要保障能抗高峰期容量峰值的1-2倍，从而导致非高峰期资源大量闲置，整体利用效率低。
【深圳站｜3天烧脑式Kubernetes训练营】培训内容包括：Kubernetes概述、架构、日志和监控，部署、自动驾驶、服务发现、网络方案等核心机制分析，进阶篇——Kubernetes调度工作原理、资源管理及源码分析等。
注意到上面这些问题后，我们经过调研与测试，结合业界的实践经验，决定基于Docker容器技术来实现服务的弹性伸缩，有效应对快速扩缩容需求、提升资源利用效率。
Docker容器技术也是一类虚拟化技术，不同于虚拟机的硬件虚拟化，容器是基于操作系统内核的隔离机制实现。容器省去了模拟底层硬件、指令等操作，直接基于宿主机内核，并隔离出独立的系统环境、加以资源限制，能有效提升启动速度和性能。
HULK容器平台简介
美团点评基础架构团队在2015年中旬启动了公司级的容器集群管理及弹性伸缩平台——HULK项目，目标是提供Docker容器平台，推动公司的服务容器化，实现自动的弹性扩容、缩容，提升资源利用率、业务运维效率并降低IT运维成本。
HULK是美国漫威漫画旗下超级英雄“绿巨人”，拥有强大的变身能。变身后的绿巨人对各类疾病、射线、毒药及物理攻击有很高的免疫力，加上超强的再生能力使得其非常强大。
我们选择HULK作为项目名，就是希望美团点评服务在接入HULK之后可以拥有绿巨人般强大的变身能力（弹性扩缩），进而在此基础上提升服务的健壮性、稳定性及资源利用率。
HULK容器平台系统层次图
在HULK所有模块中，调度系统负责对资源池进行统一的调度分配与管理。主要职责包括：
- 接受上层弹性伸缩及集群管理模块的资源申请、回收请求，执行资源分配。
- 综合多种资源利用、服务优化的调度算法，决策最优资源部署位置，提高资源利用率、节约成本并保障服务稳定性。
- 对接云平台IaaS层。
本文将主要对HULK容器平台的调度系统进行介绍，包括当前调度系统的设计、考量指标、相关算法等。
HULK调度系统介绍
核心指标
从HULK弹性调度系统的设计以及后续的演进过程来看，一个完善的调度系统主要需要关注以下三个指标：
调度系统核心指标
- 资源利用率：即提高整体物理集群的资源利用率。一个优秀的调度系统可以把资源利用率提高到30%~70%，而简陋的调度系统甚至会使资源利用率降低到10%以下。
- 业务最优化：即保障运行业务的稳定高可用，以及服务相互调用的优化。比如，如果调度系统一味的追求资源利用率，将宿主机上堆砌超过其负载能力的实例，又或一台宿主机/机架的故障会影响到一个服务下所有实例的运行，都在业务稳定性上打了折扣。
- 并发调度能力：调度系统请求处理能力的体现。一个大规模的物理集群上，往往运行了数以千百计的业务，当出现调度请求高峰的场景下，调度系统要有能力在短时间内给出答案，即使这个答案可能只是全局近似最优解。
调度系统设计难题
调度系统设计的难题，在于
几个调度核心指标在实现上存在的矛盾关系
，类似于CAP理论中的三要素，无法同时满足。
在CAP理论中，Consistency（一致性）、Availability（可用性）与Partition Tolerance（分区容错性）无法同时满足。如果追求可用性与分区容错性，则需要牺牲强一致性，只能保证最终一致性；而如果要保障强一致性与可用性，如果出现网络故障将无法正常工作。
类似的，在调度系统中，如果要追求极限的资源利用率，则每一次调度的结果必须是基于当前资源池状态的最优解，因此不管调度队列还是调度处理计算只能是“单行道”，效率低下是毋庸置疑的，大批量伸缩调度场景下任务堆积严重。
如果追求高效的调度能力，则所有调度请求需要并发处理。但底层资源池只有一个，很容易出现多个调度请求争抢同一份资源的情况。这种情况下，就要采取措施来保障资源层数据一致性，且调度所得的结果不能保证是全局最优解（无法最大化资源利用率）。
业界解决思路
Mesos
Mesos采用双层调度的理念，把应用相关的管理交由上层Framework来做，这也是Mesos与Kubernetes等系统最大的不同点。Mesos只是分布式系统内核，即管理分布式资源、对外暴露标准接口来操作集群资源（屏蔽资源层细节）。在双层调度的模式下，Mesos只负责在不同的Framework之间分派资源，将资源作为Offer的形式提供给Framework。
这种做法把上述调度设计矛盾丢给了Framework，但如果只从提供资源Offer的角度来看，这是一种并发调度的形式（同一个Mesos资源池，资源要提供给上层多个Framework）。Mesos解决并发调度、资源池数据一致性的方案是，资源Offer同时只会分派给一个Framework。这种资源分派方式是悲观的，资源被Framework独占，直到返回或超时。
显然，这种悲观锁导致了Mesos双层调度的并发粒度较小，但是在多数情况下，同个Mesos集群上层的Framework数量不会太多，有时只有一个Framework在独享资源，因此这种悲观锁的方案一般不会存在分配调度的瓶颈问题。
Omega
Omega同样采用了将资源分派给上层应用的调度方式，与Mesos的悲观锁不同，Omega采用了乐观锁（MVCC，基于多版本的并发访问控制）解决并发调度的问题，因此Omega也被称为共享状态调度器。
由于将资源层信息作为共享数据提供给上层所有应用，Omega为了解决数据一致性，会对所有应用调度的提交冲突做解决，本质上是为每个节点维护了一个状态关系数据库。从这个角度看，Omega也存在一些缺点：
- 共享调度时冲突发生的频率，直接影响了整体调度器的性能。
- 由于没有集中的调度模块，难以对所有资源分组（Namespace）或用户的资源使用量做精确限制。
- 上层调度器数量仍然不能很多，并行分发完整的集群状态的开销较大。
Borg与Kubernetes
Borg据说现在已经逐渐演进吸收了Omega的很多设计思想，包括共享状态调度模式，然而Kubernetes默认调度plugin的做法仍然是串行处理队列中的调度任务，这也符合Kubernetes追求的简洁优雅。
HULK调度解决方案
对于调度器设计难题，我们认为针对不同的场景，指标的侧重点不同。
比如对于分布式系统的CAP，大多数互联网场景下都会保证AP而舍弃C（只保证最终一致性），因为在互联网分布式集群规模大、网络故障频发的场景下，要保证服务高可用只能牺牲强一致；而对于金融等涉及钱财的领域，则一般保证CA、舍弃P，即使遇到网络故障时只读不写，也必须保证强一致性。
同理对于调度器资源层设计，在互联网高并发、弹性伸缩频发的场景下，可以
牺牲部分资源利用率从而提高并发调度能力
。
HULK调度系统模型如下：
HULK调度模型
如图，HULK调度系统分为调度请求队列、调度计算模块、调度资源池这三个模块。工作流程如下：
- 上层HULK弹性伸缩系统，将调度任务ID写入调度请求队列中。
- HULK调度系统消费调度请求队列，取出的调度任务ID将由调度计算池执行调度计算，决策出备选的部署位置，并向调度资源池申请资源。
- 调度资源池维护管理宿主机集群资源，全部资源会提供给所有调度任务共享（与Omega类似），资源池中每个宿主机都有一个对应的Actor来负责管理。
调度计算模块（资源调度算法）
HULK调度系统的调度计算方式与诸多业界调度系统类似，通过过滤+打分的方式筛选出“最优部署位置”：
HULK调度任务
- 宿主机（Host）：调度资源池中共享的宿主机集群，支持pool级别硬隔离，如在线服务与数据库/缓存的实例部署在不同的物理机集群中；支持资源软隔离，如在线服务离线任务混布部署，通过cgroups等机制隔离和设置权重。
- 过滤（Filter）：预选（Predicates）的概念，通过超售、打散限制策略，排除掉一部分不合需求的宿主机。
- 打分（Rank）：优选（Priorities）的概念，通过在线离线混布、不同资源类型混布、宿主机负载均衡等策略和对应权重，最终计算出一个rank值，根据rank值排序最终得出最优部署位置。
超售
不管是在传统虚拟机时代还是容器时代，超售始终是一个让人又爱又恨的机制。
超售在一定程度上提高了集群的资源利用率，因为机器在申请之时往往提高对真实资源消耗的预估，也就是在服务运行中，绝大多数情况用不到申请的所有资源。然而正因为超售，常常会带来各种因资源争用引发的服务异常，严重的情况下会导致宿主机上所有实例的不可用。
HULK容器调度同样采用了超售机制，我们和IaaS层对资源进行了分类，可压缩资源（如CPU、I/O等）使用超售机制，而不可压缩资源（如Memory、Disk）只允许在一些测试环境超售。
相比于是否开启超售，超售系数才是更为棘手的难题，它直接关系到资源利用率和服务稳定性。我们采用了超售上限+动态系数的机制，从IaaS层设置的超售上限固定了资源超售的上限比例，超过上限的实例创建将会失败，而HULK调度系统会根据具体场景决定超售系数：
- 参考宿主机实时监控，如Load负载、内存使用、带宽占用等指标。
- 不同的实例类型（在线、离线）调度时超售系数不同。
业务实例打散
随着物理集群规模的扩大，宿主机故障频次也会响应提高。如果一个在线服务的所有实例都部署在同一个宿主机上，很可能出现宿主机宕机后服务整体不可用，这是我们不能接受的。
业务用户在HULK上配置不同的伸缩组，每个组对应了一个机房（数据中心），同个机房调度过程中会把同个服务的实例打散到不同的宿主机上，并优先在不同的交换机（机架）下。此外，针对数据库/缓存类的实例还有更严格的容灾策略，比如Redis实例调度部署时，不允许同一个交换机下部署超过该Redis集群25%的实例数量。
在线离线混布
一般来说，在线服务（如外卖、酒旅等服务）和离线任务（如定时任务、爬虫、大数据计算）的需求资源类型和高峰/执行时间不尽相同，将这两种实例进行混布可以有效提高物理集群的资源利用率。
Borg系统中对prod与non-prod实例的一类处理方式是，根据宿主机上实例运行状况，实时调整实例的资源配置。比如当在线服务迎来流量高峰、宿主机内存告急时，Borg会调整宿主机上non-prod任务的内存配额，以保证在线服务的稳定性。
但这种方案对Google中的部分C/C++服务适用，在美团点评Java服务的场景下，实例内存配额调整可能会导致OOM，而重启服务非我们所愿。
下图是HULK某台宿主机一天内的实例部署情况：
宿主机实例部署
目前HULK平台上的离线任务主要还是定时任务与爬虫，HULK针对在线离线混布场景从资源分配、时间错峰上优化。根据美团点评的服务特性，HULK会尽量保证在早晚高峰的时期动态扩容在线服务承接流量，而在低峰期会对应缩容在线服务，并调度部署离线任务执行。
宿主机负载均衡
在调度计算的打分过程中，还会参考当前宿主机的负载情况。
HULK会从监控系统中获取宿主机的系统监控数据，包括了CPU、Load、Memory、IO等指标。针对负载较低的宿主机我们给予较高的权重，而负载较高的宿主机，即使物理资源较为空闲，也不会优先选择部署。
调度资源池（资源申请算法）
当调度计算过程决策出一个根据调度rank权重排序好的资源可部署位置列表后，调度任务会取列表前n个元素，依次向对应的宿主机Actor申请资源，直到宿主机Actor返回批准（调度成功）；如果取出的前n个均被拒绝，调度任务需要根据新的全局资源池共享状态再次调度计算。
如果两个调度任务基于共享资源状态同时申请某个宿主机上同一块资源，则宿主机Actor会根据mailbox中消息的顺序来处理，资源先到先得，后者调度任务会继续向下一个备选资源的宿主机Actor尝试申请。
调度资源申请
这种资源调度的架构下，调度的并发度相比串行调度有了显著的提高，即使出现提交冲突，重试机制也是非常轻量的，一般都可以在前n次之内完成。
这里另一个核心问题在于n取值的权衡。如果n取值1，则每次失败后就需要根据当前的集群资源状态重新调度计算，这种情况下调度资源利用率较高，但效率较低；而若n取值大于1，则重试后的调度位置往往并非当前最佳调度位置，且n越大这里的最优调度偏差就越大。我们考虑的是根据当前整个系统中的调度请求数量来确定这个动态的n变量取值，当调度任务较少时n取较小值，当调度任务较多、弹性伸缩频繁时，n的取值会相应调大。
调度模式总结
总的来看，HULK调度系统的共享状态资源调度模式与Omega比较相似，不同的是Omega采用MVCC为每个节点维护一个状态关系数据库，而HULK使用Actor模型来解决提交冲突。另外，HULK调度任务的n次最优重试机制，在互联网的弹性伸缩场景下可以带来更高效的调度能力。
结束语
弹性调度系统作为HULK平台的核心模块之一，有着下接美团云IaaS平台、抽象化资源层，上承弹性伸缩系统、处理调度请求的职责。我们从美团点评的服务特殊性出发，打造适用于大规模容器化场景的调度体系，后续还会在大数据离线任务场景下做更优化的深层智能调度。
此外，我们对Kubernetes等开源解决方案同样抱有极大的兴趣，从Kubernetes近年来的发展上能看到未来容器平台的标准雏形，我们也在积极参与和回馈开源社区。
作者：思宇，2015年加入美团点评，目前是美团点评基础架构团队高级工程师，负责容器集群管理与弹性调度平台的设计开发工作，主攻调度、容器研发、集群管理等方向。
原文发布时间为：2017-05-15
本文作者：李颖杰
本文来自云栖社区合作伙伴Dockerone.io，了解相关信息可以关注Dockerone.io。
原文标题：美团点评容器平台HULK的调度系统
