基于拍卖的数据中心资源匹配算法

王 旭，倪 宏，韩 锐

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190； 2.中国科学院大学,北京 100049)

0 引 言

近年来，云计算技术蓬勃发展，其应用也越来越受到重视[1-3]。用户可以通过租用数据中心资源的方式灵活构建自己的应用，而不必像传统方式那样采购主机、自行维护。所有的主机维护均由数据中心代为完成。当需求发生变化时，用户也能快速改变虚拟机资源以适应这种变化。在云计算系统中，数据中心利用大量商用服务器来为用户提供虚拟计算服务，通过为终端用户分配虚拟机，使得用户能够访问数据中心的资源，并且能够轻松更新系统配置。

用户可在虚拟机创建过程中定制需求，包括一系列功能性需求，如操作系统版本、预装应用软件等；一系列非功能性需求，如CPU虚拟内核数量、CPU主频、内存数量、内存读写速率、存储空间大小、存储介质、网络性能等，同时也包括对特殊处理单元的需求，如对支持CUDA(Compute Unified Device Architecture)显卡的需求。然而，用户需求往往各不相同，进而造成了用户需求的异构性。此外，由于硬件性能的提高和价格的下降，系统资源的异构性体现在，当进行系统扩充时，人们往往会购买或开发新型的计算机系统，而不是采用系统中已有的设备类型，保持系统的同构性；而且，把不同硬件和软件系统结合往往可以得到较高的性价比。因此，在一般情况下，用户需求和系统资源均是异构的[4]。

进一步地，虚拟机的资源利用率及主机的总体资源利用率均随时间变化[5]。通过提高主机资源利用率，减少空闲主机数量，数据中心能够在一定程度上减少电力消耗，进而降低运行成本[6]。通常情况下，虚拟机对各项资源的需求并不相同，因此导致了主机资源消耗不平衡，最终导致了较差的主机资源利用率[7]，同时造成了能量的浪费[8]。举例来说，诸如图像纹理采集之类的任务会大量使用CPU资源，然而对内存需求不高。某一主机中存在过多这类任务时，主机CPU满载时，内存尚未被充分利用，主机资源无法被充分利用。进一步地，某些主机因其底层硬件架构关系尤其适合执行某些特定任务的虚拟机[9]。数据中心固有的异构性和其所负载的动态性也常被忽视[10]。因此，云计算数据中心使用虚拟机在线迁移操作完成动态负载管理[11-12]。通过虚拟机在线迁移技术，虚拟机能够从一个主机迁移到另一个主机，并且在此过程中尽量少地影响虚拟机中执行的任务[13]。

拍卖是买卖没有标准价值的商品或服务的过程。连续双向拍卖(Continuous Double Auction，CDA)[14]是一种市场化的资源管理方式，并且在近年来应用的比较普遍[15-17]。事实证明，市场化手段针对云环境下的资源分配问题效果较为显著。通过拍卖方式为资源分配问题引入供求机制，利用市场化方法就可以解决数据中心内部的资源配置和管理问题。

本文提出基于市场化双向拍卖的云数据中心资源管理架构。它是一种基于CDA的算法，旨在运用市场理论解决数据中心内部资源的分配和管理问题。然而，与原始CDA算法不同，本文所述场景涉及多种资源类别。在拍卖中，每种资源类别的需求均需要被满足。同时，本文在拍卖成交策略中引入资源匹配度，以此匹配资源相似度高的主机与虚拟机。

1 虚拟机迁移流程

虚拟机迁移过程中，源主机对虚拟机资源进行打包，发送至目标主机。目标主机获得虚拟机后立即恢复虚拟机执行。一般而言，为保证虚拟机迁移的有效性，即能够获得资源平衡或主机资源利用率的提高，源主机、目标主机、虚拟机的选择都十分重要。对应地，本文引入主机选择算法、虚拟机选择算法、虚拟机拍卖算法。算法流程如图1所示。

