Hadoop中Speculative Task调度策略

标签: Hadoop-MapReduce Hadoop,推测式任务 | 发表时间:2012-03-22 17:03 | 作者:Dong
出处:http://dongxicheng.org
作者: Dong | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及 版权声明
网址: http://dongxicheng.org/mapreduce/hadoop-speculative-task/

1. 背景

Speculative Task,又叫推测式任务,是指在分布式集群环境下,因为程序bug,负载不均衡或者资源分布不均,造成同一个job的多个task运行速度不一致,有的task运行速度明显慢于其他task(比如:一个job的某个task进度只有10%,而其他所有task已经运行完毕),则这些task拖慢了作业的整体执行进度,为了避免这种情况发生,Hadoop会为该task启动speculative task,让该speculative task与原始task同时运行,哪个先运行完,则使用它的结果。

Speculative Task思路是以空间换时间的,同时启动多个相同task,哪个完成的早,则采用哪个task的结果,这样明显可以提高任务计算速度,但是,这样却会占用更多的资源,在集群资源紧缺的情况下,合理的控制Speculative Task,可在多用少量资源情况下,减少大作业的计算时间。

本文主要介绍了Hadoop各个版本中Speculative Task设计思路,并指出了各自的不足及改进之处。

2. Hadoop 0.20.2和1.0.0中的算法

【算法流程】

如果一个task满足以下条件,则会为该task启动speculative task:

(1)该task还未启动任何speculative task(TaskInProgress仅对应一个running的task)

(2)在60s内落后(同一个作业所有task的)平均进度20%

某个Task可能对应多个正在运行的attempt task,任何一个运行结束,则会kill(不是fail)其他task。

【相关代码】


boolean hasSpeculativeTask(long currentTime, double averageProgress) {
// these constants should be examined
// in more depth eventually...
//
  if (!skipping && activeTasks.size() <= MAX_TASK_EXECS &&
     (averageProgress - progress >= SPECULATIVE_GAP) &&
         (currentTime - startTime >= SPECULATIVE_LAG)
            && completes == 0 && !isOnlyCommitPending()) {
    return true;
  }
  return false;
}

【存在问题】

以上算法可能造成以下几个问题:

(1) 作业的某个task被卡在87.7%处(MAPREDUCE-94)

(2) 当作业将要运行结束时,总不会启动speculative task

(3)  各个参数不可配置(SPECULATIVE_GAP,SPECULATIVE_LAG),不够灵活。

3. Hadoop 0.21.0中的算法

为了对Hadoop-0.20.2中的算法进行改进,Hadoop-0.21.0进行了以下优化:

(1) 添加了三个可配置选项

mapreduce.job.speculative.slownodethreshold,默认是1,用于判断某个TaskTracker是否适合启动某个task的speculative task

mapreduce.job.speculative.slowtaskthreshold,默认是1,用于判断某个task是否可以启动speculative task

mapreduce.job.speculative.speculativecap, 默认是0.1,用于限定某个job最多同时启动的spculative task的数目

(2) 限定条件

如果一个tasktracker/job/task满足以下条件,则会在该tasktracker上为该task启动一个speculative task:

(1)  Job已经启动的specutive task数目小于SpeculativeCap

(2) 该TaskTracker上该Job的所有task平均进度不小于SlowNodeThreshold,具体判断方法为:

tasktracker. mean-job.progessRate >job.std*job. SlowNodeThreshold

其中,tasktracker. Mean为该job在该tasktracker正在运行/已经运行完成的task的平均进度,job.progessRate为该作业的平均计算速度,job.std为该作业所有task计算速度的标准方差。

(3)  按照Task剩余时间,对Task进行排序

Task剩余时间定义为:(1-progress) / progressRate,其中process为task当前进度,progressRate为task的平均计算速度:progressRate= progress/deltaTime,其中deltaTime为该task启动以来所经历的时间

(4) 选择一个剩余时间最多,且 mean-progessRate >std*SlowTaskThreshold的task,并为该task启动speculative task,,其中mean为所有task平均计算速度,std为所有task计算速度的标准方差。

(3) 存在问题

(1) MAPREDUCE-2062

当一个作业只有一个task时,所有task的计算速度的标准方差为0,因而,总会为这样的作业启动speculative task

如果一个作业仅有一个task正在运行,则所有task的标准方差仍未0,Hadoop很可能为其他所有task启动speculative task。

(2) MAPREDUCE-3895

在Hadoop中,reduce task进度(对应上面的progress变量)计算很不合理,采用的方法是,将reduce task分为三个子过程:shuffle(copy),sort和reduce,各个阶段占进度的1/3,比如,一个task的shuffle阶段刚结束,它的进度应该是33.3%。 对于大部分作业,reduce task的进度变化并不是均匀的,一个task在某一时刻进度为33.3%,下一秒进度可能变为66.6%,这主要是因为sort阶段所做工作非常少,时间很短。也正是由于以上原因,reduce task很容易被误判速度过慢,进而启动speculative task。一种可行的解决方案是将sort阶段利用某个数学模型平滑处理。

4. 终极解决方案

拖后腿task出现的原因是系统负载不均衡和资源分配不均。尤其是在异构Hadoop集群中,拖后腿task会经常出现,而且最好不要打开speculative task功能,否则会出现大量的speculative task,造成严重的资源浪费,因为当前所有的speculative task解决方案均是假设集群是同构的。

