云计算并非无中生有的概念，它将普通的单台PC计算能力通过分布式调度软件连接起来。其最核心的问题是如何把一百台、一千台、一万台机器高效地组织起来，灵活进行任务调度和管理，从而像使用单台机器一样方便地使用多台机器。目前，业界已存在多种分布式调度实现方案，比较知名的有 Hadoop YARN、Mesos、Google Borg 等。
区别于以上调度系统，腾讯云的 VStation 从诞生之初，便肩负着大规模调度、海量并发和支持异构计算的历史使命，历经五年的打磨和历练，VStation 通过消息压缩、镜像缓存、快照回滚等系列优化实践，实现了生产吞吐率从数百台/分钟到数万台/分钟、平均创建时间由300秒下降到30秒以下的惊人蜕变。本文将从分布式调度系统的演进史说起，深入浅出腾讯云 VStation 的缘起、架构和调度模式。
1. 分布式系统中调度的分类与含义
在腾讯云中，不同的产品会解决不同的调度问题，例如批量计算 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. 腾讯云调度系统面临的核心挑战
异构性与调度质量
腾讯云集群规模庞大、架构复杂，伴随着业务的高速增长和发展，系统的调度质量随着宿主机的异构趋势和虚拟机多样化需求呈现指数增长。
宿主机的异构性趋势
虚拟机的多样性需求
腾讯云的客户应用场景多种多样，行业覆盖十分广泛，其对计算资源的需求和敏感点也千差万别。为此，腾讯云提供不同实例机型来满足用户多样化的机型，包括产品概念上的系列1、系列2、系列3机型，分别对应前文所述的 Intel Haswell、Broadwell、Skylake 机型；每个系列中，我们也会提供标准型、计算型、内存型、高IO型等不同机型。
在当前异构计算兴起的背景下，腾讯云率先支持 GPU、FPGA、智能网卡的异构机型，将业界最新、最强的计算能力开放给用户使用。用户购买不同的虚拟机机型，腾讯云后台的调度器会选择满足相应条件的宿主机，这种多样化的产品机型策略，也加剧了异构化的挑战。
异构性对调度质量造成的挑战
在宿主机和虚拟机异构化的场景下，出现了一些明显的趋势：不是所有的宿主机都可以满足虚拟机的需求，即硬性约束；即便是满足虚拟机基本需求的宿主机，其满足程度也是不同的，即软性约束。公有云中的资源调度本质上是对虚拟机和宿主机进行匹配，而异构性增加了二者匹配过程的复杂度，这对调度质量造成了挑战。
大规模与调度吞吐率
超大规模的宿主机集群
近年来，公有云迎来爆发式增长，腾讯云则长期保持着优于市场水平的超高增速，连续多年以三位数的百分增长率飞速发展。为此，腾讯为用户提供了丰富类型、数量巨大的宿主机。伴随着这样的高增长，腾讯云单个 Region 规模越来越大，达到了十万量级，整个 Region 的数据中心都由一套腾讯云调度系统负责管理和调度。可扩展性是分布式系统公认的核心挑战，超大规模的集群对分布式调度系统带来了显著挑战。
海量的云主机购买需求
同样是收益于云计算的快速发展，在2016、2017年，虚拟机的购买次数指数级增长，并伴随着明显的波动性，形成了潮汐式的海量并发购买现象。对于这种潮汐式用户，可以划分为“直接用户”和“间接用户”，直接用户是指直接购买 CVM 的用户，比如网络爬虫、秒杀抢购用户；间接用户是指用户通过其他腾讯云产品或服务来购买 CVM 实例，例如弹性伸缩（AS）、批量计算（Batch）、竞价实例（Spot）引流的客户。
我们可以设想，弹性伸缩的用户，在其集群负载高企的时候，希望可以尽快的完成扩容操作，以此保障其自身的服务质量。其实，无论是直接用户还是间接用户，都具有规模大、时效强的特征。这个规模有多大呢？每小时需要完成数万台虚拟机的购买请求，峰值则为每分钟上千台虚拟机的购买请求。
超大规模对调度吞吐率带来的挑战
在 CVM 进行专题优化之前，当时的单个 Region 的生产吞吐率约为 100 台/分钟，统计的时间标准是从腾讯云后台收到请求为起点，到交付可用的虚拟机为终点来计算，整个统计过程包括IO操作，覆盖完整的生产流程。100台/分钟生产吞吐率意味着每小时可以生产6000台虚拟机。直观来说，对于一款 toB 的产品，这样的生产吞吐率并不算低，但是当时已经无法满足用户的海量购买需求。
通过系统测评，我们发现调度器已经成为整个系统的性能瓶颈，调度吞吐率不足，处理延迟增加，影响了整个系统的可扩展性。同时，我们的用研团队通过调研发现，国内用户对于等待时间非常敏感，长时间创建容易引起焦虑，希望可以进一步的缩短创建时间。总体来说，性能瓶颈既影响了用户业务的时效性，又影响了用户体验，无论从理性还是感性来看，都需要解决调度吞吐率面临的挑战。
3. 调度架构的演化规律
在异构化、规模化的背景下，针对调度质量、吞吐率等问题，许多公司和研究机构都做了相应的工作。Google 和 UC Berkeley 就提出了他们认为的调度系统的演变规律[2]：伴随着调度系统的发展，逐步出现统一调度架构、两级调度架构和共享状态调度架构。
统一调度架构
如图所示，左侧的架构即为统一调度架构，下方是集群的宿主机；中间是集群状态信息，用于保存宿主机的资源状态；上方是统一的调度器，负责接收调度请求，并在集群状态信息的基础上进行调度决策。许多调度系统最初都被设计为这种架构，例如第一代 Hadoop MapReduce。
这种架构，设计简单，可以便捷的保持资源数据一致性，但是当宿主机规模增大时，调度器处理单次资源调度请求的时间会开始增加。当资源调度请求增大到一定程度时，调度器的吞吐量不足，调度请求开始排队，造成任务阻塞积压。
两级调度架构
和 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 就是其中的一种模块，负责为虚拟机选择合适的宿主机。
在 VStation 中，每个模块并不直接相互调用，而是监听特定的队列并提供一个回调函数，框架会将参数传递给回调函数执行，业务层的开发人员只需专注于自身的业务逻辑，不必关心消息通信，通信会由框架统一进行管理。
那么各个模块如何协同完成任务的呢？这些模块会通过消息队列进行间接通信，具体的通信策略由上层 VStation API 进行配置化，API 定义每个流程需要执行的具体步骤和顺序。
这样的架构设计理念类似于 Unix，只做一件事并把它做好。每个模块就像 Unix 中的命令一样，专注于自身的逻辑，如果它们需要互相组合，开发人员可以通过上层 API 进行配置化组合。
以创建云主机为例，当 VStation API 收到用户的创建任务时，API 会构造一个消息模板，设置好用户的参数，填充好预先定义的配置步骤，按照配置步骤发送给第一个步骤对应的模块，第一个步骤的模块执行完成后会发送给第二个步骤的模块，依次类推。Scheduler 则属于其中的一个模块，其中的一个消费者收到任务信息后，选择合适的选宿主机，当完成调度后，将数据包转发给下一个接收模块进行处理。最后所有的步骤按照配置的顺序执行完成，虚拟机创建流程也就自然完成了。
5. VStation 的调度架构与优化实践
调度架构
VStation 的调度架构，本质上与 Google Borg/Omega类似，采用共享状态调度架构，众多调度器采用无锁乐观并发机制、基于全局资源视图进行调度决策，显著提升了调度器的吞吐率； 提交调度结果保证事务性，保证资源数据的强一致性。另一方面，针对 Google Omega 存在的隐患，对调度冲突进行优化。
总体来说，调度过程包括资源同步、调度决策和提交调度结果三个环节。
资源同步
调度器在接收待调度虚拟机后，会先进行资源同步，拉取集群状态信息，以此为数据基础进行调度决策。资源同步操作在逻辑上看较为直观，但是在超大规模数据中心中遇到了挑战。腾讯云单个 Region 宿主机的规模达到了十万量级，调度器达到了数百规模，即调度总量数据为千万级规模，即使使用高配置的数据库集群也会在调度高峰时出现明显的延迟。
为此，我们采用私有缓存和增量更新的方法拉取数据。调度器启动后首次调度时，会全量拉取数据，并缓存在调度器本地内存中，形成私有缓存；后续调度时会根据时间戳进行增量更新，对上一次调度之后发生变化的数据进行更新。这样，在大规模调度的场景下，同步数据量可减少95%以上。
调度决策
在资源同步之后，调度器会在全局资源视图的基础上，为虚拟机选择合适的宿主机，整体包括3个环节过滤、排序和打散。
提交调度结果
VStation 提交调度结果，会保证资源数据更新的事务性。这一点非常重要，因为在并发调度的场景下，很容易出现调度冲突，我们通过事务来保证资源数据的一致性。主要环节如下：
如果发生调度冲突，VStation 会选择次优宿主机。相比 Google Omega 重新调度的做法，对调度冲突的处理代价显著减小。在公有云海量并发创建的场景下，VStation 在调度决策和调度吞吐率进行权衡，选择次优解来保证调度吞吐率。
海量并发场景下的极速创建
在调度专题优化以外，针对其他问题，VStation 也进行了相应优化，包括：
结合这些技术优化，VStation 生产流程的整体吞吐率得到了大幅提升。在十万量级的宿主机环境下，采用数百个 Scheduler 消费者，我们对 CVM 进行了多次海量并发创建演习，生产吞吐率从原来的数百台/分钟提升到数万台/分钟；而平均创建时间降低了90%，部分公有镜像的创建时间更是可以缩减到10秒以内。成功应对了2016、2017年以来的海量并发创建的挑战，为腾讯云 CVM 业务的爆发式增长提供了坚实的技术基础。
调度系统的演化
在 VStation 专题优化的尾声，团队进行了回顾和总结，更加广泛的去分析和对比业界的系统，我们发现，VStation 的许多机制都和业界的做法相似，VStation 从一开始就采用共享状态调度架构；为了解决资源数据量级过大的问题，采用私有缓存和增量更新的方法，这些都与 Google Borg 的做法不谋而合。面对相同的问题和挑战，不同的系统，可能无法战胜挑战，被替换掉；也可能采用相同或相似的方法解决问题，并最终进化为类似的架构。
6. 腾讯云分布式调度系统的技术优势
业界系统对比，VStation 具有大规模调度能力，速度快，高可用，支持异构计算调度。
7. 未来改进策略
任务间调度
目前，VStation 侧重点是一个资源调度系统，未来会对加强任务间的管理与调度，能够对任务关系和资源统一进行管理，整合资源的负载情况，做出最优的调度决策。
调度系统的可视化运营
对于资源运营同学来看，资源调度的内部逻辑相当于黑盒。例如这台宿主机为何没有被分配资源，整个调度过程是如何层层筛选的、又是如何优选排序的？我们计划开发一个为调度系统服务的实时可视化系统，使得调度逻辑更加透明化、直观化，让使用的人员可以了解调度系统的内部运行机制。
