摘要

      Stratus是一个新的集群调度器，专门用于协调在虚拟集群上运行的batch作业，在公共的IaaS平台动态分配虚拟机实例的集合。与传统的集群调度器不同，Stratus主要致力于成本方面的考虑，因为公有云有效的提供了无限制的，高度异构的，按需分配的资源。但是由于资源在分配时是收费的，Stratus在作业运行时评估的指导下，积极地将任务打包到机器上，尽可能让任务分配的资源要么是满的要么是空的（满的可以提高利用率空的可以节约成本）。基于谷歌的集群负载追踪器和TwoSigma展示，Stratus与最先进的虚拟集群调度器相比降低了17-44%的成本。

CCS概念

• Computer systems organization --> Cloud computing ;
• Software and its engineer --> Scheduling ;

术语介绍

术语	描述
Instance/Server/VM	在IaaS平台租用的一组资源，通常是虚拟机的形式（比如亚马逊的EC2）
Container	可在Instance中部署的隔离环境（比如Linux Container）
Resource	实例的硬件资源，比如虚拟化核或内存
Resource until	分配给task的实例资源聚合百分比
Task	计算的最小逻辑单元，通常在单个container中执行
Job	由集群中用户提交的运行计算任务的集合
Runtime bin	由时间间隔定义的逻辑bin，由一组Instance组成，这些instance上task的运行时小于时间间隔的上限。Stratus使用它将相似运行时的任务分配给实例。
Instance type	https://www.amazonaws.cn/en/ec2/instance-types/

EC2的三种计费方式

1. On-demand Instance 按需计费。提供以GB/小时为粒度的计费单位，无须预付费，也无须承诺使用时长，并且可以通过Auto Scaling功能自动增删所租用的资源，做到了按需支付
2. Reserved Instance 预付费。需要事先承诺合同时长，比如一年或三年，并需要缴纳一定的一次性费用，但是此后在实际中使用仍然以小时计费，而且单价比On-demand Instance 平均低50%。在服务等级上Reserved Instance也高于On-demand Instance ，亚马逊保证Reserved Instance用户随时可以获取其所需要的服务资源，而按需的没有这种保证，不过也很少会出case
3. Spot Instance 竞价/自定义价格。在这种服务中用户自己定价，定下愿意接受的最高价格，来租用EC2的闲散资源。亚马逊根据供需情况会周期性的发布即时价格，若用户定价高于该价格时则服务运行且以实际价格支付，若用户定价低于即时价格则系统自动终止服务待即时价格低于用户最高限价时再次启动。这种模式适合需要大量计算能力但对计算响应要求不高的用户。当然用户需要自行保证使用Spot Instance的应用对于随时宕机具有调整能力。

