0 概述

云计算是一种新型的并行计算技术, 其综合了分布式计算、并行计算、网格计算的特点与优势^[1]。云基础设施由共享的硬件和软件商品资源池组成, 这些资源池按地理位置分布并提供按需服务^[2], 支持多租户并根据需要动态配置服务器, 可以是物理机器或虚拟机。云计算具有虚拟化、高度灵活性与可扩展、按需服务等特点^[3], 因其具有卓越的服务性能和较高的资源利用率, 目前关于云计算的研究实现与商业应用迅速发展, 如Amazon的EC2、Google的App Engine、IBM的Blue Cloud等优秀云计算平台, 都为用户提供了极大的方便。

云计算通过有效分配虚拟机来提供计算服务的动态配置^[4], 因此, 虚拟资源和虚拟机的调度方法是云计算系统的关键技术之一^[5]。有效的调度机制将改善云计算中的工作负载管理, 并且可以进一步优化资源利用率和系统服务质量(Quality of Service, QoS)^[6]。云计算中的调度步骤主要包括发现资源和过滤资源、选择目标资源、分配资源给目标任务^[7]。由于异构云环境下的任务调度问题是一个NP-hard问题^[8], 特别对于云环境中的密码服务而言, 其面临诸多问题, 例如密码算法种类多样且资源需求个性化、运算过程多轮交互且中间状态具有保密性、终端处理节点运算能力有差异且功能实现有限等, 因此必须设计高效的调度机制对各类密码服务资源进行管理与利用, 形成服务资源按需供给能力^[9]。

密码服务是一种由安全协议、密码算法、密码基础设施、密码芯片等密码相关设备和系统提供的服务, 包括加密、解密、数字签名、认证等安全服务以及密码资源管理服务等^[10]。云计算弹性供应虚拟资源并按需付费的性质, 为处理密码服务等大规模科学工作流提供了便利^[11]。

为最大化云计算在密码服务领域中产生的效益, 本文针对异构云环境中密码服务算法种类多样、业务执行时间裕值不一、用户资源需求各异、云中节点处理能力差异化等特点, 综合考虑用户请求任务和运算节点角度属性, 提出一种二级密码服务调度策略。

1 相关研究

目前虽然国内外关于云环境中密码服务调度的研究较少, 但是传统分布式环境以及云环境下的传统业务调度的研究迅速发展, 为本文策略的设计提供了参考。

文献[12]提出一种网格计算环境下基于传统粒子群优化(Particle Swarm Optimization, PSO)和遗传算法(Genetic Algorithm, GA)的混合工作流调度策略, 该方法在执行时间的优化方面取得了明显效果。文献[13]提出一种改进的Min-Min算法, 该算法具有用户QoS约束, 但算法性能没有得到显著的改善。文献[14]为改善系统负载均衡设计一种随机循环选择虚拟机机制, 其中数据中心控制器将业务请求分配给旋转的虚拟机列表, 虚拟机一旦分配到请求即移动到该列表的末尾, 这种分配机制的主要问题是未考虑高级负载平衡要求, 可能导致传入作业等待时间过长而失效。为进一步解决负载平衡的问题, 文献[15]结合用户优先级感知和负载均衡Min-Min算法^[16](Load Balance Improved Min-Min Scheduling Algorithm, LBIMM)的设计思想, 提出PA-LBIMM算法, 但该算法未考虑每个任务的最后截止时间, 在分配任务之前资源上的现有负载过多, 导致任务失效, 不能达到适当的负载平衡。通过分析可知, 以上调度算法只关注调度系统的某一性能, 无法满足实际云计算环境中的各方复杂需求。

文献[17]从负载平衡和利润最大化2个不同角度提出一系列基于蚁群优化(Ant Colony Optimization, ACO)的任务调度算法, 但都没有考虑任务的时间限制。为尽可能满足实际云环境下的任务处理需求, 文献[18]综合考虑正在执行任务的剩余时间、活跃主机、虚拟机配置以及任务截止时间等多种因素, 提出一种基于滚动窗口的节能调度算法, 在保持任务调度成功率稳定的同时, 有效降低了系统总能量消耗和平均单任务能耗, 该策略能够满足异构云环境中最小化虚拟机节点耗能的应用场景需求。文献[19]通过深层挖掘和分析用户的行为信息, 引入相关反馈机制, 提出一种基于用户行为反馈的资源调度机制(User Behavior-based Resource Scheduling Mechanism with Feedback Control, UBRSM-FC), 实现了面向用户需求的资源调度, 然而该机制需要花费额外的空间和时间以存储和更新任务需求矩阵以及任务偏好矩阵, 使得运行时间随着反馈循环的次数成比例增长, 对于实时调度系统的性能有较大影响。此外, 文献[20]提出云环境下带任务准备时间和截止日期约束的代价驱动工作流调度算法, 在合理的CPU时间内有效减少了工作流的执行代价。文献[21]在解决虚拟化云中随机业务与资源的调度问题时, 通过引入资源监控器与资源调整器2个功能模块, 提出一个集成前摄性和反应式策略(Proactive and Reactive Strategy, PRS)的启发式调度算法, 以提高系统保障实时任务时效性的能力。文献[22]通过综合考虑任务的剩余价值密度与执行紧迫性两方面因素, 提出一种实时任务优先级动态分派(Dynamic Priority Assignment, DPA)策略, 以达到系统价值收益与任务成功执行率的最优综合性能。

与传统任务相比, 密码服务任务与虚拟资源属性之间、任务与用户身份之间存在着严重的依赖性:同一密码服务的具体实现算法可能不同, 不同密码算法对虚拟资源的需求以及调用过程不同, 同一用户在不同时刻的密码服务请求也不相同。密码服务的调度专业性、安全性、时效性要求更高, 所提供的服务种类也更复杂, 因此, 上述云计算环境下的调度方案无法直接应用于密码服务领域。针对该问题, 本文从以下2个角度考虑, 提出一种适用于异构云环境的二级密码服务调度策略。

1) 任务角度。云环境中密码服务所需要的功能丰富多样, 包括加密、解密、签名验签以及用于实现各功能具体的密码算法, 而且不同的功能实现算法对资源的需求也各不相同。本文策略使用任务需求分析机制, 将各种密码服务请求按其实现算法进行分类管理调度, 以方便后续功能实现过程中的密钥匹配。此外, 由于网络时延以及算法本身的运算量等因素, 使得不同任务的执行时间裕值即紧急程度也各不相同, 包括任务的就绪时间、任务的截止时间、任务在第i个运算节点上的预计执行时间等。

2) 运算节点角度。在异构云计算环境中, 运算节点的数据处理能力与功能实现有限且存在着较大的差异。因此, 在任务的调度过程中应充分考虑各节点的任务负载能力, 遵循“能者多劳”的调度原则, 以实现调度性能与业务处理性能的最优化。本文调度策略的第二级调度实现同一密码算法功能的节点共用一个节点监控单元, 用于收集和监控各节点的任务处理水平和实时负载信息, 在保证任务调度分配成功率的基础上, 减少各业务的等待时间, 提高整体密码服务系统的实时性。

2 调度系统模型

本节建立密码服务的任务模型以及云环境中的运算节点模型, 同时给出调度系统架构, 并对各单元的作用进行说明。

2.1 任务模型

为方便任务分析单元准确识别任务的功能需求以及查询匹配实现该功能的节点集合, 设置任务模型属性, 包括任务标识、待运算处理的数据量以及处理命令和执行算法等。为保证系统资源调度的成功率, 同时标识每个任务的时间属性, 包括截止时间与就绪时间。任务模型中各项参数的作用具体如下:

1) 任务标识(T_id):任务的唯一性标识。

2) 数据量(Size):任务中待处理数据量大小。

3) 处理命令(Cmd):用户服务请求中的常见密码操作, 包括加密、解密、签名、HASH等。

4) 执行算法(Algorithm):与用户服务请求处理命令相对应的具体密码算法, 包括用于完成加密/解密的对称和非对称密码算法(AES、ZUC、RSA等)、HASH算法(MD5、SHA-1等)以及数字签名算法(DSA、DSS等)等。

5) 截止时间(T_deadline):任务的最晚执行完成时间, 即任务失效时间。

6) 就绪时间(T_ready):系统收到用户服务请求信息与第一个服务任务(或同一用户连续2个服务任务)到达任务分析单元之间的时间差值, 包括任务在传输过程中的网络时延和在任务接收队列中的等待时间。

任务集中的待处理任务可以通过一个包含上述属性的多元组表示:{T_id, Size, Cmd, Algorithm, T_deadline, T_ready}。针对云中多算法随机交叉并发密码服务请求任务, 任务模型同时考虑任务的功能属性与时间属性, 将其与运算节点模型相结合, 可保障高度异构密码服务系统中任务请求功能的正确高效实现。

2.2 运算节点模型

在异构云环境中, 用于实现相同密码服务请求功能和执行算法的各运算节点带宽、存储能力、功能实现过程、体系结构等都存在差异, 为了将各用户的任务分配到最佳的运算节点中, 需要针对节点的各个必需属性进行统一管理和更新。运算节点模型涉及的节点属性除节点标识、数据运算速率和可实现密码算法功能外, 还考虑了执行时间以及最早可执行时间。运算节点模型中各项参数的作用具体如下:

1) 节点标识(M_id):用于标识节点唯一性的必需参数。

2) 数据运算速率(Rate):密码运算节点的数据处理速率。

3) 密码算法功能(Func):运算节点可实现的密码算法请求功能, 包括处理命令以及对应的具体密码算法。

4) 执行时间(Esti_finish_time):在第i个节点的数据处理速率下, 预估的运行完成当前任务j的所需时间。该属性可由节点监控单元通过下式计算获得:

$ {M_i}.{\rm{ }}Esti\_finish{{\rm{ }}_ - }time{\rm{ }} = \frac{{{T_j}.{\rm{ }}Size{\rm{ }}}}{{{M_i}.{\rm{ }}Rate{\rm{ }}}} $

(1)

5) 最早可执行时间(Ear_exe_time):节点处理完所有已分配任务后可开始运行当前任务的最早时间。设节点i下共有t个已分配任务, 则该节点的最早可执行时间为:

$ {M_i}.{\rm{ }}Ear\_exe\_time{\rm{ }} = \sum\limits_{j = 0}^{t - 1} {\left( {{T_j}.{\rm{ }}Esti\_finish\_time{\rm{ }}} \right)} $

(2)

类似地, 云中运算节点也可通过一个包含上述属性的多元组表示:{M_id, Rate, Func, Esti_finish_time, Ear_exe_time}。上述属性都是由系统第2级调度中的节点监控单元负责管理与更新, 供调度管理单元在为任务选择最佳执行节点时参考使用。运算节点模型兼顾各运算节点的功能异构与性能异构特性, 其采用静态调度参数与动态调度参数相结合的思想, 在调度系统为任务匹配执行节点的过程中, 实现对节点群中各运行节点当前状态的实时获取与更新, 可有效减少任务的等待时间并提高任务处理的实时性。

2.3 调度系统架构

本文策略的完整调度过程分两级完成:

1) 由任务分析单元完成第1级任务处理命令和执行算法的分类, 将这两项属性相同的任务传送至同一个二级调度目录下。

2) 由一一对应的节点监控单元和调度管理单元组成资源调度单元作为第2级调度子系统, 每个子系统管理具有相同密码算法功能的运算节点群, 并根据该节点群中各节点的数据处理能力对节点进行顺序编号。节点监控单元负责完成对各节点属性信息的实时管理更新以及对该节点群中节点的扩充和删除。调度管理单元通过优先级算法, 结合节点监控单元信息, 负责计算各节点优先值, 将当前任务分配至该值最大的对应节点下执行。实现密码算法功能相同的节点构成一个节点群, 处在同一个节点监控单元目录下, 用于实现不同密码算法功能的节点处于不同的第2级调度子系统中。

本文调度策略对应的完整调度系统架构如图 1所示。首先通过一级子系统完成对任务请求密码算法功能的分簇, 然后由二级子系统在各自独立的簇节点群中为任务匹配最佳执行节点。与集中式调度相比, 该调度架构可降低资源调度单元的任务处理负载, 缩小可用运算节点的搜索范围。

3 调度策略

本节主要说明调度策略的完整实现过程, 包括第1级调度子系统(任务请求分析)的实现流程, 以及第2级调度子系统(资源调度单元)所用节点优先级函数的设计目标和算法描述等。

3.1 任务请求分析

面对用户请求任务处理命令和执行算法组合丰富多样的密码服务, 调度系统应首先从云环境中筛选出能够实现该请求密码算法功能的执行节点群, 然后才能考虑系统的服务质量与服务代价的优化问题, 这也是第1级调度子系统的设计目标。

在用户请求任务通过系统任务接收队列后, 到达任务分析单元, 该模块通过提取和分析任务中的请求功能和执行算法, 利用映射:

$ \{ (Cmd, {\rm{ }}Algorithm{\rm{ }}) \mapsto ({\rm{ }}Node{\rm{\_}}monitoring{\rm{\_}}unit{\rm{ }})\} $

(3)

选择与该任务实现功能和算法相匹配的第二级调度子系统。一级调度映射关系如图 2所示。

3.2 运算节点匹配

任务通过第一级子系统后, 到达能够实现其密码算法功能的节点监控单元和调度管理单元。其中:节点监控单元负责实时统计管理其目录下各节点的属性信息; 调度管理单元结合任务与节点属性信息, 通过节点优先级算法, 为任务计算其对应节点群中每个节点的优先级值, 然后根据该值为任务选择最佳执行节点, 完成任务的调度过程。下文对节点优先级函数的设计目标以及算法描述进行说明。

3.2.1 设计目标

为保障调度系统的任务调度成功率和任务处理实时性, 在确立节点优先级算法时, 遵循以下设计目标:

1) 为进一步保障密码服务系统的实时性, 减少已分配任务在节点队列中的等待时间, 在不考虑优先级函数其他各项影响的情况下, 应将任务分配至节点属性最早可执行时间较小的节点处。编号为i的节点优先级可以以参数M_i.Ear_exe_time为参考依据, 当该值越小时, 节点i的优先值越大。

2) 在密码服务系统中, 单位任务的调度失败可能会导致整体作业流的运算结果错误, 因此, 应尽可能保障系统的任务调度成功率。为了防止紧急程度较缓的任务占用过多的高运算速率节点资源, 在任务的有效执行时间允许范围内, 本文根据任务的时间裕值和各节点关于该任务的执行时间, 将紧急程度较缓的任务分配至运算速率较低的节点中, 以预留部分运算速率较高的节点处理后续任务队列中的紧急任务。以第i个节点为例, 节点优先级可以以参数M_i.Esti_finish_time为参考依据, 即在任务的有效执行时间内, 该参数值越大, 其对应节点的优先级应越大。

3.2.2 算法描述

节点优先级算法的主要功能是在负责实现同一密码算法功能的节点群中, 计算比较各节点对于当前任务的优先级值, 为任务寻找和匹配最佳的执行节点。完整节点优先级算法综合考虑了任务的截止时间、就绪时间以及节点的执行时间和最早可执行时间等属性, 从任务角度、节点角度权衡优化整体调度系统的实时性和调度成功率, 既满足了一般密码服务调度系统的功能和性能需求, 又方便了特殊使用场合中某些指定性能的加权值调整。第i个节点的完整优先级算法表达式如下:

$ \begin{aligned} F[i]=&-\alpha \times\left(M_{i} . { Ear }\_ {exe}\_ {time }\right)+\\ & \beta \times\left(M_{i} . { Esti\_finish }\_ {time }\right) \end{aligned} $

(4)

其中, α, β∈[0, 1]且α+β=1。为避免任务在已分配节点队列中因等待时间过长而失效, 在计算节点优先级值之前, 应先判断在该节点下当前任务的完成时间长短并与待处理任务的截止时间进行比较, 以此判断该节点是否满足任务的时间裕值需求。判断公式如式(5)所示。

$ \begin{array}{*{20}{c}} {{M_i}.{\rm{ }}Esti{{\rm{ }}\_ }finish{{\rm{ }}\_ }time \le {T_j}.{T\_ }deadline - }\\ {{T_j} \cdot {T\_ }ready{\rm{ }} - {M_i}.{\rm{ }}Ea{r\_ }exe\_time{\rm{ }}} \end{array} $

(5)

以任意一个拥有n个节点(0≤i < n)的第2级调度子系统为例, 对于m个待分配任务(0≤j < m), 节点优先级算法描述如下:

算法1  节点优先级算法

输入  待分配任务属性, 包括任务数据量、处理命令、执行算法、截止时间以及由第1级调度子系统产生的就绪时间; 对应第2级调度子系统运算获得的节点群中各节点的任务执行时间和最早可执行时间

输出  若任务分配成功, 则将当前任务分配至目标运算节点下; 否则, 写入任务失效标识

1.初始化局部标识变量big=error(失效标识, 系统指定值), F[big]=0;

2.for(j=0;j++; j < m)

3.{

4.for(i=0;i++; i < n)

5.{

6.if (式(5)成立)

7.计算节点i的优先级值F[i], 如式(4)所示;

8.end if

9.else F[i] = 0;

10.if (F[i]>F[big])

11.big=i;

12.end if

13.}

14.if (F[big]!=0)

15.将任务j分配至标识为big的运算节点下;

16.end if

17.else返回任务j失效标识;

18.}

节点优先级算法在为任务搜索可用计算节点时, 首先通过式(5)综合分析目标节点的实时负载情况和任务的时间属性约束, 避免已分配任务在节点任务队列中因等待时间过长而失效的情况, 确保已分配任务得到有效执行; 然后通过式(4)计算和比较所有可用节点的优先级; 最后将任务分配至最高优先级对应的节点任务队列中等待执行。节点优先级算法在提高当前任务处理实时性的同时, 预留部分高性能节点资源用于后续高并发紧急任务的处理, 以保障随机高并发密码服务系统的任务执行成功率。