图1 主机算法流程

主机选择算法针对源主机和目标主机，利用启发式算法选择所有应迁出虚拟机的过载主机作为备选源主机，选择所有资源过剩主机作为备选目标主机。双方备选主机将参与后续虚拟机拍卖，但并非所有备选主机均能在拍卖中成功迁出或迁入虚拟机。

虚拟机选择算法针对源主机，按照启发式规则选择源主机中的某一虚拟机作为备选虚拟机。备选虚拟机作为待迁出对象，在后续拍卖过程中作为标的物。备选虚拟机的自身属性将决定其在拍卖过程中的价值。

虚拟机拍卖算法通过连续双向拍卖，将备选源主机与备选目标主机引入市场竞争之中，通过市场化方法确定买卖关系。拍卖算法主要需要确定买卖双方的定价策略及中间人的交易策略。

2 主机启发式算法

2.1 主机选择算法

主机选择启发式用于选择需迁移部分虚拟机到其他主机的过载主机及可用于接收虚拟机迁入的欠载主机。过载主机在后续拍卖过程中将作为卖方出现，欠载主机在后续拍卖过程中将作为买方出现。

虚拟机的迁移过程对当前主机和目标主机的资源状况均会产生影响。基于权衡考虑，本文仅考虑CPU与RAM的资源状况。

对于CPU而言，当使用率升高时，系统处理效率下降，能耗上升。本文采用了基于滑动窗口的管理策略。令滑动窗口长度为T，在某时刻t时窗口平均CPU利用率为：

(1)

(2)

(3)

2.2 虚拟机选择算法

虚拟机选择启发式算法用于选择要进行迁移的虚拟机。由于主机异构性，同一虚拟机在不同主机运行对主机资源的影响也并不相同。为了能够有效预测虚拟机对不同主机的资源及性能影响，尤其是计算能力的占用情况，需要了解各个主机的真实性能。因此，需要在各主机上运行综合基准程序，以了解各主机CPU处理能力。Whetstone和Dhrystone均为经过精心设计的经典综合基准程序，它们通过在统计意义上模拟常用程序的使用来测试CPU性能[18]。一般而言，获得较高基准程序得分的处理器能够在一定时间内处理更多指令，即性能更佳。

假定虚拟机目前在主机Hi上运行，并将要迁移至主机Hj。在迁移完成后，虚拟机Vj对主机Hi的CPU利用率影响为：

(4)

相似地，可以计算在迁移完成后，虚拟机Vj对主机Hi的RAM利用率的影响为：

(5)

当主机过载并准备迁出虚拟机时，虚拟机选择启发式用于选择要进行迁移的虚拟机。一旦超载，主机会选择一个或多个虚拟机来进行迁移。为了尽量快速地降低负载，资源消耗最大的虚拟机会被优先选择。

设虚拟机的总体资源利用率为主机CPU利用率与RAM利用率的加权平均值,可以表示如式(6)：

(6)

其中，λCPU和λRAM分别为CPU和RAM负载的权重因子，且满足：

λCPU+λRAM=1， λCPU,λRAM∈0,1

(7)

为了反映CPU和RAM的负载，现定义λCPU和λRAM进一步表达如式(8)：

(8)

可得到：

(9)

该权重因子设定方法会使得uij更加关注利用率较高的资源。综上，具有越高uij值的虚拟机被迁移的优先级越高。

3 虚拟机分配中的拍卖过程

3.1 拍卖理论

本文将主机分为3类：买方(主机欠载，准备接受虚拟机迁移请求)、卖方(主机过载，准备迁出虚拟机)以及旁观者(既未欠载也未过载，不参与虚拟机迁移)。本文只针对买方和卖方进行讨论。在拍卖进行过程中，拍卖中间人负责收集卖方价格和买方价格信息，并按照拍卖规则进行交易匹配。文中将虚拟机作为拍卖标的物，将资源作为货币。至此，虚拟机分配与管理问题便可转化为云计算虚拟市场中的买卖问题。该市场中，过载主机作为卖方出售虚拟机，欠载主机作为买方利用其空闲资源购入虚拟机。

