You are viewing a plain text version of this content. The canonical link for it is here.
Posted to mapreduce-dev@hadoop.apache.org by Venu Gopala Rao <ve...@huawei.com> on 2011/06/17 15:46:12 UTC

Quincy Fair Scheduler Vs Hadoop Fair Scheduler

Hi All,

 

   I have come across a Fair Scheduler published by Microsoft known as
Quincy Fair SCheduler. In this they compare Hadoop Fair Scheduler with
Quincy and say the Hadoop Scheduler has the following problems

 

1)  Sticky Slots - One drawback of simple fair scheduling is that it is
damaging to locality. Consider the steady state in which each job is
occupying exactly its allocated quota of computers. Whenever a task from job
j completes on computer m, j becomes unblocked but all of the other jobs in
the system remain blocked. Consequently m will be assigned to one of j's
tasks again: this is referred to as the "sticky slot" problem.

 

2) Fair Scheduler may not be able to utilize the Data locality to maximum
possible extent.

 

Does these problems get solved in the 0.21 or Next Gen Map Reduce?

 

Regards

Venu

 

 

 


Re: Quincy Fair Scheduler Vs Hadoop Fair Scheduler

Posted by Harsh J <ha...@cloudera.com>.
Arun,

Small question: Is MR-517 included in the 203 release? Asking cause it
may appear so from your comments and the JIRA may need a resolved in:
field for the same :)

On Wed, Jun 22, 2011 at 12:53 AM, Arun C Murthy <ac...@yahoo-inc.com> wrote:
> Venu,
>
>
> On Jun 17, 2011, at 7:16 PM, Venu Gopala Rao wrote:
>>
>> Does these problems get solved in the 0.21 or Next Gen Map Reduce?
>>
>
> The CapacityScheduler in both 0.20.203 and NextGen MR have significantly
> better scheduling for locality including a highly modified 'delay
> scheduling' algorithm Matei mentioned in his reply.
>
> The highlights are (via MAPREDUCE-517 for 0.20.203 -
> http://tinyurl.com/6e9qlun )
>
> # The CS tracks 'number of scheduling opportunities' missed by a job and
> gets jobs to use that to prevent starvation. AFAIK the FairScheduler uses
> 'time' rather than 'scheduling opportunities'.
> # I've also added 'pace' to the back-off by getting ensuring jobs do not
> back-off as aggressively as they make progress. At the end of a job, i.e.
> last 10 tasks of a job with 100k tasks,  latency is more important than
> perfect data-locality.
> # The implementation also gets small jobs to 'delay' less vis-a-vis larger
> jobs by weighing the size of job.
> # The implementation also ensures jobs with no locality requirements, e.g.
> sleep-job/randomwriter, do not have any 'delay'  since it doesn't make sense
> at all.
>
> Since we deployed the new CS (via 0.20.203) we've seen >100% improvement for
> locality of jobs in our production clusters.
>
> The NextGen MR CapacityScheduler has a very similar implementation to the
> one described above.
>
> hth,
> Arun



-- 
Harsh J

Re: Quincy Fair Scheduler Vs Hadoop Fair Scheduler

Posted by Arun C Murthy <ac...@yahoo-inc.com>.
Venu,


On Jun 17, 2011, at 7:16 PM, Venu Gopala Rao wrote:
>
> Does these problems get solved in the 0.21 or Next Gen Map Reduce?
>

The CapacityScheduler in both 0.20.203 and NextGen MR have  
significantly better scheduling for locality including a highly  
modified 'delay scheduling' algorithm Matei mentioned in his reply.

The highlights are (via MAPREDUCE-517 for 0.20.203 - http://tinyurl.com/6e9qlun 
  )

# The CS tracks 'number of scheduling opportunities' missed by a job  
and gets jobs to use that to prevent starvation. AFAIK the  
FairScheduler uses 'time' rather than 'scheduling opportunities'.
# I've also added 'pace' to the back-off by getting ensuring jobs do  
not back-off as aggressively as they make progress. At the end of a  
job, i.e. last 10 tasks of a job with 100k tasks,  latency is more  
important than perfect data-locality.
# The implementation also gets small jobs to 'delay' less vis-a-vis  
larger jobs by weighing the size of job.
# The implementation also ensures jobs with no locality requirements,  
e.g. sleep-job/randomwriter, do not have any 'delay'  since it doesn't  
make sense at all.

Since we deployed the new CS (via 0.20.203) we've seen >100%  
improvement for locality of jobs in our production clusters.

The NextGen MR CapacityScheduler has a very similar implementation to  
the one described above.

hth,
Arun

RE: Quincy Fair Scheduler Vs Hadoop Fair Scheduler

Posted by Venu Gopala Rao <ve...@huawei.com>.
Thanks Matei.

-----Original Message-----
From: Matei Zaharia [mailto:matei@eecs.berkeley.edu] 
Sent: Saturday, June 18, 2011 4:18 AM
To: mapreduce-dev@hadoop.apache.org
Subject: Re: Quincy Fair Scheduler Vs Hadoop Fair Scheduler

Hi Venu,

The paper compares against a naive implementation of fair scheduling, not
against the Hadoop Fair Scheduler. You can find out about the data locality
algorithms used in the Fair Scheduler in
http://www.cs.berkeley.edu/~matei/papers/2010/eurosys_delay_scheduling.pdf.
These are available in 0.21+, and they have also been in various
distributions of Hadoop (e.g. Cloudera's and Facebook's) for a while. I
don't think they got backported into 0.20.203 though and I'm not sure what
scheduling algorithm the next-gen team is doing for locality.

Matei

On Jun 17, 2011, at 6:46 AM, Venu Gopala Rao wrote:

> Hi All,
> 
> 
> 
>   I have come across a Fair Scheduler published by Microsoft known as
> Quincy Fair SCheduler. In this they compare Hadoop Fair Scheduler with
> Quincy and say the Hadoop Scheduler has the following problems
> 
> 
> 
> 1)  Sticky Slots - One drawback of simple fair scheduling is that it is
> damaging to locality. Consider the steady state in which each job is
> occupying exactly its allocated quota of computers. Whenever a task from
job
> j completes on computer m, j becomes unblocked but all of the other jobs
in
> the system remain blocked. Consequently m will be assigned to one of j's
> tasks again: this is referred to as the "sticky slot" problem.
> 
> 
> 
> 2) Fair Scheduler may not be able to utilize the Data locality to maximum
> possible extent.
> 
> 
> 
> Does these problems get solved in the 0.21 or Next Gen Map Reduce?
> 
> 
> 
> Regards
> 
> Venu
> 
> 
> 
> 
> 
> 
> 


