去中心化分布式(获国际架构顶会ATC2021最佳论文！Fuxi2.0去中心化的调度架构详解)

电商上海

2022-04-20 15:08:53

引言

近日，在国际架构峰会USENIX ATC2021上，阿里云天妃伏羲团队与香港中文大学合作的一篇论文《分区同步扩展大型生产集群》不仅成功被大会接受，还被大会专家组评为三篇最佳论文之一。

ATC在计算机系统领域有很大的影响力。自1992年以来，ATC已成功举办了31届，吸引了普林斯顿、斯坦福、加州大学伯克利分校、康奈尔、清华、北京大学等顶尖高校。，以及微软、英特尔、三星等科技巨头发布研究成果。ATC对论文要求极高，必须满足基础贡献、前瞻性影响、系统实现扎实等要求。2021年USENIX组委会录用了64篇论文(录取率为18%)，只有三篇最佳论文在全球范围内被选中(另外两篇来自斯坦福大学和哥伦比亚大学)。这也是ATC最好的论文第一次出现在中国公司。

在本次大会上，我们详细介绍了伏羲2.0项目的最新成果——超大规模分布式集群的分散调度架构，并首次向外界披露了阿里云实现超大规模集群调度的细节，这是天妃操作系统核心能力的又一次成功展示。

一论文背景

AI/大数据计算场景，随着计算需求的快速增长，云计算集群已经超过单个集群1万台的规模(一个集群可能有10万台机器，每天执行数十亿次任务，尤其是短期任务)，从而实现高利用率、低成本的附加值，意义重大。资源调度器作为大规模生产集群的核心组件，负责高效地将多维资源请求与集群中的机器资源进行匹配。然而，集群规模的增长意味着有更高的并发请求，从而产生“乘积”效应，大大增加了调度的复杂性。因此，如何实现集群规模的可扩展性，在保持良好调度效果的同时实现高并发和低延迟，是业内公认的非常艰巨的任务。传统的中央调度器受限于单点调度能力，大多无法处理生产级规模，无法保证稳定性和健壮性，使得升级过程对用户透明。

二现状分析

1工作量

去中心化是什么意思

在阿里巴巴，一个计算集群每天运行数百万个工作。图1a(实线)示出了某个月中每天由集群随机处理的作业数量，范围从334万到436万，而一个作业由许多任务组成。图1a(虚线)示出了每天的任务数量大约从31亿到44亿。大部分任务是短期任务，如图1b所示，87%的任务在10秒内完成。大规模集群的调度负载还是很大的。

2安排架构升级的必要性

在Fuxi1.0中，调度器遵循典型的主从架构。FuxiMaster负责管理和调度集群中的所有资源。同时每台机器都有一个代理Tubo，通过心跳消息定期与FuxiMaster同步状态。用户提交的每个作业都有其配额组的信息，配额组可以使用的资源的最大值和最小值由SRE设置。我们的配额机制不仅可以在集群高负载时保证配额组之间的公平性，还可以在集群相对空闲时削峰填谷，使集群资源得到充分利用。

近年来，计算集群的规模正在显著增加，在可预见的未来，集群的规模很可能超过10万台。面对超大规模集群，一种方法是将集群静态划分为若干个小集群，但这种方法有明显的局限性。首先，一些超大规模操作的资源需求可能会超过上述单个集群的规模；其次，集群分割还会带来资源碎片化问题，局部视图无法保证最优的全局调度结果。最后还有其他非技术因素，比如项目之间的依赖关系，同一个业务部门的不同项目需要访问彼此的数据。将它们部署在同一个集群中(而不是拆分成小集群)，将大大降低运营和管理成本。

但是，单主架构无法处理10万的集群规模。主要有两个原因:1)随着集群规模的扩大，由于单个调度器处理能力的上限，主、从机之间的心跳延迟会增大，调度信息无法及时下发，导致集群利用率下降；2)规模的增加意味着更高的任务并发，使得调度复杂度急剧增加，最终超过单个调度器的处理能力。

3时间安排的目标和挑战

除了规模可扩展性的挑战之外，调度者还应该权衡以下调度目标，我们重点关注的主要包括:

调度效率(或延迟)，即一个任务需要等待资源多长时间，一个好的调度器应该让资源快速流动。

是否满足质量和资源限制，例如数据局部性、更大的内存、更快的CPU模型等。

并且在多租户共享生产环境中，需要保证租户之间资源使用的公平性，同时为高优先级作业提供保障机制。