拍卖中，当存在潜在买方和潜在卖方时，交易便有可能达成。在连续双向买卖中，单次拍卖存在交易时间限制。在时限内，买卖双方可以连续出价，并根据既定价格策略调整价格。在本文场景中，买卖双方实际上是在买卖虚拟机。通过引入多种资源类型，使得拍卖中交易双方需要考虑的因素增多。在达成交易时，买方在每种资源上的买方价格均要符合卖方对应资源的卖方价格。通过引入这种市场化手段，确保了虚拟机在正确的主机中运行。

3.2 定价策略

在决定最终定价时，需要考虑多种策略来解决在拍卖过程中的不同问题。单次拍卖的剩余时间、系统资源余量均为常用的定价策略。本文使用剩余时间和系统剩余资源来决定买方价格，使用剩余时间和虚拟机占用资源来决定卖方价格。

3.2.1 基于时间的策略

在给定的议价期限τ内，假设在某一时刻t，议价的剩余时间为δ(t)，且满足δ(t)∈[0,τ]。

给定资源k的最低和最高卖方价格分别是akmin和akmax。在时刻t，ak(t)∈[akmin,akmax]。a(t)初始值为akmax，随着时间接近于最后期限，最终降至akmin。基于上述设定，设ak(t)可表示为：

ak(t)=akmax-f(δ(t))(akmax-akmin)

(10)

式中,f是δ(t)的函数，用以计算卖方价格。

满足要求的函数f的选择多种多样。文献[19]中给出了常用的多项式函数：

(11)

易得出，卖方价格：

(12)

类似地，买方价格bk(t)可表示为：

(13)

3.2.2 基于资源的策略

至于资源，实际资源量被视为价格，因此在议价期价格相对固定。但是，值得注意的是，实际资源量仅为主机能够支撑虚拟机的最低要求。若主机当前空闲资源与虚拟机需求资源相当，则在迁移后极有可能导致主机过载，进而产生新的虚拟机迁移需求，对系统稳定性造成影响。因此，通过适当提升卖方价格，有助于筛选主机，减少后续迁移的可能性。

策略中，主机Hi针对虚拟机Vj的CPU资源基础卖方价格为虚拟机Vj占用主机Hi的CPU资源实际计算量，可表示为：

(14)

类似地，主机Hi针对虚拟机Vj的RAM资源基础卖方价格为虚拟机Vj占用主机Hi的RAM资源实际大小，可表示为：

(15)

设资源k的最低和最高卖方价格为：

(16)

其中，1<μkminμkmax。当1<μkmin，虚拟机要求更多的资源，同时降低后续迁移的可能性；当μkmin=μkmax，资源k的卖方价格在议价期限内是常数。

类似地，Hi对CPU资源的出价为主机Hi的CPU资源实际可用计算量，可表示为：

(17)

Hi对RAM资源的出价为主机Hi的RAM资源实际可用大小，可表示为：

(18)

与卖方价格类似地，资源k的最低和最高买方价格为：

(19)

其中，1<μkminμkmax。

3.2.3 总体价格

总体的卖方价格和买方价格将通过上述2项策略进行整合。在时刻t，针对资源k，卖方价格为：

强化工程全过程质量监督，实行定期工程质量管理巡查与不定期检查相结合，坚持开工初期、施工中间、隐蔽工程施工、工程支付验收四到场，严把工程质量关，跟踪督查，精准监管，全面提升工程质量，为水利项目建设保驾护航。不定期开展水利工程质量大检查，发现的问题按照影响程度分别以现场口头告知、下发整改通知和通报等方式责令整改，对各单位的问题整改情况逐一进行跟踪销号，有效提高了实体工程质量。

(20)

买方价格为：

(21)