Re: Quincy Fair Scheduler Vs Hadoop Fair Scheduler

Posted by Matei Zaharia <ma...@eecs.berkeley.edu>.
Hi Venu,

The paper compares against a naive implementation of fair scheduling, not against the Hadoop Fair Scheduler. You can find out about the data locality algorithms used in the Fair Scheduler in http://www.cs.berkeley.edu/~matei/papers/2010/eurosys_delay_scheduling.pdf. These are available in 0.21+, and they have also been in various distributions of Hadoop (e.g. Cloudera's and Facebook's) for a while. I don't think they got backported into 0.20.203 though and I'm not sure what scheduling algorithm the next-gen team is doing for locality.

Matei

On Jun 17, 2011, at 6:46 AM, Venu Gopala Rao wrote:

> Hi All,
> 
> 
> 
>   I have come across a Fair Scheduler published by Microsoft known as
> Quincy Fair SCheduler. In this they compare Hadoop Fair Scheduler with
> Quincy and say the Hadoop Scheduler has the following problems
> 
> 
> 
> 1)  Sticky Slots - One drawback of simple fair scheduling is that it is
> damaging to locality. Consider the steady state in which each job is
> occupying exactly its allocated quota of computers. Whenever a task from job
> j completes on computer m, j becomes unblocked but all of the other jobs in
> the system remain blocked. Consequently m will be assigned to one of j's
> tasks again: this is referred to as the "sticky slot" problem.
> 
> 
> 
> 2) Fair Scheduler may not be able to utilize the Data locality to maximum
> possible extent.
> 
> 
> 
> Does these problems get solved in the 0.21 or Next Gen Map Reduce?
> 
> 
> 
> Regards
> 
> Venu
> 
> 
> 
> 
> 
> 
>