1 简介

      公有云计算已经成熟到很多组织都依赖它来减轻传统的本地集群（所谓的云爆发）的工作负载甚至完全取代本地集群。虽然传统的集群调度器可以管理大多数公有云虚拟机实例的静态分配，但是这种安排将无法利用公有云的弹性按需属性，所以是不必要的成本。（原文中使用实例instance这一术语来代指在公共IaaS云中租用的虚拟机资源）
      通用方法 [15,36,38,54] 都是在任务提交时分配实例在任务完成时释放实例。虽然简单但是这种为每个任务都新建一个实例的方式失去了一个重要的机会：通过将任务打包成更少虽然可能更大的实例中来降低成本。这样做可以提高资源利用率，也能够利用实例类型之间不同的价格差异。
      我们需要一个虚拟集群调度器virtual cluster (VC) scheduler，它可以像传统的调度器一样，将工作打包成instances，不需要假设正在管理一个固定的资源池。这种调度器与传统的集群调度器不同，与强迫任务等待其他任务完成的方式相比，它通过按需获取额外资源的能力，增加了资源租用成本，消除了排队延迟。最小化成本依赖于做出正确的决策，包括哪些任务可以一起打包在instances上，何时添加更多实例，添加何种实例类型，以及何时释放以前分配的实例。
      Stratus是专门为公共IaaS平台上的虚拟集群设计的调度器。Stratus会自适应的增加或缩小它所分配的实例集，精心选择成本最小利用率最高的任务集进行打包。随着时间的推移为了最大限度降低成本，Stratus努力尽可能的让提交的作业达到100%利用率或0%利用率以便可以立即交付（或停止支付）。通过积极使用我们称之为runtime binning的新方法，Stratus基于它们的预期完成时间进行分组和打包。如果做得好，这样打包的任务将完全利用一个实例 ，大约在同一时间完成，并且在利用率最低时允许释放当时空闲的实例。为了避免由于错误预测运行时间而延长低利用率实例的保留时间，Stratus会迁移仍在运行的任务来清除此类实例。
      Stratus的拓展决策也旨在利用实例类型多样性和实例定价变化（静态和动态）。当虚拟集群中需要额外的实例以立即运行提交的任务时，Stratus会请求经济高效的实例类型来满足一组预计完成时间相似的任务。我们发现要实现良好的成本节约，需要考虑将那些使用的每种资源成本都是一致的pending任务打包，如果要是先单独考虑一个再考虑另一个会导致<packing, instance-type>的组合更少并且成本更高。Stratus 共同决定要打包哪些任务以及使用何种实例类型。
      来源于亚马逊商城虚拟集群中的模拟实验，通过谷歌和TwoSigma的集群负载跟踪驱动，证明了Stratus的有效性。与最先进的没有打包的，每个任务一个虚拟机的方法相比，Stratus将总成本分别降低了25%（Google）和31%（TwoSigma）[74]。将两个最先进的虚拟集群调度器进行比较：动态虚拟集群扩展和作业打包，Stratus降低成本17%-44%。即使使用静态的实例定价，比如亚马逊的按需实例以及谷歌的计算引擎和微软的Azure，stratus也能将成本降低10-29%。Stratus的优势归因于它的每一个主要元素：运行时意识的打包，实例多样性意识和低利用率驱动的迁移。此外，我们发现组合比分开的总和还要多，如果不能一起决定打包的任务和实例类型，那么会显著的降低成本节约。
      本文主要有四个贡献：1. 它确定了一系列独特的特征，这些特征表明了一个专门用于虚拟集群的新作业调度器的角色。2. 它描述了如何使用运行时意识的打包来最大限度的减少租用实例的低利用率以及即使存在不完美的运行时预测也可以使其在生产环境中运行良好的方法。3. 它揭示了打包决策和实例类型选择之间的相互依赖性，展示了对他们进行共同决策时所带来的成本收益。4. 它介绍了一种使用新型的打包和实例获取策略的batch作业调度器（Stratus），并且通过两个大规模的真实环境的集群工作负载的跟踪驱动模拟，展示了其策略的有效性。

2 背景和相关工作

      计算机集群的作业调度有着丰富的历史，随着新系统处理更大规模和合并的工作模式，创新仍在发生[16,19,22,24,31,32,41,46,55,56]。一般来说，作业调度器是集群管理系统的资源分配决策组件，包括检测和监视集群资源，启动分配的作业执行，强制执行资源使用限制等等。用户向集群管理系统提交一个或多个任务（共同组成一个作业的单台计算机程序）的作业，通常还包含每个任务的资源请求（比如需要多少CPU和内存）。作业调度器需要决定什么时候在哪个集群的计算机上执行这个作业中的每一个任务。处于资源隔离和安全的目的，每个任务通常以某种形式的容器执行。
      Stratus是一个集群调度器，其目的是在虚拟集群中调度批处理的工作负载（比如机器学习模型，并行测试组件，以及像MapReduce和Spark这类的分布式ETL）。本文描述了Stratus如何通过有效利用公有云无限虚拟集群弹性，实例类型多样以及租赁价格的变动来降低成本。本节概述了共有IsaS云产品的相关方面并讨论的相关工作。

2.1 云服务提供商产品

IaaS instance types and contracts IaaS实例类型及合同。

