关于架构:获国际架构顶会ATC2021最佳论文Fuxi20去中心化的调度架构详解

简介：近日，在国内体系架构顶会 USENIX ATC2021 上，阿里云飞天伏羲团队与香港中文大学单干的一篇论文《Scaling Large Production Clusters with Partitioned Synchronization》不仅胜利被大会录取，而且被大会专家组评定为三篇最佳论文之一（Best Paper Award）。

作者 | 冯亦挥、刘智、赵蕴健、金晓月、吴一迪、张杨、郑尚策、李超、关涛
起源 | 阿里技术公众号

引言

近日，在国内体系架构顶会 USENIX ATC2021 上，阿里云飞天伏羲团队与香港中文大学单干的一篇论文《Scaling Large Production Clusters with Partitioned Synchronization》不仅胜利被大会录取，而且被大会专家组评定为三篇最佳论文之一（Best Paper Award）。

ATC 在计算机系统畛域极具影响力。自 1992 年至今，ATC 已胜利举办 31 届，吸引了普林斯顿、斯坦福、加州大学伯克利分校、康奈尔、中国清华大学、北京大学等顶级名校，以及微软、英特尔、三星等科技巨头公布研究成果。ATC 对论文要求极高，必须满足基础性奉献、前瞻性影响和松软零碎实现的要求，2021 USENIX 组委会录用 64 篇（录取率为 18%），寰球仅选取 3 篇最佳论文（其余两篇来自 Stanford University 和 Columbia University）。这也是 ATC 最佳论文首次呈现中国公司的身影。

本次大会上，咱们具体介绍了 Fuxi 2.0 我的项目的最新成绩，超大规模分布式集群去中心化的调度架构，首次向外界披露了阿里云在超大规模集群调度上的实现细节，也是飞天操作系统外围能力的又一次胜利展示。

一 论文背景

AI/ 大数据计算场景，随着计算需要的快速增长，云计算集群冲破单集群万台规模（一个集群可能有 10 万台机器，每天执行数十亿个工作，特地是短时工作），以实现高利用率低成本的附加值，具备重要意义。资源调度器作为大型生产集群的外围组件，它负责将集群内的多维度资源申请与机器资源进行高效匹配，而集群规模的增长，意味着有更高的并发申请，产生”乘积“效应，使调度复杂度急剧减少。因而，如何实现集群规模的可扩大，在保持良好的调度成果的同时，做到高并发、低延时，是业内公认的十分艰巨的工作。传统的核心调度器，受限于单点调度能力，大多数无奈解决生产级别的规模，也无奈保障稳定性和健壮性，做到降级过程对用户通明。

二 现状剖析

1 作业负载

在阿里巴巴，单个计算集群每天运行着数百万的作业。图 1a（实心曲线）绘制了一个集群某个月份内每天随机解决的作业数，334 万至 436 万，而一个作业由许多工作组成，图 1a（虚线）显示每天的工作数量大略为从 31 亿到 44 亿。其中大部分工作都是短时工作，如图 1b 所示，87% 的工作在 10 秒内实现。大规模集群的调度负载还是十分大的。

2 调度架构降级的必要性

在 Fuxi1.0，调度器遵循典型的 master-worker 架构，FuxiMaster 负责管理并调度集群中的所有资源，同时每台机器上有一个 agent，Tubo，定期通过心跳音讯向 FuxiMaster 同步状态。用户提交的每个作业都有其所在的 quota 组的信息，quota 组能应用资源的最大最小值由 SRE 设置。咱们的 quota 机制既能在集群高负载时保障各个 quota 组之间的公平性，也能在集群绝对较闲时，削峰填谷，让集群资源被充沛应用。

