基于云计算平台的多数据库并行调度算法仿真

2023-07-29杨毅,熊鹰

计算机仿真 2023年6期

杨毅,熊鹰

(华中科技大学网络与计算中心,湖北武汉 430074)

1 引言

随着信息技术的飞速发展,互联网+、云计算平台等陆续被开发,在云平台背景下保证多数据库同时运行且负载均衡是十分重要的[1]。数据库的可靠调度关系到云计算的全局运行速率,对多数据库实施调度,不但要和多个服务器合作,也涉及多数据库的信息筛查。但并行调度的难点在于不同数据库的调度信息量过大[2]、数据库的计算机语句设置各不相等、复杂性较高等,大大影响了数据库之间的信息交互。

针对并行调度问题,文献[3]通过构建多信道链路模型,求解均衡调度问题,创建双适应度函数并进行恰当调整,完成调度目标。但该方法没有考虑节点的真实负载状态,致使节点负载不均。文献[4]融合多核集群拓扑特征,综合消息传递与共享存储编程模型,使用作业优先级编码模式转移鸟巢位置,并将位置信息作为作业调度序列排列优先级求解,实现调度任务。但该方法无法自动完成作业调度序列的队列选择与设定,数据库调度效率较低,适用性不高。

本文吸取文献方法的优势,针对其不足提出一种基于云计算平台的多数据库并行调度算法,组建高可信度云计算平台,利用MapReduce编程得到多数据库并行调度模型,运用离散粒子群算法完成高效率并行调度目标。仿真结果证明,经所提算法调度后,实现了网络负载均衡,可应用于多种类数据库,适用范围广。

2 云计算平台构建

云计算平台涵盖应用层、平台层与基础设施层三个层次,以基础设施层为例,引入可信根与信任传递思维,面向虚拟层实际特征,给用户提供一个高度安全的云计算平台[5]。云计算平台构建技术中最关键的就是虚拟化技术,虚拟化是一种从底层硬件或软件抽象出应用程序、用户操作系统。虚拟化的核心是服务器虚拟化,主要划分为底层硬件下的虚拟化、宿主操作系统下的虚拟化两种模式。

云平台在创建过程中,需确保每个组件都能完整度量的同时,得到系统控制权顺序。构建顺序执行信任链的过程为

Ii+1=Ii∧Vi(Si+1)

(1)

其中,Ii表示云平台物理主机操作系统引导时第i个阶段的完整性,如果第i个阶段是完整的,那么Ii=1,反之Ii=0。Vi(Si+1)是第i个阶段的度量控制组件,对引导序列内第i+1个阶段实施度量的参数。

以云计算设备Eucalyptus为基础,设计满足多任务调度的可信云计算平台结构体系,如图1所示。图1内的阴影部分代表云服务商对某些节点采取可信增强措施。交互接口是云计算平台设计的用户可见入口,是用户开启与停止运作的服务接口[6]。云管理员利用集群控制器把虚拟机实例传递至不可信平台,实现云计算平台最优的存储与计算效用。

图1 云计算平台架构示意图

3 基于离散粒子群的多数据库并行调度算法

3.1 多数据库并行调度模型

为实现多数据库的有效调度,创建并行调度模型前,需要进行如下优化运算。多数据并行调度时间序列拥有显著的混沌特征,提取相关的混沌特征可以有效优化模型的调度速率[7]。将数据库调度的控制集合记作式(2)

(2)

融合并行策略与混沌因子,计算调度时间顺序适应值

(3)

最终将调度任务的效率描述成

φ=|θ-j|

(4)

其中,φ表示调度任务效率,θ表示递增系数。

当前多数云计算平台将MapReduce编程模型应用在海量数据库的并行运算中。MapReduce操作融合Map与Reduce函数,将其传输至调度系统,分配到可用计算资源。综合以上运算过程,将多数据库并行调度模型表示成图2。

图2 并行调度模型

Map操作是把较大的任务划分成若干子任务,再把子任务分配至计算资源内执行运作,利用Reduce操作获得并行调度输出结果[8]。把类资源均看作计算资源,设置运行条件:已知子任务需要的计算量、计算速率和子任务在各计算资源内运行完毕的时间。如果子任务个数是M,计算资源个数是N,使用M×N矩阵描述每个计算资源内任务运行所需的时间。把多数据库并行调度问题简化成:怎样把若干任务恰当配发至计算资源,让全部任务完成的总时间最小。

3.2 算法实现

并行调度模型构建完毕后,融合基于离散粒子群的并行调度算法,实现在保证负载均衡前提下的多数据库高质量并行调度任务。利用离散粒子群法计算调度问题,组建有效的粒子编码结构,使用间接编码模式完成各子任务的资源编码,编码长度是当前子任务的数量,一个编码对应一个并行调度方案[9]。

本文使用可靠性来定义离散粒子群算法中的实用度函数,经过不断上升的迭代数量,完成高可靠性数据库并行调度目标。适应度函数值可以准确评估调度任务策略的优劣,适应度函数值越高,表明任务调度性能越好。假设随机一个任务ti调度至某个云计算资源,调度执行时间一定要处于截止时间之内,若超出该时间,则说明调度任务失效[10]。把具备截止时间的任务调度问题约束公式记作

