面向云计算多租户的主模块公平调度算法*

高 倩 王钺霖 于世行 王淑玉

（中国石油大学（华东）计算机与通信工程学院 青岛 266580）

1 引言

近年来，随着互联网基础设施的发展以及移动设备的普及，云计算［1］作为一种新型的计算模式得到了学术界、工业界以及政府等多方面的高度关注。云计算中的租户［2］通常代表着一个组织机构，而用户通常表示使用该组织机构租用资源中的一名成员，租户的概念也可以更好地表示客户对使用资源的租用关系。

为了进一步保证共享环境中租户的服务质量并提高资源利用效率，公平的资源分配和任务调度是多租户服务面临的重要问题。文献［3］将虚拟机分配调度问题及满足用户QoS相结合，通过改进遗传算法来实现最大化服务利润。文献［4］考虑了在云计算环境下基于用户任务的信任QoS情况，提出了一种在多维QoS约束条件下的任务调度机制，同时为了实现云数据中心动态的负载均衡采用了相对成熟的虚拟机迁移技术。关于多种资源的公平分配，许多研究仅关注可交换资源的公平分配问题［5］，然而云计算环境中许多情况下需要研究不可交换资源的公平分配问题。文献［6］首次对云计算中的多资源公平分配问题进行了系统性的调研，提出的主资源公平分配方法旨在使租户之间的关键资源比例相等，并且进一步证明了该公平分配理论所具有的公平特性。文献［7］提出了多资源分配的统一分析框架，可以调节多资源分配中公平与利用率之间的平衡。文献［8］从另一个角度分析了多资源的公平分配问题，提出了基于资源瓶颈的公平分配，并分析其具有两种公平特性。文献［9］通过分析不同配置的主资源公平，给出了主资源公平与资源瓶颈公平之间的关系。文献［10］基于最大最小公平算法［11］来满足更多用户在资源需求方面的要求，这也是这个公平性理论的体现。

首先需要明确租户共享的工作流程，以及工作流中不同服务模块的资源需求量。在租户的资源需求具有差异性的情况下，需要将各个服务模块的资源高效且公平地提供给每一位租户。服务提供者需要设计公平的分配方案，使得租户之间不存在嫉妒或者欺骗等不利于共享的情况。另一方面，需要设计任务调度机制，对租户多个共享服务模块的调度进行统一管理，以保证资源公平分配方案的高效执行。因此，通过公平的资源分配和任务调度，可以更好地实现租户之间的性能隔离。

2 系统模型

在云计算中，租户们在一个共享的数据中心上部署他们的服务。在服务运行时，租户的任务量随着时间不断变化，资源的供给也需要随之变化。租户的资源供给过程如图1 所示，租户通过调用不同的服务模块完成租户的任务，通过虚拟化底层硬件资源形成资源池，可以根据租户的任务量进行动态供给［12］。

图1 系统模型图

3 主模块公平形式化描述

3.1 定义主模块

在多租户服务系统中，资源的共享级别与租户的隔离性［13］相互制约，即总资源是共享的，各个租户之间的资源是隔离的。用户可以共享同一应用服务，如图2 所示，租户通过多个服务模块的配合完成一项作业，租户I 和租户II 共享服务模块A 和B，租户I 需要服务模块A 一个单位资源，需要服务模块B 两个单位资源，而租户II 需要服务模块A 两个单位资源，需要服务模块B一个单位资源。

图2 多租户之间的性能隔离与资源共享

将服务模块最小的资源单位设定为单位大小的虚拟机，服务模块不同的任务类型不同，租户对不同服务模块需要的虚拟机数量也不同，根据主资源公平理论［14］，我们将租户需要资源比例最大的共享服务模块定义为租户的主模块。

将第i个租户表示为ti，将其第j个共享服务模块资源需求量表示为tdij。租户需要的总资源

完成一项作业需要n 个共享服务模块的集合表示为C：

第j 个共享服务模块的最大虚拟机数量为Cj。tdij/cj表示租户i 需要共享模块j 的资源所占该共享服务模块总资源的比例。其最大的比例值dci可表示为

例如，租户I 和租户II 共享服务模块A 和服务模块B，服务模块A的虚拟机容量为10，服务模块B的虚拟机容量为20。租户I 对服务模块A 的虚拟机需求量为3，对服务模块B 的虚拟机需求量为4；租户II 对服务模块A 的虚拟机需求量为1，对服务模块B的虚拟机需求量为4。如图3所示。

即租户I 对A 和B 的需求比例分别为30%和20%，根据主模块定义，租户I需要资源比例最大的共享服务模块A 为主模块。同理可求得，租户II对A 和B 的需求比例分别为10%和20%，租户II 的主模块为B。

图3 共享模块分配示例

3.2 定义公平

由于多租户需要共享基础设施、数据库甚至应用服务模块，而且租户都本能地希望通过占有更多的资源以获得更好的服务，共享服务模块被所有租户竞争共享，因此保证资源的公平分配尤其关键。同一公平分配策略在不同的应用场景下具有不同的有效性，在多租户环境中判断一个分配策略是否公平，不能仅从资源分配的数量去判断。

当有两个共享服务模块A 和B 时，部分租户需要较多服务模块A的资源，部分租户需要较多服务模块B 的资源，简单将不同模块资源进行平分的策略将导致资源与需求的不合理匹配主模块公平策略将尽可能使租户I使用模块A的资源比例与租户II使用模块B的资源比例相等。

每个租户都拥有主模块，主模块公平的核心思想就是让各个租户主模块分配到的资源比例尽可能相等，在该约束条件下，为了使资源充分利用，可以将主模块公平分配形式化为最大化可执行任务数的优化问题：

在如上主模块共享资源例子中，求解优化方程组：

求解方程组，可得：

x 和y 分别表示租户I 和租户II 可以完成的作业个数。因此，根据主模块公平策略可以得到图3所示的分配方案，租户I 在其主模块A 中获得60%的资源，租户II 在其主模块B 中也同样获得60%的资源，两个租户主模块资源比例相等。

4 主模块公平调度算法

4.1 虚拟队列

虚拟队列表示服务模块优先级最高的任务集合，虚拟队列中的任务根据其加入虚拟队列的时间实行FCFS的调度方式。由于工作流程导致服务模块之间本身具有一定的先后顺序，假设服务模块中选择当前主模块资源比例最少的租户任务作为高优先级进行调度。如果租户的主模块是流程中靠后的服务模块，那么即使在第一个模块调度了该租户的作业，由于需要一段时间才能执行到租户的主模块，其主模块资源比例也不会提高。这样可能出现即使调度了该租户大量的作业，但是由于主模块资源比例提高的延迟性，其作业在一段时间内将被作为高优先级调度，这也将导致其他租户等待时间的增长。但是当该租户作业的任务到达其主模块时，其主模块资源比例又会大幅提高，这样其优先级又变得很低，这将出现系统调度的不稳定性。

所以我们设计一个虚拟队列来解决调度时不稳定的问题，当模块资源任务来临时，若空闲资源量大于需要的资源量时，服务模块从实际队列中选择时间戳小的任务执行；若空闲资源量不能满足所需的资源量时，服务模块的虚拟队列就进行任务入队操作，且以当前时间作为任务的时间戳，任务调度流程图如图4所示。

4.2 公平因子

虚拟队列可以使调度算法在保证公平的基础上，提高系统调度的稳定性。为进一步提高资源利用率本节提出调度的公平因子，通过调节公平因子阈值的大小，进行公平与效率之间的平衡［15］。

图4 任务调度流程图

使用公平因子需要对任务执行时间有一定的估计能力。假设服务模块现有空闲资源量为w，在虚拟队列中需要执行的任务为a，其需要的资源量为n 且n＞w。在实际队列中需要执行的任务为b，其需要的资源为m且m＜w。按照公平的原则，需要等待服务模块中有任务完成，等待总空闲资源可以执行a 时，优先调度执行a。但是这可能造成空闲资源量w 的浪费。通过获取模块中所有任务的执行情况，可以预估出等待可用资源n 所需要的时间tn，当tn大于任务b的执行时间tb时，即使选择执行任务b也不会影响任务a的执行。这样可以进一步提高资源的利用率。

设定服务模块拥有执行虚拟队列任务所需资源的最短等待时间为TN，当前空闲资源执行实际队列中可调度任务所需要的完成时间为TB。公平因子Δ 表示为两者的比值：