近年来，计算集群的规模在显著地增长，在可预感的未来，集群规模很可能冲破十万台。面对超大规模集群，一种办法是将集群动态切分为几个小集群，但该办法有着显著的局限性。首先，一些超大规模作业的资源需要可能就超过上述单个集群的规模；其次，集群的切分也会带来资源碎片问题，部分视图无奈保障全局调度后果的最优；最初是其余非技术的因素，比方 project 之间存在依赖关系，同一业务部门的不同 project 须要相互拜访数据，将它们部署在同一个集群（而不是拆分成一个个小集群）会大大降低运维和治理的代价。

但单 master 架构无奈解决十万级别的集群规模，次要有两方面起因：1）随着集群规模的扩充，受限于单调度器解决能力的下限，master 和 worker 之间的心跳延时会减少，调度信息不能及时下发，导致集群利用率降落；2）规模的晋升意味着更高的工作并发度，使调度复杂度急剧减少，最终超过单调度器的解决能力。

3 调度的指标和挑战

除了规模可扩展性上的挑战，调度器还应在以下多个调度指标间进行衡量，咱们关注的指标次要包含：

• 调度效率（或者延时），即一个工作须要在资源上期待多长时间，一个好的调度器应该让资源疾速流转。
• 调度品质，资源的束缚是否都被满足，比方 data locality，更大体积的内存，更快的 CPU 型号等。
• 公平性和优先级，在多租户共享的生产环境，须要保障租户间资源应用的公平性，同时提供高优先级作业的保障机制。
• 资源利用率，一个极其重要的指标，集群利用率低会面临很多挑战，尤其是财务上的挑战。

但上述几个指标之间通常是互相冲突的，比方，更好的调度成果往往象征更长的调度延时，相对的公平性有时会导致资源未能被充沛应用，从而导致集群利用率降落。

通过十几年的积攒，伏羲的资源调度器通过各种策略在上述几大指标间实现了很好的衡量，但思考资源调度周边还有其余兄弟团队开发的利用组件，咱们在设计新的调度器时，也应该做到尽量少改变，以放弃零碎的健壮性和向前兼容性。调度器架构调整引入的系统升级应该对用户是通明的，不论是外部用户还是内部用户。

三 实践概述

针对调度器的规模可扩大问题，咱们对业内现有的调度模型做了宽泛的调研（详见论文），并选取了其中一个最适宜咱们场景的计划（Omega）进行进一步的剖析。以 Omega 为代表的 shared-state 的多调度器架构能满足咱们之前说的那两个约束条件，向后兼容和对用户通明。然而 share-state 计划不可避免的会带来调度抵触，咱们心愿能分明如下几个问题：

1. 有哪些因素会影响抵触，它们各自的权重是多少？
2. 调度提早会好转到什么水平？
3. 如何才可能防止或减缓抵触？

咱们首先对抵触进行建模，得出抵触 (Conflict) 的冀望为(推导过程详见论文)：

在上述公式中，Yi 是多调度器在某个 slot 上抵触的冀望，N 是调度器的数量，K 是单个调度器的解决能力，S 是机器可调度的槽位数。可见，如果想缩小抵触的概率，能够通过减少 S 或者 N 来实现。减少 S 是一种很合乎直觉的形式，通过额定的资源供应来升高抵触概率。减少 N 的形式有些反直觉，因为调度器越多，越容易减少抵触，然而尽管在一轮调度过程中抵触变多了，但每个调度器一开始分到的 task 调度压力也等比例地减小了，所以就有了更多的工夫来解决抵触，最终反而起到了升高抵触概率的成果。总结起来，减少 N 是在整体压力不变的状况下，通过升高每个调度器的调度压力来实现抵触的缩小的。

此外咱们也通过公式证实了，在调度器数量 >1 的状况下，无奈彻底消除抵触。

上面的试验反映了不同的抵触因素对抵触的影响：