为什么会造成这种问题?根本原因这种基于speculative task来解决拖后腿task是有问题的。拖后腿task最终应该通过调度器解决:每个TaskTracker通过heartbeat汇报自己机器上的资源分布情况和当前资源使用情况,比如CPU个数,CPU利用率,内存剩余量,IO负载等,然后由调度器根据当前资源使用情况,动态对任务进行调度(参考 https://issues.apache.org/jira/browse/MAPREDUCE-1380),进而最大限度避免产生拖后腿task。

关于拖后腿task,还有一个需要解决的问题是,防止为某个task启动speculative task后,该task又变成拖后腿task,比如:某个node上所有task均往一个磁盘上写数据,且该磁盘负载很重,而此时又将一个speculative task调度到该节点上(也往该磁盘上写数据),此时,该speculative task变得缓慢,因而有人提出了Hadoop disk scheduler,具体参考: https://issues.apache.org/jira/browse/MAPREDUCE-2636

5. 关于Speculative Task的Hadoop代码

Hadoop中,关于推测式任务的相关代码均在文件JobInProgress.java和TaskInProgress.java中,JobInProgress.java主要函数定义如下:


  protected synchronized TaskInProgress findSpeculativeTask(
    Collection<TaskInProgress> list, String taskTrackerName,
      String taskTrackerHost, TaskType taskType) {….}

TaskInProgress.java中主要函数定义如下:

  boolean canBeSpeculated(long currentTime){…}

原创文章,转载请注明: 转载自 董的博客

本文链接地址: http://dongxicheng.org/mapreduce/hadoop-speculative-task/


Copyright © 2008
This feed is for personal, non-commercial use only.
The use of this feed on other websites breaches copyright. If this content is not in your news reader, it makes the page you are viewing an infringement of the copyright. (Digital Fingerprint:
)

相关 [hadoop speculative task] 推荐:

Hadoop中Speculative Task调度策略

- - 董的博客
Dong | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及 版权声明. 网址: http://dongxicheng.org/mapreduce/hadoop-speculative-task/. Speculative Task思路是以空间换时间的,同时启动多个相同task,哪个完成的早,则采用哪个task的结果,这样明显可以提高任务计算速度,但是,这样却会占用更多的资源,在集群资源紧缺的情况下,合理的控制Speculative Task,可在多用少量资源情况下,减少大作业的计算时间.

hadoop输入分片计算(Map Task个数的确定) - 有无之中

- - 博客园_首页
  作业从JobClient端的submitJobInternal()方法提交作业的同时,调用InputFormat接口的getSplits()方法来创建split. 默认是使用InputFormat的子类FileInputFormat来计算分片,而split的默认实现为FileSplit(其父接口为InputSplit).

Task运行过程分析

- - 互联网 - ITeye博客
Map Task分解成Read、Map、Collect、Spill、Combine五个阶段,Reduce Task分解成Shuffle、Merge、Sort、Reduce、Write五个阶段. Read阶段:Map Task通过用户编写的RecordReader,从输入InputSplit中解析出一个个key/value;.

backlogs自定义task的状态

- - CSDN博客研发管理推荐文章
这点完胜IceScrum,在多人协作的时候,不同的角色需要围绕着一个task协作. 这时候,默认的状态可能不够用或者. 一些人提出要可以定制两个状态,比如QA verified. 其实熟悉Redmine的人可以直接定制. 我已经回答了该issue,下面是测试样例的截屏:. 作者:sheismylife 发表于2014-2-11 21:16:30 原文链接.

强大、简洁、优雅、免费——iPhone应用Task This

- king - 葡挞生活
iPhone上的To-do软件看过试过不少,最好的那几款都是收费的,免费版本都有诸多限制;纯免费的软件经常缺这少那,设计也很多不合理之处. 然而这一切终于改变了——因为有了Task This.. 功能强大和界面简洁似乎常常水火不容. 每当整理收集箱的任务时,看着一长串需要填写的选项,总不禁有几分烦闷.

Task Coach:个人事务(待办事项)管理工具

- - 软件志
三、Task Coach相关下载信息: Windows  ||  Mac OS X ||  Linux ||  BSD  iPhone and iPod Touch ||  官方主页.

JBPM具体应用之task节点的使用

- - CSDN博客综合推荐文章
task节点是最常用的节点之一,也因为执行任务的情况有很多种,所以他的用法也是多种多样的,本文主要讲解task的三种用法分别如下:. 1.candidate属性. 该熟属性在于task节点中,他的作用类似于组内工作分配,假如一个组内有两个人a1和a2,将该属性所在任务分配给两人中的一个后,则只有该任务被分配人才能看到任务,其他人都看不到.

LTS 轻量级分布式任务调度框架(Light Task Schedule)

- - Java - 编程语言 - ITeye博客
LTS是一个轻量级分布式任务调度框架,参考hadoop的部分思想. 有三种角色, JobClient, JobTracker, TaskTracker. 各个节点都是无状态的,可以部署多个,来实现负载均衡,实现更大的负载量, 并且框架具有很好的容错能力. 采用Zookeeper暴露节点信息,master选举.

Hadoop Streaming 编程

- - 学着站在巨人的肩膀上
Hadoop Streaming是Hadoop提供的一个编程工具,它允许用户使用任何可执行文件或者脚本文件作为Mapper和Reducer,例如:. 采用shell脚本语言中的一些命令作为mapper和reducer(cat作为mapper,wc作为reducer). 本文安排如下,第二节介绍Hadoop Streaming的原理,第三节介绍Hadoop Streaming的使用方法,第四节介绍Hadoop Streaming的程序编写方法,在这一节中,用C++、C、shell脚本 和python实现了WordCount作业,第五节总结了常见的问题.

Hadoop使用(一)

- Pei - 博客园-首页原创精华区
Hadoop使用主/从(Master/Slave)架构,主要角色有NameNode,DataNode,secondary NameNode,JobTracker,TaskTracker组成. 其中NameNode,secondary NameNode,JobTracker运行在Master节点上,DataNode和TaskTracker运行在Slave节点上.