可见Δ 的值越大，表明可以选择实际队列中可执任务的调度弹性空间越大，根据贪心的思想选择优先级高且资源需求大的可执行任务。由于任务执行时间具有随机性，因此根据任务执行时间的均值方差S 统计数据，可以设定不同的公平因子阈值X，那么：

1）计算得到的公平因子大于阈值，即Δ ＞X时，调度器可以选择充分利用空闲资源，调度实际队列中的任务；

2）当计算得到的公平因子小于阈值，即Δ ＜X时，调度器等待正在执行的任务完成并调度虚拟队列中优先级最高的任务。

5 算法实现及分析

本节针对上述调度算法机制，给出调度算法伪代码。调度过程可以分为两部分，首先是主模块选择算法，如算法5.1所示，从整体上根据主模块公平对租户的作业进行调度，其目的是保证整体的公平；其次是服务模块调度算法，如算法5.2 所示，根据模块中任务调度的优先级，并且通过虚拟队列和公平因子保证调度的稳定性并提高模块的资源利用率。

5.1 主模块选择算法

Require：

模块总资源C，＜c1；c2；…cj＞；

模块现有资源CR，＜cr1；cr2；…crj＞；

租户i模块占有量TCi，＜tci1；tci2；…tcij＞；

租户i模块需求量TDi，＜td1i；td2i；…tdij＞；

租户i主模块资源比例，dci；

Ensure：

是否可以进行调度；

1：选择dci最小的租户i，其主模块为j；

2：if CR≥TDithen

3：TCi=TCi+TDi；

4：CR=CR-TDi；

5：dci=tci/cj；

6：returntrue；

7：else returnfalse；

8：end if

5.2 服务模块调度算法

Require：

模块资源空闲量,rw;

模块正在执行任务列表TE,＜te1;te2;…teq＞;

公平因子的阈值,X;

Ensure:

无返回值;

1:while!vheap.empty()andvheap.top().req＜=rwdo

2:TE.add(vheap.top());

3:rw=rw-vheap.top().req;

4:vheap.pop();

5:end while

6:if!vheap.empty()then

7:rn=vheap.top().req;

8:EN=set{sum(rheap.top(EN).req)＜rn};

9:ET=EN.makespan*X;

10:foreach i∈ETdo

11:foreach j∈TEdo

12:sumrn=TE[j].et＜ET[i]?sumrn+TE[j].et:sumrn;

13:end for

14:ifsumrn＜rnthen

15:TE.add(rheap.top());

16:rheap.pop();

17:elsebreak;

18:end if

19:end for

20:else:将rheap中可执行任务添加至TE;

21:end if

6 性能评价

本节从模块资源利用率以及完成时间两个方面进行仿真实验，仿真工具选择CloudSim［16］平台，对主模块公平调度算法进行性能评价。仿真设置初始服务模块数量为3，租户量为2。租户I的服务模块资源需求向量为（2；10；2），租户II的服务模块资源需求向量为（10；5；40）。服务模块A，B，C 的资源总量均为500，且服务速率均为2/s（完成时间期望为500ms）。根据设定参数可以计算，租户I的主模块为B，且主模块资源需求比例为0.02；租户II的主模块为C，且主模块资源需求比例为0.08。实验中将主模块公平与模块比例公平进行性能比较，模块比例公平中各个服务模块均严格按租户I与租户II 的资源需求比例进行分配调度。实验中将主模块公平与模块比例公平进行性能比较，模块比例公平中各个服务模块均严格按租户I与租户II的资源需求比例进行分配调度。

图5 主模块公平

在满足算法分配比例的情况下，比较服务模块的资源利用率。从图5 中可以看出，主模块公平除了模块A 资源利用率在70%上下波动外，模块B 和模块C 的利用率均在90%以上。这也说明模块B和模块C 不仅为租户的主模块并且为系统的资源瓶颈，因此利用率很高。而图6 的模块比例公平中，三个模块利用率均有较大波动且利用率均低于主模块公平。

图6 模块比例公平

7 结语

本章对多租户中公平的资源分配与任务调度问题进行了研究，首先，对主模块以及公平性定义，分析其关键性。其次，为了在工作流中保证资源公平稳定且高效地分配，提出基于虚拟队列以及公平因子的调度算法。最后，通过性能评价展示了调度算法的有效性，与服务模块比例公平的调度算法相比，主模块公平调度保证了整体的公平性并提高了各个模块的资源利用率。