3.3 交易策略

在交易中仅存在一类资源的情况下，对于资源r，对买方价格和卖方价格按照自然顺序排序，即对买方价格按照降序排序，对卖方价格按照升序排序。例如，一次拍卖中存在n名买方及m名卖方。对买方价格按照降序排序，b1≥b2≥…≥bn；对卖方价格按照升序排序，a1≤a2≤…≤am。设平衡点索引位置为k，k为满足bk≥ak的最大值。随后，卖方价格低于ak的卖方与买方价格高于bk的买方之间进行交易。

但在本文场景下，由于拍卖中存在多种资源，因此上述方法并不适用。为解决文中多种资源情况下的拍卖问题，本文提出一种基于虚拟机资源与买方主机资源的匹配程度的交易策略。

(22)

(23)

(24)

在资源数目为2的情况下，以上过程如图2示。

图2 资源相似度计算方法示意图

卖方集合记为A，买方集合记为B。

双方通过下列步骤匹配交易：

1)对A中任意Hi及B中任意Hj，计算二者间的相似度dij；

2)对所有dij按照升序排列，记排序结果为D；

3)选择剩余dij中最小者；

4)若Hj能负担Hi需求的所有价格，则转至步骤5，否则转至步骤6；

5)Hi与Hj进行交易，将所有Hi与Hj从D中去除；

6)重复步骤3～步骤5，直至D为空。

4 实验评估

4.1 评估方法

本评估中涉及3组，每组6台，共计18台主机。同组主机具有相同的系统参数配置和阈值设置，不同组主机间系统参数配置有所差异，且根据其自身特点设定了不同的阈值，用以模拟数据中心的异构性。

表1 主机参数设置

主机参数设定如表1所示。其中，高阈值用于判定主机是否过载，若超出该阈值则主机执行虚拟机迁出机制；低阈值用于判定主机是否欠载，若低于该阈值则主机将接受虚拟机的迁入请求。

系统中，由独立的管理单元负责提交新的虚拟机分配申请。虚拟机的到达与离开为泊松过程。在仿真中，设定平均任务到达时间为1000 ms。为模拟虚拟机的异构性，虚拟机被CPU设定为2核、4核或8核，内存被设定为2 GB、4 GB或6 GB。各类虚拟机的数量符合平均分布，且各虚拟机的长期平均资源利用率为0.5。

在相关研究中，随机算法常作为不同方法比较的基准方法，因此，本文仿真中加入随机算法作为基准方法。当主机过载时，随机算法在当前主机中随机选取一个虚拟机，并将其迁移至其他某个随机主机中。理论上，全局资源信息对随机算法透明，因此，随机算法在稳定状态波动较大。

4.2 资源占用率

仿真中，针对每种方法，本文分别统计了第1组、第2组和第3组各组内部主机在各个时刻CPU、RAM利用率，并给出了各组的平均值与标准差。值得注意的是，平均值指标给出了各组资源利用率总体水平，通过平均值是否达到设定值可对各组主机整体资源利用率是否达到设定值做出简要的判断；标准差给出了各组内部各主机资源利用率的差异程度。

4.2.1 基准方法

图3给出了基准方法第1组主机的资源利用率统计。第1组目标资源利用率介于0.4～0.5之间。仿真中，基准方法CPU与RAM平均利用率达标，CPU与RAM利用率标准差约2%～8%，波动较大。对于第1组，基准方法能够有效地控制资源利用率，但同组各主机之间资源利用率相差较大，资源利用不平衡。

图3 资源占用统计(基准方法，第1组)

图4给出了基准方法第2组主机的资源利用率统计。第2组目标资源利用率介于0.6～0.7之间。仿真中，基准方法CPU平均利用率达标，RAM平均利用率较低约50%，CPU与RAM利用率标准差约2%～6%，波动较大。对于第2组，基准方法能够有效地控制资源利用率不使主机过载，但主机各类资源利用不平衡；同组各主机之间资源利用率相差较大，资源利用不平衡。

