大数据处理框架中基于MDP的任务调度算法*

冯延蓬，仵 博，孟宪军，何国坤，江建举

（深圳职业技术学院 教育技术与信息中心，广东 深圳 518055）

MapReduce是一个用于大数据处理的分布式计算框架，是目前大数据处理平台使用最为广泛的并行编程模型[1]．MapReduce将待处理数据集分为若干独立的数据块，由map任务以完全并行的方式处理，然后对map任务的输出进行排序，并把结果输入给reduce任务．Hadoop[2]是由Google提出的基于MapReduce编程模型的开源实现，由分布式编程模型（MapReduce）和分布式存储系统（HDFS）组成，具有高可靠性、高扩展性、高效性和高容错性等优点，是对大数据进行分布式处理的典型框架．Hadoop得到业界和研究领域的共同关注，被众多大型公司选作业务平台，比如Yahoo、Facebook、Twitter等．

任务调度是MapReduce框架的重要组成部分，用户作业提交后，系统会将其划分为多个任务，通过调度算法决定将任务分配到哪个任务服务器上来执行．FIFO是 Hadoop默认的调度器，其优点是算法简单，便于实现，其缺点为仅以作业进入队列的先后顺序作为调度依据，无法针对作业的不同需求进行差异化调度．Zaharia M.等人提出一种公平调度（Fair Scheduler）算法[3]，在多用户共享集群的环境下，最大化地保证系统中的作业能平均分配到集群的资源．公平调度器能最大限度地满足公平性原则，但无法满足数据本地性要求．文献[4]提出一种延迟调度（Delay Scheduling）算法，为队首作业设置延迟等待时间，当空闲节点出现时，如果此节点包含队首作业所需数据，则立刻执行队首作业，否则先调度其它作业，在队首作业的等待时间超过阈值时，立即执行队首作业．延迟调度策略能够很好地做到公平性与数据本地性之间的均衡，延迟调度的等待时间是通过配置文件进行静态设置的，无法满足集群负载动态变化的情况[5]．

本文提出一种基于 Markov决策过程[6]的MapReduce任务调度算法（Markov Decision Process Scheduling，MDPS），使用状态空间描述集群中节点的负载情况和作业相关的数据本地性情况，通过状态转移函数描述调度前后节点和作业的变化，使用回报函数描述数据本地性、作业等待时间和节点负载的综合回报，利用值迭代策略求解算法求解最优调度策略，动态调节作业数据本地性与作业响应时间，达到最优调度的效果．

1 基于 Markov决策过程的调度算法

1.1 Markov决策过程

Markov决策过程（Markov Decision Process，MDP）是为Agent进行智能决策建立的数学模型，如图1所示．

1）S：状态集，表示Agent所有可能状态的集合；

