Autopilot: workload autoscaling at Google
论文：Autopilot: workload autoscaling at Google
发表时间：2020
论文链接：论文链接
在许多公共和私有云系统中，用户需要指定资源量（CPU内核和RAM）的限制以为其工作负荷提供资源。 超出其限制的作业可能会受到限制或终止，从而导致最终用户请求的延迟或丢弃，因此人工操作人员针对这种问题出于谨慎考虑，会申请高于任务自身需要的配置。 从规模上讲，这将导致大量的资源浪费。
为了解决这个问题，Google使用Autopilot自动配置资源，同时调整作业中的并发任务数（水平缩放）和单个任务的CPU /内存限制（垂直缩放）。 Autopilot与人工操作员遵循相同的原则：Autopilot的主要目标是减少松弛（slack）（申请资源和实际资源使用之间的差异），同时最大程度地降低因内存不足（OOM）错误或 由于CPU节流，其性能下降。 Autopilot将机器学习算法应用到有关作业先前执行情况的历史数据上，再加上一组经过微调的启发式方法来实现这一目标。 在实践中，Autopilot工作只有23％的松弛（slack），而手动管理工作只有46％的松弛（slack）。 此外，Autopilot将受OOM严重影响的工作数量减少了10倍。
尽管有其优点，要确保Autopilot被广泛采用仍需付出巨大的努力，包括使尚未加入的客户容易看到潜在的建议，自动迁移某些类别的任务以及增加对自定义推荐器的支持。 在撰写本文时，Autopilot任务占Google资源使用的48％以上。
介绍
在Kubernetes集群中，用户可以设置Pod副本的数量和单个Pod的资源限制,但是我们很难估计一个作业需要多少资源才能最佳运行：CPU功率，内存和同时运行的副本数的正确组合。 负载测试可以帮助找到初始估计值，但是随着资源需求随时间变化，这些建议将过时，因为许多最终用户服务工作具有每日或每周的负载模式，并且随着服务变得越来越流行，流量在更长的时间内发生变化 。 最后，处理给定负载所需的资源会随着基础软件或硬件堆栈的新功能，优化和更新而变化。如果CPU容量不足，超出请求的资源可能会导致性能下降，或者导致任务被杀死 内存不足（OOM）。
针对配置资源的困难，一种常见的模式是采用水平自动缩放器，该缩放器通过监控终端用户流量或平均CPU利用率的变化添加或删除副本来缩放任务。 所有主要的云提供商（AWS，Azure和GCP）都提供水平自动扩展功能； 它在某些云中间件（如Kubernetes）中也可用。 较不常见的模式是使用垂直自动缩放来调整每个副本可用的资源量。 两种技术也可以组合。
Autopilot是Google在其内部云上使用的主要自动缩放器。
- 描述下Autopilot，以及它用于垂直自动缩放的两个主要算法：第一个算法依赖于历史用量的指数平滑滑动窗口； 另一个是基于从强化学习中借用的思想的元学习，该算法运行滑动窗口算法的许多变体，并为每个任务选择历史数据表现最佳的算法。强化学习：依赖海量的训练，并且需要精准的奖励。成本较高且比较复杂。元学习：具备自学能力，能够充分利用过去的经验来指导未来的任务。被认为是实现通用人工智能的关键。
- 通过Google的工作负载采样评估Autopilot算法的有效性；
- 讨论为使我们的集群广泛采用Autopilot而采取的步骤。
通过Borg管理云资源
机器、作业和任务
Google计算基础架构由分布在多个地理位置的许多集群组成。一个集群大约有10,000台物理机，并同时运行许多不同类型的工作负载。一台物理计算机可能会同时计算大量占用内存和CPU的批处理，提供存储和内存数据库的切片提供查询能力，还可以处理对延迟敏感的终端用户请求。
运行的工作负载可以分为两类：服务和批处理。服务工作通常旨在严格保证查询响应时间的性能（例如，在95％的位置上，请求延迟服务级别目标或SLO≤50 ms）。如此严格的等待时间要求排除了OS内核决定之外的任何带内资源分配决策，因此服务作业具有为其明确请求预留的资源。相反，批处理作业旨在“快速”完成并退出，但通常没有严格的完成期限。服务性工作是我们基础架构能力的主要驱动力，而批处理工作通常会填充剩余或暂时未使用的能力。
内存不足（OOM）事件终止单个任务。某些工作可以合理地容忍OOM事件。有些根本不是；还有一些介于两者之间。总体而言，由更多任务组成且状态较少的作业在单个任务终止时遇到的服务故障越小，因此对OOM容灾能力更高。有些作业需要低的，可重复的延迟来处理请求。有些没有。Autopilot会根据作业的声明大小、优先级和类别选做默认值，但允许我们的用户覆盖它们。Borg驱逐任务，为了安全性和OS更新，为更高优先级的任务腾出空间，并让我们更有效地将工作打包到计算机上。我们有意识的通过计算集群架构和应用的弹性来分散负荷。系统期望通过弹性解决任务驱逐和硬件故障问题。Borg发布了预期内最大驱逐率，观察到的驱逐率之间的差异也使我们可以自由地使用任务的资源设置进行实验-在了解任务需要时可以偶尔进行OOM。 （使用VM实时迁移之类的工具来隐藏外部Cloud VM的这些内部优化。）一个典型的服务工作有很多任务，并且负载均衡器将流量驱动到可用负载，因此丢失任务只会导致其负载平摊给其他任务。 这是正常现象，而不是灾难性的故障，它使我们能够更加积极地利用基础架构，并能够妥善处理偶发的硬件故障。 使用MapReduce中使用的技术，在批处理作业中也内置了类似的弹性。
Borg调度架构
Borg有一个多复本的Borgmaster，负责制定计划决策，还有一个称为Borglet的代理程序，它在集群中的每台计算机上运行。 一台机器可以同时执行Borglet控制的数十个任务； 依次将其状态和资源使用情况报告给Borgmaster。 将新作业提交给Borgmaster时，它会选择一台或多台机器，这些机器上有足够的空闲资源来执行新提交的作业–或通过驱逐优先级较低的作业来腾出空间来创建这种情况。 在Borgmaster决定将任务的任务放置在何处后，它将启动和运行任务的过程委派给所选计算机上的Borglet。
通过任务限制进行资源管理
为了获得可接受和可预测的性能，必须将一台计算机上运行的任务相互隔离。 与Kubernetes一样，Borg在单独的Linux容器中运行每个任务，并且本地代理设置容器资源限制以使用cgroup实现性能隔离。 与操作系统级别的传统公平共享不同，这可确保任务的性能在同一二进制文件，不同机器（只要硬件相同）和不同邻居（任务在同一机器上共同调度）的不同执行之间保持一致 。
Borg允许作业在作业运行时修改其资源需求。在水平缩放中，作业可以动态添加或删除任务。在垂直扩展中，作业可以更改其任务的RAM和CPU限制。增加作业的RAM和CPU限制是一项潜在的高成本操作，因为某些任务可能不再适合他们的计算机。在这种情况下，这些计算机上的Borglet将终止一些优先级较低的任务；反过来，这些任务将重新安排到其他计算机上，并可能触发其他优先级更低的任务的终止。
在实践中，理论上可达到的效率通常很难实现，因为手动执行所需的努力或风险过高。 我们需要一种自动进行权衡的方法。 这就是Autopilot所做的。
Autopilot
Autopilot使用垂直缩放来微调CPU和RAM限制，以减少冗余（即资源限制与实际使用之间的差异），同时确保任务不会耗尽资源。 它还使用水平缩放（更改作业中的任务数）来适应更大的工作负载更改。
架构
Autopilot的功能体系结构是三合一的闭环控制系统，一个用于每个作业级别的水平缩放，另两个分别用于每个任务资源（CPU和内存）的垂直缩放。
Autopilot每个job分别考虑，没有跨job学习。有3个实例，其master负责选择推荐算法并将推荐结果传给Borgmaster。Autopilot从独立的监控系统订阅每个task的资源使用情况。
垂直（按task）自动扩展
预处理：聚合监控
原始的监控是每秒一个样本的时间序列，聚合为5分钟粒度。
- 对于CPU，分为400个桶，记录落入每个桶的个数。
- 对于内存，只记录最大值，因为内存不足会导致OOM。
将每个task的直方图相加得到job的直方图。
滑动窗口推荐
策略：需求增加时上界快速增加，但缓慢减少，防止对短时的工作量下降抖动响应过快。为了平滑load毛刺，增加指数下降的权重：
\(w[τ] = 2^{-τ/t_{1/2}}\)
其中τ为样本age，\(t_{1/2}\)为半衰期。Autopilot是给长运行任务优化的，分别使用12小时和48小时作为CPU和内存的半衰期。
针对CPU
- batch jobs：使用\(S_{avg}\)
- serving jobs: 使用\(S_{p95}\)或者\(S_{p90}\)，取决于job的latency敏感度。
针对内存，Autopilot根据job的OOM容忍度使用不同的统计值。OOM容忍度对大多数大任务设置为low，对小任务设置为minimal，并且可以被用户覆盖。
- low: \(S_{p98}\)
- minimal: \(S_{max}\)
- 对于中等容忍度，使用\(S_{p60}\)或者\(0.5S_P{max}\)
最后，加上10-15%的安全边界（上界越大则边界越小）。并且使用上一小时的最大推荐值以防止抖动。
ML推荐
定义cost function，对每个job选取适当的参数来优化cost function，Autopilot可以自动化的对每个job优化滑窗推荐中固定的参数，如半衰期、安全边界、downscaling稳定时间。
ML推荐内部由大量的模型构成。对每个job，recommender定期选择最优表现的模型，被选中的模型负责设置上限。每个模型都是arg min类型的算法，优化cost——模型的区别在于arg min的每个元素的权重不同。Autopilot需要向job owner解释recommender设置的上界，有许多简单模型的好处是单个模型大致对应于推断出的job特点（例如稳定时间长的模型对应于使用率剧烈变化的job）。因此给定选中模型的权重，很容易解释决策。
单个模型
在时刻t，对每个bucket的上界值L，计算最近使用直方图s[t]的underrun和overrun损失，然后和历史值做指数平滑。
包含三部分的关键损失
- overrun 表示失去机会的损失。serving中请求被延迟，终端用户可能放弃使用。
- underrun 表示infra的损失。任务预留的资源越多，需要越多的电力、机器和人。
- 惩罚项Δ帮助避免过于频繁的修改上界。
ensemble
单个模型的cost
在离线实验中优化这些超参数，在保存的代表性的job的trace样本中模拟Autopilot的行为，目标是产生大幅领先其他算法的配置。以迭代和半自动的方式进行：穷举权重的可行值，然后人工分析异常点，如果异常不可接受，在下次迭代聚合结果时人工增加相应job的权重。
水平自动扩展
垂直扩展确定单个task的最佳资源，水平扩展增加或减少实例。水平扩展支持两种方式指定：
- 根据cpu利用率。用户指定平均CPU使用率的窗口时长（默认5分钟）、水平长度T（默认72小时）、统计值S(max或P95)、目标平均使用率r。Autopilot计算最近T时间内的使用率统计值，原始实例数等于统计值/r。
- 目标大小。用户指定函数f(t)，函数使用监控系统中的数据，如文件服务器使用文件大小来做伸缩。
水平扩展需要更多的定制化。原始的实例数再做后处理得到稳定的推荐，目标是防止实例数的突然变化。
- deferred downscaling。使用最近Td时间段的最大值。40%使用2天，35%使用3天。
- slow decay 避免同时停止过多task，每5分钟做停止。
- defer small changes 忽略过小的修改
- limiting growth 允许用户指定在初始化的任务比例上界，因此控制task增加的速度。
赢得用户信任：逐步推广的关键点
评估过程
离线模拟评估
dry run，推荐结果写入日志，但不生效。分析统计聚合数据和异常点。
A/B test
分批部署上线。
用户易于访问Autopilot上界
在dashboard中展示资源使用情况，以及Autopilot计算的资源上界（即使没有开启），帮助用户理解Autopilot的行为和赢得信任。
自动迁移
赢得足够信任后，对存量的小任务和新任务默认开启。用户收到提前通知，可以选择退出。
自定义recommender
自定义recommender可以让用户沉淀带有业务特点的算法、或者在Autopilot之前开发的auto scailing算法。
减少工程苦工
Autopilot减少了需要人工调整的情况和OOM。
参考：
Autopilot: workload autoscaling at Google
译《Autopilot: workload autoscaling at Google》