• 云服务提供商(CSP)以精细的时间粒度提供了一组有效的无限可供租用的VM实例。每个云服务提供商都提供不同的VM实例类型，主要是通过其组成的硬件资源（比如核心数，内存大小）和租赁合同模型来区分的。
• CSP[3,6,8]提供的两种主要的合同模式是on-damend和transient。根据on-damend合同租赁的实例是不可抢占的，根据transient租赁的合同通常是便宜很多但是CSP可以在任何时间单方面撤销。on-damend实例的价格通常会固定很长一段时间，而transient实例的价格会随时间频繁变化。
• 在亚马逊的EC2[3]，使用transient合同租赁的实例被称为spot Instance。spot Instance的价格通过spot market[4]规定，该价格会随时间波动，但是一般会比on-demand的价格低70-80%。为了租用spot Instance，用户会指定一个bid price（招标价格），这个价格是用户所能接受的最高价。spot Instance可以随时被取消，但是在使用常见的竞标策略（比如使用on-demand的价格）时这种情况一般很少发生。

Autoscaling of virtual clusters 虚拟集群的自动扩缩容

• 虚拟集群中的自动扩缩容分为两个部分：确定scale的容量以及选择正确的实例集以scale到指定的容量。
• CSP提供VC管理框架（比如Amazon EC2 Spot Fleet）用于选择和获取实例以根据用户指定的策略进行扩展，直至达到目标容量。在Spot Fleet的可用策略中包含lowestPrice（总是以当前最低的spot价格添加新实例）和diversified（添加新实例以增加spot虚拟机池中的多样性）
• 确定VC的目标容量可以由VC的调度器reactively，每当新作业中的任务不能在现有的资源上运行时就可以进行扩展。虽然Web服务需要预测正确的目标容量，但是为了防止违反SLO（其中可容忍的延迟大约为秒或更少[21,27,39,49]），作业调度器的集群工作负载更加宽容。即使与总是可以立即启动每一项新job的理想情况相比，我们观察到，reactive的VC缩放器也提供了合理的工作延迟（见第5章）。

Assigning containerized tasks to instances 将容器化任务分配给实例

• 容器服务可以容器化用户的应用任务使其在公有云上运行。有两种主要的容器管理服务可用：server-based和container-based
• server-based模式[1]，用户提供一个实例队列（比如Spot Fleet），容器服务根据配置的放置策略将任务调度到可用的VM中。比如在亚马逊ECS[2]中可用的任务放置策略包括binPack（将任务放置到可用资源最少的Instance上）random和spread（轮询）。server-based的容器服务，在VC调度的上下文中，负责将容器化任务打包到VM实例中。
• container-based模式[5]，容器服务自动管理容器的放置，执行以及所有的基础设施。用户根据容器消耗的资源付费。正如第4章中的描述，改方法比当前普遍使用的server-based模式的要贵很多。

2.2 相关工作

Private cluster schedulers 私有集群调度器

• 私有集群通常有一组固定的机器组合，在部署时无论什么样的硬件异构都是存在的。现有的先进调度器[17,19,22,24,29,31,32,41]经常根据现有的实例集优化调度策略。但是公有云提供了多种类型和大小的实例，并且允许虚拟集群随着时间的推移其大小和组合都可以变化，因此通常可以在需要时获得给定作业的最佳匹配实例类型。当然不同的类型会有不同的价格，这是必须考虑的。更复杂的是，指定实例类型的价格会随着时间而变化，尤其是在AWS的spot市场中（如上所述）。与传统的集群调度器相比，这种差异要求VC调度器关注不同的问题。

Task-per-instance virtual cluster schedulers 为每个任务都创建实例的虚拟机群调度器

• 以前大多数关于在公有云资源上调度作业的工作都是将每个job中的每个task映射到一个Instance上，并且仅在任务持续时间获取。这种方法既适用于cloud bursting配置[15,25,54]（其中来自私有集群的多余负载被卸载到共有与资源上）也适用于全虚拟集群的配置。
• 对于Task-per-instance调度器已经做了各种的策略改进。Mao等人[36,38]提出了一种平衡job deadline和预算约束的框架感知VC调度技术。Niu等人[40]讨论了调度启发法，以解决AWS以前基于小时的计费模式，方法是将实例重新用于在小时付费周期内有剩余时间的新任务。Hotspot[47]解决（利用）spot市场的动态性和Instance type的多样性，随着市场的价格变动，总是将合适的新任务或者从较贵实例上迁移下来的任务分配到最便宜的实例中。

Packing VC schedulers 集群打包调度器

