您的位置:js12345金沙官网登入 > 网络编程 > 完爆 Best Fit,看阿里如何优化 Sigma 在线调度策略

完爆 Best Fit,看阿里如何优化 Sigma 在线调度策略

2019-10-02 10:01

摘要: 2017年是 Sigma 正式上线以来第1次参与阿里双11,在双11期间成功支撑了全集团所有容器的调配,使双11IT成本降低50%。

摘要:2018 年“双 11”的交易额又达到了一个历史新高度 2135 亿。相比十年前,我们的交易额增长了 360 多倍,而交易峰值增长了 1200 多倍。相对应的,系统数呈现爆发式增长。系统在支撑“双 11”过程中的复杂度和难度呈现指数级形式上升趋势。

导读:为了保证系统的在线交易服务顺利运转,最初几年,阿里都是在双11大促来临之前大量采购机器储备计算资源,双11之后资源大量闲置。是否能把计算任务与在线服务进行混合部署,在现有弹性资源基础上提升集群资源利用率,降低双11资源新增成本?阿里巴巴研发效能事业部容器调度域,测试开发专家何颖为我们揭秘。

作为阿里巴巴全集团范围的容器调度系统,Sigma 在“双11”期间成功支撑了全集团所有容器(交易线中间件、数据库、广告等 20 多个业务)的调配,是阿⾥巴巴运维系统重要的底层基础设施。Sigma 已经是阿里全网所有机房在线服务管控的核心角色,管控的宿主机资源达到百万级,重要程度不言而喻,其算法的优劣程度影响了集团整体的业务稳定性,资源利用率。

Sigma 是阿里巴巴全集团范围的 Pouch 容器调度系统。2017年是 Sigma 正式上线以来第1次参与双11,在双11期间成功支撑了全集团所有容器(交易线中间件、数据库、广告等20多个业务)的调配,使双11IT成本降低50%,是阿⾥巴巴运维系统重要的底层基础设施。

当用戶向调度系统申请容器所需的计算资源(如 CPU 、 内存、磁盘)时,调度器负责挑选出满足各项规格要求的物理机来部署这些容器。在相同的资源需求下,调度策略的优劣决定着集群计算资源利用的水平。本文将简要介绍群体增强学习算法在调度策略优化中的应用。

Sigma 已经是阿里全网所有机房在线服务管控的核心角色,管控的宿主机资源达到几十万量级,重要程度不言而喻,其算法的优劣程度影响了集团整体的业务稳定性,资源利用率。

当用户向 Sigma 申请容器所需的计算资源(如 CPU、Memory、磁盘等)时,调度器负责挑选出满足各项规格要求的物理机来部署这些容器。通常,满足各项要求的物理机并非唯一,且水位各不相同,不同的分配方式最终得到的分配率存在差异,因此,调度器的一项核心任务就是按照某一策略从众多候选机器中挑出最合适的物理机。

Sigma-cerebro 系统是 Sigma 系统的调度模拟系统,可以在无真实宿主机的情况下,以最小成本,最快速度模拟线上1:1机器资源和请求要求的调度需求完成情况,从各个角度进行扩缩容算法的评测。在对抗系统资源碎片化,在有限资源条件下大批量扩缩容,预期外超卖等问题的过程中,系统一步步发展成现在的样子。

在文献中,计算资源调度一般被表述为矢量装箱问题(vector bin packing problem),如果各应用的容器数量事先已知,调度器可一次性为所有容器生成优化的排布方案,此时问题可以表述为整数规划,可使用通用求解器或专门开发的算法来求解;如果各应用的请求陆续到达 Sigma ,调度器需要在每次请求到达时即时生成部署决策,此时问题可表述为马尔可夫决策过程 (Markov Decision Process, MDP),原则上可以通过值迭代或策略迭代求得最优策略。

在2017年双11中,依靠 cerebro 进行预处理,Sigma 成功完成了双11一键建站,30分钟内完成建站任务,且系统静态分配率从66%提升到95%,大大提升了资源利用的有效性。

最常用的调度策略包括 First-Fit 和 Best-Fit 。如果使用 First-Fit算法,调度器会将容器部署到遍历中碰到的第一个满足所有要求的物理机上;而Best-Fit算法则会在满足要求的物理机中挑选分配水位最高的机器来部署容器。对于经典的 bin packing 问题(即一维矢量装箱问题),First-Fit 和 Best-Fit 的近似比均为1.7,即二者都可保证所使用的机器数不超出最优方案的170%;对于2维及以上的矢量装箱问题,理论上不存在有着明确近似比保证的多项式算法。当物理机的某个资源维度明显为瓶颈而导致其它资源维度普遍有剩余时,其有效维度可视为1,使用 First-Fit 或 Best-Fit 一般可以取得不错的分配率;而一旦瓶颈并未集中体现在同一维度,两种策略的效果就要大打问号了。

