面向云计算服务的互联网应用的自动缩放
原文地址
https://scholar.google.com/citations?view_op=view_citation&hl=zh-CN&user=9sq1eeUAAAAJ&citation_for_view=9sq1eeUAAAAJ:ULOm3_A8WrAC
概述
一些互联网应用可以自动缩放特性中收益，他们的资源使用可以由云服务提供商自动伸缩。我们提出了一个能在云环境中的互联网应用下提供自动缩放的系统。我们在虚拟机中封装每个应用实例，使用虚拟化技术提供故障隔离。
Class Constrained Bin Packing 类约束装箱问题:
在计算机科学领域,"Class Constrained Bin Packing"是一个常见的优化问题。它的基本思路是将一组物品装入多个容器(或箱子)中,使得所有物品都能被放置,同时满足以下约束条件:
- 每个物品属于某个预定义的"类"或"组"。
- 每个容器都有其自己的容量限制。
- 容器中同一类型的物品的总大小不能超过该容器的容量限制。
简单地说,这就是在装载物品时需要同时考虑物品类别和容器容量的一个组合优化问题。
这个问题在实际应用中有很多场景,比如:
- 仓储管理:根据不同类型商品的特性,将它们分类存放在不同货架上。
- 运输规划:根据货物种类和卡车载重限制,合理安排货物装载。
- 计算机内存管理:将不同类型的数据块分配到有限的内存空间中。
解决这个问题的常用方法包括贪心算法、动态规划、启发式算法等。具体的解决方案会根据问题的具体约束条件和目标函数而有所不同。
我们的模型类似CCBP问题，每个服务都是箱子（bin），每个class都代表应用。类约束反应了服务器可以同时运行的应用程序数量的实际限制。我们开发了一种高效的半在线颜色集合算法，达到了良好的需求满足率和节省能源，通过在 低负载时减少服务数量节省能源。实验结果表明，与亚马逊的开源实现Amazon EC2相比我们的系统可以将吞吐量提升180%，从突然拥挤到回复到正常的Qos访问的时间快了五倍。大规模仿真结果表明，该算法具有极强的可扩展性：在10000个服务器和一万个应用中决策时间保持在4s之内。这与传统环境的应用安置算法提升了一个数量级。
1概要
云计算服务的资源弹性是经常被提到的好处之一：企业用户可以根据资源需要按规模增大和减少资源使用在没有前期投入或长期支出的情况下。举个例子亚马逊的EC2服务，允许用户购买虚拟机实例，并操作它们像一个物理机一样。然而，用户还是需要确定自己需要的资源规模和时间。我们相信一些互联网应用可以通过云服务提供商在他们需要时自动放大和缩小中收益。用户只需要将它们应用上传到单一的云服务器上，而云服务将根据需求复制到更多或更少的服务器上。用户只需要支付自己真实的使用，这就是所谓的，按需付费模型。
如图1所示，是典型的互联网应用数据中心服务。它包含了负载均衡交换机，应用服务器集合和后端存储集合。后端交换机是典型的7层交换机，它解析应用级别的信息。为了容错，交换机有时候会在冗余对下运行。每个应用可以运行在多个服务上，它们运行的实例集通常由一些集群软件(如WebLogic)管理。每个服务机器可以托管多个应用程序。应用存储他们的状态信息在后端的存储服务中。这对于应用本身是重要的，所以他们可以安全的进行复制。存储服务器也可能过载，但是这项工作的重点是在应用层。举个例子，谷歌的AppEngine服务，要求应用程序是结构化的，在这样的俩层架构中，使用BigTable作为可扩展的存储解决方案。与AppEngine详细的比较将会被退出到第七节，以建立足够的背景。一些分布式数据处理应用不能映射到简单的分层结构，因此他们不是这项工作的目标。我们相信我们的架构代表了很大一部分互联网托管到云计算的环境的应用。
尽管云计算模型有时候被认为是在需要的时候提供无线的资源，真实世界中数据中心的容量是有限的。当大量应用在同一需求时间到达峰值时，云中的可用资源可能会收到限制一些需求可能不能被满足。我们定义了需求满足比率，成功满足应用需求的百分比。应用程序可用的计算量受到它运行在服务实例的位置的影响。应用实例越多底层的服务就越强，满足应用需求的潜在容量就越高。另一方面，当应用程序的需求降低时，重要的是减少服务器数量来节省能源。各种研究表明电力成本是大型数据中心的主要运行成本。在大部分时间，平均服务的利用率在很多网络中心是很低的：真实的占用大学在5-20%之间。此外工作发现，最有效的节能方式是关闭整个服务器。应用程序放置问题的关键是，在不浪费能源的情况下实现高需求满足率。
在这篇论文中，我们提出了一个系统，他提供在云环境下自动缩放互联网应用的功能。
我们的贡献包括:
- 我们概括了自动缩放在云环境下的问题，并将其建模为一个修改过类约束装箱问题CCBP，每个服务器都是箱子，每个类代表一个应用。我们提出了新的自动缩放算法解决问题，在可证明的界限内提出严谨的分析。与已存在的装箱方案比较，我们创造性都支持了项目离开，有效的避免了频繁的改变放置导致的重新装箱。
- 我们提供了绿色计算自适应的调整应用实例的位置同时将空闲机器进入待机模式。经验和模拟展示了我们算法的高效和可缩放，实现了较高的需求满足率，低放置修改频率，低请求响应时间和优秀的节能。
- 我们发布了一个真云计算系统他提供了自动缩放算法。我们比较了我们的系统和开源的亚马逊EC2自动缩放系统在实验室的30台戴尔PowerEdge刀片服务器下的性能。实验表明，当快速拥挤发生时，系统恢复正常的Qos速度提高了5倍。
- 我们使用了虚拟机的快速重启技术，进行终止和恢复，极大的减少了网络应用启动的时间
本文身下其余部分组织如下，第二章介绍了系统的体系结构，第三章阐述了自动缩放问题，第四章描述了我们算法的详情，环境和模拟结果的表现分别在第五和第六章，第七章描述了相关工作，第八章是结论
2系统架构
系统家架构如图2所示，我们将每个应用实例封装在虚拟机（VM）中。亚马逊EC2和微软的Azure都在云计算产品中使用虚拟机。系统中的每个服务都允许Xen管理程序，支持特权域0和一个或多个域U。每个区域U都封装了应用实例，它们连接到共享网络存储（即存储层）。将虚拟机多路复用到物理机，使用Usher框架进行管理。（在本文中，我们交替使用术语“服务器”、“PM”（物理机）和“节点”。）我们的主要逻辑在系统中的视线是通过设置Usher的插件。每个节点在domain 0上运行一个Usher本地节点管理器（LNM），他在节点上跟踪应用集合运行和每个应用的资源使用情况。L7交换机负责转发请求和响应。
我们系统中的调度程序可以做以下描述。
- 每个节点上的LNM和L7交换机收集了应用程序的位置，每个实例的资源使用情况，和每个应用程序的总请求数。然后当应用程序调度器运行时，信息被转发到Usher中央控制器（Usher CTRL）。
定期调用应用程序调度器做出以下决定。
- 应用放置：对于每个应用，我们需要决定运行其实例的服务器集合。
- 负载分发：对于每一个应用，我们需要根据他的请求率和过去的统计预测将来的资源需求，然后决定如何分配负载给实例集合。应用程序的负载很大程度上取决于用户请求的速率。我们对应用程序进行概要分析，估计每个请求带来的平均负载。然后我们分析了L7交换机中挂起的请求队列以预测服务器上的负载。
决策被转发到LNM和L7交换机执行。每个节点的操作项列表包括：
- 待机或者唤醒指令
- 应用启动和停止
- 应用程序之间的本地资源分配
节点上LNM调整封装应用的虚拟机本地资源分配，Xen可以在CPU调度中调整虚拟机的权重来改变虚拟机之间的CPU分配。虚拟机之间的内存分配可以通过使用ballooning进行调整。
- 应用程序列表
- 对于每个应用程序，实例运行的位置和请求在它们之间分布的概率
L7交换机开始处理web请求根据它最新的配置。
调度器的决策间隔取决于我们希望应用程序更改的响应速度。频繁的改变应用放置会影响应用的性能，应该被避免。
看起来上面讨论的Usher CTRL是一个故障的中心点。幸运的是，它不涉及用户请求的正常处理逻辑。它的故障只会中断更新负载的分发和应用的放置策略。新来的用户请求会被保持操作已经存在的应用实例进行处理。如果需要更高程度的容错，我们可以使用我们组开发的热惊喜技术来备份复制Usher CTRL
我们也注意到复杂的应用启动和完成所有初始化需要很长的时间（几分钟或者更长）。由于我们在VM中运行每个应用程序，整个运行状态可以挂起到磁盘然后在稍后恢复。我们通过这个高级特性来绕过应用启动步骤：挂起一个完全启动和初始化的应用实例到磁盘。然后可以恢复它，在所需的服务器上启动应用程序实例。恢复时间与应用启动时间无关。这基本上取决于服务从磁盘上读取被挂起的虚拟机文件有多快。使用现在的磁盘技术恢复时间是相当短的，这大大降低了放置变更的成本。
RUBiS 是一个基于网络的拍卖系统,模拟 eBay 的功能。它是一个用于研究和基准测试网络应用系统的开源项目。
RUBiS 服务的主要特点包括:
- 它提供了一个功能完整的拍卖网站系统,包括浏览商品、下订单、评价商品等功能。
- 它被广泛用于研究和测试网络应用系统的性能、可扩展性、容错性等特性。
- RUBiS 系统由多个组件构成,包括 Web 服务器、数据库、缓存等,模拟了真实的网络应用架构。
- 研究人员可以针对 RUBiS 系统进行各种测试和分析,以评估不同的系统设计、算法和优化方法。
我们评估技术的效果使用RUBiS服务在戴尔的PowerEdge刀片服务器中的JBoss上，它的配置为 Intel 5620 CPU和1万RPM的SAS磁盘。对于这个想对简单的程序，启动时间接近100秒，与内存大小无关。当它可以响应用户请求时，我们认为应用程序完全启动了。用恢复先前创建的VM快照，我们可以显著的减少小虚拟机的启动时间。1G内存下的VM启动时间减少了百分之70。
为了支持绿色计算，我们设置空闲服务会进入待机模式，所以他们可以按需进行快速唤醒。我们使用刀片服务器自带的瓦特表测量了在各种TCP-W工作负载下的电力消耗。我们发现空闲的刀片服务器消耗130W，满载的服务器消耗205W，当服务待机模式下仅消耗大概20W。因此，让空闲的服务器进入待机模式可以节省大约85%的能源，激励了我们，在系统整体负载很低的情况下让空闲的服务休眠，特别是在晚上。当服务需求增加了，我们可以使用Wake-on-LAN（WOL互联网唤醒）技术轻松的从休眠模式恢复主机到运行状态。根据linux的文档，ACPI S1状态(备用)和备用转换时间为1-2秒ACPI S3状态3-5秒(suspend to ram)。这就足以快速满足需求的变化。
3问题定义
在这个章节，我们会总结自动缩放的问题转化为公式。
对于网络应用，存在多维度的资源需求，比如CPU，内存，网络带宽，磁盘带宽等。在它们之中我们选择了CPU和内存作为要考虑的典型代表。这是模仿谷歌AppEngine，它主要托管电商应用，并根据用户的CPU消耗进行计费。对于这些应用，内存是典型的决定多少应用能跑在同时运行的因素，当CPU是目标资源，我们需要在应用实例之间分配它。然而我们也可以把其他类型的瓶颈资源处理的很好（比如，将内存替换为磁盘空间,用于流媒体应用程序）。我们无法处理同时拥有大量瓶颈资源的程序（CPU，内存，磁盘，网络I/IO等）。显存的商业云计算产品包含谷歌AppEngine和亚马逊EC2自动缩放系统。这在实践中通常不是问题。装箱问题变化为向量装箱，似乎考虑了多为约束，但是不能用于这种情况，将会在第七章中解释。
我们要解决的自动缩放问题如下：我们有的服务器设为S，我们需要运行一组应用（表示为A），服务器的s（S包括了s）的CPU容量是Cs。根据内存因素，服务器 s同时运行的应用程序实例最大数量为Ms，应用a（A包括了a）的CPU需求ca。让P成为应用的放置矩阵。（Pa,s=1代表着应用a有运行实例在服务s，Pa,s=0也是同理）L代表应用负载分布矩阵（La,s是服务器s上为应用程序a分配的资源）。E是在决策间隔期间活动服务器的能量消耗。如之前所述，应用程序调度器的输入包含了当前应用放置放置矩阵P*，预测CPU需求（ca）和每个服务的CPU与内存资源容量（Cs和Ms）。输出包括了新应用放置在矩阵P和加载分布矩阵L。
我们的目标是最大化需求的满足率，最小化放置的修改频率和能源消耗。我们优化的最佳目标可以表示为：
带有约束
为了简化上述问题，我们假设服务器是同构的，有统一的容量（Cs和Ms）。自动缩放问题类似类约束装箱问题（CCBP），我们将每个应用程序标记为一个类，将所有对|A|类cpu需求视为要打包到|S|箱中的项目。唯一的区别就是CCBP问题没有包含最小化放置修改频率这个目标。因此，为了解决我们的问题，我们修改了CCBP模型，已提供最小化放置修改频率目标还提供了新增加半在线近似算法在下一章节中解决它。请注意上面的方程只是目标的一个正式表达和问题的约束，我们需要直接解决它。
4CCBP于资源自动缩放
在传统的装箱问题，一系列不同尺寸的物品需要装入最小数量的箱子。这个问题的约束版本将项目划分为类或颜色。每个箱子有v的容量可以容纳最多c个不同的类。这是类约束，因为打包到一个项目到一个箱子重的类多样性是收到限制的。目标是将这些项目打包的最少数量的箱子中。
我们可以建模资源分配为限制装箱问题，每个服务都是箱子每个类代表了一个应用。类约束反映了服务器可以同时运行的应用程序数量的实际限制。对于J2EE应用，举个例子，内存是典型的瓶颈资源。bin容量代表着服务器上所有应用程序的可用资源。我们假设服务器是同构的具有统一的容量。这个假设将在本章节后放宽。在实践中，服务的可用数量是有限的。我们的算法处理这些都用完了的情况。这个项的大小表示了相应的应用加载数量。通过使所有项目具有相同的单位大小，我们可以将项目大小表示为等于服务器容量的特定部分的负载单位。这被称为负载单元。这个箱子的容量V因此代表着服务器可以容纳多少个负载单元。等待从特定类打包的数量表示相应的资源需求量。应用的资源需求会随着时间发生变化。这被建模为资源的到达和离开：负载增加与新物品的到达相对应，负载减少与已存在物品的离开相对应。
图三展示了一个例子，当我们有俩个服务和三种应用，每个服务可以最多同时运行俩种应用（即c=2）。我们把负载设置为20%（即，一个单元代表的负载容量是服务容量的20%，）。因此每个服务器可以满足五个单元的负载（即v=5）。让应用的资源需求分别为60%，20%，120%。这意味着要为其相应的类打包3、1和6个项目。
NP-hard 是 "Non-deterministic Polynomial-time Hard" 的英文缩写。
NP-hard是计算复杂性理论中一个非常重要的概念。它指一类问题是属于NP-complete问题集中最"困难"的一些问题。具体来说:
- NP问题是可在多项式时间内验证其解的问题集。也就是说,给定一个解，我们可以在多项式时间内确认它是正确的。
- NP-complete问题是NP问题中最"困难"的一类问题。这意味着如果我们能在多项式时间内解决任意一个NP-complete问题,那么所有NP问题也都能在多项式时间内解决。
- NP-hard问题是更广泛的一类问题,它们至少和NP-complete问题一样"困难"。也就是说,如果我们能在多项式时间内解决任何一个NP-hard问题,那么所有NP-complete问题也都能在多项式时间内解决。
总之,NP-hard问题是计算机科学中一类公认的最"难"的问题之一。目前还没有人发现如何在多项式时间内解决这些问题,这也是计算机科学中一个非常活跃的研究领域。
CCBP问题是一个NP-hward问题（就像他传统的非约束类版本一样）。现在已经有非常多的近似算法了。这些算法假设输入的项目序列是提前已知的。这在我们的系统是不现实的，因为一样资源的需求是会不断变化的。此外，它们不会尽量减少以打包好的项目的混乱，这可能让花销变得明显因为一样放置改变。
对我们工作的一个重要观察是：不是所有的项目移动都是一样高代价的。回想一下我们系统需要做出俩个决策：应用放置和负载分发。在服务上创建一个新应用实例是昂贵的。在CCBP模型下，这对应于打包第一个项目到容器中。另一方面，调整负载分发是一个廉价的操作。他设计修改L7交换机使用新的分发策略。在CCBP模型下，这用对于调整箱子重现有项目的数量。基于这个观察，我们开发了半在线CCBP算法，他在不知道输入序列后续情况下打包当前项。
在线算法在处理开始时，并不需要知道所有的输入数据。数据是逐步到达的，算法必须随着数据的到达做出即时的决策。
离线算法在开始处理前，需要全部输入数据集。算法可以访问完整的数据集并进行任意次数的遍历。
我们的目标是最小化应用修改和调节现存的负载分发，接下来，我们将会描述算法的详情。
4.1 我们算法的详情
我们的算法属于颜色集算法族（论文Tight bounds for online classconstrained packing），但是为了适配我们的问题，我们显著修改了算法。与现有算法的详细比较将会被放到第七章，所以这样既可以建立足够的背景。我们将每个项目类型标记一个颜色，当他们到达输入序列时将它们组成为颜色集合。不同颜色在一个颜色集合中的数量最多为c（即箱子中不同的类最大数量）。这是为了确保颜色集合中的项目永远可以被打包的到相同的箱子中，而不违反类约束。包装仍然受制于箱子容量的限制。所有颜色包含了c种颜色，除了最后一个可能包含较少的颜色。
颜色集不同的项目单独进行包装。在每个颜色集合中使用贪心算法进行包装：项目被打包到当前的箱子中，直到达到容量为止。然后打开下一个箱子进行包装。因此每个颜色集最多有一个未填充（即非满的）的箱子。注意这个满的箱子可能包含了少于c种颜色。当来自新项目的颜色集到达时，它被装入未填充的箱子里。如果该颜色集的所有箱子满了，就打开一个新箱子来容纳该项目。
4.1.1应用程序负载增加
应用负载的增加被建模为响应颜色的项目到达。一种朴素的算法是，如果有未填充的箱子，就总是把项目打包到这个箱子中。如果这个未填充的箱子不包括当前颜色，就添加新的颜色到箱子中。这相对应会启动新的应用实例，这是一个昂贵的操作。相反，我们的算法试图在当前已满的箱子中腾出一些空间，方法是将它们的一些项目移动到未填充的箱子中。设c1为新项目的颜色，c2是未填充的箱子中的任何现有颜色。我们找到包含俩种颜色项目的箱子。设b是这样一个箱子。然后我们从b中移动颜色为c2的项目到未填充的箱子中。这为我们包装新物品的箱子b里的物品腾出了空间。
如果我们不能找到包含俩个颜色的箱子，我们是否可以使用第三种颜色c3作为中间角色来移动项目。更具体的说，我们找俩个箱子：
- 箱子b1包含颜色c1和c3
- 箱子b2包含颜色c2和c3
入股我们能找到这样俩个箱子，我们做如下处理
- 移动颜色c2的项目从b2箱子到未满的箱子
- 移动c3颜色的项目从b1箱子到b2箱子中
- 将项目装入b1箱子
这个过程如图4所示（回想一下，v是箱子的容量，c是类约束）。一般来说，我们可以有一个颜色链c1，c2，c3
- c1是新项目的颜色
- ck是未填充的箱子中已存在的颜色
- 每俩个相邻的颜色公用一个箱子（注意，颜色之间的“共享一个容器”关系是不可传递的。）
这个链的长度由颜色集中的颜色指定（即类约束）。只要这样的链条存在，我们可以沿着这条链移动现有的项目以容纳新的项目。注意这里的项目移动是基于假设的，只需要计算新的负载分发就可以。不是对一些应用进行物理的移动。也要记住这个链的长度是恒定有限的，不会随着系统或者应用服务器的增加而增加。如果颜色集没有空的箱子，就分配给他一个新的箱子。如果所有的箱子都用完了，负载的增加就不能满足了。
4.1.2应用负载减少
应用的负载减少被建模为已经装箱的应用的离开。注意这里的离开事件与特定颜色相关联，而不是特定的项目。算法可以自由的选择需要删除的颜色。
这里的挑战是维护每个颜色集，最多只有一个未填充箱子的特性。我们的离开算法工作如下。如果颜色集合没有任何一个未填充的箱子，我们可以删除一些这个颜色的项目，产生的箱子将成为未填充的箱子。否则，如果未填充的箱子包含了已经填充的颜色，则可以直接删除项目。除此所有其他情况下，我们需要删除现在已满的箱子中的条目，然后用移动其他项目到这里来弥补这个空缺。设c1是要离开的条目，c2是未填满箱子里的任何颜色。我们需要同时找到包含了这俩个颜色的条目。设b是这样一个箱子。我们从箱子中移除离开的物品，然后从未填充的箱子中移入颜色为c2的物品。通常来说，我们可以找到颜色链，修补离开的项目造成的空缺，通过沿着链移动现有的项目。这个过程类似于前面应用程序负载增加的情况。如图4的右边，这个过程为三种颜色的链。
如果我们找不到这样的链条，我们启动新应用实例来填补这个空缺：
- 从任何包含这些颜色的箱子中移除这些减少的颜色
- 查找未填充箱子重的颜色c2，添加这些颜色到离开的箱子中
- 将未填充箱子中，移动c2颜色的项目到离开的箱子中。
如果未装满的桶变成空的，我们可以从颜色集中删除他，因为那里全部的应用实例都没用收到负载。
应用程序负载的减少可能导致新的应用程序实例的启动，这似乎是违反直觉的。如果我们想要整合服务器以节省能源，这是不可避免的。
4.1.3应用的加入和离开
当最后一个特定颜色的物品离开时，这个颜色可以在颜色集中被移除。这意味着负载到0的时候结束最后的应用实例（另一种策略是保留最后一个实例，这确保了每个应用有最后一个实例运行在系统中）。当颜色从颜色集中删除，颜色集将会变空（即未满）。这里的挑战是保持系统中最多有一个未填充的颜色集。这是重要的因为每个颜色集都是独立包装的。
我们的基本思想是填充未满的集合（除了最后一个）使用最小化影响现有颜色工作的方式。我们首先检查是否有将新颜色添加到系统的待定请求。如果有，我们首先使用如下add_new_colors步骤分配新的颜色到未填充的集合
- add_new_colors步骤
- 根据他们的基数倒序排序未填充的颜色集合
- 根据他们在列表中的位置使用贪心算法添加新的颜色到这些集合中
- 如果在填满除最后一个未填充集合之外的所有集合之前用尽了新的颜色,请使用下面的consolidate_unfilled_sets过程来合并剩余的未填充集合,直到只剩下一个集合。
- 如果在填满系统中未填充的集合后还有新颜色剩余，我们使用额外的颜色集使用谈心算法划分剩下的新颜色
下面consolidate_unfilled_sets步骤将在系统中合并未满的集合直到只有一个残留为止
- consolidate_unfilled_sets步骤
- 倒排序未满的颜色集合根据他们的基数
- 使用列表中最后一个元素（颜色最少）去填充列表中第一个元素（颜色最多），通过如下的fill过程。从列表中删除完整集和空集。
- 重复这些步骤直到他们只有一个未填充的集合残留在列表中
fill(s1,s2)步骤如下使用集合s1中的元素填充集合s2
- fill(s1,s2)的步骤
- 升序排序s1中的颜色列表，根据他们的项目数量
- 添加第一个元素从列表中（少的哪个项目）到s2。在s1中使用项目离开操作，将该颜色的所有项目从s1移动到s2，然后从列表中删除该颜色。
- 重复上面的步骤直到s1变空了或者s2满了
4.2近似比分析
多项式时间算法A的质量是通过与其最有算法OPT的近似比R(A)来衡量的
当o是输入序列的列表，A(o)和OPT(o)分别是是A算法下使用箱子的数量和最优算法。因为这个问题是np-hard的，不存在多项式时间最优算法。因此这里的OPT其实是一个不切实际的上界。
- 为了分析算法的近似比，我们定义了以下的标记
- m：系统中总颜色数量
- li：第i种颜色的项目数
- c：类约束（多少种颜色）
- v：箱子的容量
让k=[m/c]，平均负载L
我们有
结果在“Tight bounds for online classconstrained packing”我们有
我们可以忽略我们[]分析中的操作，当OPT(o)趋近于无穷,则上式为
v和L的具体指取决于服务的容量如何离散化。因为俩个变量都表示为项目的倍数。我们可以用它的比值，t=L/v 以服务器的容量的倍数表示平均应用程序的负载。我们有
记住这个 1/v是一个负载单元如图5所示。近似比率如何随参数变化。
数字表明近似曲线主要由c和t的乘积决定。防御力所有应用在颜色集中的总负载。这表明了我们的算法使用了最小的服务数量满足了负载降低时全部应用的需要，在高负载时也能有很好的满意率。这将在实验的第五章得到支持。
4.3实际情况
在这个阶段，我们研究一些需要在事件中考虑的实施问题。
4.3.1服务等价类
我们的算法假设物理服务同构有相同的容量（虚拟机和明显是异构的就像亚马逊EC2）。这是文献中的典型装箱算法（这个版本的问题叫做VCCBP，允许箱子有不同的大小，然而，这样做的目的是最小化箱子的使用，这不符合我们的设置）。人们可能想知道这个假设在实践中有多现实。
数据中心的服务器通常是大批量采购的。每一批都包含大量的服务器具有完全相同的硬件。当然，大型数据中心的服务器并不完全相同。多代硬件可能会共存。我们可以服务器的硬件设置将其划分为“等价类”，并在每个等价类中运行我们的算法。我们的算法还假设物品有相同的尺寸。这在实践中并不是一个限制，因为项目大小被用作负载单位，以表示服务容量的一定百分比。只要服务器具有相同的容量，项目大小就相同。
4.3.2类限制
在云计算环境，在在每个机器上运行每个应用是不可能的，因为资源是受限的。如电商应用，物理内存是典型的瓶颈资源，他限制了多少个应用可以同时运行。这个限制在我们的算法中明确被建模为类约束，是可以被云服务商实施的。注意着不是我们算法强加的限制。我们只需要运行足够的应用让服务器忙起来，例如，让CPU的时钟周期饱和。如上所述，在一个颜色集中应用的负载很高时，我们的算法运行的很好。对于网络应用，这通常意味着，CPU相对于内存消耗需求很高。对于那些应用，一个相对保守的策略就可以让服务器饱和。稍后我们将在评估中看到，我们算法的需求满足率，对于类约束的特定的选择不敏感。
请注意我们并不需要应用或者封装它的VM有具有相同的内存。我们在Xen4.0中使用自膨胀技术调节虚拟机之间的内存分配。这个技术允许管理程序从内存中收集未使用的内存到共享池中，然后可以被需要的虚拟系统访问。他也允许管理程序保留一些特定内存量作为预留，
4.3.3负载改变
数据中心的应用负载是不断改变的。我们只需要定期或当负载改变到一定阈值执行我们的算法。我们算法每一步的动作是整理过的，当算法完成时执行。因此，快速拥挤需要应用程序添加大量服务器，所有程序是并行开始的。在我们稍后的模拟中会看到，我们的算法高效和可以扩展到上万个服务和应用。
在决策区间内的负荷变化量可能对应于连续几个项目的到达或离开。大的负载单元减少了我们的算法的开销，因为相同数量的负载变化可以用更少的项目表示。它还提高了算法在负载小震荡的可能性。另一方面，他可能导致服务资源的低效使用和降低应用程序需求的满意度。我们可补货的负载变化粒度，收到负载单元的限制。
4.3.4优化
在我们的算法中，每个颜色集有最多一个未填充的箱子。在未填充箱子重的颜色数量一些时候是最小于类约束的。当颜色集的数量很大，这些容器未填充总数是不可忽略的。我们可以提升需求满足率，我们使用未满的容量来满足未完全满足需求的应用程序，即使他们属于不同的颜色组。更具体的说，我们将有备用颜色槽的未填充箱按容量降序排序。我们也排序应用列表根据他们为满足的需求降序。然后我们使用贪婪算法将这些应用程序放入未填充的箱子中:当箱子已满或达到类约束的时候，我们移动到列表中的下一个元素。通过允许暂时违反颜色集的属性，我们可以增加需求满足率，当这些资源是紧张的时候。注意原始CCBP问题从来没有被违反。
5实验
我们评价了实验中我们的系统。我们的web应用程序使用实验环境是apache服务CPU密集型的PHP脚本。每个应用实例包裹在单独的虚拟机中。服务通过千兆以太网进行连接。客户端机器运行httperf请求apache服务器上的PHP脚本。这可以允许我们通过客户端请求率对应用程序施加不同程度的CPU负载。如果到达了容量的80%，我们视为服务已经满了。这在我们启动一些其他服务的应用，额外负载增加的时候留下了一些空间。为了节省实验的时间，我们配置了激进的应用调度时间，调用之间的间隔为俩分钟。这使我们能及时完成实验。在实践中，调度器运行频率要低得多。我们配置了算法每个服务器上最多运行4个应用，负载单位为1。
5.1负载变化
我们首先评估在负载修改是我们的算法有效性，避免应用放置发生修改。如图6所示，实验有三个服务器和三个应用
服务器是Intel E5420 CPU，8GB内存运行在Xen-3.3.1。我们保持如此小的实验规模是因为我们可以在所有服务中展示结果。在下一个章节中，我们将会展示一组30个服务的实验。使用不同的应用来区分图6中的应用。应用1和3运行在服务1上，应用2和3运行在服务上，应用2运行在服务上。服务是唯一一个有空闲容量的服务（即未填充箱子）。所有的应用都属于一个颜色集。我们首先逐步增加了应用1的负载。没有负载变化，应用程序的新实例在服务器3上启动。当有了负载变化，算法切换应用3的负载到应用2上，给应用1释放出了容量。由于服务2的占用也是满的，算法切换了负载从服务2到服务3，以便容纳从应用3到服务1的负载，因此服务3的负载增加了这是由于我们增加应用1的负载，尽管应用1没有运行在服务3上。换句话说，我们使用空闲箱子重备用的容量去吸收了已满的箱子重需求的增长。
在他达到稳定状态之后我们主键在减少了应用1的负载，进行反向操作。算法切换了服务2从应用3的负载到server1，以保持服务1是满的。他切换了应用2上的负载从服务3到服务2，以保持服务2是满的。作为结果，服务3的负载降低了以填补应用1留下的空白尽管应用1没有运行在服务3上。
注意在1450秒左右，服务器1上的负载大概下降了100秒，因此在这个期间系统看起来有俩个未填充的箱子。这是因为决策算法只是定期执行的。应用1负载的减少发生在算法岗执行完。调度器还不知道负载改变了，再一次俩分钟之后。在这个期间，L7交换机继续按照已有的分布转发请求。因此应用1上的负载会导致响应的服务1的负载减少。一旦调度器再次执行，他会切换负载填满这个空缺。
5.2自动缩放
我们评估我们算法的自动缩放能力使用9个应用和30个戴尔PowerEdge服务器， Intel E5620 CPU，24GB内存。服务运行在Xen-4.0和Linux2.6.18。结果如图7和图8所示。我们剧烈增加一个应用的负载，模仿快速拥挤事件，同时保持其他应用的负载稳定。如图7左边展示了快速拥挤应用的请求率和使用中所有应用使用的活动服务器的数量（即APM）。一开始，负载在系统中很低只有少数的服务有占用。当快速拥挤发生了，我们的算法发现发现请求速率飙升，然后果断扩展服务器资源。数据显示，在需求峰值时，他用光了30台服务器。然后我们缓慢的减少了请求率模拟快速拥挤结束了。算法按比例缩小了服务器资源以节省能源。
在上述的实验中，由于绿色计算，服务有百分之39的时间出于待机中，这大约可以转换为每台服务器节省了51瓦特的能源或者1530瓦特在一组30个服务的实验环境中。
图7中、右图为实验过程中快闪人群应用的回复率和错误率。图8展示了所有应用的响应时间。恢复表明了多少时间请求能被正确答复。这可以看出应用的吞吐量。作为比较的目标，我们使用了Amazon EC2中自动扩展的Scalr开源实现。Scalr基于EC2上观察到的负载动态调整VM实例的数量。他只考虑每个应用的数量没有类约束的概念。因此，这看起来是一种无类算法，他没有为服务器同时可以运行多少个应用设置固定值。当然，应用放置仍然需要考虑候选服务是否有足够的资源容纳应用。
图中我们可以看出，快速拥挤的开始，这两种算法都降低了吞吐量，增加了响应时间。俩者都有一定的请求返回错误。这是因为启动和预热新的VM实例需要时间。然而，这段时间我们的算法比Scalr算法要小得多：我们的算法正5分钟之内回到正常的Qos，及时在25分钟之后Scalr还是会对性能有很大的下降。Scalr对每个应用执行自动缩放，也没有负载切换（如图6所示）他是跨应用程序执行的。这策略导致了有一些应用服务已经有未填充容量，一些应用需求还是为满足。
6模拟
之前的章节已经证明了我们系统在真实环境下的有效性。这一章节品谷我们一样调度算法在大规模仿真下的性能。我们的模拟器使用与前一节中的实际实现相同的调度算法代码库。这确保了我们模拟结果的有效性。模拟的输入包括了每个服务的资源容量，每个应用的资源需求，和在每个决策之间的每个应用的总cpu需求。我们假设所有服务是同构的。我们将需求比例定义为所有应用的总需求和服务的总容量的占比。我们标志为D。举个例子D=0.9意味着，在所有应用需求满足的情况下，平均服务利用率来到了90%。然后根据类约束C和服务的内存容量（Cm），我们设置了应用实例最大内存需求Cm/c。总CPU需求分配给一组应用程序如下：根据满足率D和服务总CPU容量（CCPU）。我们可以得到全部应用的总CPU需求是D*CCPU。每个应用选择0-1的随机数作为其权重。然后,CPU需求会按照它们归一化的权重进行相应的分配。在每个决策期间，每个应用的需求随机变化20%。
如果最少有一个实例在运行，我们认为服务是活动的。我们叫做APM。否则，不活动的可能会为了节省能源而关闭。这个模拟反应了我们的调度算法按照先前给定的输入和计算执行指标如APM在系统的数量，决策时间，应用需求满足率，和位置变化的数量。每个数据点重复俩白次取平均值。
6.1应用满足率
第一组实验有一千个服务器和一千个应用。我们增加需求率（D）从0.05到0.99。结果在图9和图10展示。图9展示了APM数量数量随着需求的增加而增加，在最高点到达百分之百。
当需求较低时,由于类约束的存在,CPU需求的分配会略有下降,但这种影响很小。平均决策时间如图10中展示（左）
注意，决策时间是基于部署中使用的实际代码的实际执行。数据表明了决策时间随着需求率和类约束的增长而增长。这很大程度是是由于当应用需求改变，查找项目链需要搜索时间。就如4.1.1章中描述的。最长的决策时间小于0.8秒。在这种规模的系统下是非常快的。中间的数据展示了需求满足率保持在100%，当D=0.65会小幅下降。稍微有点出乎意料类约束对于需求满足率没有本质上的影响：当类约束从4增加到32（是原来的八倍）。满足率基本保持不变。这是由于第4.3.4节中的优化：用更高的负载满足更多应用的需求，即便类约束很小。这表明了我们的算法的性能对特定的类约束选择不敏感。右边的图表展示了应用程序启动和停止导致的总体放置变更次数。俩者都随着需求率的增加而增加，随着类约束的减小而减小：当每个服务同时运行更大的应用数量，这样就不需要频繁修改放置位置了。这在需求高的时候很重要。启动应用多余停止的应用，因为一些应用程序实例在整个模拟过程中一直在运行。注意我们不迁移虚拟机。
6.2可扩展性
我们评价算法的可扩展性根据增长的服务数量和与数量从1000到10000.如图11左边所示决策时间是如何随着系统大小而增加的，我们根据数字看到，我们的算法非常的快，即使是用python实现的：在系统大小到达1000时，决策时间仍小于4秒。中间的图展示了需求满足率，和系统大小无关（取决于D如前所示）。右图显示，位置变化的数量随系统大小线性增加。同样，当需求增加时类约束的影响更大。在服务器数量上取平均值时，对于任何给定的需求比率，每个服务器经历的放置更改数量大致是恒定的。
6.3应用数量
接下来我们改变应用和服务之间的比例，把应用数量从200增加到2000。服务器的固定数量为1000.结果如12所示。当应用程序多，类约束较大时，左边的数据展示了决策时间很长（但是保持在0.5秒以下）。中间的数据展示了应用数量对满足率对影响不大。右图展示了当需求很高，更多的应用导致了更多的放置修改。这是因为在给定的类约束下，越多的应用意味着每个应用更少的实例运行时间。同样, 更大的类别约束有助于减少放置变更的频率。当需求较低时，这俩个的负载小得多。
7相关工作
传统的装箱问题在文献中得到了广泛的研究（“On-line bin packing-a restricted survey”）。多维装箱问题在装入项目到最少数量的箱子中是考虑了多维度的约束。有人可能会认为我们可以将应用中程序CPU需求和内存需求视为向量中的单独元素，然后使用向量装箱来解决我们的问题。遗憾的是，应用的内存需求必须从整体上得到满足。内存大部分都被消耗掉了，无论怎么样即便应用只接受一点负载。对于java应用程序尤其如此，他的内存使用受之前负载的影响，这是由于使用了垃圾收集器。因此我们不能划分内存需求，并以零碎的方式在服务器上满足他。现有的装箱问题不能在我们的环境中应用。
类约束多背包问题（CCMK）目的是在限制条件下，最大化包装物品总数，每个背包都有容量限制，能容纳的每个类型的项目数量也是有限的。不像CCBP，这个目的不是最小化背包的使用。所以，不像我们的算法，只在系统负载很低的时候提供绿色计算。
一些CCBP的近似算法是成熟的。他们大部分是离线算法，不支持项目离开。其余的是严格的在线算法，不允许已经包装好的物品移动。当物品离开的情况下，但箱子里的其余物品不需要重新包装。当由于应用的离开颜色集变成未填充时，这些算法不保证该属性即系统中最多有一个未填充的颜色集。这会严重降低性能，因为每个颜色集都是独立的。研究表明，现有的颜色集算法在频繁有物品离开时表现不佳。它们不能应用在应用需求多变的运输计算环境。
23-26对web资源提供进行了研究
[23] B. Urgaonkar, P. Shenoy, and T. Roscoe, “Resource overbooking and application profiling in shared hosting platforms,” SIGOPS Oper.Syst. Rev., vol. 36, no. SI, pp. 239–254, 2002.
[24] M. Aron, P. Druschel, and W. Zwaenepoel, “Cluster reserves: A mechanism for resource management in cluster-based network servers,” SIGMETRICS Perform. Eval. Rev., vol. 28, no. 1, pp. 90–101, 2000.
[25] J. L. Wolf and P. S. Yu, “On balancing the load in a clustered web farm,” ACM Trans. Internet Technol., vol. 1, no. 2, pp. 231–261, 2001.
[26] C. Zhang, V. Lesser, and P. Shenoy, “A multi-agent learning approach to online distributed resource allocation,” in Proc. Int. Joint Conf. Artif. Intell. (IJCAI’09), 2009, pp. 361–366.
[27] S. Osman, D. Subhraveti, G. Su, and J. Nieh, “The design and implementation of zap: A system for migrating computing envir onments,” SIGOPS Oper. Syst. Rev., vol. 36, no. SI, pp. 361–376, 2002. [28] A. Karve, T. Kimbrel, G. Pacifici, M. Spreitzer, M. Steinder, M. Sviridenko, and A. Tantawi, “Dynamic placement for clustered web applications,” in Proc. Int. World Wide Web Conf. (WWW’06), May 2006, pp. 595–604.
[29] C. Tang, M. Steinder, M. Spreitzer, and G. Pacifici, “A scalable application placement controller for enterprise data centers,” in Proc. Int. World Wide Web Conf. (WWW’07), May 2007, pp. 331–340.
[30] C. Adam and R. Stadler, “Service middleware for self-managing large-scale systems,” IEEE Trans. Netw. Serv. Manage., vol. 4, no. 3, pp. 50–64, Dec. 2007.
[31] J. Famaey, W. D. Cock, T. Wauters, F. D. Turck, B. Dhoedt, and P. Demeester, “A latency-aware algorithm for dynamic service placement in large-scale overlays,” inProc. IFIP/IEEE Int. Conf. Symp. Integrat. Netw. Manage. (IM’09), 2009, pp. 414–421.
[32] E. Caron, L. Rodero-Merino, F. Desprez, and A. Muresan, “Autoscal ing, load balancing and monitoring in commercial and opensource clouds,” INRIA, Rapport de recherche RR-7857, Feb. 2012.
有些以整个服务器为粒度进行资源分配。这可能导致资源效率低下。一些不考虑服务器可以同时运行的应用程序数量限制。Bhuvan 等人。支持共享主机，但是要管理每个应用程序实例。它们不提供自动缩放属性。Mohit等人。将应用程序到服务类重，然后将这些服务类映射到服务器集群上。但是，当应用程序需求变化时，它们不会尝试最小化放置更改，并且主要用于离线使用。张等人将一组共享集群加入到网络中，研究共享集群的资源分配，这不是本文的重点。
过程迁移已经经过了各种研究（The design and implementation of zap: A system for migrating computing envir onments,）不像虚拟技术，他不捕获正在执行的环境。也不支持基于观察到的需求对应用程序的自动缩放。
应用在企业环境中的放置在【28】-【31】.它们在同一个服务集合上运行了多中应用不需要使用虚拟机或者沙箱环境。当应用是可信赖的，它们的方法是合适的。（比如企业应用）。当应用来自于不受信任的用户时，这个方案不适合云环境。与我们的不同,他们的决策算法并没有考虑绿色计算的因素,而是基于一组启发式方法,没有任何可证明的边界条件或最优性。我们的算法可以扩展到比[28],[29]中的服务器多一个数量级。因为我们算法的复杂性更低。
就像我们的系统，谷歌AppEngine服务提供了自动缩放Web应用。用户按照CPU的周期消费，而不是应用实例的数量。其内部使用的算法没有披露。我们的算法可以用于实现这样的服务。AppEngine中的应用必须运行在沙盒中，服务的行为受到严格的限制。在写这篇文章的时候。它主要支持java或python或者谷歌自己的GO编程语言。这导致难以转移遗留的程序到他们的平台上。作为对比，移植已有的应用程序到虚拟机平台中就简单多了。它提供给了用户更好的选择弹性，它们最喜欢的程序语言操作系统，库，等等。
也有一些云厂商为云用户提供自动扩展解决方案（见调查【32】）。用户允许定义一组规则来控制缩放行为。然而它们使用的规则和负载均衡策略非常简单。就像亚马逊的EC2中的Scalr。它们只在满足某些条件时执行伸缩操作，并在所有实例之间均匀地平衡负载。由于它们不考虑系统的状态，它们不能实现最佳决策。
8结论和未来工作
我们展示了系统的设计和实现，他可以基于需求自动的等比缩放提升和降低应用实例的数量。我们开发了颜色集算法去减少应用放置和加载分布。我们的系统实现了应用需求高满足率，即使遇是负载非常高。他通过在低负载时减少运行实例数量的方式节省能源。未来的工作有几个方向。一些云服务提供商可能提供了多级服务给它们的客户。当资源变得紧张时，他们可能希望给予他们的优质客户比其他客户更高的需求满意度。在未来，我们计划扩展我们的系统义支持差异化服务，而且在跨应用程序分配资源时也要考虑公平性。我们提到过在论文中，我们可以在数据中心中划分多个世代的硬件作为等价类，在每个类中运行我们的算法。我们未来的工作是开发一种高效的算法,将传入的请求分配到一组等价类中。自适应地平衡这些服务器集群之间的负载。如本文分析，当颜色集中的应用负载总数很高时，CCBP算法工作的很好。未来工作的另一个方向是扩展算法，将具有互补瓶颈资源的应用程序打包在一起。例如，将CPU密集型应用程序与内存密集型应用程序放在一起，以便充分利用不同维度的服务器资源。