Linuxeden开源社区云计算并非无中生有的概念，它将普通的单台PC计算能力通过分布式调度软件连接起来。其最核心的问题是如何把一百台、一千台、一万台机器高效地组织起来，灵活进行任务调度和管理，从而像使用单台机器一样方便地使用多台机器。目前，业界已存在多种分布式调度实现方案，比较知名的有 Hadoop YARN、Mesos、Google Borg 等。
区别于以上调度系统，腾讯云的 VStation 从诞生之初，便肩负着大规模调度、海量并发和支持异构计算的历史使命，历经五年的打磨和历练，VStation 通过消息压缩、镜像缓存、快照回滚等系列优化实践，实现了生产吞吐率从数百台/分钟到数万台/分钟、平均创建时间由300秒下降到30秒以下的惊人蜕变。本文将从分布式调度系统的演进史说起，深入浅出腾讯云 VStation 的缘起、架构和调度模式。
1. 分布式系统中调度的分类与含义
在正式介绍分布式调度之前，我们首先来明确调度的含义。事实上，在分布式系统中，调度的概念比较广泛。主要包括以下2种：
- 任务之间的调度，负责管理任务间的关系，典型系统/组件包括 Hadoop YARN 中的 Application Master 和 Airflow。
- 任务资源调度，负责为任务分配资源，典型系统包括 Google Borg、Mesos、Kubernetes 等。
在腾讯云中，不同的产品会解决不同的调度问题，例如批量计算 Batch 主要解决任务之间的调度问题，本质上属于工作流产品；云主机 CVM 则主要解决任务的资源调度问题。本文主要关注 CVM 产品，聚焦讨论的是第二种调度——任务资源调度。
公有云中的调度模型
分布式系统中的调度器通常是整个系统的核心组件，关系着整体性能， 因此业界也始终关注着任务资源调度问题。Google 还对任务调度进行了定义[1]。
Task scheduling refers to the assignment of tasks to machines.
这里的调度就是指为任务分配机器资源，从中不难看出，Task 和 Machine 是任务资源调度中的2个主角。
而在公有云中，VM（虚拟机）和 HOST（宿主机）则是调度天然的主角，我们其实仍然可以复用任务资源调度模型，只是2个角色发生了演化，Task 演化为 VM，Machine 演化为 HOST。这样，在公有云中，任务资源调度的模型就从“为 Task 分配 Machine 资源”演化为“为 VM 选择和分配 HOST 资源”。如果把负责任务资源调度的调度器看作一个函数黑盒，其输入是 VM 需求信息，调度器在 HOST 信息的基础上进行调度决策，为 VM 选择合适的 HOST，输出则是 VM 和 HOST 的匹配对。
2. 腾讯云调度系统面临的核心挑战
异构性与调度质量
腾讯云集群规模庞大、架构复杂，伴随着业务的高速增长和发展，系统的调度质量随着宿主机的异构趋势和虚拟机多样化需求呈现指数增长。
宿主机的异构性趋势
数据中心通常具有集群规模大、维护周期长的特点。在数据中心的生命周期中，经常会新增采购新型宿主机，例如伴随着硬件更新换代，会逐步采购 Intel Haswell、Broadwell、Skylake 机型，而这些机型在计算能力上的表现是不同的。在集群整合的背景下，也可能将不同批次的中小集群整合为一个大型集群使用。考虑到这些情况，集群宿主机通常会存在一定的差异。
腾讯云的硬件和虚拟化团队会不断的研究和发布新特性，为用户提供更为优质、稳定的服务。对于大部分特性，我们通常会在一个相对可控、较短的时间内完成全网发布。但是，对于一些提升明显的大型特性，出于安全稳定的综合考虑或者受限于存量宿主机的升级方式，也会采用灰度升级的发布方式，这样也会造成宿主机集群的异构性。
虚拟机的多样性需求
腾讯云的客户应用场景多种多样，行业覆盖十分广泛，其对计算资源的需求和敏感点也千差万别。为此，腾讯云提供不同实例机型来满足用户多样化的机型，包括产品概念上的系列1、系列2、系列3机型，分别对应前文所述的 Intel Haswell、Broadwell、Skylake 机型；每个系列中，我们也会提供标准型、计算型、内存型、高IO型等不同机型。
在当前异构计算兴起的背景下，腾讯云率先支持 GPU、FPGA、智能网卡的异构机型，将业界最新、最强的计算能力开放给用户使用。用户购买不同的虚拟机机型，腾讯云后台的调度器会选择满足相应条件的宿主机，这种多样化的产品机型策略，也加剧了异构化的挑战。
与此同时，调度过程中通常还要考虑多种策略因素，例如：
- 同一用户的虚拟机反亲和性打散，将用户的虚拟机分散放置到不同的故障域中，以此保证用户服务的高可用性；
- 并发创建打散，控制单台宿主机同时创建虚拟机的数量，以此保证虚拟机创建速度；
- 优先选择命中镜像缓存的宿主机，以此避免下载镜像，加快创建速度；
- 考虑资源利用率，保证SLA和集群资源利用率的相对平衡；
- ……
异构性对调度质量造成的挑战
在宿主机和虚拟机异构化的场景下，出现了一些明显的趋势：不是所有的宿主机都可以满足虚拟机的需求，即硬性约束；即便是满足虚拟机基本需求的宿主机，其满足程度也是不同的，即软性约束。公有云中的资源调度本质上是对虚拟机和宿主机进行匹配，而异构性增加了二者匹配过程的复杂度，这对调度质量造成了挑战。
大规模与调度吞吐率
超大规模的宿主机集群
近年来，公有云迎来爆发式增长，腾讯云则长期保持着优于市场水平的超高增速，连续多年以三位数的百分增长率飞速发展。为此，腾讯为用户提供了丰富类型、数量巨大的宿主机。伴随着这样的高增长，腾讯云单个 Region 规模越来越大，达到了十万量级，整个 Region 的数据中心都由一套腾讯云调度系统负责管理和调度。可扩展性是分布式系统公认的核心挑战，超大规模的集群对分布式调度系统带来了显著挑战。
海量的云主机购买需求
同样是收益于云计算的快速发展，在2016、2017年，虚拟机的购买次数指数级增长，并伴随着明显的波动性，形成了潮汐式的海量并发购买现象。对于这种潮汐式用户，可以划分为“直接用户”和“间接用户”，直接用户是指直接购买 CVM 的用户，比如网络爬虫、秒杀抢购用户；间接用户是指用户通过其他腾讯云产品或服务来购买 CVM 实例，例如弹性伸缩（AS）、批量计算（Batch）、竞价实例（Spot）引流的客户。
我们可以设想，弹性伸缩的用户，在其集群负载高企的时候，希望可以尽快的完成扩容操作，以此保障其自身的服务质量。其实，无论是直接用户还是间接用户，都具有规模大、时效强的特征。这个规模有多大呢？每小时需要完成数万台虚拟机的购买请求，峰值则为每分钟上千台虚拟机的购买请求。
超大规模对调度吞吐率带来的挑战
在 CVM 进行专题优化之前，当时的单个 Region 的生产吞吐率约为 100 台/分钟，统计的时间标准是从腾讯云后台收到请求为起点，到交付可用的虚拟机为终点来计算，整个统计过程包括IO操作，覆盖完整的生产流程。100台/分钟生产吞吐率意味着每小时可以生产6000台虚拟机。直观来说，对于一款 toB 的产品，这样的生产吞吐率并不算低，但是当时已经无法满足用户的海量购买需求。
通过系统测评，我们发现调度器已经成为整个系统的性能瓶颈，调度吞吐率不足，处理延迟增加，影响了整个系统的可扩展性。同时，我们的用研团队通过调研发现，国内用户对于等待时间非常敏感，长时间创建容易引起焦虑，希望可以进一步的缩短创建时间。总体来说，性能瓶颈既影响了用户业务的时效性，又影响了用户体验，无论从理性还是感性来看，都需要解决调度吞吐率面临的挑战。
3. 调度架构的演化规律
在异构化、规模化的背景下，针对调度质量、吞吐率等问题，许多公司和研究机构都做了相应的工作。Google 和 UC Berkeley 就提出了他们认为的调度系统的演变规律[2]：伴随着调度系统的发展，逐步出现统一调度架构、两级调度架构和共享状态调度架构。
统一调度架构
如图所示，左侧的架构即为统一调度架构，下方是集群的宿主机；中间是集群状态信息，用于保存宿主机的资源状态；上方是统一的调度器，负责接收调度请求，并在集群状态信息的基础上进行调度决策。许多调度系统最初都被设计为这种架构，例如第一代 Hadoop MapReduce。
这种架构，设计简单，可以便捷的保持资源数据一致性，但是当宿主机规模增大时，调度器处理单次资源调度请求的时间会开始增加。当资源调度请求增大到一定程度时，调度器的吞吐量不足，调度请求开始排队，造成任务阻塞积压。
两级调度架构
两级调度系统，其典型代表是 Mesos。Mesos Master 通过 Resource Offer 的形式和上层 Framework 的调度器进行资源通信。在灵活性上和并发性上有了一定的改善。但是仍然存在局限性。
- 缺乏全局资源视图。上层调度器只能在分配给它的 Resource Offer 的范围内进行调度，相当于只有子集资源视图，没有全局资源视图，无法保证调度决策全局最优。特别是在需要抢占的情况下，无法实现跨调度器抢占，例如公有云中竞价实例的场景。
- 并发度仍然受限，Resource Offer 机制本质上是在不同的 Framework 之间进行串行轮询，相当于悲观加锁并发控制，并发度仍然有提升空间。
和 Mesos 同时期的 Hadoop YARN 是另一款著名的分布式调度系统，其类型划分一直存在争议。Hadoop YARN 的支持者[3]表示 YARN 是一款两级调度系统，而 Google 系的研究成果则通常认为 YARN 属于统一调度架构。我们更加认同 Google 的看法，认为 YARN 属于统一调度架构。
如果要讨论调度架构的划分，首先要明确调度的含义。统一调度、两级调度、共享调度是 Omega 提出的分类方法，这里的调度是指为任务分配资源，而不是处理任务间的关系。在这个前提下，Hadoop YARN 的调度过程是由 Resource Manager 完成的，而 Application Master 主要负责任务间关系的管理工作，并未实际参与调度过程。因此，Hadoop YARN 属于统一调度架构。
共享状态调度架构
两级调度架构在资源视图、调度并发度方面存在的问题，业界提出了共享状态调度架构，其典型代表是 Google Borg 和 Omega。调度系统具有多个调度器，调度器之间采用无锁乐观并发机制，每个调度器都具有全局资源视图，可接收待调度任务，同时进行调度。
但是，并发调度也带来一个明显的问题——调度冲突：即多个调度器同时工作并选中了相同的宿主机，只有一个调度器可以调度成功，其余调度器需要重新进行调度。在调度并发度较大的情况下，其实调度冲突的概率是比较大的，重新调度的代价偏大。
4. VStation 总体架构
为了解决超大规模对调度吞吐率带来的挑战，2013 年初，腾讯云自主研发的革命性虚拟化平台 VStation 全面上线。作为腾讯云新一代的调度系统， 作为腾讯云新一代的调度系统，VStation 承载了腾讯云 CVM 后台的整体集群管理与系统调度，其架构图如图所示。在 VStation 架构中存在多种模块，Scheduler 就是其中的一种模块，负责为虚拟机选择合适的宿主机。
- Compute，是宿主机上的 agent 程序，负责和后端通信，并调用 libvirt 等工具。
- Compute Access，是 Compute 与后台架构通信的一个接入层。
- Network，负责云主机的网络相关操作。
- Image，负责云主机的镜像相关操作。
- Scheduler，负责调度功能，为云主机挑选最佳宿主机。
- Resource，负责资源数据的操作。
- Volume，负责磁盘相关操作。
在 VStation 中，每个模块并不直接相互调用，而是监听特定的队列并提供一个回调函数，框架会将参数传递给回调函数执行，业务层的开发人员只需专注于自身的业务逻辑，不必关心消息通信，通信会由框架统一进行管理。
那么各个模块如何协同完成任务的呢？这些模块会通过消息队列进行间接通信，具体的通信策略由上层 VStation API 进行配置化，API 定义每个流程需要执行的具体步骤和顺序。
这样的架构设计理念类似于 Unix，只做一件事并把它做好。每个模块就像 Unix 中的命令一样，专注于自身的逻辑，如果它们需要互相组合，开发人员可以通过上层 API 进行配置化组合。
以创建云主机为例，当 VStation API 收到用户的创建任务时，API 会构造一个消息模板，设置好用户的参数，填充好预先定义的配置步骤，按照配置步骤发送给第一个步骤对应的模块，第一个步骤的模块执行完成后会发送给第二个步骤的模块，依次类推。Scheduler 则属于其中的一个模块，其中的一个消费者收到任务信息后，选择合适的选宿主机，当完成调度后，将数据包转发给下一个接收模块进行处理。最后所有的步骤按照配置的顺序执行完成，虚拟机创建流程也就自然完成了。
5. VStation 的调度架构与优化实践
调度架构
VStation 的调度架构，本质上与 Google Borg/Omega类似，采用共享状态调度架构，众多调度器采用无锁乐观并发机制、基于全局资源视图进行调度决策，显著提升了调度器的吞吐率； 提交调度结果保证事务性，保证资源数据的强一致性。另一方面，针对 Google Omega 存在的隐患，对调度冲突进行优化。
总体来说，调度过程包括资源同步、调度决策和提交调度结果三个环节。
资源同步
调度器在接收待调度虚拟机后，会先进行资源同步，拉取集群状态信息，以此为数据基础进行调度决策。资源同步操作在逻辑上看较为直观，但是在超大规模数据中心中遇到了挑战。腾讯云单个 Region 宿主机的规模达到了十万量级，调度器达到了数百规模，即调度总量数据为千万级规模，即使使用高配置的数据库集群也会在调度高峰时出现明显的延迟。
为此，我们采用私有缓存和增量更新的方法拉取数据。调度器启动后首次调度时，会全量拉取数据，并缓存在调度器本地内存中，形成私有缓存；后续调度时会根据时间戳进行增量更新，对上一次调度之后发生变化的数据进行更新。这样，在大规模调度的场景下，同步数据量可减少95%以上。
调度决策
在资源同步之后，调度器会在全局资源视图的基础上，为虚拟机选择合适的宿主机，整体包括3个环节过滤、排序和打散。
- 过滤，应对硬性约束。根据虚拟机信息中的资源需求和私有缓存中的宿主机信息，对宿主机集合进行过滤，保留符合标准的宿主机，剔除不符合标准的宿主机，得到候选宿主机列表。
- 排序，应对软性约束。根据候选宿主机列表，计算每台宿主机多个维度的优先级值，并对宿主机进行优先级排序，得到候选宿主机排序列表。
- 打散。根据候选宿主机排序列表，对其中第一档前 k 个宿主机进行随机打散重新排序，得到新的排序列表，这样做的目的是防止众多调度器在并发场景下都选择相同的宿主机，尽量防止调度冲突，降低其发生概率。
提交调度结果
VStation 提交调度结果，会保证资源数据更新的事务性。这一点非常重要，因为在并发调度的场景下，很容易出现调度冲突，我们通过事务来保证资源数据的一致性。主要环节如下：
- 按序遍历宿主机候选列表
- 对当前宿主机模拟扣减资源
- 提交资源变更事务：更新资源数据、反亲和性记录
- 如果事务成功，则本次调度成功，同时更新私有缓存中的数据
- 如果事务多次失败，则发生调度冲突，尝试下一台宿主机
如果发生调度冲突，VStation 会选择次优宿主机。相比 Google Omega 重新调度的做法，对调度冲突的处理代价显著减小。在公有云海量并发创建的场景下，VStation 在调度决策和调度吞吐率进行权衡，选择次优解来保证调度吞吐率。
海量并发场景下的极速创建
在调度专题优化以外，针对其他问题，VStation 也进行了相应优化，包括：
- 消息压缩、合并，提升系统内部消息流转效率；
- 宿主机缓存高频使用镜像，调度器优先选择命中镜像缓存的镜像，尽量避免下载镜像；
- 采用 CBS 云盘快照回滚技术，避免下载镜像，减少创建时间。
结合这些技术优化，VStation 生产流程的整体吞吐率得到了大幅提升。在十万量级的宿主机环境下，采用数百个 Scheduler 消费者，我们对 CVM 进行了多次海量并发创建演习，生产吞吐率从原来的数百台/分钟提升到数万台/分钟；而平均创建时间降低了90%，部分公有镜像的创建时间更是可以缩减到10秒以内。成功应对了2016、2017年以来的海量并发创建的挑战，为腾讯云 CVM 业务的爆发式增长提供了坚实的技术基础。
调度系统的演化
在 VStation 专题优化的尾声，团队进行了回顾和总结，更加广泛的去分析和对比业界的系统，我们发现，VStation 的许多机制都和业界的做法相似，VStation 从一开始就采用共享状态调度架构；为了解决资源数据量级过大的问题，采用私有缓存和增量更新的方法，这些都与 Google Borg 的做法不谋而合。面对相同的问题和挑战，不同的系统，可能无法战胜挑战，被替换掉；也可能采用相同或相似的方法解决问题，并最终进化为类似的架构。
6. 腾讯云分布式调度系统的技术优势
业界系统对比，VStation 具有大规模调度能力，速度快，高可用，支持异构计算调度。
- 速度快：VStation 在腾讯云数十万集群规模中，得到了充分的考验。结合腾讯云的真实业务场景来看，调度模块的吞吐量可达每分钟数万台，整个系统的生产吞吐率可达每分钟数万台，相比业界 OpenStack Nova，其并发调度和创建100台虚拟机，则系统运行开始变慢，在冲突加剧的场景则会导致创建失败，需要重新进行调度资源，调度效率低。
- 高可用：得益于框架的能力，VStation 的每个调度进程都是无状态、可平行扩容的。同时，在一些特殊情况如消费者崩溃、MQ 崩溃等极端场景下，VStation 能够基于 MQ 的 ACK 机制、Mirror 机制、消息持久化机制等，将未执行完成的消息重新发送给活跃的进程，重新进行调度。
- 支持异构计算：随着硬件产品的丰富，例如 GPU、FPGA、智能网卡等专用设备的出现，以前的调度系统也需要考虑相关新硬件的资源统筹调度。在 VStation 中，针对这类的 PCI 设备进行统一管理，可以快速适配和纳管新型异构硬件，腾讯云的专有云解决方案 TCE 就采用了 VStation 分布式调度系统。
7. 未来改进策略
任务间调度
目前，VStation 侧重点是一个资源调度系统，未来会对加强任务间的管理与调度，能够对任务关系和资源统一进行管理，整合资源的负载情况，做出最优的调度决策。
调度系统的可视化运营
对于资源运营同学来看，资源调度的内部逻辑相当于黑盒。例如这台宿主机为何没有被分配资源，整个调度过程是如何层层筛选的、又是如何优选排序的？我们计划开发一个为调度系统服务的实时可视化系统，使得调度逻辑更加透明化、直观化，让使用的人员可以了解调度系统的内部运行机制。
参考
[1] Sharma, Bikash, et al. “Modeling and synthesizing task placement constraints in Google compute clusters.” Proceedings of the 2nd ACM Symposium on Cloud Computing. ACM, 2011.
[2] Schwarzkopf, Malte, et al. “Omega: flexible, scalable schedulers for large compute clusters.” Proceedings of the 8th ACM European Conference on Computer Systems. ACM, 2013.
[3] Vavilapalli, Vinod Kumar, et al. “Apache hadoop yarn: Yet another resource negotiator.” Proceedings of the 4th annual Symposium on Cloud Computing. ACM, 2013.
作者简介
陈煜东（dondonchen），腾讯云高级工程师，2014年加入腾讯，现为腾讯云云主机核心研发，一直从事分布式资源调度、系统框架研发工作，对大规模集群调度具有丰富的理论与实践经验。
王旻（alexmwang），腾讯云高级工程师，硕士就读于中科院计算所，有丰富的分布式调度系统理论和实践经验。2015年加入腾讯，负责腾讯云CVM（云主机）和批量计算产品的设计和开发，致力于打造高吞吐、高可用的调度系统和计算产品。
转自 http://www.infoq.com/cn/articles/tecent-cloud-distributed-system-vstation