资源利用率是一个极其重要的目标，集群利用率低会面临很多挑战，尤其是财务方面的挑战。

然而，上述目标通常是相互冲突的。比如，更好的调度效果往往意味着更长的调度延迟，绝对公平有时会导致资源利用不足，从而导致集群利用率下降。

经过十几年的积累，福喜的资源调度器通过各种策略，在上述目标之间取得了很好的平衡。但考虑到围绕资源调度器还有其他兄弟团队开发的其他应用组件，我们在设计新的调度器时应该尽量少做改动，以保持系统的健壮性和前向兼容性。由调度器架构调整引入的系统升级应该对用户透明，无论是内部用户还是外部用户。

三理论概述

鉴于调度器的可扩展性，我们对业界现有的调度模型进行了广泛的研究(详见论文)，并选择了其中一个最适合我们场景的方案(Omega)进行进一步的分析。以Omega为代表的共享状态多调度器架构可以满足我们前面提到的两个约束，向后兼容，对用户透明。但是，共享状态方案将不可避免地导致调度冲突，我们希望明确以下问题:

哪些因素会影响冲突，各自的权重是多少？

调度延迟会有多糟糕？

我们如何避免或减轻冲突？

首先，我们对冲突进行建模，得到冲突的期望如下(推导过程见论文):

上式中，Yi是多个调度器在一个时隙上碰撞的期望，n是调度器的个数，k是单个调度器的处理能力，s是机器可以调度的时隙数。由此可见，想要降低冲突概率，可以增加S或者n，增加S是通过提供额外资源来降低冲突概率的一种非常直观的方式。增加n的方式是反直觉的，因为调度器越多，越容易增加冲突。但是，虽然在一轮调度的过程中冲突更多，但是每个调度器在开始时分配的任务调度压力也成比例减少，因此有更多的时间来解决冲突，最终起到降低冲突概率的作用。综上所述，增加n是在总压力不变的情况下，通过降低各调度器的调度压力来减少冲突。

此外，我们还通过公式证明了当调度器数目>:1时，冲突不能完全消除。

以下实验反映了不同冲突因素对冲突的影响:

图A考虑了任务压力变化对冲突的影响。r表示调度程序接收任务的速率。可以看出，随着R的增加，为了保持冲突数量不变，需要补充的槽位数量会增加。另一方面，当r一定时，随着调度器数量的增加，每个调度器所承受的调度压力减小，需要补充的时隙数量减少。

图B反映了资源视图同步频率变化对冲突的影响。g代表同步的延迟。可以看出，当调度器数量相同时，随着G的增加，为了保持冲突数量不变，需要补充的时隙数量会增加。另一方面，在g不变的情况下，随着调度器数量的增加，每个调度器所承受的调度压力减小，需要补充的时隙数量减少。

图C反映了机器分数(例如更好的硬件性能)对冲突的影响，V表示机器分数的方差。可以看出，随着V的增加，为了保持冲突不变，需要补充的槽位数量会增加。另一方面，在v不变的情况下，随着调度器数量的增加，每个调度器所承受的调度压力减小，需要补充的时隙数量减少。

图D反映了机器划分数对冲突的影响，可以看出这个因素对冲突的影响很小。因为不管机器分区的数量如何，调度器总是用自己的内部视图状态进行调度，即使某些视图的状态不够新，所以分区的数量不会对冲突产生显著影响。

从上面的分析中不难发现，在共享状态架构下，如果我们想尽可能的减少冲突，可以通过增加额外的资源或者增加调度器的数量来减少冲突。但是，在实际生产环境中，不可能增加额外的资源。一方面，集群规模相对固定，新引入的槽位也会大大增加集群的成本。但是，增加一个调度器显然会带来维护和升级的成本。

四方案实现

既然我们的目标是减少冲突，那就简单介绍下一个可以完全消除冲突的策略，悲观锁定策略。悲观锁策略是指每个调度器可以调度的机器是“静态独占、静态分割”的，这显然可以消除冲突，但对利用率非常不利，因为会浪费资源(其他调度器本来可以调度的)。另一种策略是基于锁抢占的调度策略，由zookeeper这样的组件实现。当一批机器被某个调度器锁定时，其他机器因为无法获得机器锁而暂时无法调度。当持有锁的调度程序释放锁时，其他调度程序可以通过锁竞争来尝试调度。但在大规模、高并发的调度场景下，这种高频率的交互会对调度效率产生很大的负面影响。

