基于MapReduce分级调度的试题库组卷算法研究

苑立娟

摘 要：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.