• 图 a 考量的是工作压力变动对抵触产生的影响。R 示意调度器收到的 task 速率，能够看到在调度器数量雷同的状况下，随着 R 的增大，为了放弃抵触数量不产生显著的变动，须要额定补充的 slot 数目就越多；反过来，在 R 不变的状况下，随着调度器数量的减少，每个调度器接受的调度压力降落，须要额定补充的 slot 数目就越少。
• 图 b 反映的是资源视图同步频率变动对抵触的影响。G 示意同步的提早，能够看到在调度器数量雷同的状况下，随着 G 的增大，为了放弃抵触数量不产生显著的变动，须要额定补充的 slot 数目就越多；反过来，在 G 不变的状况下，随着调度器数量的减少，每个调度器接受的调度压力降落，须要额定补充的 slot 数目就越少。
• 图 c 反映的是机器分数 (比方更好的硬件性能) 对抵触的影响，V 示意机器分数的方差，能够看到在调度器数量雷同的状况下，随着 V 的增大，为了放弃抵触不产生显著的变动，须要额定补充的 slot 数目就越多；反过来，在 V 不变的状况下，随着调度器数量的减少，每个调度器接受的调度压力降落，须要额定补充的 slot 数目就越少。
• 图 d 反映的是机器 partition 数量对抵触的影响，能够看到这个因素对抵触简直没有影响。因为不论机器 partition 的数量是多少，调度器总是以本人外部的视图状态进行调度，即便有些视图的状态曾经不够新了，所以 partition 数量并不会对抵触产生显著的影响。

由以上剖析不难发现，在 shared-state 架构下，如果咱们想尽可能的升高抵触，能够采取减少额定资源或者减少调度器数量的形式来升高抵触，但在理论的生产环境中，减少额定资源是不可能的，一方面是集群大小是绝对固定的，此外新引入 slot 也会大幅减少集群的老本；而减少调度器则会显著带来保护 \ 降级的代价。

四 计划实现

因为咱们的指标是为了缩小抵触，所以咱们先简略介绍下一种可能齐全打消抵触的策略，乐观锁策略。乐观锁策略是每个调度器可能调度的机器是“动态排他 \ 动态划分”的，这样显然可能打消抵触，然而对利用率是十分不利的，因为会产生资源节约（其余调度器原本能够调度）。还有一种策略是通过相似于 zookeeper 等组件实现的基于锁抢占的调度策略，当一批机器被某一个调度器锁住时，其余机器是因为拿不到机器锁从而临时无奈调度，当持锁的调度器放锁时，其余调度器能够通过锁竞争来尝试进行调度，然而在大规模高并发的调度场景下，这种高频的交互会对调度效率产生很大的负作用。

由后面的剖析能够晓得，升高资源同步的提早可能无效升高抵触，由此咱们提出了一种基于“分区同步”（下称 ParSync）的策略：首先将集群的机器分为 P 个 partition，同时要求 P >N。通过 round robin 策略，每个调度器在同一个时刻去同步不同 partition 的资源视图，这样做可能保障在每个 round 内每个调度器都可能更新完所有 partition 的资源，而 P >N 保障了同一时刻不同的调度器不会同步雷同的 patition 资源。

依据前文所述，在大规模高并发的调度场景下，调度器最优先的指标往往不是 locality prefer 而是 speed prefer，所以调度器会优先在最新同步的 partition 机器内进行资源调度，在该策略下多调度器间是不会产生资源抵触的。ParSync 其实是变相升高了每个 patition 对其以后同步调度器的同步提早，因为站在以后更新的调度器的视角，这个 partiton 的同步提早其实是低于其余未同步的调度器的，这也是可能无效升高抵触的实践起因。

咱们提供三种调度策略：latency-first，quality-first，adaptive。latency-first 是在优先在最新的 partition 上调度资源，quality-first 是优先在 score 最好的机器上调度资源，而 adaptvie 是先采取 quality-first 的调度策略，当资源等待时间超过阈值时再采取 latency-first 的策略。咱们通过一组试验来验证 3 种调度策略的调度成果：咱们将调度器分为 2 类，A\B 类调度器在阶段 1 都收到本身调度能力的 2 / 3 调度申请；阶段 2，A 类调度器收到等同于本身调度能力的调度申请，而 B 类调度器不变；阶段 3，A\B 类调度器都收到等同于本身调度能力的调度申请。