• 与常用的Task-per-instance调度方法相比它降低了成本，因为它降低了由于不完美匹配导致利用率降低的风险。
• 一种合理的方法[10]是使用CSP提供的服务将容器化任务打包到弹性虚拟集群上。特别是可以使用server-based的容器服务在spot实例上放置任务，同时使用实例管理框架（SpotFleet）维护正在使用的实例队列。这种组合基本上产生了packing VC scheduler并且也是在第5章中与Stratus比较的方法之一。
• SuperCloud是一个允许应用跨云迁移的系统[48]，它包括一个子系统（SuperCloud-Spot）用于获取和打包spot实例[30]。SuperCloud-Spot似乎主要针对一组固定的长时间运行的作业而设计，因为没有讨论为了解决动态任务到达/完成的在线打包方法以及任务CPU/memory需求变化的方法。但是它代表了朝着有效的VC调度器迈出的重要一步，我们将其纳入我们的评估中。我们还评估了对它的自然拓展，这也是我们理解Stratus个性化功能的增量收益。

Energy-conscious scheduling 节能调度器

• Energy-conscious调度器试图通过主动让一些机器空闲并关闭它们的电源来减少集群的能耗。因此它们视图将任务密集的打包到机器上，以尽量减少必须保留的机器数量[13,14,35]。它的目标与VC调度器目标类似，VC调度器主要通过减少实例时间和更高效的打包来最小化集群开销。从云中获取/释放实例类似于打开/关闭物理机。
• 虽然Energy-conscious调度器和VC调度器的共同目标都是最大化机器利用率，但是节能调度器通常不会利用实例异构或者价格变动带来的机会。不过它会严格关注任务打包，与Stratus最接近的调度器是Knauth等人提出的，基于预先确定的运行时将虚拟机打包到物理机上。不同的是，Stratus没有已知的运行时，但他利用运行时预测来对预期在同一时间内完成的任务进行打包。

3 STRATUS

      stratus是一个集群调度，旨在共有云上可以实现经济高效的作业执行。Stratus将新的弹性意识的打包算法与成本意识的集群缩放器相结合，利用了实例类型的多样性以及实例价格的变动。Stratus从两个方面降低了成本：1）通过调整任务运行时使一个Instance上的所有任务都在相同时刻完成（理想情况），这样可以使实例快速的从几乎完全的利用率过渡到被释放。2）通过选择在扩容时获取哪种新的实例类型并同时对任务打包进行决策，使它可以平衡实例利用率的成本收益以及实例价格随时间变化之间的关系。本节主要介绍Stratus的设计与实现

3.1 架构

      本节介绍Stratus的架构和关键组件，并引导读者了解job在Stratus中的生命周期。Stratus充当整个运行环境中的调度组件，例如YARN或者kubernetes集群。Resource Manager(RM) （比如YARN RM/ Kubernetes master）仍然负责执行环境中的调度决策。

1. 用户提交job请求被RM接收。job请求中包含要启动的task数量，以及每个task中的资源需求。

2. 如果job被接纳，RM会从job中剥离出task请求并将其发送给Stratus RM Proxy。RM Proxy负责接收来自RM的事件状态（比如新的任务请求，任务失败，任务完成等等）然后会将其路由到调度器。

3. 调度器包含packer和scaler。packer决定tasks被调度到哪些可用的Instance上。scaler决定应该何时为集群获取哪些VM instances，以及何时执行任务迁移以处理任务运行时的错误校准。来自RM Proxy的任务请求，packer会将其放置到调度队列中。Pending任务会在周期性调度事件中被批量调度，调度事件的频率是可配置的。

4. packer和scaler做调度决策和缩放决策时依赖Runtime Estimator所提供的任务运行时预估值。

5. 如果task不能被调度到集群中可用的任何可用instance上，packer将这些任务及它们的运行时估计值一起转发给scaler，scaler会决定为这些tasks获取instance。scaler将相应的请求发送给Cloud Connector，Cloud Connector是云提供商的特定可插拔模块，用于为Stratus从中获取和中止instance。

6. Cloud Connector翻译请求并异步通知IaaS云平台API来获取新的instance。当新的instances准备好后Cloud Connector会通过异步回调通知packer。

7. 调度器会通知RM关于任务的放置决定，新实例的可用性，以及在调度事件结束后要迁移的任务。

8. RM会强制执行任务的放置策略并将新实例添加到实例管理器的队列中。

