转让海淀3万执照:基于元区间的云计算基础设施服务的资源分配算法研究

2010，46（34）
1 绪论
日益膨胀的能耗、人员费用、硬件成本、数据中心空间的
匮乏以及用户对简化网络配置和管理的迫切愿望，推动了云
计算的发展[1]。云计算基础设施服务是物理资源、数据与网络
的融合，而云应用则是那些经过扩展能够通过互联网访问的
各种应用。基础设施服务是云计算的基石，它可以被动态地
提供、配置、再配置和解除，以满足云应用对基础设施资源的
需求。所以，如何根据用户的资源需求来分配云计算基础设
施服务是云计算研究的关键问题之一[2]。
目前，云计算系统比较多，基础设施服务的管理方法也各
有千秋。亚马逊弹性计算云[3]由用户创建一个亚马逊机器图
像（AMI），它包含操作系统，应用程序和配置设置，然后由亚
马逊弹性云按照先来先服务方式分配用户所需的虚拟机。开
放云计算平台EUCALYPTUS[4]由三层体系结构组成，顶层是
云控制节点，它的主要任务是协调云，中间层是集群控制器，
其主要职责是跟踪集群节点上资源的使用情况，第三层是节
点控制器，它负责资源监视和管理虚拟资源，它采用集群技术
管理资源。IBM的蓝云云计算[5]包括硬件、软件和服务三个方
面。IBM云资源管理的核心是资源的预留和调度。它能够预
测到当前或者将来可提供给用户的计算力。基于这个原因，
每个使用资源者都有一个严格的开始日期和结束日期，根据
这个日期，管理者就可以很好地预留和调度其拥有的资源。
Google 使用的云计算基础架构模式包括4 个相互独立又紧密
结合在一起的系统[6]。包括Google 建立在集群之上的文件系
统Google File System，针对Google 应用程序的特点提出的
Map/Reduce 编程模式，分布式的锁机制Chubby 以及Google
开发的大规模分布式数据库BigTable。其主要依靠集群技术
来调度作业、管理共享资源、处理节点的失效以及监视机器的
状态。微软的Azure（http：//www.microsoft.com/windowsazure/）
是一款云操作系统，它内部包括了操作系统、基础设施服务以
及应用等各种组成部分，并且每部分能够被单独管理，这使得
用户能够快速升级其应用或者重新启动计算资源。Azure 将
所有的可运行物理节点组成一个Fabric，由Fabric controller
对所有的资源进行控制、调度和分配。Azure 采用贪婪算法进
基于元区间的云计算基础设施服务的资源分配算法研究
汤小春，刘健
TANG Xiao-chun，LIU Jian
西北工业大学计算机学院，西安710129
摘要：针对云计算中基础设施服务资源分配问题，提出了一种最佳分配决策算法。该算法通过估计待选元区间的资源配额参
数，选择一个最小的满足用户应用要求的元区间，提高了基础设施服务资源的利用率。首先给出了基于元区间的基础设施服务
模型，其次给出了云用户应用以及元区间资源之间的适应模型，最后提出了元区间决策算法并对该算法进行了系统地评价，该算
法取得良好的效果。
关键词：云计算；元区间控制器；基础服务
DOI：10.3778/j.issn.1002-8331.2010.34.070 文章编号：1002-8331（2010）34-0237-05 文献标识码：Ａ 中图分类号：TP311
作者简介：汤小春（1969-），男，副教授，博士，主要从事软件开发环境、分布/并行处理技术的研究；刘健（1987-），男，硕士研究生，专业方向为软件
工程与网络软件。
收稿日期：2010-07-21 修回日期：2010-10-13
Computer Engineering and Applications 计算机工程与应用237
Computer Engineering and 2010，46（34） Applications计算机工程与应用
节点控制器物理机器节点控制器物理机器
高速网络
元节点控制器
图1 元区间基础设施服务模型
行资源的分配，Fabric controller 中定时收集资源的使用情况
并保存。由于其采用的是贪婪算法，因此一旦分配决策产生，
就无法在后来的时间进行变更。这些系统在为虚拟机找到宿
主时，基本采用先来先服务，没有对用户的资源请求以及可用
的物理资源进行评估，因此存在资源利用不充分的现象。
首先对物理资源划分不同的元区间，再通过对用户的资
源需求情况以及物理机器资源的综合评估，采用资源标杆的
思想，在物理机器上合理地分配虚拟机，满足用户的基础设施
资源需求，同时尽量减少物理机器的使用数量。
2 基于元区间的基础设施服务模型
基于元区间的基础设施是一个简单、灵活以及模块化的
结构，采用层次化的方式，可以很好地反映可用资源环境。本
质上来说，系统允许用户开始、控制、访问以及结束全部的虚
拟机器。当用户先定制所需要的CPU、内存、存储、中间件和
成员组等后，就通过一个Web 接口提交这个请求。云计算基
础设施服务接收到这样的请求后，首先对请求进行审核，审核
一旦通过，就通过基础设施服务管理器去分配服务，即为虚拟
机找到宿主。服务一旦建立，就通知云用户来使用服务。设
计基础设施服务架构的目标在于提供弹性、高可用性等。
对于云计算基础设施资源的分配，采用一种邮局运输包
装箱的思想，即，邮局制作标准的包装箱，然后用户根据需要
购买包装箱来装邮寄物，最后由邮局的运输车运送邮寄物。
对于云计算物理节点，按照不同资源的大小和类型，将这样的
资源分解成许多虚拟机，在虚拟机上通过集群系统、分布式文
件系统、网格计算等技术，实现多个存储设备之间的协同工
作，使多个存储设备可以对外提供同一种服务，并提供更好的
数据访问性能。当用户向云计算平台提出基础设施服务请求
时，由系统进行统一的算法评估后，分配一个或者多个虚拟节
点给用户，用户就可以在这样的虚拟节点上运行自己的应用
程序，完成必要的任务。其模型如图1 所示。
图1 中，VM代表一个虚拟机器，一个物理计算机上可以
运行多个虚拟机器，但是所有虚拟机器的资源总和不能超过
一个单独的物理机器。
定义1 节点：它是一个可以独立运行的物理资源体，它具
有指定的资源的配额，如CPU、内存、磁盘空间以及控制系
统等。
定义2 元区间：它是云计算基础设施服务分配的最小单
位，是无法分割的整体。元区间有两种表现形式，一种是一个
物理节点，另一种是物理资源的一部分，即，将物理资源按照
一定的要求分割出来的一个个虚拟机器，元区间必须寄生在
某个宿主上。
定义3 元区间申请单：租赁云计算资源的申请者为了得
到资源，用来描述其资源需求情况的一个列表。
定义4 元区间清单：用来描述其可用资源配额情况的一
个列表。
定义5 元区间管理器：是一个保证正常运行和公平分配
的中间机构，它根据元区间申请单和元区间清单，按照一定的
算法，将一定的元区间公平合理地分配给资源租赁申请者。
定义6 节点控制器：节点控制器运行在每个物理节点上，
其任务是安排元区间实例的运行。节点控制器一旦发现自身
资源发生变化，就立即通知节点控制器。
元区间管理器是系统的核心，向上提供给云用户接口，进
行认证和协议的转换，向下与数据存储服务连接，支持持久稳
固的用户和系统数据，元区间管理器的主要任务是基础设施
在服务的分配和调度等，它是整个基础设施管理的关键。
3 云计算基础设施服务调度模型
为了更好地实现按需分配的云计算基础设施服务资源，
在多个自治、异构的工作站或服务器上，建立资源配额不同的
元区间，即虚拟机器。这些元区间可以像一个机器节点一样
工作。从这些元区间中选择一个节点，叫做元区间管理器，它
可以对其他所有元区间进行控制和收集各个元区间的负载信
息，并对这些元区间进行管理和监控。
元区间控制器根据申请单和元区间清单的限制条件，找
到一个双方都满意的结果。这时，元区间控制器的任务完成，
交易双方进行单独的联系，这有两种结果，一个是交易结果的
否定；一个是双方达成协议，进行服务活动。
整个元区间分配模型可以分解成5 个过程：
（1）元区间清单生成。它是提供基础设施服务的元区间
通过用一种定义语言来描述它们所拥有的元区间资源配额信息。
（2）申请单。需要租赁元区间的用户根据云应用程序的
资源需求，描述资源的类型以及资源大小的信息。
（3）元区间分配。它规定元区间管理器按照一种公平合
理的方式，同时考虑双方资源内容进行匹配的过程。
（4）分配回复。它定义了如何通知云用户以及元区间的
过程以及通知哪些内容给双方。
（5）分配确认。它定义了匹配成功后的云用户以及元区
间如何履行自己的义务的过程。
假设云用户请求租赁基础设施服务，那么它就向云计算
基础设施服务申请租赁元区间资源；此时如果存在有合适的
元区间，元区间服务器就将该节点分配给云用户，并在物理机
元区间
清单（2） （1）申请单
元区间云应用程序
分配通知（4）
确认（5）
元区间
管理器
图2 元区间基础设施服务调度模型
238
2010，46（34）
器上启动元区间，云用户就可以配置自己的应用程序，使用该
元区间完成任务。其主要步骤如下：
如图2 中的第（1）步，需要租赁云计算基础设施服务的请
求者按照自己的要求建立描述自己属性和限制条件的数据结
构，也就是说各自填写自己的申请单，然后将申请单递交到元
区间管理器。这个申请单必须按照元区间管理器指定的协议
来填写。例如，最小需要的内存和磁盘空间大小，最大需要的
内存以及磁盘空间大小，操作系统类型等。
在元区间管理器中，保存着各个元区间的信息，如OS 类
型，CPU数量，内存大小，网络类型，I/O控制器类型以及磁盘
大小。元区间管理器定时收集来自元区间的负载信息，如图2
所示的第（2）步。云计算基础设施服务分配过程一般要求资
源一方是申请单，另一个必须是可用的元区间，同时双方资源
配额限制条件的最终结果必须都是真值时，才可以认为该元
区间可以分配给云用户，即达成初步的意向。如租赁申请的
内存必须小于元区间的最小内存；租赁请求者申请的执行节
点的OS 必须与元区间的OS 相同，等等。
下面，给出一个基础设施服务租赁申请单的例子。
元区间清单包括：MID（元区间标识）；Mname（元区间名
称）；PMID（元区间所属物理机标识）；OType（操作系统类型）；
Qstat（配额状态）；Daytime（以凌晨为基准现在时刻）；Mem（可
用内存大小）；Qdel（分配标志）；CPU（CPU数量）；cmdenv（执
行环境参数）；Ifile（Image 文件名）；DType（元区间磁盘格式）；
DSize（磁盘大小）；NType（网络参数）；Constraint（分配限制条
件表达式）。
当云用户提交申请后，元区间管理器就开始分配元区间，
如图2 中（3）。设元区间为mnode，云用户任务为Capp，其
Constraint 如下：
Mnode.Qdel 为未分配；
（Mnode.OType||Capp.OType）&&（Mnode.DType||Capp.DType）为真；
Mnode.CPU ³ Capp.CPU；
Mnode.cmdenv==Capp.cmdenv；
当Constraint 为真后，再要求满足磁盘空间要求Mnode.
DSize ³ Capp.DSiza 以及内存空间要求Mnode.Mem ³ Capp.
Mem。全部满足后，元区间管理器就使用分配协议来通知云
用户与元区间，如图2 中的第（4）步。分配协议产生一个对话
的标示号，主要用于进行双方的进一步的认证和安全考虑。
然后云用户就按照元区间管理器给出的标示号直接与元区间
进行联系，如图中的第（5）步。云用户与元区间进行进一步的
联系是非常必要的，分配时的状态与最新的状态有可能出现
偏差。
4 云计算基础设施服务调度算法
基础设施服务调度算法的基本思想来源于布局问题中的
最优匹配算法。假设有N 个用户的请求达到，有Q个物理节
点可以被使用，其调度结果是找到最小的物理节点来运行云
用户的基础设施服务。
设n 为用户的应用程序对资源的需求集合，N={ < d1m1 >,
< d2m2 > ，…，< dnmn > } ，q 是可以提供的物理机器的集合，
Q={ < d1m1 > ，< d2m2 > ，…，< dqmq > } 。设ri 为用户请求
中的磁盘大小与内存大小的比率，sj 为可用的物理节点的磁
盘大小与内存大小的比率。rN = å
i Î N
di / å
i Î N
mi 代表n 个请求的
磁盘大小与内存大小和的比率。sQ = å
i Î Q
di / å
i Î Q
mi 代表q 个物
理节点的磁盘大小与内存大小和的比率。如果rN 大于sQ ，
即相对于物理节点而言，要求的磁盘空间大，则依据内存大小
为标杆；反之则要求的内存空间大，依据磁盘大小为标杆；相
等时，任意选择一种标杆。
对于每个物理节点，指定一个ε ，¶j = (|1 - ådi /dj| £ ε) Ù
(|1 - åmi /mj| £ ε) ，¶j 表示分配到物理节点上的请求的总磁盘
或者内存大小与物理节点的磁盘或者内存大小之比在一个差
异水平内。差异水平用来保证每个元区间的资源分配偏差。
元区间分配算法：
输入：当前物理机器资源状态以及所有要求分配资源的
云应用程序。
输出：应用程序到元区间的映射。
方法：
步骤1 初始化用户请求队列Qapp；
步骤2 初始化元区间队列Qmnode；
步骤3 计算rN 以及sQ ；
步骤4 如果rN > sQ ，按照ri 由大到小的原则排列用户的请求；按
照sj 由大到小的原则排列可用物理节点；如果rN £ sQ ，按照ri 由小到
大原则排列用户的请求；按照sj 由小到大原则排列可用物理节点；
步骤5 初始化i=1，j=1；
步骤6 do {
取一个物理机器j；
Do{
取一个请求i；
Call flag=meta_alloc（Qapp，Qmnode）；
If（flag==true）{
通知云用户以及元区间分配消息；
}
i ++；
}while（¶j 为真）；
j ++；
}while（Qapp!=NULL||Qmnode！=NULL）
步骤7 如果Qapp 不为空，且有元区间被释放，则继续进行分配；
步骤8 退出。
Meta_alloc：
if（Qmnode[k].Constraint==TRUE）{
if（（mnode[i].Dsize £ app[j].Dsize）
&&（mnode[i].mem>app[j].mem））{
mnode[i].mem-=app[j].mem；
mnode[i].Dsize=-app[j].Dsize；
return true；
}
}
return false
元区间管理器要求云用户发送应用所需要的资源配额上
下文，这时，元区间管理器的调度进程就从未分配的所有元区
间中取出一个满足最低要求的元区间，如果目前没有元区间
能够满足云用户的应用要求，则发出NO_alloc 给元区间管理
器，等待下次再分配。
元区间管理器将在所有的列表队列中找到一个最合适于
汤小春，刘健：基于元区间的云计算基础设施服务的资源分配算法研究239
Computer Engineering and 2010，46（34） Applications计算机工程与应用
当前应用程序的元区间。找到的元区间必须满足下列条件：
可用磁盘空间满足用户要求，可用内存大小满足用户要求，用
户应用程序必需的执行环境在元区间上已经存在等等。如果
一个用户应用本次没有分配成功，那么它下一次可以继续被
分配。
如果元区间管理器为当前用户的应用找到一个特别合适
的元区间，它就会向云用户发送这个元区间的名称，否则就会
发送一个拒绝命令。此时云用户的应用在队列中的优先级别
就会被提高，在进行下一轮的分配过程中，优先级别处于最高
的云用户应用就会被分配，这样直到分配全部完成。然后再
等待下一个时间段的分配过程的到来。
5 算法评价
5.1 系统效率
设O(n) 为一个具有n 个元区间的云计算系统完成单位任
务的时间，T(n) 是单位任务花费的时间。一般来说，如果单位
时间内n 个元区间完成一个以上的任务，则T(n) < O(n) ，其中
n ³ 2 。假设单处理机系统中T（1）=O（1）。加速比因子可以定
义为：
S(n) = T(1)/T(n)
n 个元区间的效率可以定义为：
E(n) = S(n)/n = T(1)/(nT(n))
效率是实际达到的加速比性能与其最大值之比。效率高
时，说明全部元区间都被使用。
给出了由10 000 个并行计算组成的单位任务，每个计算
是一个矩阵与矩阵相乘的算法。每个物理机器由4 核CPU组
成，内存是4 GB，磁盘大小为500 GB，使用KVM，安装Open
SUSE 11.0。元区间的image 文件提前做成，元区间启动后，
使用机群作业管理系统（http：//www.nec.co.jp/middle/Web-
SAM/）提交作业，作业的执行数据如表1 所示。
当效率为1 时，说明效率最好。从表1 的数据看，每个物
理机器分割为8 个虚拟机器时，效率最高。但是，当分割的元
区间太多的时候，反而影响到效率，所以元区间的分割要满足
一定的物理资源条件。
5.2 性能分析
5.2.1 算法性能
还可给出可用资源列空闲比B，即所有物理节点可用资
源之和与总资源之比值，来检查资源分配后，可用资源的利用
率。空闲比越低，说明利用率越好。表2 是测试用的一组虚
拟机资源需求情况。表格中的各个数据代表需要的虚拟机的
数量。分别采用先来先分配、内存大优先、磁盘大优先以及本
文中的元区间算法，分别得到磁盘的空闲比率以及内存的空
闲比率，选用150 台不同的物理机器（每台物理机的内存1~
8 GB之间，磁盘大小400~1 500 GB之间），其结果如表3 所示。
从几种不同的云计算基础设施资源分配方法的资源空闲
比可以看出，在使用不同的资源分配方法时，先来先服务不管
是内存空闲比或者磁盘空闲比，都比较差；内存大优先方法
中，内存分配的比较好，但是磁盘利用率较差；磁盘大优先方
法与内存大优先刚好相反；元区间资源分配算法居于磁盘大
优先方法与内存大优先之间，包含两者的优点，效果最好，因
此，它可以提高物理机器的整体资源利用效率。
5.2.2 系统效用评价
对系统的效用值Ug 进行评价，得到系统总的资源利用情
况。效用值Ug 表示为：
Ug =å
i = 1
m
(αi*ui - ε* cos t(Vi))
其中：αi 的取值范围为[0，1]，并且å
i = 1
m
αi = 1 ；ε 是一个系数；ui
表示第i 个虚拟机的效用值，当在规定的时间内，用户的请求
得到响应ui =1；否则，ui =0；Vi 表示第i 个虚拟机，cos t(Vi) =
Cd /C t 表示第i 个虚拟机上需要的资源与全部的资源的比率。
两个用户同时发送请求，由调度算法分配云计算基础服务所
需要的资源，硬件资源同上，评价请求数量变化带来的资源利
用率的变化，测试结果如图3 所示。
当ε 为0.06，请求1 的α 为0.8，请求2 的α 为0.2 时，在t0
和t1 时间段，请求1 以及请求2 的负载都比较低，内存需求量
小，所以，效用值接近1。在t2 和t3 时间段，随着负载的变大，
内存需求量增加，CPU需求也增加，但是，负载不是太高，所以
请求的响应时间在规定时间内，效用值为1。在t4 和t5 时间
段，负载急剧增大，内存需求量增加，CPU需求也增加，由于请
求1 的α 为0.8，所以请求1 得到保证，请求2 的响应时间快速
上升，效用值低于1。在t6、t7 和t8 时间段，请求1 和请求2 的
负载相反，请求2 得到的资源超过请求1，但是总体负载不高，
效用值为1。总之，在物理资源不过载的情况下，元区间分配
算法能够得到理想的效用值。
5.2.3 虚拟机群的任务调度性能评价
效率分析仅仅考虑元区间启动后，任务在元区间执行的
物理节点数
64
物理机运
表1 基于元区间的云计算环境任务运行效率
内存大小/Mb
磁盘大小/Gb
40
10表2 不同虚拟机资源需求
1 组
表3 不同分配法资源空闲比
240
2010，46（34）
时间，如果将元区间组成集群系统，其性能的分析结果如图4
所示。
采用以下的环境进行测试，将一个有许多并行任务组成
的并行工作流提交到一个云计算模拟环境，元区间的建立和
拆除时间不进行考虑，使用作业管理系统进行任务的分配和
调度。
图4 中的横坐标代表不同规模的任务量，纵坐标代表时
间，不同的曲线分别代表作业执行时间、元区间分配花费的时
间、作业向元区间调度时间以及使用单个物理机器执行作业
花费的时间。在图中，单个物理机是作业执行时间的一个准
线，它不存在一些额外的开销。可以看出，作业数量越多，使
用元区间分配算法会导致作业执行时间大大的减少，但是，其
他的额外开销比较大。
6 结论
采用元区间分配算法后，可以向云用户提供适当的云计
算基础设施服务，提高了资源的利用效率，达到弹性、高可用
性等目标。但是，对于异构、性能差异较大的环境，分配算法
还需要进