3）T (s,a,s')：状态转移函数，表示在状态s下执行动作a，状态变为 s '的概率；

4）R (s,a)：回报函数，表示在状态s下执行动作a获得的回报值．

MDP使用状态集对当前集群与任务状态进行描述，通过回报函数对任务调度策略进行评估，使用值迭代算法进行最优策略求解，获得最优的任务调度策略．

1.2 算法建模

图1 MDP模型

在运行MapReduce的集群中，将选择一个节点作为JobTracker，该节点是MapReduce的核心部件，用来完成任务调度与监控功能．将JobTracker作为一个Agent，需要根据当前集群负载状态和不同任务的数据本地性需求，求取一个最优调度策略，其本质是一个最优决策求解问题，首要任务是建立MDPS的形式化描述模型．

（1）状态集S用来描述当前集群中节点负载状态和任务的数据本地性需求，因此状态集其中，Snode表示集群中节点的负载状态，若集群共包括n个节点，则使用一个n维向量表示，如式（1）所示：

（2）动作集A为 JobTracker可能采取的所有策略集合，即按照可能采取的策略，可定义 ai的取值为：

（3）状态转移函数T，表示在JobTracker选定某个调度策略后，系统从当前状态变化到下一状态的概率．由于状态子集Snode和Stask相互独立，按照可分解的思想，可以对Snode和Stask分别构建状态转移函数Tnode和Ttask．对于Ttask，由于任务对节点的数据本地性不受动作选择节点的影响，只与任务的初始设定相关，可得Ttask如式（4）所示：

对于 Tnode，节点若被分派新任务，则节点的负载会增加，s_ni'相对 s_ni增加的概率较大；若节点未分派新任务，则 s_ni'相对 s_ni不变的概率较大，对应的 Tnode定义如表1所示，其中d为非负数，取值为节点增加一个任务所增加的负载值，表中取值为本文实验中使用的值，在实际使用中可根据具体情况进行调节．

医学分子生物学是医学院校学生重要的基础理论课程之一，以分子生物学的方法来研究中医药，阐明中医辨证原理及中药的作用机理，才能加快中医学走向世界的步伐。中医专业的学生肩负将传统医学发扬光大的使命，分子生物学的理论和实验技术将成为有力的工具。多年来，通过不断改进教学方法，从教材的选择，教学内容的优化，加强教学过程中的各个环节等方面进行探索和实践，在中医专业医学分子生物学的教学过程中取得了较好的效果。今后还要不断努力，为社会培养更多高素质人才。

（4）回报函数R使用任务数据迁移的代价、数据本地性需求和节点负载的加权综合指作为模型的回报值，如式（5）所示：

其中，调节因子 a+b+g=1(a³0,b³0,g³0)，通过调节a、b和g的取值，可以根据不同的任务需求来设定回报函数中每一部分的权重．

表1 nodeT 定义

1.3 求解算法流程

MDPS调度算法求解目标即根据当前节点与任务的状态计算最优策略p，目标是使得长期回报值最大．MDP策略求解有多种算法，本文使用应用最为广泛的值迭代求解算法[7]．

在值迭代算法中，t时刻的回报函数可以通过当前状态，回报函数，状态转移函数以及 1t- 时刻的回报值求取，如式（6）所示．

迭代结束条件如式（7）所示：

迭代结束后，通过公式（8）求解最优策略

表2 MDPS求解算法

MDPS调度求解算法流程使用值迭代（如表2）来求解最优策略，迭代次数决定了最终求解结果的运算时间和精度，如果迭代次数过少，则无法得到足够的精度，如果迭代次数过多，则导致运算开销过大，可以通过调整e的取值来控制迭代次数．

2 实验与结果分析

2.1 实验环境

实验平台由10台曙光A840r-H组成，配置为：4*8378 CPU，16GB 内存，2*300G 15K 硬盘，256M SAS RAID 卡，2*4GB HBA 卡，2*1000M 集成网卡．采用Hadoop版本为0.21.0，通过对原有调度器包的替换和配置文件修改，运行本文的MDPS算法．

将本文MDPS算法与FIFO算法、Fair算法和Delay算法进行比较，针对每个算法所运行的环境，作业的设置和数据分布均一致．选取文本搜索作为实验对象，处理大小为256M～4G的5组样本，样本来自作者所在高校校园一卡通系统的消费记录，目的是匹配某些账号的消费记录．针对5组不同的数据样本，每组测试10个作业，值迭代求解中折扣因子g=0.95．

2.2 结果比较

从数据本地性和作业响应时间两个方面对实验结果进行分析．

图2表示了四种算法在5组样本下的数据本地性的比较．FIFO算法由于只考虑进入队列的先后，因此数据本地性存在随机性．Fair算法未考虑数据本地性，在处理数据较少时，其数据本地性低于FIFO算法，当处理数据较多时，其数据本地性与FIFO算法相当．Delay算法与本文MDPS算法在数据本地性上表现较好，不管处理数据的多少，数据本地性均维持较高水平．

图3表示四种算法在5组样本下的任务响应时间的比较．在处理数据较少时，四种算法任务响应时间差别较小．随着处理数据的增多，FIFO算法的响应时间相比其它三种算法明显增加．与Fair算法和Delay算法相比，本文的MDPS算法在任务响应时间上具有优势．

图2 数据本地性比较

图3 作业响应时间比较

3 结 论

本文使用 Markov决策过程对大数据处理框架MapReduce中的任务调度算法进行建模，采用值迭代求解算法实现最优调度策略求解．该算法可以在获得较好的数据本地性和较短的任务响应时间的同时，平衡节点的负载，提高集群的整体性能，通过实验，验证了提出算法的有效性和优越性．

[1] 李建江，崔健．MapReduce并行编程模型研究综述[J]．电子学报，2Ol1（11）：2636-2641．

[2] Apache Hadoop[EB/OL]．http://hadoop.apache.org/, 2012 March．

[3] Zaharia M, Borthakur D, Sarma J S, et al．Job Scheduling for Multi user Mapreduce Clusters[J]．EECS Department, 2009，55：1-16．

[4] Zaharia M，Borthakur D，Sarma J S，et al．Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling[C]．Proc of the EuroSys，2010：265-278．

[5] 宁文瑜，吴庆波，谭郁松．面向MapReduce的自适应延迟调度算法[J]．计算机工程与科学，2013，35（3）：52-57．

[6] Alexander L. Strehl and Michael L. Littman. An Empirical Evaluation of Interval Estimation for Markov Decision Processes[C]// The 16th IEEE International on Tools with Artificial Intelligence Conference. Washington,DC, USA: IEEE Computer Society, 2004：128-135．

[7] Kaelbling L，Littman M L，Cassandra A R．Planning and acting in partially observable stochastic domains[J]．Artificial Intelligence, 1998，101（1/2）：99-134．