9. 在task被放到instance之后，完成事件会被提交到RM。在RM接收到job中所有task的完成事件后job就被认为已完成，并且它的任务运行时会报告给Runtime Estimator用于更新job的运行历史。

3.2 Packer

      本节介绍Stratus的在线打包组件Packer，它将新到达的tasks放置到已经运行的实例上。Scaler会使用兼容的方案，基于无法打包到运行实例的tasks的打包属性来决定获取哪些新的实例。

3.2.1 Setup

      Stratus的主要目标是最大限度的减少VC的云计算账单，账单主要由完成工作负载所需的资源时间（eg：VCore-hours）所驱动。因此，Packer的目标是紧密打包任务，使实例上运行的任务的剩余运行时尽可能彼此紧密对其，否则如果一些任务比其他完成的快，那么市里的一些容量就会被浪费。

Packer input

1. Queue of pending task requests. pending任务的请求队列，其中每个任务的请求包含任务的资源向量（虚拟化核和内存），估计的运行时，优先级以及调度约束
2. Set of available instances. 一组可用的实例集合，对于每个实例，Status会追踪其上的可用资源以及分配于其上的任务的剩余运行时（也就是完成任务所需的时间）

Runtime binning

• packer维护由不相交的运行时间间隔指定的逻辑bins。每个bin包含任务的剩余运行时都在整个bin的时间间隔内。同样的，一个实例会根据其剩余的运行时被分配给一个bin，实例的剩余运行时是指其上被分配的任务中最长的剩余运行时间。在这两种情况下区间的边界都是指数定义的：第i个bin的运行时间是[2^(i-1), 2^i)。为了方便讨论，我们根据定义的运行时间间隔上限来比较运行时容器（bin），即最小的bins具有时间间隔[0,1), [1,2), [2,4) ... ...等等

3.2.2 Algorithm description

      在调度事件开始时packer组织任务和实例进入合适的bin中。然后任务按运行时降序排列-longest task first。对于每个任务，packer尝试分为两步将其分配给可用实例：up-packing 和 down-packing。

Up-packing phase

• 在放置任务时，packer首先会看与该task相同的bin中的实例。如果有多个实例都符合调度该任务的条件，packer会选择剩余运行时与当前任务最接近的实例。如果没有任何实例能够调度该任务，packer会逐步增大考虑的bin。
• 如果在一个较大的bin中有多个候选实例，那么任务会被分配给可用资源最多的实例（而不是分配给运行时最相近的实例）。这样做的原因是可以在该实例中留出更多的空间，这样在未来有相同bin中的任务到达时可以有更高的概率被调度到该实例上。
• 如果任务仍不能被调度到任何一个实例上，那么packer会继续检查下一个bin中的实例，直到检查完剩余greater bin中的所有实例。
• 虽然up-packing可能会导致实例运行时不一致，因为Stratus试图将实例上运行时较短的任务和剩余运行时较大的任务一起打包，但是他也会增加较大容器中的实例利用率，并且可以防止有足够的资源在已经获取的实例上运行小而短的任务时再获取新的实例。up-packing最低限度的中断了任务在未来被调度到更大的bin上的机会，因为向上打包的任务仅使用了实例上剩余运行时的一半。图2展示了在单个实例的up-packing阶段进行运行时装箱的示例。

该示例展示了运行时装箱是如何随着时间的推移将任务调度到一个实例上的（图a-c）。这个简单的示例架设了所有的任务都是大小一致的并且该实例总共可以容纳四个任务。实心灰色框概述了该实例，运行时bin使用了彩色的编码（比如蓝色和红色分别代表了[16, 32)和[8, 16)）。实例中的条形图表示分配给它的任务，任务条使用其bin的颜色进行编码。虚线框表示了实例分配的运行时bin。

Down-packing phase

