Maestro : replica-aware map scheduling for MapReduce
MapReduce has emerged as a leading programming model for data-intensive computing. Many recent research efforts have focused on improving the performance of the distributed frameworks supporting this model. Many optimizations are network-oriented and most of them mainly address the data shuffling st...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/101331 http://hdl.handle.net/10220/16723 |
| _version_ | 1826129989123178496 |
|---|---|
| author | Ibrahim, Shadi Jin, Hai Lu, Lu He, Bingsheng Antoniu, Gabriel Wu, Song |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Ibrahim, Shadi Jin, Hai Lu, Lu He, Bingsheng Antoniu, Gabriel Wu, Song |
| author_sort | Ibrahim, Shadi |
| collection | NTU |
| description | MapReduce has emerged as a leading programming model for data-intensive computing. Many recent research efforts have focused on improving the performance of the distributed frameworks supporting this model. Many optimizations are network-oriented and most of them mainly address the data shuffling stage of MapReduce. Our studies with Hadoop demonstrate that, apart from the shuffling phase, another source of excessive network traffic is the high number of map task executions which process remote data. That leads to an excessive number of useless speculative executions of map tasks and to an unbalanced execution of map tasks across different machines. All these factors produce a noticeable performance degradation. We propose a novel scheduling algorithm for map tasks, named Maestro, to improve the overall performance of the MapReduce computation. Maestro schedules the map tasks in two waves: first, it fills the empty slots of each data node based on the number of hosted map tasks and on the replication scheme for their input data, second, runtime scheduling takes into account the probability of scheduling a map task on a given machine depending on the replicas of the task's input data. These two waves lead to a higher locality in the execution of map tasks and to a more balanced intermediate data distribution for the shuffling phase. In our experiments on a 100-node cluster, Maestro achieves around 95% local map executions, reduces speculative map tasks by 80% and results in an improvement of up to 34% in the execution time. |
| first_indexed | 2024-10-01T07:49:13Z |
| format | Conference Paper |
| id | ntu-10356/101331 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:49:13Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/1013312020-05-28T07:18:07Z Maestro : replica-aware map scheduling for MapReduce Ibrahim, Shadi Jin, Hai Lu, Lu He, Bingsheng Antoniu, Gabriel Wu, Song School of Computer Engineering IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (12th : 2012 : Ottawa, Canada) DRNTU::Engineering::Computer science and engineering MapReduce has emerged as a leading programming model for data-intensive computing. Many recent research efforts have focused on improving the performance of the distributed frameworks supporting this model. Many optimizations are network-oriented and most of them mainly address the data shuffling stage of MapReduce. Our studies with Hadoop demonstrate that, apart from the shuffling phase, another source of excessive network traffic is the high number of map task executions which process remote data. That leads to an excessive number of useless speculative executions of map tasks and to an unbalanced execution of map tasks across different machines. All these factors produce a noticeable performance degradation. We propose a novel scheduling algorithm for map tasks, named Maestro, to improve the overall performance of the MapReduce computation. Maestro schedules the map tasks in two waves: first, it fills the empty slots of each data node based on the number of hosted map tasks and on the replication scheme for their input data, second, runtime scheduling takes into account the probability of scheduling a map task on a given machine depending on the replicas of the task's input data. These two waves lead to a higher locality in the execution of map tasks and to a more balanced intermediate data distribution for the shuffling phase. In our experiments on a 100-node cluster, Maestro achieves around 95% local map executions, reduces speculative map tasks by 80% and results in an improvement of up to 34% in the execution time. 2013-10-23T06:52:50Z 2019-12-06T20:36:49Z 2013-10-23T06:52:50Z 2019-12-06T20:36:49Z 2012 2012 Conference Paper Ibrahim, S., Jin, H., Lu, L., He, B., Antoniu, G., & Wu, S. (2012). Maestro: Replica-Aware Map Scheduling for MapReduce. 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), 435-442. https://hdl.handle.net/10356/101331 http://hdl.handle.net/10220/16723 10.1109/CCGrid.2012.122 en © 2012 IEEE |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Ibrahim, Shadi Jin, Hai Lu, Lu He, Bingsheng Antoniu, Gabriel Wu, Song Maestro : replica-aware map scheduling for MapReduce |
| title | Maestro : replica-aware map scheduling for MapReduce |
| title_full | Maestro : replica-aware map scheduling for MapReduce |
| title_fullStr | Maestro : replica-aware map scheduling for MapReduce |
| title_full_unstemmed | Maestro : replica-aware map scheduling for MapReduce |
| title_short | Maestro : replica-aware map scheduling for MapReduce |
| title_sort | maestro replica aware map scheduling for mapreduce |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/101331 http://hdl.handle.net/10220/16723 |
| work_keys_str_mv | AT ibrahimshadi maestroreplicaawaremapschedulingformapreduce AT jinhai maestroreplicaawaremapschedulingformapreduce AT lulu maestroreplicaawaremapschedulingformapreduce AT hebingsheng maestroreplicaawaremapschedulingformapreduce AT antoniugabriel maestroreplicaawaremapschedulingformapreduce AT wusong maestroreplicaawaremapschedulingformapreduce |