(5)

其中,eij为执行时间,di为时间阈值。

在式(3)基础上,将适应度值的计算过程变换为

(6)

其中,F代表适应度函数,mintpi代表目标函数,λ为调度系数。

粒子群算法为一种随机优化控制策略,算法中粒子m进化时具备两个矢量,依次为方位矢量xm=[xm,1,xm,2,…,xm,D]与速率矢量vm=[vm,1,vm,2,…,vm,D],D是空间维度。

云计算平台环境下,把多数据库并行调度问题拟作一个离散优化问题,把离散粒子群算法代入并行调度中,数学的加减乘除计算不再适用,要对其重新定义。将粒子的方位描述成一个S维矢量,即x=[x1,x2,…,xj,…,xs],粒子的速率是粒子方位改变的几率,也是一个S维矢量,记作v=[v1,v2,…,vj,…,vs]。方位和速率的加法运算可以完成粒子位置的变动。

每个粒子均拥有速率与方位两个特征,利用更新粒子速率与方位获得全新的粒子。与传统粒子群算法的速率更新解析式相比,本文在速率更新中添加一个调整因子,用来操控粒子的搜寻方向。将粒子速率更新解析式表示成

vi=ωvi+c1r1(pbesti-xi)+c2r2(gbesti-xi)

(7)

式中,ω为惯性权重,c1、c2均为学习因子,分别代表粒子向局部最优解pbest与全局最优解gbest的靠近水准,r1、r2是处于[0,1]之间的任意数值,vi的取值范围是vi∈[-vmax,vmax],这样可以避免粒子超过搜寻范围,提高并行调度的准确性。

由于粒子的搜寻空间具有不连贯性,采用下面两个公式完成粒子方位更新

xi=xi+vi

(8)

(9)

首先利用式(8)实施方位更新,但在获得的编码序列内包含不合规编码,这时要使用式(9)把不合规编码变换成合规编码,得到更新后的粒子具体方位。

粒子搜寻时为了控制并行调度算法的运算能力,引入权重影响因子ω′,ω′较大时可以实现全局查找,相反ω′较小时容易陷入局部查找,所以调节ω′值能够显著提升算法的搜寻成效,优化并行调度算法的整体性能。

ω′的取值有两种模式:

一是挑选一个常数,设置该常数是ω′,优势是方便计算,缺陷在于不能在所有迭代流程中发挥优秀的搜寻能力;另一个模式是设定动态ω′值,本文采用动态ω′值模式,通过线性变化调节在减少计算量的同时,保证调度全局最优效果。

(10)

通过以上过程,就能让算法在全部搜寻过程表现出优秀的寻优效果,获得高质量多数据库并行调度性能,保证数据库的资源调度及时性与准确性。

4 仿真研究

4.1 仿真环境

为检测本文方法在云计算平台多数据库并行调度的实际应用效果,使用CloudSim平台完成仿真任务。实验包含10个虚拟资源,7台物理机。在实验环境下对本文方法、多信道联合法和布谷鸟搜索法进行仿真分析。实验参数设定为:种群规模是400,最高迭代次数是300,惯性权重最高值与最低值依次是0.94和0.34,学习因子c1=0.2、c2=0.4。

4.2 调度长度与迭代次数分析

在不同迭代次数下反复执行30次并行调度任务,记录不同方法下调度最优解、最差解以及迭代均值,结果如表1所示。

表1 三种方法并行调度最优解结果对比

最优解表示算法获得的最佳调度次数,数值越小,表示云计算平台需要执行的次数越少,更方便操作和减少调度误差。从表1中能够看出,所提算法调度最优解、最差解都远小于文献方法,但是迭代次数相对较大。为此,分析算法获得最优调度解的迭代过程,如图3所示。

图3 三种算法数据库任务调度长度对比

图3中可知,多信道联合法在计算中丢失了一些潜在的优秀粒子,很快陷入局部最优并呈现出收敛状态;布谷鸟搜索法在融合消息传递编程模型与共享存储编程模型时,算法的计算量过高,也很快地出现了局部最优情况。本文方法在迭代次数低于40时,粒子均处在搜索状况,多次跳出局部最优,证明方法在迭代初期就拥有优质的全局搜索能力;之后粒子逐步开始局部搜寻,直至找到全局最优解。综合表1与图3的数据,充分证明了本文方法在收敛性、全局搜索能力与局部搜索能力都优于两个对比方法。

4.3 适应度值对比分析

图4是三种方法基于不同任务个数的适应度值对比,适应度函数值越高,表明任务调度的适用性能越好。

图4 三种方法不同任务数量下的适应度值对比

由图4看出,任务个数较少状态下,三种方法的适应度差距并不显著,但伴随任务数量的持续增多,本文方法的适应度函数值显著高于文献方法,且任务数量越多,此趋势越明显。这是因为该方法通过提取并行调度时间序列相关的混沌特征,优化了调度整体速率,并采用Map与Reduce函数,创建多数据库并行调度模型,有效提高了多数据库并行调度性能。