• 如果所有的greater bin都被检查过之后，packer会在down-packing阶段逐步检查lesser bin以寻找合适的VM以调度任务。如果有多个候选的VM，那么stratus会像up-packing一样，使用那个剩余可用资源最多的VM。down-packing会将原来那个实例从较小的bin中提升到与该任务同级的bin中。
• 虽然提升实例bin可能导致实例上的任务运行时不一致，但是在实践中这与直觉相反。由于具有相似运行时和资源请求的任务经常被处理batch数据的作业同时/连续提交，因此提升了大规模的没有打包好的实例，允许更多机会充分利用具有此类未调度作业的实例的可能性，而因为满足当前任务资源请求的VM既不能在任务的本地运行时bin中也不会再greater的运行时bin中，所以需要down-packing。
• 提升实例也会增加在以后的调度周期中更好的利用实例的机会，因为任务总是在down-packed之前执行up-packed。此外，如果任务的运行时已经不准确了，那么分配给实例的一些任务可能实际上属于某个更大的bin，特别是在实例很大的情况下。如果升级的实例重新分配未充分利用的资源，则可以通过实例清除（3.4节）来取消实例分配，并将任务重新分配给他们正确的bin。

3.3 Scaler

      当Stratus没有足够的实例来容纳调度事件中的所有任务时，它会立刻扩容（scale out）并请求新的实例提供给未被调度的任务。Stratus决定获取哪些实例的程序是迭代的。它在每次迭代结束时会决定获取一个新的实例，将未被调度的任务分配给该实例，并持续执行直到所有的未被调度的任务都被分配到某个新实例上。
      在scale-out期间，Stratus会一起考虑任务打包和实例类型的选择，寻求实现最具有成本效益的组合。在每一次迭代中，它会根据运行时降序的考虑每个bin中的为被调度的任务。scaler构造了几个候选任务组，将它们放置在新的实例上。每个候选任务组都会为每个可能的实例类型分配一个成本效益分数cost-efficiency score。具有最高成本效益分数的候选组将会被分配到其最佳得分的实例类型，该实例类型被获取并添加到虚拟集群中。
      同时考虑两者对于实现高成本效益至关重要。单独的执行任何一个，然后再执行另一项，都会导致较大的偏差。先选择实例类型会导致所选实例的利用率较低，因为packing的配合度较差；若先进行任务打包则会由于限制了合理的实例大小阻止了利用价格动态变化的机会。Stratus的迭代方法平衡了在组合空间中潜在的大规模搜索的复杂性和探索该空间中不同点的重要性。

Candidate task groups 候选任务组

• 候选任务组的构造使得第i个组包含了按照运行时降序排序的列表中第i个任务。也就是第一个任务组包含了运行时最长的任务，第二个任务组包含了第二长的任务，以此类推。scaler会继续构造候选任务组，直到最大的任务组资源之和超过了最大实例类型所允许的范围。

Cost-efficiency score 成本效益分数

• 计算公式：score = normalized used constraining resource / instance price
  对每个候选的<task group, instance>对儿，评估相对于实例成本在候选实例上放置候选任务组的资源效率。
• 为了找到标准化使用的资源约束normalized used constraining resource，我们首先通过计算每个资源类型（VCores, memory）的利用率来找到约束的资源类型，就好像任务组已经被分配给了实例一样。产生最大利用率的资源类型就是约束的资源类型。知道了约束的资源类型后，任务组请求的约束资源量就是used constraining resource。最后，我们通过在最小的实例类型上可用的约束资源类型的资源量来规范化已使用的约束资源，也就是我们将其作为normalized used constraining resource。该值被用于帮助约束资源类型不同的跨<task group, instance>对儿之间的比较。
  例如，一个候选组需要4虚拟化核和1GB内存，候选实例有8虚拟化核和16GB内存，那么约束的实例类型应该是虚拟化核（4/8 > 1/16）使用的约束资源量就是4虚拟化核。假设我们可以获取的最小实例类型是2虚拟化核，那么我们的标准化资源约束就是2（= 4/2）.
• 直观的说，如果只考虑一个资源维度那么成本效益分数最高的实例相当于单个资源使用成本最低的实例。
• 在每个scale-out迭代都结束后，具有最高成本效益的候选对会被选择，并将相应的任务组调度到实例上。如果仍然存在未被调度的任务，那么scaler会开启另一个迭代以放置其余的任务，并持续执行直到所有任务都被调度。

Scaling in 缩容

• Stratus中止实例有两种情况：1）没有任何tasks分配到实例上；2）一直保持低利用率那么它的tasks就会被迁移走（3.4节）

Runtime interval bin selection 运行时间隔bin选择器

