在线课程下的自适应查询调度算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇在线课程下的自适应查询调度算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要:在线课程系统中,针对如何将查询请求充分映射到有限资源上这一热点问题,设计基于系统负载平衡的自适应查询处理器。该处理器综合考虑服务器、带宽等性能指标,建立由服务资源单元和远程查询消耗单元组成的基于资源负载平衡的查询期望代价矩阵,并结合利用Min-Min和Max-Min算法的优点,提出新的自适应查询调度算法(A-MM)。实验表明A-MM有较好的执行效率和平衡负载能力。
关键词:大规模在线课程;自适应查询调度;负载平衡;负载消耗系数; Min-Min算法; Max-Min算法
中图分类号: TP311
文献标志码:A
Adaptive query scheduling for open online courses
HOU Yong1, Woxur Silamu1, YU Jiong1, ZHOU Yan-hui2
(
1. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China;
2. Service Center, State Administration of Radio Film and Television Authorities, Beijing 100866, China
)
Abstract:
This paper proposed an Adaptive Query Processing module which aims to solve the problem that how to develop a better map plan for query to achieve users’ demand in limited resources of server and bandwidth on Open online Course system. In this paper, firstly, query expected cost matrix be set up according to the performance of resources and the cost of query tasks; secondly, using the new A-MM (Adaptive Min-Min and Max-Min) algorithm which merge the merit of Min-Min and Max-Min for adaptive query scheduling; finally, experiments have been done and shown that the A-MM has better efficiency and balance capacity.
This paper proposed an adaptive query processing module which aimed to solve the problem that how to develop a better map plan for query to achieve users demand in limited resources of server and bandwidth on open online course system. In this paper, firstly, query expected cost matrix was set up according to the performance of resources and the cost of query tasks; secondly, the new A-MM (Adaptive Min-Min and Max-Min) algorithm that merged the merits of Min-Min and Max-Min was used for adaptive query scheduling; finally, experiments have been done and shown that the A-MM has higher efficiency and better balance capacity.
Key words:
Massive Open Online Course (MOOC); adaptive query scheduling; load balance; Query Expected Cost (QEC); consume load ratio; Min-Min algorithm;Max-Min algorithm
大规模在线课程(Massive Open online Course, MOOC)系统已逐渐被应用于实际。如何在有限服务资源环境下,为大规模查询请求提供满意查询处理,是阻碍MOOC发展的最主要问题之一[1-2]。作为MOOC的核心组件,自适应查询处理器(Adaptive Query Processing,AQP)[3]起着映射查询与资源的执行关系,平衡系统负载,最终决定MOOC能否在有限资源环境下为用户实现理想查询处理的功能。在AQP查询调度算法研究中:GQO[4]目标是为缩短整体查询反应时间,用资源选择策略和通用的并行处理算法去平衡优化代价和查询执行;文献[5]对资源查询模型的参数获取进行了研究,通过设置Eddy进行监控,取得相关的工作负载、传输速率等信息;文献[6]中对任务的节点分配优化进行了研究,并采用Min-Min的调度算法对子任务在节点分派的优化算法进行了研究;文献[7]对10种经典查询调度算法对比。以上工作主要集中在如何提高查询速度,而忽视了平衡系统资源负载的问题。实际应用中,MOOC查询的大规模、应用固定性特点,要求AQP必须考虑如何平衡系统负载,降低系统资源成本。为解决以上问题,本文首先介绍平衡负载的自适应查处调度器(Balanced Adaptive Query Processing,BAQP),接着提出体现查询消耗资源负载量的查询期望代价矩阵(Query Expected Cost, QEC),最后,在分析Min-Min,Max-Min优缺点基础上提出新的基于平衡系统负载的自适应查询调度算法(Adaptive Min-Min and Max-Min,A-MM)算法,并得到理想测试结果。
1 BAQP
BAQP通过监测、预测、规划、执行和反馈五个环节来实现自适应的系统负载平衡,如图1。
图片
图1
BAQP模块结构
监测与元数据服务联系,系统通过Crown[8]获取数据资源静态、动态信息,同时监测模块接受查询处理请求执行情况的反馈,将请求与资源信息统一考虑,提交给评估模块并对当前系统资源和请求状况进行评估。
评估模块根据自适应方法获得资源状态阈值,并通过预测判断系统CPU、内存剩余,服务器用户量负载和网络I/O的下一阶段资源状态,决定该资源是否可以参与调度规划,以提高执行效率。
规划模块是一个查询调度算法实现,根据当前设定的系统目标函数,寻找出最优(或次优)的查询规划,同时由于动态在线规划,对规划性能要求比较高,本文提出一种新的算法,能在保证用户服务质量前提下,平衡系统负载。
执行模块提取已规划的具体查询请求,负责监督各查询进程情况,同时负责实时将查询操作状况反馈给监测模块,执行模块还可以协调不同查询任务之间的关系,例如支持由多个查询任务组成的流程控制。
反馈模块收集查询执行的动态实时信息,将其反映到监测模块中与资源信息合并提交新的评估和规划。
整个自适应查询处理是一个循环往复的过程,在这过程不断地吸收系统资源和查询请求变化,通过不断地力图寻求最优(或次优)方案,达到系统对变化适应性的效果。
┑4期 ┖钣碌:在线课程下的自适应查询调度算法
┆扑慊应用 ┑30卷
2 A-MM查询优化算法
查询优化算法是BAQP规划组件的核心部件,主要功能是动态制定查询与资源的映射方案。查询处理过程中任务分配到的资源,可能只占用系统资源的一部分或全部;同样,一个查询在资源上运行时间可能从几秒到几小时。所以定义以下概念。
ё试吹ピ 查询处理过程中,分配给查询的最小资源数量单位,记为R,每个资源单元包括四个子单元:CPU资源单元R┆cpu、内存资源单元R┆memory、服务器资源单元R┆server和带宽资源单元R┆bandwidth。
时间单元 查询处理过程中,查询占用时间的最小单元t。
消耗资源单元量 一个请求消耗的资源单元数量,记为Q(i)。消耗资源单元包括四个子单元:CPU消耗资源单元量Q┆cpu、内存消耗资源单元Q┆memory、服务器消耗资源单元Q┆server和带宽消耗资源单元Q┆bandwidth。
元查询请求 查询请求一旦开始执行,查询与执行资源关系保持不改变,直到查询执行结束为止,不存在迁移过程。
资源集合 R={R1, R2,…,Rn},Ri由现存资源单元量组成,表示可提供的资源量;查询请求队列任务集合为Q={Q1, Q2,…,Qn },Qi由消耗资源单元量组成,表示查询消耗的资源量。
查询期望代价矩阵 QEC(Query Expect Cost)。QEC(i,j)值为子查询任务Q(i)在资源R(j)上的资源负载耗费比值:
QEC(i,j)=χ×Ncost(i,j)+β×work_load(i,j)(1)
其中,Е+β=1,权值可根据性能相关性取静态值,也可根据用户需求动态取值。
Ncost(i, j)为子查询Q(i)在资源R(j)上带宽负载耗费值:
Ncost(i, j)=R┆bandwidth(j)/Q┆bandwidth(i)(2)
Р檠i耗费资源单元量可根据文件大小和传输协议获得。
work_load(i,j)为查询i在资源j上服务端资源负载耗费值:
work_load(i,j)=∑3k=1αk×work_load(i,j,k);
∑3k=1αk=1(3)
其中:work_load(i,j,k)分别代表查询i和资源j的CPU,内存,服务器的(查询资源耗费单元量/资源单位量)值;αk可取固定值,也可以动态取值。
表1为查询队列Q1,…,Q5对资源R1的资源负载耗费值。参考公式(1~3)中的取值方法,通过所有查询任务的消耗资源单元量与R1资源单元量之比得到表1。同样方法,可以得到查询在R2,R3,R4中占的负载消耗值表。
表2为查询任务和资源组建的QEC矩阵,QEC(1,1)通过式(1)计算过程如下:
本文设Е=0.6,β=0.4,同时α1,α2,α3е捣直鹞0.3,0.3,0.4。
work_load(1,1)=0.3×0.318B2+0.3×0.392B9+0.4×0.009B4=0.217B1
QEC(1,1)=0.6×0.064B5+0.4×0.217B1=0.125B5
表格(有表名)
表1 查询队列与R1У母涸叵耗值
查询队列CPU耗费内存耗费Server耗费Net 耗费
Q10.318B20.392B90.009B40.064B5
Q20.136B40.178B60.009B40.032B3
Q30.454B50.464B30.037B70.209B7
Q40.227B30.392B90.075B50.161B3
Q50.363B70.035B70.188B70.177B4
表格(有表名)
表2 QEC矩阵
查询队列R1R2R3R4
Q10.125B50.055B20.194B80.064B3
Q20.170B40.026B70.095B70.031B0
Q30.622B10.149B70.569B50.200B8
Q40.269B40.028B60.047B80.102B9
Q50.492B30.138B20.484B00.316B7
QEC(1,1)代表查询Q1在资源R1的查询期望代价,其值越大,说明查询消耗该资源的资源单元量越多,资源处理这个请求付出的负载代价越大。
在制定查询调度计划时既要找到消耗负载代价的资源,又要尽力平衡各资源的负载。Min-Min是一种执行效率高,执行速度快,被广泛应用的查询调度算法,但从文献[9]可知,当资源性能波动比较大时,Min-Min会出现负载不均衡现象,Min-Min只是在资源性能比较均匀的情况下负载能力较好,当性能震荡比较剧烈情况时与其对应的Max-Min算法负载能力更强。本文使用A-MM算法将 Max-Min算法的负载均衡性融入Min-Min中,将两个算法优点相结合,提高了整体算法效率。
定义1 Min_Cost判断数组。在QEC矩阵中分别取出各任务i对应所有资源j的最小QECij,并将其组成一维数组,记为Min_Cost,其中Min_Cost(i)= QECij。
定义2 相对标准偏差(Relative Standard Deviation,RSD)。
RSD=s/x(4)
其中:s=∑ni=1(xi-x)2n-1, s是样本标准偏差,表示样本参数的离散程度;x是样本均值, 相对标准偏差能较好地说明数据的分散程度。
A-MM算法基本思想是:
根据系统资源量表和查询消耗量表动态获得QEC矩阵,从QEC矩阵中得到Min_Cost数组,计算出Min_Cost数组的RSD值,记为Е巍H绻ξ值小于自适应获得的相对标准偏差临界值ξ′,说明Min_Cost数组中数值大小的波动比较小,即查询消耗资源的负载波动较均一,BAQP使用Min-Min算法;反之,则说明Min_Cost数组中数值大小的波动比较大,BAQP选择使用Max-Min算法。最后,通过循环、轮循选择,可以得到较Min-Min, Max-Min更优的负载均衡。其中,Е巍洫通过每次在循环选择时,在[0.1,1],每隔0.05取值,比较取不同值时的执行效果,获得执行效果最优的Е巍洫Ъ次相对标准偏差临界值。算法流程如图2所示。
3 评价方法
在MOOC系统中,当查询获得满足其最低资源单元量时,即可顺畅执行,所以对查询调度算法的性能评价,重点不是查询执行的速度或消耗的时间等问题,而是从系统资源角度考虑,算法制定的查询调度方案能否取得系统整体平衡,降低系统负载消耗。
定义资源iУ母涸叵耗系数值:
TR(i)=max (∑nk=1Qik/RS(i))(5)
其中:RS(i)为资源i的原有资源单元量;∑nk=1Qik为在资源i上执行的所有查询消耗量资源总和。
系统的总体负载消耗系数:
makeload=max (TR)(6)
makeloadе荡表系统中所有服务的负载消耗系数值中最大值,该值越小说明系统整体负载越小,算法的负载平衡能力越强。
图片
图2
A-MM算法流程
4 实验结果
通过考查执行算法获得的负载消耗系数来判定其性能,步骤如下。
4.1 模拟环境
1)建立资源队列R={R1,…,R4};Rk=[R┆cpu(k),R┆memory(k),R┆load(k),R┆net(k)],k=4,资源剩余单元量为一在[0,300]随机取值的4×4维矩阵;
2)建立远程查询队列Q={Q1,…,Q5},Qi=[Q┆cpu(i),Q┆memory(i),Q┆load(i),Q┆net(i)],i=5,查询资源消耗单元量为在[0,30]取值的5×4维矩阵;
3)根据1)~2),通过式(1)建立5×4维QEC矩阵;
4)使用A-MM,Min-Min和Max-Min算法对同一QEC进行运算,得出计算结果。
4.2 静态权值下性能对比
图3、4分别为A-MM,Min-Min和Max-Min在4资源、5任务及20资源、100任务各10次随机实验中的makeload值对比,makeload为总体负载消耗系数。从图3、4中可以看出,代表A-MM的点始终在其他算法下方或至少和最低点重合,重合原因是由于QEC值太过于平缓或幅度一直剧烈震荡,使得A-MM算法一直在使用Min-Min或Max-Min。实验说明10种场景下A-MM较其他算法平衡负载能力强,降低了整个系统的负载率。
4.3 动态权值下性能对比
式(1)、(3)中的权值可变,主要因为不同查询对资源性能需求的侧重点不同。有些查询对CPU量需求更大,有些可能对内存需求更大,所以,针对不同查询请求设定不同查询权值。例如,传输视频文件可以采用第2章中假设的固定权值,而对于一些需要计算更多缓存的数据类型,就需要不同的权值。本节使用4.1节环境,评测算法在权值动态变化情况下的性能。式(1)中的Е,βг[0,1]随机取值,和为1,式(3)中的Е联kг[0, 1]随机取值,А3k=1αk=1。实验结果如图5、6所示。
图片
图3 静态权值下4资源、5任务查询调度算法性能
图片
图4 静态权值下20资源、100任务查询调度算法性能
图片
图5 权值动态变化时4资源、5任务下查询调度算法性能
图片
图6 权值动态变化时20资源、100任务下查询调度算法性能
从图5、6中可知,纵坐标makeload为总体负载消耗系数,代表A-MM的点始终低于或等于每个场景中的最低点,所以可知A-MM在权值动态变化下依然保持了良好的平衡负载能力。
5 结语
本文提出的以平衡系统负载为目的的自适应查询处理器BAQP能较好地解决当前MOOC系统面临的负载平衡问题,从整体降低系统成本。该处理器根据资源状态和查询信息动态建立资源负载耗费矩阵,并结合Min-Min的执行高效性和Max-Min的负载均衡性,提出新的A-MM查询调度算法。不管取静态权值,还是动态权值,该算法都能较好地降低系统负载。以后要改进的工作主要集中在将BAQP组件移植到“国家精品课程”项目中,进行实际性能评测。
参考文献:
[1]PRESTON J, BOOTH L, CHASTINE J. Improving learning and creating community in online courses via MMOG technology[C]// Proceedings of the 35th SIGCSE Technical Symposium. Norfolk: ACM Press, 2004,3: 175-180.
[2]VLAD N, ALEXANDRU I, RADU P, et al.Efficient management of data center resources for massively multiplayer online games[C]// International Conference on High Performance Computing, Networking, Storage and Analysis. Austin: IEEE Computer Society Press, 2008: 212-244.
[3]ZHAO C, CAO J, WU H, et al. Handbook of Research on P2P and Grid Systems for Service-Oriented Computing: Models, Methodologies and Applications [M]. [S.l.]: IGI Publishing, 2009.
[4]LIU SHUO, SKARIMI L. Grid query optimizer to improve query processing in grids [J]. Future Generation Computer Systems, 2008,24(5): 342-353.
[5]ZHOU Y, TAN K. An adaptable distributed query processing architecture [J]. Data & Knowledge Engineering, 2005,53(3):283-309.
[6]BLYTHE J, JAIN S, DEELMAN E, et al.Task scheduling strategies for workflow based applications in grids[C]// CCGrid 2005: IEEE International Symposium on Cluster Computing and the Grid. Los Alamitos: IEEE Computer Society,2005,2: 759-767.
[7]MAHESWARAN M, ALI S, SIEGEL H, et al.A comparison of dynamic strategies for mapping a class of independent tasks onto heterogeneous computing systems[C]// Eighth Heterogeneous Computing Workshop. [S.l.]: IEEE, 1999:30-44.
[8]怀进鹏, 胡春明, 李建欣. CROWN:面向服务的网格中间件系统与信任管理[J].中国科学:E辑(信息科学), 2006,36(10): 1127-1155.
[9]HOU YONG, YU JIONG, TURGUN.NDA-MM: A new adaptive task scheduling algorithm based on the non-dedicated constraint grid[C]// IEEE Transactions on Sixth International Conference on Grid and Cooperative Computing. Wulumqi: IEEE, 2007: 275-281.