Previous | Next --- Slide 34 of 60
Back to Lecture Thumbnails
Jing

Just curious, is this queue scheduling method now state-of-the-art method for tasks assignments in distributed environment ? (such as mapreduce on hadoop). Seems somewhat easy to think of, we just dynamically assign task to the least busy worker. Is there subtlety or more serious issue that is ignored here in a real production system (from the tasks assignments point of view)?

oulgen

@Jing From a cursory google search, task assignment in Hadoop still seems to be an open topic that has many papers published on it. One interesting paper that I found on the internet is this paper from Yale: http://cs.yale.edu/homes/xs45/pdf/fsy-spaa2010.pdf

In this paper, they talk about how optimal distribution cannot be calculated in polynomial time unless P = NP and then they proceed to explain their distribution method.

Also, as an answer to your question what is the current method: it is plain round robin.

kayvonf

Question: Often Hadoop is used to process very large datasets. Imagine that instead of 16 tasks here, we had 1 million. Assuming we're running this code on a 4-core system, and that most of the tasks are roughly the same cost at the short ones above, but the last task was again about ten times longer than the rest. Would we still have the same problem as that illustrated on the next slide?

xwenwenwen

I think we won't have the same problem on the next slide because as the next slide shows, we have so many tasks that hopefully the "long pole" could be hidden (or get shorter) relative to overall execution time when they are scheduled across the cores. The longest task is only 10 times longer than the rest, and we have 1 million tasks to be executed.

msebek

If hadoop is truly being used for batch processing, then an occasional job that is only 10x as long could be hidden among the other jobs in the batch. For more speed-oriented distributed processing, such as Google Spark, this latency could become apparent.

If a hadoop job isn't distributing work to nodes (normally reducers) properly, though, a single node could be 1000x times as long. This is a lot of serializing on a small number of jobs, and work partitioning is a big problem with hadoop jobs.