什么是好的调度?最理想的情况如何?

除了资源维度上的要求,实际调度中还有容灾和干扰隔离上的考虑:比如同一应用的容器不允许全部部署到同一台物理机上,很多应用甚至每台机器上只允许有一个实例;某些应用之间还存在互斥关系,严重影响应用的性能,因此也不允许它们被部署到同一物理机上。这些限制条件的引入,使得常用策略越发水土不服了。通过人肉反复试错,勉强扛住了多次大促建站的压力。然而,随着各业务的扩张,线上容器的规模越来越大,资源变得越来越紧张,人肉调参的效率渐渐力不从心。

我认为在满足容器的资源运行时,最小化互相干扰的前提下,越能够节省集群整体资源,提高利用率,在固定时间内完成分配的调度系统,较符合理想的调度系统。

为了把调度同学从调参中解放出来,让有限的资源扛住更大的压力,达摩院机器智能技术实验室的决策智能算法团队和Sigma调度团队展开了紧密合作,对在线调度策略问题进行了研究,并开发了基于群体增强学习的算法。

那么一个调度算法仿真评测的系统,要做到什么程度?

记当前待部署容器的规格为向量 p∈P,为其分配资源时集群状态为向量 s∈S , 候选物理机的集合为 A⊆A,策略可表示为函数 π:S×P→A。当按策略 π 选择物理机 a=π来部署该容器时,该选择的即时成本为 r,集群的新状态 s′ 由状态量 s 、p 以及动作 a 共同决定,记为 s′=L ;记后续到达的容器规格 p′, 对于在线调度,p′ 为随机量。引入折扣系数 γ∈[0,1],系统的 Bellman 方程为:

要能够真实模拟生产的大规模环境和复杂需求;

图片 1

要尽量节省模拟的开销,避免模拟的风险;

最优调度策略可表示为:

从静态和动态的角度都能够给第一个问题以定性定量的回答。

图片 2

在这个基础上,我们来看看 Sigma 的副产品,Sigma-cerebro 调度模拟器。

理论上,通过随机梯度下降,我们可以在策略空间 Π 中搜索较优的策略,但相要更进一步的优化,甚至得到全局最优策略,则需要借助其它方法,特别是当最优策略可能是 multi-modal 形式。

Sigma-cerebro 调度模拟器

为防止策略的优化陷入较差的局部最优解,同时拥有较快的收敛速度,我们基于群体增加学习的框架来设计算法。与传统的增强学习方法相比,算法使用多个 agent 来探索问题的策略空间,且多个 agent 之间存在互相学习机制,这使得算法有了跳出局部陷阱的能力。为获取各状态值的估计,一个准确的 Sigma 模拟器必不可少,团队内部同学基于 Sigma 的调度器开发了“完全保真”的模拟器 Cerebro 。

调度模拟器设计

算法首先随机初始化一群 agent 的策略,针对每个策略,通过模拟器获取相应的的状态值估计,记录当前全局最佳策略。在后续的每次迭代中,各个 agent 不断更新自身的局部最佳策略,并参照局部最佳策略与群体当前全局最佳策略,对 agent 自身的当前策略进行更新,再进行模拟,获取新策略的状态值估计,更新全局最佳策略。如此循环,直到满足收敛条件。

图片 3

在各个 agent 状态值的估计中,样本(多个随机抽取的集群快照和扩容请求序列)和各 agent 的当前策略被输入模拟器 Cerebro,追踪模拟时集群状态的轨迹,即可得到该轨迹的总成本;基于多个样本的轨迹总成本求平均,即得到相应策略下的状态估计值。

总的来说,目前的模拟器是一个使用1:1生产环境数据来进行调度分配仿真的工具平台。

图片 4

该仿真目前是纯数据层面的,动态预测也是基于静态数据的。原因是要1:1模拟线上,而线上动辄万台宿主,是不可能真的动用这么多资源的。另外后续也计划搞小规模的池子进行全动态的 runtime 仿真和评测。

在 SwarmRL 中,策略的演进方向与步长用“速度” 来表示,速度的变化涉及局部最佳策略 和群体全局最佳策略 与 agent 当前策略 的差异,并受策略惯性因子 w、本地学习因子C1(self-learning)、群体学习因子 C2 (social-learning) 等参数的调控:

模拟器需要同时满足很多需求,因此分成了多套环境,有一个环境池。每个环境池,仅需要3个容器即可完成全套任务。

图片 5

背景数据是存放在OSS中的,因为一套背景数据可能非常大,另外解耦和线上的依赖将风险降到最低,因此仿真时仅需要从OSS取数据即可。在各种仿真下,用户需要的服务是不同的,因此模拟器设计了几个不同的模式来进行支持。这些模式即可对应前面的4 个需求。

其中 ξ1,ξ2∈[0,1] 为随机量,Φ为可行性保持映射,用于将逸出可行域的 agent 重新“拉回”可行域。在迭代中,局部最佳策略 和群体全局最佳策略 不断更新:

目前已有的模式包括:扩、缩容算法评测模式,预分配模式,问题复现模式。

图片 6

对于如何衡量调度分配结果的优劣问题来说,模拟器支持将算法配置透出,支持用户自定义水位配置和调度器,模拟器会负责将一套线上1:1宿主机数据,应用要求配置等写入该环境,并将用户的算法配置写入,然后将每次相同的请求发送到该环境,待结束后用同样的方式进行打分。

下面我们先用一个随机生成的小算例来对比一下算法的效果。算例中涉及 30 个应用,其容器规格主要为 4c8g 与 8c16g,所用宿主机的规格均为 96c512g。

针对同样的一份背景数据,不同的算法配置和版本会产生不同的打分,我们就可以观察他们之间的优劣。如下图:

图片 7

图片 8

若在调度时,请求的顺序和数量均为已知,即进行事后排布,使用整数规划求得的最优解对应的分配率为 94.44 % (这也是所有调度策略在该算例上所得分配率的上界),共启用 15 台宿主机,具体排布方案为:

另外,可以快速在模拟器环境下进行资源的预分配,之后精准按照本次预分配,预热少量镜像到宿主机,使用亲和标的方式,解决如何在宿主机IO有限情况下应对快速扩容多种容器的需求问题。

图片 9

为什么需要调度模拟器?

现实场景中,每个请求所处顺序和容器数量仅在其到达 Sigma 时才揭晓,若采用 Best-Fit 进行动态调度,所得分配率为 70.83%,共启用 20 台宿主机,具体排布如下:

容器调度中有如下几个业务问题:

图片 10

  1. 如何衡量调度分配结果的优劣?

  2. 大批量应用一键建站时,如何克服镜像拉取慢的问题?

  3. 大批量应用同时一次性建站分配时,如何准确进行资源评估?

  4. 如何在测试环境复现线上的调度问题?

若采用 SwarmRL 学习所得策略进行动态分配,分配率为 94.44%,共启用 15 台宿主机,最终容器排布如下:

Sigma 调度模拟器以最低的成本和风险引入即可给上述问题一个可行的解答。

图片 11

下面将针对每个业务问题进行阐述。

在该算例中,SwarmRL 学习所得策略的表现与“上帝视角”下最优排布的表现一致,明显优于 Best-Fit 的表现,改进幅度达 23.61%.

1.1 如何衡量调度分配结果的优劣

我们再随机生成规模较大的请求数据:共计 3K 个请求,5K 个容器,其规格分布如下图,

首先,容器的调度过程一定会存在一定的碎片化情况。

图片 12

让我们先从单维度的CPU 核分配谈起。想象如下最简化的场景:

由于该场景下整数规划模型的变量规模太大,已经无法在短时间内直接求取“上帝视角”的最优解。对比 Best-Fit ,算法所得新策略的效果如下:

我们的某个总资源池仅仅有2台宿主机,每台宿主机各自有4个空闲的CPU可分配。示意图如下:

图片 13

我们要分配给3个容器:2核容器A,2核容器B,4核容器C。

相对于 Best-Fit,新策略节约宿主机 13 台,分配率提升 4.30%;相对于人肉策略,新策略节约 7 台宿主机,分配率改进 2.36%.

设想A和B的请求先至,如果我们的分配算法不够优秀,那么可能出现如下分配场景。可以很明显看出,应用C无法获得相应资源,而整个系统的静态分配率仅有50%,浪费较大。

考虑到实际场景中应用请求到达顺序的随机性,我们随机打乱请求生成多个不同的请求顺序,再分别应用三个策略按不同的请求顺序进行动态分配:

理想的分配结果当然是如下图:3 个容器全部被分配成功,总的静态分配率为100%。如果容器的资源本身需求是合理的话,那么浪费会很小。

图片 14

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:完爆 Best Fit,看阿里如何优化 Sigma 在线调度策略

关键词: