调度论文调研

发表于 2023-11-10 更新于 2024-10-27 分类于算法，调度算法阅读次数：本文字数： 23k 阅读时长 ≈ 21 分钟

Bistro

《Bistro: Scheduling Data-Parallel Jobs Against Live Production Systems》

facebook2015年论文，用于解决离在线混部时，约束离线任务运行在指定资源范围的问题

提出了一种基于树模型的资源调度问题

例如叶子节点是数据库卷，上面的父节点是主机，机架等等

在任务退出时，对影响到的叶子节点以及父节点（直到根节点）进行调度，来避免全部资源池的调度太过耗费性能

Bistro在架构上允许对树的独立资源的根节点，哈希或者按位置进行分区，从而进行并行调度和分布式调度

Stratus

《Stratus: cost-aware container scheduling in the public cloud 》

同名公司2018年论文，一个跨平台的调度组件，用于提高离线任务的资源利用率从而降低成本

主要思想是尽量让机器保持在100%或者0%的利用率，从而退机节省资源

主要手段是通过预估任务的运行时间，用类似伙伴算法的方式让每个实例上的任务同一时间运行完毕从而退机

辅助手段是对利用率过低的实例，将任务迁移到较高实例上

Alsched

《alsched: Algebraic Scheduling of Mixed Workloads in Heterogeneous Clouds》

2012年论文，是Borg论文的前置引用论文，证明了Borg粗精排系统中精排（在本文中叫做软约束）的有效性

硬约束表示必须满足的约束条件，软约束表示不是必须严格遵守的，可以提高性能的约束条件

本文将软约束表达成了一种数学模型，并且通过设计了Alsched的模拟器，证明了软约束可以比硬约束或者无视约束都更高效，任务运行的更好

Quincy

《Quincy：Fair Scheduling for Distributed Computing Clusters》

微软2009年论文，那时候还没有容器系统，所以讨论都是基于一台机器只运行一个任务来进行的

在第二节问题设定中，提出了在数据密集型计算模型场景下，调度策略中公平性和局部性两种问题的矛盾点
- 局部性
  
  同一个作业的多个任务需要尽量部署在同一个机器或者机架上，以减少任务读取数据的通讯开销
- 公平性
  
  定义：每个作业在独占集群时运行t秒，那么J个并行作业一起在集群运行时，不能超过Jt秒
为了局部性要求，作业的任务要尽可能等待更好的位置，但是这会破坏公平性，让作业执行的很慢
在第三节介绍了基于队列的调度算法

机器和机架的优先级，根据存储了任务需要的数据的比例来计算

在机器，机架和全局中各有一个队列，每个任务根据优先级选中10个机器或者10个机架的队列来投递

当一台机器空闲时，将使用这一节的一些算法来从机器队列或者所在机架队列，或者全局队列中选出一个任务来执行
- 贪心公平性算法
  
  每个作业计算出允许同时执行的任务数量，超过允许的数量会被禁止执行任务，如果超出限额的任务会被杀掉
  - 基础分配
    
    每个作业基础分配任务数\(A_j^* = \min(\frac{M}{K}, N_j)\)
    
    M是总机器数量，K是总作业数量，\(N_j\)是当前作业正在运行或者等待运行任务数量
    
    这个基础保证了，如果资源足够，每个作业至少能获得它所需的资源份额，或者每个作业能平等分享总资源。
  - 额外分配
    
    如果\(\sum_{j} A_j^* < M\)，说明因为有些作业的任务比较少，没有使用到这些资源
    
    那么额外的资源平均分配给已经准备好任务来运行的作业
    
    最终\(\sum_{j} A_j = \min(M, \sum_{j} N_j)\)，min的前者是说总任务使用资源不超过M，这是必然满足的
    
    而后者是说\(A_j\)不能超过\(N_j\)
  - 最后再加上一个cd机制
    
    这是因为存在"sticky slot"问题，当某个作业的任务完成以后，由于这个作业允许执行的任务数量小于\(A_j\)
    
    就又可以执行了，这会导致不停地执行这个作业的任务
    
    所以需要作业的任务数运行到少于一个固定值\(A_j - MH\)（GFH算法），或者隔开一段时间\(\Delta H\)（GFPH算法）才允许被执行
从最简单的G算法，然后是GF，GFP，最终是GFH和GFPH，实际上是一步一步打补丁的过程

作为启发式的算法，有一定道理但是实际上捉襟见肘，指不定哪一天出现一些问题又需要打补丁
第四节正式提出了基于流的调度算法

计算机任务调度问题转化为一个流网络问题，流网络就是一个有向图，其中的节点表示任务，边表示任务之间的关联，每条边都有两个属性：容量和成本，分别对应任务处理的能力和任务处理的成本。

“最小成本流”算法就是去寻找一种任务调度方案，让整个系统的任务处理成本最低。

简单来说，这就像物流问题要送一批货到目的地，每个车辆是一个任务，每条路是一个节点，车辆行驶的速度是任务的处理能力，油耗是任务的成本，最小成本流就是找出让整个物流系统油耗最低的路线。

节点还有一个供应量属性（也被称为“需求”或“源和汇点平衡”）是指定义在网络中的一个节点上的一个量，它表示这个节点的流入流和流出流之间的差。这可以解释为每个节点“生产”或“消费”的流量的总数量。
- 如果一个节点的供应量是正数，那么这个节点被认为是流的“源”，它提供了额外的流入网络。
- 如果供应量是负数，那么这个节点被认为是流的“汇点”，它从网络中消耗流。
- 如果供应量是零，那么这个节点的流入流和流出流必须是平衡的。
在给定的流网络中，所有节点的供应量之和必须为零，这保证了网络中流的守恒规则，即总的流入量等于总的流出量。

在这个图中，每个节点和边都代表了调度问题的一部分。

有两个用来进行配置公平性的参数后续会用到，\(E_j\)代表每个作业最小运行数量，\(F_j\)代表每个作业最大运行数量

由于\(N_j\)是作业中全部任务的数量，因此\(1 <= E_j <= F_j <= N_j\)
1. 节点：
- 工作任务节点\(W_{nj}\): 表示需要调度的工作任务，供应量为1
- 未调度节点\(U_j\): 表示作业j未被调度，供应量为\(F_j-N_j\)
- 计算机节点\(C_m\): 代表可以运行任务的计算机，供应量为0
- 机架聚合节点\(R_l\): 表示每个机架，它将同一个机架的所有计算机的信息整合在一起，供应量为0
- 集群聚合节点\(X\): 表示将所有机架的信息整合在一起，以提供全局视图，供应量为0
- 汇点\(S\): 所有流量最终都会到达此点，它负责消耗从任务节点生成的流，供应量为\(-\sum_j(F_{j} + 1)\)
1. 边：
- \(W_{nj}\)到\(C_m\)的边: 表示工作任务在特定计算机上的运行成本，当机器资源符合任务需要时，容量为1，否则为0
- \(W_{nj}\)到\(R_l\)的边: 表示任务在某个机架上最不利计算机上运行的最大成本，容量为1
- \(W_{nj}\)到\(X\)的边: 表示任务在集群中任何计算机上运行的最大成本，容量为1
- \(W_{nj}\)到\(U_j\)的边: 表示任务未被调度的惩罚成本，容量为1
- \(X\)到\(R_l\)的边：选择\(X\)以后再选择\(R_l\)的成本为0，表示没有额外开销，容量为1
- \(R_l\)到\(C_m\)的边：选择\(R_l\)以后在选择\(C_m\)的成本为0，表示没有额外开销，容量为1
- \(C_m\)到\(S\)的边：成本为0，容量为1
- \(U_j\)到\(S\)的边：成本为0，容量为\(F_j − E_j\)
- 启动任务后，从该任务到除\(C_m\)之外的所有节点的边都会带有一个额外的、随时间增长的成本，用于执行杀死或移动任务，从而浪费了它消耗的工作。
这里最关键的设计就是\(U_j\)了，由于他的供应量是\(F_j-N_j\)，到\(S\)的边容量是\(F_j-E_j\)，假设\(U_j\)流入的流量是\(f\)

一方面\(U_j\)的流量加供应量，一定小于\(U_j\)到\(S\)的边的容量，也就是\(f + F_j-N_j <= F_j - E_j\)，简化一下变成\(f <= N_j-E_j\)

由于\(f\)是未调度的数量，所以本轮调度后的作业的任务总数量\(s = N_j - f\)，所以\(0 <= (N_j - f) - E_j\)，也就是\(0 <= s - E_j\)，也就是\(s >= E_j\)

另外一方面\(U_j\)的流量加供应量，一定大于0，也就是\(f + F_j-N_j >= 0\)，简化后为\(f >= N_j - F_j\)，所以\(0 >= (N_j - f) - F_j\)，也就是\(0 >= s - F_j\)，也就是\(s <= F_j\)

综上设计\(E_j <= s <= F_j\)用于配置控制本轮调度后的每个作业的任务总数量
- 公平性参数
  
  在第三节中介绍的基于队列的公平性算法得到的\(A_j\)在这里进行复用
  
  当\(E_j = F_j = A_j\)时，就是公平性调度
- 抢占参数
  
  对于运行中的任务，除当前运行计算机以外的所有节点到所有节点的边的容量都设置为0，那么就无法被抢占
第五节进行了实验

实验指标是我看到的几篇论文中很详尽的了
- 完成时间
  
  所有作业全部完成的时间
- 系统归一化性能（System Normalized Performance，SNP）
  
  \(SNP = \overline{ANP} = \frac{1}{J}\sum_{j=1}^{J}ANP_j\)
  
  \(ANP_j\)是指作业j在理想条件下的执行时间和当前实验下的执行时间的比值，越大越好，为1说明当前实验可以达到理想情况（独占集群没有任何外部干扰的情况）
- 减速标准化（Slowdown norm）
  
  \(\sigma_j = 1 / ANP_j\)，\(\mathcal{J}\)是作业的总数量
  
  有三个指标
  - \(l_1 = \sum_j\sigma_j/\mathcal{J}\)
    
    均值
  - \(l_2 = \sqrt{\sum_j\sigma_j^2} /\sqrt{\mathcal{J}}\)
    
    欧几里得范数然后\(/\sqrt{\mathcal{J}}\)归一化
    
    欧几里得范数对异常大值更敏感，因为赋予更大的权重
  - \(l_\infty = \sigma_j\)
    
    最大值
- 不公平性（Unfairness）
  
  是\(ANP_j\)的变异系数，就是标准偏差和均值的比值 \[ \overline{ANP} = \frac{1}{J}\sum_{j=1}^{J}ANP_j\\ \text = \frac{\sqrt{\frac{1}{J}\sum_{j=1}^{J}(ANP_j - \overline{ANP})^2}}{\overline{ANP}} \] 如果所有作业的归一化性能越接近，就越公平，那么标准偏差越接近0
- 数据传输 (DT)
  
  从本地磁盘读取的数据、穿过机架交换机的数据和穿过中心交换机的数据
结论

在实验中集群之间传输的数据量减少了最多3.9倍，使得吞吐量增加了最多40%，在体现了更好的局部性同时，保证了公平性

但是这个设计也具有一定的局限性
- 由于年代比较久远，对作业的调度都是以计算机数量为单位的，对cpu，内存，网络等其他资源没有限制，算法是单维度的，但是在容器调度的今天，显然需要一个多维向量来表达容量
- 对作业的任务A和B必须放在同一台机器上的约束不够，在流网络中没有建模
- 没有根据作业和任务的运行时间预测来更好的安排调度，以优化利用率（类似Stratus论文的做法）
这里还有几篇文章也对该论文做了解读，和我侧重点不同，对论文本身的细节说的不太多
- Quincy调度算法一(背景篇)
  
  Quincy调度算法二(算法篇)
- 基于最小费用最大流的大规模资源调度方法
  
  这一篇论文是Quincy展望中最小成本流的增量解算法实现和测试，本身没什么亮点
  
  但是介绍了17年以前的知名调度系统（或基于模拟器的模型），分成了
  - 面向公平性的资源调度方法
    
    代表Quincy，Mesos等
  - 面向优先级的资源调度方法
    
    代表Borg，Omega等
  - 面向放置约束的资源调度方法
    
    代表Alsched，Bistro等
  我希望能把这些论文都看一遍

Kelly

《Kelly：resource allocation, combinatorial auctions, knapsack problems, utility maximization》

2003年论文，是Alsched论文的前置引用论文，不是一篇结论性的论文，探讨了将资源分配问题通过收益最大化机制转换成多维多选择的背包问题

收益最大化问题

通过引入经济学关于Efficiency（效率）和Incentive Compatibility（激励兼容性）的内容来说明，在买家（外部客户）和卖家（资源分配者）的双边交易中无法达到效用最大化

具体来说，效率是指净社会福利的最大化，在这个场景下就是资源分配的收益最大化

而激励兼容性是指为了激发参与者提供真实信息，需要设置一种机制让他们从诚实中获利，所以这可能导致资源分配并非最有效率的方式

但是如果不考虑卖家的利益完全最大化，可以保证买家的收益最大化，这就是广义维克瑞拍卖（Generalized Vickrey Auction，GVA）
- 什么是GVA
  
  举个例子来说，假设我们有两个竞拍者A和B，他们正在竞拍一个项目。A出价10元，B出价15元。按照规则，B会赢得这个项目。但他支付的金额并不是他提交的15元，而是A的出价10元（假设没有其他竞拍者）
  
  这种机制的独特之处在于，每个竞拍者的最佳策略就是真实地报价他们对每个项目的估价。这是因为他们支付的金额并不取决于他们自己的出价，而是取决于他们排挤出的所有其他潜在获胜者的估价。换句话说，通过反向报价（故意报出低于他们实际愿意支付的价格，希望以此减少自己最后的支付金额），他们无法减少自己的支付金额。这就形成了一种激励机制，鼓励竞拍者真实地报价。
我认为，对资源分配场景来说，只考虑买家收益是可以接受的（只要买家出价高于卖家成本价格）
将调度问题转换成最大化效用的多维多选背包问题 \[ \begin{align} (1)&\qquad maximize \qquad &&{\textstyle \sum_{t=1}^{T}}{\textstyle \sum_{b=1}^{B_{t}}} x_{bt} u_{t}(b)\\ (2)&\qquad subject\, to \qquad &&{\textstyle \sum_{b=1}^{B_{t}}} x_{bt} \le 1\qquad && t = 1,...,T\\ (3)&\qquad subject\, to \qquad &&{\textstyle \sum_{t=1}^{T}}{\textstyle \sum_{b=1}^{B_{t}}} x_{bt} q_{rt}(b) \le N_{r}\qquad && r = 1,...,R \end{align} \]

\(B_{t}\)表示任务t可接受的资源组合的种类，比如某个任务支持3c的cpu资源，或者1c的cpu资源+1卡的gpu资源

\(u_{t}(b)\)表示任务t使用了某项资源组合产生的收益，比如某个任务使用了1c的cpu资源+1卡的gpu资源，运行的收益产出会比3c的cpu资源更快更好

\(x_{bt}\)代表了任务t选择了第b个资源组合方案，那么值为1，否则为0，就是说任务选择了3c的cpu资源，那么这个方案值为1，不然就为0

所以公式1表示最大化任务选择资源组合的总收益
- 公式2是一种约束条件
  
  约束了\(x_{bt}\)求和不超过1
  
  如果选中了多个方案，求和就会超过1了，也就是说只能选择一种资源组合方案
- 公式3也是个约束条件
  
  r是资源的种类，\(q_{rt}(b)\)表示任务t使用的单项资源
  
  也就是说每个任务使用的单类资源求和，不能超过这一类资源的总和\(N_{r}\)
重点来了
- 当R=1并且\(B_{t}\)为1时，就相当于0-1背包问题
  
  因为只有一种资源类型，每个任务只有一种资源选择方案，可以选择运行这个任务或者不运行
  
  任务的收益是价值，任务的资源使用是重量，总资源就是背包重量上限
- 当R=1并且\(B_{t}\)无限时
  
  相当于整数背包问题，在0-1背包问题的基础上，每个任务可以任意选择资源
  
  由于任务的资源使用（重量）是可以无限增加的，相当于重复选择任务放入背包
- 如果只要求R=1，\(B_{t}\)是有限的
  
  那么就是多重选择背包问题，在0-1背包的基础上，每个任务有几个资源选择方案，但是只能选择一种
  
  相当于每个任务是一类背包，有不同的重量可以选择，但是只能选择一次
- 最后，如果不限制资源的类型R=1，那么就是多维背包问题了

Borg

本篇论文简直处处是经典，需要通读，在这里只对调度算法部分做一些笔记，由于论文在很多细节都没有进行描述，有很多没看懂的，我就加粗标识了

1 用户视角（就是运维和业务开发视角）
- 2.5 优先级，配额和准入控制
  
  优先级包括了monitoring（基础组件）, production（生产）, batch（批处理）, best-effort（尽力而为又叫测试或者免费）依次递减
  
  For this paper, prod jobs are the ones in the monitoring and production bands
  
  对于本文，生产作业包含了monitoring 和 production
  
  这里对生产任务进行了定义，但是没有定义非生产任务，由于后续多次提到生产和非生产类别，因此需要明确优先级和类别关系
  
  在2.1 中提到
  
  For this paper, we classify higher-priority Borg jobs as “production” (prod) ones, and the rest as “non-production” (non-prod)
  
  对于本文，我们将优先级较高的Borg作业分类为生产作业，其余的为非生产作业。
  
  因此生产任务 = monitoring + production，非生产任务 = batch + best-effort
  
  在资源不足时，为了运行高优可以杀死低优，有个抢占级联（监控淘汰生产，生产淘汰批处理）的情况，不允许监控杀死的生产的情况
  
  我觉得只淘汰最低优先级的不就行了？
  
  配额决定了每个作业的整体资源使用，配额不足的会被准入控制拒绝，这是防止有问题的作业占光整个集群
2 Borg架构
- 3.2 调度
  
  作业被记录在paxos存储中，并且加入优先级队列，调度程序对他异步扫描，如果有可用的资源分配给任务，就给任务分配机器
  
  扫描按优先级进行，同一个优先级的不同作业，轮流执行其子任务，防止不公平和大型作业的队头阻塞
  
  调度算法包括了可行性检查和评分（类似k8s的粗精排）
  
  Borg最早使用E-PVM的变种进行评分，它在异构资源中生成单一成本值，并在放置任务时，使资源最小化
  
  E-PVM会将负载分布到所有机器上，为负载峰值留出余地，但是这会导致大型任务碎片化，这又叫做worst fit
  
  与此相反的是best fit，尽可能紧密地填满机器。这使得一些机器为空闲（退机或者用来放大型任务）
  
  缺点是平时对资源需求很低的任务，尝试使用额外的资源会无法使用
  
  Borg为了减少搁浅效应最终采用了一种混合模型，它的效率比best fit高3-5%，不过论文中没有具体解释算法是如何实现的
  
  对于启动时间优化，Borg只是让任务尽量启动在已经安装指定软件包的程序上
- 3.4 可扩展性
  
  调度程序从Borgmaster中拆出副本，成为独立运行进程，实现成一主调度节点和多个副本调度节点
  
  副本调度节点从主调度节点检索状态变化（分配过和未分配过的作业），来更新自己的本地副本。对未分配的任务进行调度，并且通知主调度节点调度结果
  
  主调度节点检查任务结果认为合适就接受，也可以因为例如过期状态的原因拒绝。
  
  论文没有解释状态过期的原因，我认为是负载偏差较大。而这有可能是任务突发资源使用，也有可能是其他副本并发调度。
  
  多个副本调度器看到的资源视图可能是一致的，会造成较多的资源冲突？论文没有详细解释，但是我猜测和下面的宽松随机化策略有关，通过引入随机性减少冲突可能（我也是这么干的）
  
  为了增加调度程序的可扩展性，还有引入了一些优化手段
  - 分数缓存（Score caching）
    
    缓存了粗排和精排的结果，只有当机器或者任务属性发生变化，例如机器资源情况变化或者任务终止，才会丢弃缓存
    
    这里又有点奇怪？不同任务的粗排和精排结果应该是不一样的，这要针对任务缓存那不是要好大内存
  - 等价类（Equivalence classes）
    
    相同需求的任务，只需要对其中一个进行粗精排即可
    
    我猜测这里解释了分数缓存的问题，也就是针对等价类来进行缓存
  - 宽松随机化（Relaxed randomization）
    
    以随机顺序检查机器，直到找到足够多的用于精排的机器就进入精排阶段，而不是粗排所有的机器
    
    k8s也采用了一样的策略，因此k8s在资源不足时调度性能严重下降，需要保证充足的资源来保证调度性能，这会导致资源利用率上不去
  论文提到将集群中全部任务重新调度需要几百秒，但是关闭了上述优化手段以后，3天也无法调度完成
5 利用率
- 5.1 评估方法
  
  详见基于模拟器的调度算法评估算法
- 5.2 集群共享
  
  Borg管理的机器中，98%同时运行生产任务和非生产任务，有83%能运行非生产任务
  
  这说明大约有15%是只允许运行生产任务的，将生产任务和非生产任务混合，预估节省了20-30%左右的资源
  
  为了评估CPU干扰，研究了CPI（每指令周期）变化，这部分引用了
  
  X. Zhang, E. Tune, R. Hagmann, R. Jnagal, V. Gokhale, and J. Wilkes. CPI2: CPU performance isolation for shared compute clusters. In Proc. European Conf. on Computer Systems (EuroSys), Prague, Czech Republic, 2013.
  - CPU使用率和任务数量基本独立，在机器上每增加一个任务，会使别的任务CPI增加0.3%
  - 机器的CPU使用率每增加10%，CPI增加不到2%
  - 共享机器的CPI均值1.58，标准差0.35，专用单元的均值1.53，标准差0.32，总体上共享单元性能要差3%左右
- 5.5 资源回收
  
  A job can specify a resource limit – an upper bound on the resources that each task should be granted. The limit is used by Borg to determine if the user has enough quota to admit the job, and to determine if a particular machine has enough free resources to schedule the task. Just as there are users who buy more quota than they need, there are users who request more resources than their tasks will use, because Borg will normally kill a task that tries to use more RAM or disk space than it requested, or throttle CPU to what it asked for. In addition, some tasks occasionally need to use all their resources (e.g., at peak times of day or while coping with a denial-of-service attack), but most of the time do not.
  
  作业可以设定资源限制 - 每个任务应被授予的资源的上限。这个限制被Borg用来判断用户是否有足够的配额来接受作业，以及某个特定的机器是否有足够的空闲资源来执行任务。就像有些用户购买的配额比他们需要的多，有些用户请求的资源比他们的任务实际需要的多，因为Borg通常会终止试图使用超过其请求的RAM或磁盘空间的任务，或者将CPU的使用限制在其请求的范围内。此外，有些任务偶尔需要使用所有的资源（比如在峰值时段或处理拒绝服务攻击时），但大部分时间并不需要这样。
  
  任务可以限定资源上限（相当于k8s的limits）
  
  当超限以后，如果是内存或者磁盘等非压缩资源；任务会被杀死，如果是CPU等可压缩资源，任务会被限制
  
  Rather than waste allocated resources that are not currently being consumed, we estimate how many resources a task will use and reclaim the rest for work that can tolerate lower-quality resources, such as batch jobs. This whole process is called resource reclamation. The estimate is called the task’s reservation, and is computed by the Borgmaster every few seconds, using fine-grained usage (resourceconsumption) information captured by the Borglet. The initial reservation is set equal to the resource request (the limit); after 300 s, to allow for startup transients, it decays slowly towards the actual usage plus a safety margin. The reservation is rapidly increased if the usage exceeds it.
  
  为了不浪费当前没有被消耗的分配资源，我们估计任务会使用多少资源，并回收剩余的部分供那些可以容忍较低质量资源的工作使用，如批处理任务。这个整个过程被称为资源回收。这个估算被称为任务的预留，并且每隔几秒由Borgmaster计算，利用Borglet捕获的细粒度使用（资源消耗）信息。初始预留等于资源请求（上限）；经过300秒（允许启动的瞬间变化），它慢慢减少到实际使用量加上一个安全边际。如果使用量超出预留，预留会迅速增加。
  
  The Borg scheduler uses limits to calculate feasibility (x3.2) for prod tasks(To be precise, high-priority latency-sensitive ones – see x6.2), so they never rely on reclaimed resources and aren’t exposed to resource oversubscription; for non-prod tasks, it uses the reservations of existing tasks so the new tasks can be scheduled into reclaimed resources. A machine may run out of resources at runtime if the reservations (predictions) are wrong – even if all tasks use less than their limits. If this happens, we kill or throttle nonprod tasks, never prod ones.
  
  Borg调度器使用限制来计算生产任务（准确的说，是6.2章会提到的高优先级延迟敏感任务）的可行性，所以他们从不依赖于回收的资源也不会被资源超卖影响；对于非生产任务，它使用现有任务的预留，以便新任务可以调度到被回收的资源中。如果预留（预测）错误，机器可能会在运行时耗尽资源 - 即使所有任务使用的都小于它们的限制。如果发生这种情况，我们会终止或限制非生产任务，而从不终止生产任务。
  
  Borg调度器会每隔几秒预估每个任务所需的资源量（reservation）
  - 初始reservation = 资源上限
  - 运行300秒后，reservation = 实际使用量 + 安全系数
  - 如果实际使用量超过reservation，reservation会迅速增加（我猜测是乘以一个系数）
  对于非生产任务，可以回收资源上限和预估量的差值来使用，
  
  对于生产任务（又叫延迟敏感任务），不能使用回收的差值，因为这部分资源是不稳定的，随时有可能被原来的任务使用
  
  如果预测出错，机器耗尽了资源，那么Borg会杀死或者限制非生产任务
  
  Borg使用任务指定的上限来进行调度，而不是预估值，也就是超卖只用来运行非生产任务
  - k8s的requests和limits
    
    作为通用化的解决方案，k8s新增了一个requests属性
    
    cpu requests会转化为cgroup的cpu.shares，表示相对其他容器使用cpu的权重
    
    cpu limits会转换为cgroup的cpu.cfs_quota_us和cpu.cfs_period_us的比值，表示这个容器的cpu使用上限
    
    memory limits会转换为cgroup的memory.limit_in_bytes，表示这个容器的memory使用上限（tmpfs之类的内存文件系统也会被限制）
    
    如果超卖导致资源耗尽，需要杀死不可压缩资源的任务，那么首先杀死没有设置requests或者limits的Pod，其次杀死包含容器没有全部设置requests和limits的Pod，最终杀死包含容器全部设置requests和limits的Pod
    
    k8s使用Pod的所有容器requests之和来进行调度。也就是超卖可能运行所有任务
- 6.2 性能隔离
  
  这一部分有很多可以细致研究的，因此会全部翻译在下面
  
  Early versions of Borglet had relatively primitive resource isolation enforcement: post-hoc usage checking of memory, disk space and CPU cycles, combined with termination of tasks that used too much memory or disk and aggressive application of Linux’s CPU priorities to rein in tasks that used too much CPU. But it was still too easy for rogue tasks to affect the performance of other tasks on the machine, so some users inflated their resource requests to reduce the number of tasks that Borg could co-schedule with theirs, thus decreasing utilization. Resource reclamation could claw back some of the surplus, but not all, because of the safety margins involved. In the most extreme cases, users petitioned to use dedicated machines or cells.
  
  早期版本的Borglet在资源隔离执行方面比较原始：对内存、磁盘空间和CPU周期进行事后检查，kill过度使用内存或磁盘的任务，并且采用Linux的CPU优先级对过度使用CPU的任务进行严格控制。但是，对其他任务的性能产生影响的恶意任务仍然很容易出现，所以一些用户会提高他们的资源请求，以此减少Borg能与他们的任务一起调度的任务数量，从而降低资源利用率。资源回收可以回收一些剩余量，但并非全部，因为其中涉及到安全余额。在极端的情况下，用户会要求使用专用的机器或细胞。
  
  上面这一段大概就是我的调度系统现状了，有一些用户对性能特别敏感，因此会使用cgroup声明更多的预留资源，防止其他任务一起占用机器。甚至还有一些不差钱的业务要求独占机器。
  
  我的调度系统更惨的地方在于由于使用cgroup限制，所以我根本无法回收资源
  
  Now, all Borg tasks run inside a Linux cgroup-based resource container [17, 58, 62] and the Borglet manipulates the container settings, giving much improved control because the OS kernel is in the loop. Even so, occasional low-level resource interference (e.g., memory bandwidth or L3 cache pollution) still happens, as in [60, 83].
  
  To help with overload and overcommitment, Borg tasks have an application class or appclass. The most important distinction is between the latency-sensitive (LS) appclasses and the rest, which we call batch in this paper. LS tasks are used for user-facing applications and shared infrastructure services that require fast response to requests. High-priority LS tasks receive the best treatment, and are capable of temporarily starving batch tasks for several seconds at a time.
  
  如今，所有的Borg任务都运行在一个基于Linux cgroup的资源容器[17,58,62]中，Borglet会操纵这些容器的设置，因为操作系统核心参与了其中，从而显著提高了控制力。即便如此，偶尔还是会发生一些低级别的资源干扰（例如内存带宽或L3缓存污染），如[60,83]中所述。
  
  为了解决任务过载和用户过度提高资源请求的问题，Borg任务有一个应用类别。最重要的区别在于延迟敏感（LS）类和我们在本文中称为批处理的其他任务之间。LS任务用于需要快速响应请求的面向用户的应用程序和共享基础设施服务。高优先级的LS任务得到最好的处理，能够在几秒钟的时间内临时性地饿死批处理任务。
  
  批处理任务和其他任务应该是指优先级分类的batch和best-effort，在本文又定义为非生产任务，所以只要是生产任务，都会属于LS类
  
  LS(Latency-Sensitive)类等价于生产任务
  
  A second split is between compressible resources (e.g., CPU cycles, disk I/O bandwidth) that are rate-based and can be reclaimed from a task by decreasing its quality of service without killing it; and non-compressible resources (e.g., memory, disk space) which generally cannot be reclaimed without killing the task. If a machine runs out of non-compressible resources, the Borglet immediately terminates tasks, from lowest to highest priority, until the remaining reservations can be met. If the machine runs out of compressible resources, the Borglet throttles usage (favoring LS tasks) so that short load spikes can be handled without killing any tasks. If things do not improve, Borgmaster will remove one or more tasks from the machine.
  
  第二种区分在于压缩资源（例如，CPU周期，磁盘I/O带宽）是基于速率和可以在不杀死任务的情况下从任务中回收的；而非压缩资源（例如，内存，磁盘空间）通常无法在杀死任务的情况下回收。如果一台机器耗尽了非压缩资源，Borglet会立即结束任务，从最低到最高优先级，直到剩余的保留可以满足。如果机器耗尽了可压缩资源，Borglet将节流使用（优先考虑LS任务），这样短暂的负载峰值可以在不杀死任何任务的情况下处理。如果情况没有改善，Borgmaster将从机器上移除一个或多个任务。
  
  以上的策略和k8s现状是一致的
  
  A user-space control loop in the Borglet assigns memory to containers based on predicted future usage (for prod tasks) or on memory pressure (for non-prod ones); handles Out-of-Memory (OOM) events from the kernel; and kills tasks when they try to allocate beyond their memory limits, or when an over-committed machine actually runs out of memory. Linux’s eager file-caching significantly complicates the implementation because of the need for accurate memory-accounting.
  
  在Borglet中，用户空间运行的定时控制模块，基于预测的未来用量（对于生产任务）或内存压力（对于非生产任务）为容器分配内存。该模块处理来自内核的内存不足（OOM）事件。并且在任务试图分配超出其内存限制的内存，或当超额使用的机器实际上耗尽内存时，会结束这些任务。由于需要进行精确的内存核算，Linux的Eager file-caching机制大大增加了这一实现的复杂性。
  
  这个用户空间的控制模块接管了OOM事件
  
  是5.5中提到的"对生产任务资源预估，并超卖给非生产任务，由超卖导致的内存资源耗尽，会优先干掉非生产任务"这个功能的细节补充
  - 对于生产任务，会根据未来的使用预测来为容器分配内存
  - 对于非生产任务，由于其性能要求较低，资源需求更加灵活和不可预测，因此控制模块会基于当前的内存压力来分配内存
    - 如果内存压力低，系统可以更灵活的分配更多的内存给任务
    - 如果内存压力高，那么系统在分配内存时就需要更加谨慎，例如可能需要限制内存的分配，或者回收一些已分配但暂时未使用的内存
  To improve performance isolation, LS tasks can reserve entire physical CPU cores, which stops other LS tasks from using them. Batch tasks are permitted to run on any core, but they are given tiny scheduler shares relative to the LS tasks. The Borglet dynamically adjusts the resource caps of greedy LS tasks in order to ensure that they do not starve batch tasks for multiple minutes, selectively applying CFS bandwidth control when needed [75]; shares are insufficient because we have multiple priority levels.
  
  Like Leverich [56], we found that the standard Linux CPU scheduler (CFS) required substantial tuning to support both low latency and high utilization. To reduce scheduling delays, our version of CFS uses extended per-cgroup load history [16], allows preemption of batch tasks by LS tasks, and reduces the scheduling quantum when multiple LS tasks are runnable on a CPU. Fortunately, many of our applications use a thread-per-request model, which mitigates the effects of persistent load imbalances. We sparingly use cpusets to allocate CPU cores to applications with particularly tight latency requirements. Some results of these efforts are shown in Figure 13. Work continues in this area, adding thread placement and CPU management that is NUMA-, hyperthreading-, and power-aware (e.g., [81]), and improving the control fidelity of the Borglet.
  
  Tasks are permitted to consume resources up to their limit. Most of them are allowed to go beyond that for compressible resources like CPU, to take advantage of unused (slack) resources. Only 5% of LS tasks disable this, presumably to get better predictability; fewer than 1% of batch tasks do. Using slack memory is disabled by default, because it increases the chance of a task being killed, but even so, 10% of LS tasks override this, and 79% of batch tasks do so because it’s a default setting of the MapReduce framework. This complements the results for reclaimed resources (x5.5). Batch tasks are willing to exploit unused as well as reclaimed memory opportunistically: most of the time this works, although the occasional batch task is sacrificed when an LS task needs resources in a hurry
  
  为了提高性能隔离，LS任务可以预留完整的物理CPU核心，这会阻止其他LS任务使用这些核心。批处理任务被允许在任何核心运行，但相比于LS任务，它们得到的调度份额很小。Borglet仅在需要时选择性地应用CFS带宽控制[75]，来动态调整贪婪的LS任务的资源上限，以确保它们不会让批处理任务饿死若干分钟。仅依赖cgroup的cpu.shares参数不足以满足因为存在多个优先级而产生的复杂CPU资源管理需求
  
  像Leverich[56]一样，我们发现标准的Linux CPU调度器（CFS）需要大量的调整才能够同时支持低延迟和高利用率。为了减少调度延迟，我们的CFS版本采用了扩展的per-cgroup负载历史机制[16]，允许LS任务抢占批处理任务，以及在一个CPU上有多个LS任务可运行的时候减小调度的相关系数。幸运的是，我们许多的应用程序使用每请求一个线程的模型，这缓解了持续的负载不平衡的影响。对于特别有严格延迟要求的应用程序，我们精心利用cpusets来分配CPU核心。这些努力的一些结果展示在图13中。当下，这个领域的工作还在继续，我们正在添加对NUMA、超线程和电源感知的线程放置和CPU管理（如[81]），并且正在提高Borglet的控制精度。
  
  任务被允许消耗的资源可以达到其限制。大部分任务都被允许超越这个限制以利用未使用的（slack）资源，比如CPU等可压缩资源。只有5%的LS任务禁用了这个功能，可能是为了得到更好的可预测性；不到1%的批处理任务这样做。默认情况下禁用了使用slack内存，因为这增加了任务被杀死的可能性，但尽管如此，还是有10%的LS任务覆写了这项设置，79%的批处理任务也是如此，因为这是MapReduce框架的默认设置。这补充了关于回收资源的结果（参见5.5节）。批处理任务愿意抓住机会充分利用未使用的和回收的内存，在大多数时间里，这是有效的，尽管偶尔在LS任务急需资源时有批处理任务需要被牺牲。
  
  论文在说完内存细节以后，继续说了CPU细节：
  
  生产任务绑核，而非生产任务可以运行在任何核心上。生产任务之间不会发生干扰，然后使用了cgroup的cpu.cfs_quota_us和cpu.cfs_period_us，确保生产会比非生产获得更多的cpu时间片
  
  并且通过CFS的per-cgroup负载历史机制(CFS per-entity load patches)，允许生产任务直接抢占非生产任务

基于模拟器的调度算法评估算法

《Evaluating job packing in warehouse-scale computing》

Borg中提到的评估算法，引用了这一篇2014年的论文

本篇论文评估算法的指标不考虑公平性等问题，纯粹是评估哪个算法对资源的利用程度最高

论文提出了4种评估算法进行对比

总体利用率

隐藏了碎片效应，未使用资源的“洞”可能太小而无法被利用

隐藏了搁浅效应，CPU和内存利用率独立计算，尽管有的机器上有可用的CPU字眼，但是因为没有额外内存而无法安排进程
Hole Filling

每个维度通过填充固定大小的单维度虚拟任务，来查看塞满集群以后这个维度的极限利用率

缺点是只查看了单一维度单元的资源，从而和实际的多维度任务不一致，并且忽略了实际任务的任务限制（例如只希望部署在有公网ip的机器上）

Workload Inflation

工作负载膨胀算法通过扩大原有的工作负载情况，来解决填洞法的局限性

// 输入：带有机器列表的集群检查点
Input: vector<Machine> clusterCheckpoint;
// 输出：膨胀后的CPU和内存利用率，膨胀后的待处理任务数量
Output: int CPUUtilizationAfterInflation, MemoryUtilizationAfterInflation, PendingTasksAfterInflation;
// 参数：允许待处理任务的比例τ，是否符合要求
Parameters: float fractionOfPendingTasksAllowed = τ, bool conforming;

vector<Job> Jobs = getAllJobs();
if (conforming) {
    Jobs = getOnlyConformingJobs();		//规格太大（超过60%机器规格中位数）或者限制太多（有60%的机器不符合要求）的任务不能被选中
}
while (getFractionOfPendingTasks() < τ) {
    Job j = pickUniformlyRandomFrom(Jobs); // 使用蒙特卡洛随机算法挑选一个任务来进行膨胀
    Job j_prime = clone(j);
    scheduleAllTasksOnMachines();
}
printPendingTasks();
printCPUAndMemoryUtilizationAfterInflation();

Cluster Compaction

集群压缩算法和工作负载膨胀算法刚好相反：固定工作负载，然后缩小集群，直到工作负载不再适合

具体来说，是生成集群中机器的随机排列，然后使用二分查找确定运行工作负载所需排列的最小前缀。二分查找的终点作为该试验的压缩集群大小返回。运行多次试验以获取压缩集群大小的分布，以消除不幸排列（例如，所有大机器都在一端）的影响。

谷歌对每个集群的测试，对每个不同的参数\(\tau\)，都重复了11次实验，并且展示了90%百分比值和最小最大值的误差棒，这也造成了计算时间是所有算法里最久的

所以误差上限\(\mu\)用来控制算法的计算时间，当二分查找过程中的最大值和最小值之间的差异小于\(\mu\)时，查找停止，此时的中间值作为所需最小机器数量的估计，\(\mu\)越小，结果越准确