• 如果运行库中有足够数量的任务，那么就会有更多的实例扩展选项，特别是对于那些更大，可能更实惠更不容器出现资源碎片的实例。正如日常所观察到的[20，44]，作业和任务的运行时分布经常是长尾的。因此我们以指数形式定义运行时bin的时间间隔，以便能够以一种原则性的方式对尾部运行时的任务进行分组，同时不牺牲位于较小时间间隔bin中任务的打包效率。以指数方式定义运行时存储bin还允许我们绑定bin的数量，而无需指定静态大小的运行时间间隔或者是准确算出特定的最佳bin的容量。

Bidding strategy and instance revocations 投标策略与实例撤销

• Stratus不准备利用spot实例撤销的退款政策，也就是在第一个小时内被撤销的spot实例将会全额退款；相反，它只关注利用动态的资源成本变动来实现成本效益（在EC2的spot市场中，单个资源的成本变化频繁。比如仅在us-west-2的m4实例，虚拟化核的成本排序顺序一天变化850次）。Stratus使用安全的实例投标策略，也就是以其对应的按需价格为实例投标。Shastri等人[47]发现对于spot实例使用按需的价格进行投标，需要很长时间才会撤销（平均25天）。我们的实验也证明了这一点，在我们所有的实验中，只出现了一次spot的价格飙升。

3.4 Runtime estimates

Runtime Estimator 运行时估计器

• Runtime Estimator是一个提供运行时预测的组件，它通过一个可查询的任务运行是预测系统获取预测值，该系统服务于提交给Stratus的任务。对于预测job和task运行时的话题已经得到广泛研究[34,50-52]，Stratus没有尝试在这方面进行创新。我们获得了JVuPredict[52]的副本并修改以供于预测平均的task运行时而不是job运行时。
• JVuPredict算法的工作原理：对于每一个提交的job，根据作业属性确定与作业历史执行相似的作业候选组（作业属性比如由同一用户提交，在一天的相同时间内提交的相同作业名等等）。对于每一个候选组生成多个候选预估值，该值通过对组中所有作业的平均运行时进行估计得出（比如平均值，中位数等等）。JVuPredict将历史上表现最好的attribute-estimator对所产生的估计值与传入的job相关联。

Handling runtime misestimates 处理运行时估计错误
      运行时估计的准确性在Stratus的打包算法中起着重要的作用。虽然Stratus使用指数大小的运行时bin可以容忍一定程度的运行时估计错误，但是引入更专业的方法来处理更大的估计错误是有益的。Stratus使用两种启发式方法来减轻任务运行时错误对成本的影响：

1. Task runtime readjustment. 任务运行时重新调整。在对任务运行时的估计值下限进行调整时，Harchol-Balter等人观察到[26]，一个运行了T秒的进程至少在持续T秒的概率约为1/2。因此Stratus通过假设任务已经运行了它运行时一半的时间来重新调整任务运行时的估计值下限。
2. Instance clearing. 实例清除。Stratus将那些连续经历低资源利用率的实例中的任务迁移走（在我们的实验中连续意味着在一分钟超过三个调度事件），因为任务运行时不同规模的错误对齐，所以可以在不丢失任务进程的情况下安全中止。我们定义在每个维度中的资源利用率低于50%的实例为低资源利用率实例，因为通常情况下，都可以根据VM的CSP大小将一个实例上的所有任务迁移到一个更小实例上。

VM候选者根据每种资源的成本降序排序来进行评估是否清除。对于每个VM候选者，其实例上的任务要么全部迁移，要么全部不迁移，因为如果一个实例只进行了一部分迁移，那么它的利用率就会降低，但是用户仍然需要支付相同的费用来保持实例的运行；因此，每当选择一个要迁移的实例时，都会将其放到黑名单上防止其他新的任务被调度在上面。对于每个VM候选者上的任务，Stratus尝试使用3.2节中的算法将任务重新打包到当前正在运行的实例上。如果没有找到合适的实例，Stratus可能会选择获取一个新的可能更小/更便宜的实例用于放置候选者上的全部任务。Stratus在执行任务迁移之前会计算清除实例的利弊。Stratus只有在实例中任务的最长预测运行时大于估计的迁移时间时才会清除实例。