图4 资源占用统计(基准方法，第2组)

图5给出了基准方法第3组主机的资源利用率统计。第3组目标资源利用率介于0.8～0.9之间。仿真中，基准方法CPU平均利用率达标，RAM平均利用率较低约50%，CPU与RAM利用率标准差约2%～4%，波动较小。对于第3组，基准方法能够有效地控制资源利用率不使主机过载，但主机各类资源利用不平衡。

图5 资源占用统计(基准方法，第3组)

总体而言，基准方法能够有效地控制资源利用率，但主机各类资源利用率不平衡，同组各主机之间资源利用不平衡。

4.2.2 本文方法

图6给出了本文方法第1组主机的资源利用率统计。第1组目标资源利用率介于0.4～0.5之间。仿真中，方法2的CPU与RAM平均利用率达标，CPU与RAM利用率标准差约2%，波动较小。对于第1组，方法2能够有效地控制资源利用率，同组各主机之间资源利用率相差较小，资源利用平衡。

图6 资源占用统计(本文方法，第1组)

图7给出了本文方法第2组主机的资源利用率统计。第2组目标资源利用率介于0.6～0.7之间。仿真中，方法2的CPU与RAM平均利用率达标，CPU与RAM利用率标准差约2%，波动较大。对于第2组，方法2能够有效地控制资源利用率，同组各主机之间资源利用率相差较小，资源利用平衡。

图7 资源占用统计(本文方法，第2组)

图8给出了本文方法第3组主机的资源利用率统计。第3组目标资源利用率介于0.8～0.9之间。仿真中，方法2的CPU平均利用率达标，RAM平均利用率较低约70%，CPU与RAM利用率标准差约2%～4%，波动较小。对于第3组，方法2能够有效地控制资源利用率，同组各主机之间资源利用率相差较小，资源利用平衡。

总体而言，基准方法能够有效地控制资源利用率，同组各主机之间资源利用率相差较小，资源利用平衡。

图8 资源占用统计(本文方法，第3组)

4.2.3 讨论

为能够更加清晰地了解各方法的优势与不足，现将各方法CPU利用率达标状况、RAM利用率达标状况、各类资源平衡状况、组内主机平衡状况等信息列于表2中。

表2 迁移算法结果比较

基准方法能达到最终系统平衡，且各类资源自利用率均低于设定的上限阈值。然而，基准方法无法实现整体资源的平衡利用，且各组内主机负载均衡性差，迁移次数过多。这是由于基准方法采用随机化方法，无视系统资源状况。随机迁移无法保证资源的平衡利用，同时一定程度上会导致虚拟机迁移至濒临过载主机。大量的虚拟机迁移造成了过多的系统开销。

本文方法不仅实现了整体资源的平衡利用，且各组内主机负载均衡性好，同时，虚拟机迁移次数更少。这是由于方法2在利用市场化拍卖手段的同时，在拍卖交易策略中引入了资源利用率相似度的概念。通过将虚拟机迁移至资源利用率相似度较高的宿主机，能够保证宿主机与其上各虚拟机各种资源利用率的一致性。

5 结束语

为解决虚拟机资源与云计算主机资源之间的匹配问题，本文提出了一种基于拍卖的方法来处理云计算环境数据中心的资源分配和管理问题。通过制定出价策略，建立拍卖规则，实现了云计算数据中心环境下的虚拟机拍卖市场。通过引入基于拍卖的市场化方法，对资源有不同要求的虚拟机能被分配给适当的主机进行执行。本文通过引入一种基于资源匹配度的拍卖规则实现了拍卖交易。仿真实验结果表明，文中提出的方法均能有效解决云数据中心虚拟机分配问题。异构的任务负载能够获得合适的数据中心资源，同时异构主机也可以根据自身的能力获得负载均衡，从而提高整体效率，保证了云资源与虚拟机之间的适配性。