基于MapReduce分级调度的试题库组卷算法研究
2014-07-02苑立娟
苑立娟
摘 要:MapReduce调度算法包括默认的FIFO调度策略、公平调度策略、计算能力调度策略,在试题库组卷过程中采用的是分阶段的任务方式来实现的,根据任务优化MapReduce算法是本文要解决的问题。提出分级调度算法,把现有的调度策略在分级任务基础之上分为多级模式,不断趋近最终结果,根据任务的不同阶段进行分级分阶调度符合不同阶段不同需求。实验表明,多阶段调度算法能够满足试题库组卷任务的检索需求。
关键词:云计算;MapReduce;分级调度;组卷
随着云计算不断的发展,各行各业都纷纷应用这种高效、安全和便捷的大数据、分布式服务。高等院校也都纷纷涉足云计算,分布式存储、MapReduce算法以及基于云计算的各种服务系统等都在高校研究中有所体现。高等院校考试系统的组卷过程是一个复杂的检索过程,而这一过程正是云计算的强项,因此组卷算法如何利用云计算中的MapReduce编程模型来实现是本文研究的主要方向。MapReduce是Google公司开发的Hadoop框架中进行分布式数据处理的一种编程模型。在组卷过程中主要关注两个问题:一个是组卷参数分级问题、一个是组卷分级任务中的各个级别的检索问题。MapReduce的任务调度过程是将一个任务分为多个子任务进行并行处理,这个过程正好与组卷的任务有相同之处。MapReduce的调度分为:先进先出、公平调度和计算能力评估调度。这几个调度算法对于特定的组卷任务来说并不是最优化的。试题库组卷的过程可以分为多级多阶段,将复杂的任务分层剥离。这样化繁为简,提高组卷的命中率和效率。本体提出了分级调度算法,该算法要解决的重要问题是:
首先,任务分级划界。MapReduce会将一个任务分解为多个子任务,而试题库组卷过程也是一个分级不断靠近需求的过程,本文第一层级任务确定题型和分数,第二层级任务根据题型和分数确定试题个数,第三层级任务对难度系数进行优化,第四层级任务迭代微调。其次,层级上下文衔接。一层级任务完成后,应该把结果及其参数传递给二层级,依次类推。
结合MapReduce的调度过程,本文提出了分级调度的概念,每级层调度选择该层级的较为优秀的调度方法。整个任务被分为多层有先后的子任务,每个任务为下层任务提供参数进行参考,该层任务提交给适合执行的对象来处理。
1 MapReduce任务调度过程
MapReduce是Hadoop框架的一种编程模式,是进行分布式数据处理的。它的关键在于Map(地图)和Reduce(化简)。第一阶段数据检索过程,Map获取系统或数据库中的子数据,根据用户设定好的Map函数将数据分为多个Key/Value对的子数据,排序后存储与在客户端。在化简阶段,Reduce任务读取相应的子数据,这样任务被分为多个子任务并行处理,提高数据处理的效率。整个过程处于主节点的控制之下,JobTracker负责对众多节点进行掌控。
2 多级分层调度思想
试题库组卷过程在本文中可分为四层到多层,基础为四层,如果得不到优化的结果,需要在最后一层进行不断迭代优化来满足用户需求。四层任务从上到下依次是:题型确定层,该层需要很短的时间,时间可以忽略不计,只要获取用户设定的题型即可;分数确定层,这一层同上,也是直接获得;而题型确定层和分数确定层之间的衔接问题应该要处理好,思路在于M为一个完整的一次组卷过程,这个过程定义如下所示:M=f1(f2(T,F),…,fn),M表示一个完整组卷任务,f1是任务分解函数,f2表示一层和二层衔接函数,fn表示N-1层和N层的衔接函数。这样首位呼应的衔接方式,确保了能在一下层级中获得上一层级的结果参数。紧接着就是难度系数确定层,获得试题个数和分数之后,根据个数和分数的配比比例来进行难度系统比例分配,这个分配过程要求用户提供配比比例,例如1:2:3等,如果由上层函数传遞过来的分数为20分,很容易获得难度个数比例,比例依次就是3:6:9+2,四舍五入最后多余的2道题则自动分配给难度最高的配比。当然,根据用户的设定的难度要求,这个2可以分配给难度系数为1的部分,也可以分配给难度系数为2的部分。这样任务就在第三层有了详细的处理过程,分配给调度器检索任务变的更加简单而有效了。当三层级处理完毕后可以将结果参数传递给四层级,进行题库覆盖任务的调度处理,那么这个过程同样也被细化了。
3 算法实现的流程
定义M函数,M=(T,F,N,C);T定义为题型,F为分数,N为难度系数,C其他用户要求参数类型。为任务1定义函数f1(T,F),通过MapReduce处理之后将结果x1赋值给函数f2,函数f2的定义为f2(N,x1),再次交给MapReduce处理将结果x2赋值给函数f3,f3定义为f3(x2,C)。将每个任务分别作为每个Mapper的输入,每个Mapper处理一个任务的数据,按需求执行运算(因为这里对数值和题目的比例不一样,调用的方法不一样)并产生结果,Reducer把多个Mapper的结果组合即完成一次组卷。Master主控程序将任务分配给Worker。Map任务负责检索,Reduce任务负责整合。Map任务根据条件进行数据检索,获得符合要求的题目的键值数据,将其传递给用户定义的Reduce()函数。Map产生的中间结果对缓冲到内存。Map函数缓冲的中间结果被定时写到本地磁盘,这些数据根据需求利用分区函数被分别放置。这些中间结果即试题的位置信息发送给Master,Master负责把该位置信息传递给Reduce()的Worker。通知传递后,Worker调用Map读取本地机器上试题信息,读取后标记这些数据为被选用数据,即标记该题被选用,选用次数加1。Reduce函数根据中间记过的key值进行遍历,把符合要求的数据集合后传递给Reduce,Reduce将结果存放在Master掌管的一个输出文件中。
用户程序综合所有数据,形成最终结果。
4 测试与分析
通过实验测试,本文介绍的分层级调度算法对于1500道题库4种题型分数为10,20,30,40难度系数比例为1:1:2,最终获得结果耗时2.35秒,对于3000道题库4种题型分数和难度系数比例同上的要求,最终获得结果耗时4.88秒,对于9000道题库4中题型分数和难度系数比例同上的要求,最终获得结果耗时7.12秒。可以获得效果是比较满意的。随着题库数量的不断增加时间耗时不断的增加,但是其结果是趋于越来越少的。
5 结束语
本文提出的分层级的试题库组卷算法基本满足了用户的要求,通过对任务的特定的层级进行分析,针对不同层级的不同要求选取适应的调度方式来满足要求,同时能够保证任务的并行性和时间的高效性。
[参考文献]
[1]刘吉,陈香兰.一种MapReduce实时调度算法设计及实现.计算机系统应用,2013,22(8):116-123.
[2]白东玲,郭绍永.改进的遗传算法在智能组卷系统中的应用研究.计算机与现代化,2013,(3):25-28.
[3]李钢.基于出题系统的随机算法.软件,2013,34(2):84-85.
[4]王凯,吴泉源.一种多用户MapReduce集群的作业调度算法的设计与实现.计算机与现代化,2010,(10):23-28.