从前面的分析可以知道，减少资源同步的延迟可以有效地减少冲突。因此，我们提出一种基于“分区同步”(以下简称ParSync)的策略:首先将集群机器划分为P个分区，同时要求P & gtn .通过轮循策略，每个调度器同时同步不同分区的资源视图，可以保证每个调度器每轮都能更新所有分区的资源，而P & gtn保证不同的调度器不会同时同步相同的专利资源。

根据前述，在大规模、高并发的调度场景下，调度器的优先级目标往往不是局部性偏好，而是速度偏好，所以调度器会在新同步的分区机上优先进行资源调度，在这种策略下，多个调度器之间不会发生资源冲突。ParSync实际上是变相降低了每个专利对其当前同步调度器的同步延迟，因为从当前更新的调度器来看，这个部分的同步延迟实际上低于其他不同步的调度器，这也是有效降低冲突的理论原因。

我们提供了三种调度策略:延迟优先、质量优先和自适应。延迟优先是优先调度最新分区上的资源，质量优先是优先调度分数最好的机器上的资源，而adaptvie采用质量优先的调度策略，当资源等待时间超过阈值时，再采用延迟优先的策略。我们通过一组实验验证了三种调度策略的调度效果:我们将调度器分为两类，AB类调度器在第一阶段都接收到自己2/3的调度请求；阶段2，A型调度器接收与其自身调度能力相等的调度请求，而B型调度器保持不变；在阶段3中，AB类调度器都接收到与其自身调度能力相等的调度请求。

从(a)和(b)可以看出，在阶段123，调度质量的表现都很好，但是在阶段23，随着调度压力的增加，调度延迟线性上升，这符合直观的预期。

从(c)和(d)可以看出，当调度器的压力只有阶段1的2/3时，调度延迟和质量都较好。随着调度压力的增大，质量开始下降，但延迟的增加非常有限，也符合直观预期。

从(e)和(f)可以看出，在阶段2中，由于B类调度器的调度压力仍然只有2/3，仍然停留在质量优先策略，而A类调度器由于调度延迟的增加而进入延迟优先策略。通过仔细观察，我们可以看到质量图中B类调度器的质量品质(浅灰色)优于延迟优先策略。在第三阶段，AB类调度器同时将调度延迟限制在阈值(1.5s)以内，达到了设计预期。

五实验分析

我们通过“风洞”系统来验证整个调度框架。在风洞环境中，除了调度器是真实的，单机节点和am都是用程序模拟的。它们与调度器进行真实资源的交互，通过睡眠来模拟作业的执行，从而可以在一个节点上进行1:500的模拟。

测试环境:

20个调度程序，2个资源管理器

群集中有20w个插槽。

调度程序的调度能力为40ktask/s

调度分为三个阶段，调度压力分别为调度人员能力的50%、80%、95%、80%、50%。

从图(a)可以看出，随着调度压力的变化，latency-first在调度延迟上优于adaptive，而quality-first优于StateSync(Omega代表的视图同步策略，调度器每次同步整个视图信息)。延迟优先策略可以将延迟控制在非常好的水平，但是StateSync的延迟却失控了，这也证明了ParSync策略对于冲突控制的有效性。对于质量优先策略，它的延迟也是失控的，这是调度器试图在得分最高的机器上调度而产生的副作用。自适应策略在延迟优先和质量优先之间做出了很好的折衷。

从图(b)可以看出，随着调度压力的变化，延迟优先和自适应策略在质量上的表现有明显的下降，这符合预期。而质量第一的表现和StateSync基本相同。

综上所述，ParSync在质量与StateSync相当的情况下，延迟性能远远优于StateSync。有关更详细的数据分析，请参见论文。

六总结

本文首先介绍了分布式调度领域解决规模问题的常用方法:多调度器联合调度。其次，介绍了一种通用的多调度器资源供应模型StateSync。在StateSync模式下，不同调度器之间会产生严重的调度冲突，进一步影响集群的调度效率和利用率。针对上述问题，本文通过理论分析给出了缓解冲突的方法:增加可调度资源或扩充调度器，但这两种方法在实践中是不可接受的。

本文提出了一种新的资源供应模型:ParSync。在ParSync模式下，不同的调度程序通过循环调度以分时方式更新机器资源。同时，ParSync提供了延迟优先、质量优先和自适应三种调度策略，用于满足不同场景下调度器对延迟质量的要求。大规模实验表明，ParSync在调度质量上与其他调度器相当，但在调度延迟上远远优于其他调度器。

附录