// 输入：带有机器列表的集群检查点
Input: vector<Machine> clusterCheckpoint;
// 输出：需要的最小的机器数量
Output: int minNumberOfMachinesNeeded;
// 参数：允许待处理的任务的比例τ，所需机器数量的误差上限µ
Parameters: float tasksAllowedToGoPending = τ, int numberOfMachinesNeededErrorBound = µ;

vector<Machine> machines = clusterCheckpoint;
while (getPercentTasksPending() > τ) {
    //翻倍集群的规模，直到待处理的任务比例降低到参数τ所设定的比例以下
    //以确保有足够的机器来运行所有的任务
    vector<Machine> clonedMachines = clone(machines);
    machines.insert(machines.end(), clonedMachines.begin(), clonedMachines.end());
    scheduleAllTasks(machines);
}
vector<Machine> p = generateRandomPermutation(machines);	//生成随机序列
int min = 0;
int max = p.size() + 1;
while (max - min >= µ) {
    int mid = (min + max) / 2;
    // 禁用mid开始的后面全部机器
    for (int i = mid; i < p.size(); i++) {
        disableMachine(p[i]); //取消被禁用机器上的任务，等待重新调度
    }
    rescheduleAllTasks(machines);
    if (getPercentTasksPending() > τ) {
        min = mid;
    } else {
        max = mid;
    }
}
cout << "Minimum number of machines needed: " << min;

论文测试了4种调度算法进行模拟调度，来对比评估算法的可靠性

测试调度算法是基于生产的调度算法的，只是改变了优先调度任务的顺序
- 按任务到达时间调度
- 按cpu递减调度
- 按内存递减调度和按cpu
- 内存归一化递减调度
根据11个集群的测试，Workload Inflation和Cluster Compaction得到的结论基本是一致的，按任务到达时间调度或者内存归一化递减调度的调度算法效果是最好的

Hole Filling只有当总体利用率特别高的时候，得到的结论才有效

拿Workload Inflation和Cluster Compaction比

前者侧重于在这个调度算法下集群还能增加多少任务（有啥用？）

后者侧重于在这个调度算法下集群还能减少多少机器（这个听起来很实用）

读后感

文中提到的E-PVM似乎很有意思，还需要学习一下
非生产任务调度

Borg和k8s在资源回收上的区别也很有意思

k8s作为通用化系统，在预测方面更为保守，引入了requests概念，让用户决定是否超卖（当requests = limits），就完全不超卖。

在超卖时也无法决定是否杀死非生产任务还是其他任务，这有可能是k8s本身无法判断任务的类型

我的调度系统应该向Borg看齐，允许任务设置软上限，用软上限来进行调度决策，然后通过预估资源的使用量来回收软上限和预估值的差值，运行非生产任务

总结一下：
- 现状
  
  设置了cgroup的任务全程通过cgroup的设置值来调度决策
  
  不设置cgroup的任务通过预估值来调度决策
  - 启动时，预估值是根据历史数据的一个估值，如果没有历史数据就使用一个默认值
  - 启动后，预估值 = 实际使用量
  整机会预留一个百分比的资源来给不设置cgroup的任务所需的突发流量使用
  
  对标k8s的一句话总结：
  - 不设置requests的时候由调度预估requests
  - 设置requests的时候同时会生效limits
    
    这个limits会比k8s更强力，例如机器上限10c，进程A的limits为2c，那么其他进程会在一个8c的limis的默认cgroup里面
- 优化后
  
  新增一个业务手动设置的软上限任务，仅供生产任务使用
  
  可以选择是否要超出软上限，cpu默认开启，内存默认关闭
  - 这个任务的自身启动所需的调度通过软上限来调度决策
  - 在其他任务启动，查看这个任务所在机器的剩余资源时
    - 如果是生产任务，那么通过这个任务的软上限来计算占用了这个机器多少资源
    - 如果是非生产任务，那么通过这个任务的预估值来计算占用了这个机器多少资源
      - 初始预估值 = 软上限
      - 运行300秒后，预估值 = 实际使用量 + 安全系数
      - 如果实际使用量超过预估值，预估值会迅速增加
  相对不设置软上限的任务，设置软上限能尽量保证这个任务的资源所需
  
  相对设置cgroup的任务还能超出一部分资源使用
  
  对标k8s的一句话总结：
  - 不设置requests的时候由调度预估requests
  - 设置requests的时候，可以选择是否设置limits
    
    对于不设置limits的情况，离线任务忽略设置requests，使用调度自己预估的requests
现状的超卖策略比较简单粗暴，只要当前没有使用的资源，就能超就超，只靠整机的少量预留百分比资源来兜底。

这导致同一台机器的高优任务一起突发流量时，容易一起过载，因此业务别无选择只能通过设置cgroup选项来保证任务的可用资源

最终导致了实际资源利用率下降

新增的软上限任务给业务增加了一个额外选择，这个选择相对设置cgroup，对平台可以提高利用率，对业务也能额外节省成本
- 难点
  - 对机器的守护进程会比现在多一些逻辑
    - 守护进程需要定时的预估任务的资源使用
    - 内存管理上，守护进程需要接管OOM事件，优先干掉非生产任务，然后是超出软上限的生产任务
    - CPU管理上
      - 为了让生产任务不会因为非生产任务的资源回收而饥饿
        
        还需要论文提到的CFS的per-cgroup负载历史机制(CFS per-entity load patches)，允许生产任务直接抢占非生产任务的时间片
        
        这个我搜了一下相关资料，有点摸不到头脑，可能需要定制内核调度器代码来实现了
      - 反过来，为了不会因为贪婪软上限任务而饿死非生产任务
        
        守护进程需要及时的给超出上限一段的时间的软上限任务添加cgroup限制

参考资料

Google的Borg论文都说了啥?

Google 大规模集群管理器 Borg

Borg论文阅读