• 从 (a)(b) 能够看出，在阶段 1\2\3, 调度 quality 的体现都是很好的，然而在阶段 2\3 随着调度压力的减少，调度 latency 呈现了直线回升的状况，这是合乎直觉预期的。
• 从 (c)(d) 能够看到，在阶段 1 调度器压力只有 2 / 3 的时候，调度 latency 和 quality 都是体现比拟好的。随着调度压力的减少，quality 品质开始呈现了降落，然而 latency 的减少却十分无限，这也合乎直觉预期。
• 从 (e)(f) 能够看到，在阶段 2，因为 B 类调度器的调度压力仍只有 2 /3，所以还停留在 quality-first 策略，而 A 类调度器因为调度 latency 的减少进入到了 latency-first 策略。通过仔细观察能够看到在 quality 的图里 B 类调度器的 quality 品质 (浅灰色) 是优于 latency-first 策略的。在阶段 3，A\B 类调度器同时将调度 latency 束缚在了门限值(1.5s)，合乎设计预期。

五 试验剖析

咱们通过“风洞”零碎来验证整个调度框架。在风洞环境下，除了调度器是实在的，单机节点和 am 都是程序模仿进去的，它们和调度器进行实在的资源交互，通过 sleep 来模仿作业的执行，这样在一个 node 上就能够进行 1:500 的模仿。

测试环境：

1. 20 个调度器，2 个 resource manager
2. 集群总共有 20w 个槽位
3. 调度器调度能力为 40k task/s
4. 调度分为 3 个阶段，调度压力别离调度器能力的 50%，80%，95%，80%，50%

从图 (a) 能够看出，随着调度压力的变动，latency-first 在调度 latency 上优于 adaptive, 而 quality-first 优于 StateSync(以 Omega 为代表的视图同步策略，调度器每次同步整个视图信息)，latency-first 策略可能将 latency 管制在一个十分好的水准，而 StateSync 的 latency 曾经不受管制了，这也很好地证实了 ParSync 策略对抵触管制的有效性。对于 quality-first 策略，其 latency 也呈现了不受管制的状况，这是调度器始终尝试在分数最高的机器上进行调度所带来的副作用。而 adaptive 策略对 latency-first 和 quality-first 进行了一个良好的折中。

从图 (b) 中能够看出，随着调度压力的变动，latency-first 和 adaptive 策略在 quality 上体现都有一个显著的降落，这个合乎预期。而 quality-first 的体现根本和 StateSync 持平。

综上，ParSync 在 quality 与 StateSync 体现持平的状况下，latency 体现远优于 StateSync。其余更多的具体的数据分析详见论文。

六 总结

论文首先介绍了散布式调度器畛域在解决规模问题时的常见做法：多调度器联结调度，其次介绍了多调度器的一种常见的资源供应模型 StateSync。在 StateSync 模式下，不同调度器间会产生重大的调度抵触，进而影响集群的调度效率和利用率。针对上述问题，论文通过实践剖析，给出了缓解抵触办法：减少可调度资源或裁减调度器，然而在理论中这 2 种办法都是不可承受的。

本文提出了一种新的资源供应模式：ParSync。在 ParSync 模式下，不同的调度器通过 round robin 的形式来分时更新机器资源。同时 ParSync 提供了三种调度策略：latency-first，quality-first，adaptive，用来满足不同场景下调度器对于 latency\quality 的要求。大规模试验表明，ParSync 在调度品质上与其余调度器持平，但在调度延时上远优于其余调度器。

附录

生产集群资源调度架构图

原文链接
本文为阿里云原创内容，未经容许不得转载。