4 仿真与性能测试

通过在Windows环境下的C语言编程仿真, 对本文调度策略进行测试, 包括执行效率、负载均衡以及线性可扩展性能等, 仿真测试代码运行参考机环境为:Inter(R) Core(TM) i7-6700, 工作主频3.4 GHz。由于每一个二级调度子系统的调度过程相似, 因此选取任一子系统中的调度管理单元进行系统仿真。

设置节点数为4, 对于待处理数据量大小相同的单位任务, 各个节点的预计完成时间(单位时间)M_i.Esti_finish_time={4.8, 4.2, 3.5, 2.7}, 0≤i < 4, 同时设置任务属性参数如表 1所示。

4.1 加权系数对算法性能的影响

本文通过以下2个测试分析加权系数对算法性能的影响:

1) 测试加权系数对平均单位任务等待时间的影响。按照上述方法随机生成1 000个待处理任务并保持各属性不变, 在保证所有任务成功调度的前提下, 依次改变加权系数α、β的值, 分别测试对应加权系数下节点任务量(单位任务)和单位任务的平均等待时间(单位时间), 测试结果如图 3所示。可以看出, 当α逐渐增大时, 调度系统将运算速率较慢、队列等待时间较长的节点1和节点2处的部分任务迁移至运算速率较快、队列等待时间较短的节点3和节点4处, 使得系统平均单位任务等待时延显著减小, 测试结果满足算法设计目标。

2) 测试加权系数对任务调度失败率的影响。保持节点个数及属性不变, 随机生成1 000个待处理任务, 为测试任务调度失败率, 重新设置各任务的截止时间属性T_deadline∈[20, 50], 分别测试对应加权系数下任务调度失败率, 测试结果如图 4所示。可以看出, 算法取得的最小任务调度失败率由加权系数α和β共同决定, 这是因为随着α值的逐渐增大, 一方面充分利用了高运算速率节点的性能优势, 提升了任务执行效率, 另一方面也加大了该类节点的运算负载, 使得其任务负载在短时间内趋于饱和, 从而无法保障后续紧急任务的及时处理, 导致整体系统的任务调度失败率有所上升。

4.2 负载均衡测试

由于在异构云环境中, 不同运算节点完成同一任务的执行时间不同, 因此在评价该类系统负载均衡时, 不能像在传统任务的处理环境中一样以各个节点的任务数量为参考。本次系统负载均衡测试以分配至各节点下的任务运行完成时间为标准, 保持节点各属性不变, 测试算法在不同任务个数下的负载均衡性能, 测试结果如图 5所示。可以看出, 在该调度策略驱动下, 系统保持了良好的负载均衡性, 即与总体任务完成时间相比, 各节点的任务完成时间相差较小, 同时也合理地减轻了节点4的部分任务负载, 为后续大规模紧急任务的处理预备了较为充足的运算资源。

4.3 不同策略的对比测试

为测试比较本文策略与已有相关策略的执行效率, 分别将遗传算法(GA)和实时任务优先级动态分派(DPA)算法作为对比策略应用于异构云环境中的密码服务调度, 在保持相同节点和任务属性的情况下, 测试本文策略与2种对比策略在不同任务量下的系统执行时间, 如图 6所示。

通过分析图 6可知, 在相同的异构节点环境中, 对于相同数量的任务, 本文调度策略驱动系统的执行时间相比于DPA和GA策略分别减少了4%和17%左右。这是因为本文调度策略相对于其他策略, 充分考虑了云中任务执行节点的功能异构和性能异构, 以节点的任务运行时间作为参考为任务匹配最佳执行节点, 在保障密码任务调度成功率的前提下, 有效利用了高性能节点的处理优势, 充分实现了“能者多劳”的调度机制, 对于实时密码服务系统性能的提升具有显著优势。

5 结束语

本文针对异构云计算环境下的复杂密码服务请求, 提出一种同时支持多种处理命令和密码算法的二级调度策略。在任务分析单元中根据任务处理命令和执行算法2项属性, 将任务传送至与其密码算法功能相匹配的第2级调度子系统下, 通过该系统管理具有相同密码算法功能的运算节点群。在此基础上, 在调度管理单元中利用节点优先级算法计算比较各节点对于该任务的优先级值, 为其寻找和匹配最佳的执行节点。仿真结果表明, 该策略的执行效率较DPA和GA策略分别提高了约4%和17%, 能够满足实时密码服务系统的任务调度需求。下一步将在本文研究基础上, 针对云中数据依赖性密码服务, 设计任务关联数据安全、高效的交互方法, 以拓展本文策略的应用场景。