ABSTRACT
Data center-scale clusters are evolving towards heterogeneous hardware for power, cost, differentiated price-performance, and other reasons. MapReduce is a well-known programming model to process large amount of data on data center-scale clusters. Most MapReduce implementations have been designed and optimized for homogeneous clusters. Unfortunately, these implementations perform poorly on heterogeneous clusters (e.g., on a 90-node cluster that contains 10 Xeon-based servers and 80 Atom-based servers, Hadoop performs worse than on 10-node Xeon-only or 80-node Atom-only homogeneous sub-clusters for many of our benchmarks). This poor performance remains despite previously proposed optimizations related to management of straggler tasks. In this paper, we address MapReduce's poor performance on heterogeneous clusters. Our first contribution is that the poor performance is due to two key factors: (1) the non-intuitive effect that MapReduce's built-in load balancing results in excessive and bursty network communication during the Map phase, and (2) the intuitive effect that the heterogeneity amplifies load imbalance in the Reduce computation. Our second contribution is Tarazu, a suite of optimizations to improve MapReduce performance on heterogeneous clusters. Tarazu consists of (1) Communication-Aware Load Balancing of Map computation (CALB) across the nodes, (2) Communication-Aware Scheduling of Map computation (CAS) to avoid bursty network traffic and (3) Predictive Load Balancing of Reduce computation (PLB) across the nodes. Using the above 90-node cluster, we show that Tarazu significantly improves performance over a baseline of Hadoop with straightforward tuning for hardware heterogeneity.
- R. Agrawal and R. Srikant. Fast algorithms for mining association rules. Proceedings of 20th Intl. Conference on Very Large Data Bases, VLDB, 1994. Google ScholarDigital Library
- Amazon EC2. http://aws.amazon.com/ec2.Google Scholar
- G. Ananthanarayanan, S. Kandula, A. Greenberg, I. Stoica, Y. Lu, B. Saha, and E. Harris. Reining in the outliers in Map-Reduce clusters using Mantri. In Proceedings of the Usenix Symposium on Operating Systems Design and Implementation (OSDI), 2010. Google ScholarDigital Library
- D. G. Andersen, J. Franklin, M. Kaminsky, A. Phanishayee, L. Tan, and V. Vasudevan. FAWN: A Fast Array of Wimpy Nodes. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), 2009. Google ScholarDigital Library
- Apache Mahout: Scalable machine learning and data mining. http://mahout.apache.org.Google Scholar
- A. C. Arpaci-Dusseau, R. H. Arpaci-Dusseau, D. E. Culler, J. M. Hellerstein, and D. A. Patterson. High-performance sorting on networks of workstations. In Proceedings of the SIGMOD International Conference on Management of Data, pages 243--254, Tucson,Arizona, May 1997. Google ScholarDigital Library
- Calxeda, Inc. http://www.calxeda.com.Google Scholar
- Q. Chen, D. Zhang, M. Guo, Q. Deng, and S. Guo. SAMR: A Self-adaptive MapReduce Scheduling Algorithm in Heterogeneous Environment. In Proceedings of the International Conference on Computer and Information Technology (CIT), 2010. Google ScholarDigital Library
- B.-G. Chun, G. Iannaccone, G. Iannaccone, R. Katz, G. Lee, and L. Niccolini. An Energy Case for Hybrid Datacenters. In SOSP Workshop on Power Aware Computing and Systems (HotPower), 2009.Google Scholar
- J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. Commun. ACM, pages 107--113, Jan. 2008. Google ScholarDigital Library
- Facebook Hive. http://hadoop.apache.org/hive.Google Scholar
- A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant Resource Fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX conference on Networked systems design and implementation(NSDI), 2011. Google ScholarDigital Library
- A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. VL2: A scalable and flexible data center network. In Proceedings of the SIGCOMM conference on Data Communication, pages 51--62, 2009. Google ScholarDigital Library
- Hadoop. http://lucene.apache.org/hadoop/.Google Scholar
- J. Hamilton. When Very Low-Power, Low-Cost Servers Don't Make Sense. In http://perspectives.mvdirona.com/2010/05/18/WhenVeryLowPowerLowCostServersDontMakeSense.aspx, 2010.Google Scholar
- B. He, W. Fang, Q. Luo, N. K. Govindaraju, and T. Wang. Mars: A MapReduce framework on graphics processors. In Proceedings of the 17th international conference on Parallel Architectures and Compilation Techniques, pages 260--269, 2008. Google ScholarDigital Library
- HP Labs. Project Moonshot. In http://www.hp.com/hpinfo/newsroom/press_kits/2011/MoonshotInfrastructure/index.html, 2011.Google Scholar
- M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: Distributed data-parallel programs from sequential building blocks. In EuroSys '07: Proceedings of the 2nd SIGOPS/EuroSys European Conference on Computer Systems, 2007. Google ScholarDigital Library
- M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, and A. Goldberg. Quincy: Fair scheduling for distributed computing clusters. In Proceedings of the 22nd symposium on Operating systems principles, SOSP, pages 261--276, USA, 2009. Google ScholarDigital Library
- V. Janapa Reddi, B. C. Lee, T. Chilimbi, and K. Vaid. Web search using mobile cores: Quantifying and mitigating the price of efficiency. In Proceedings of the International Symposium on Computer Architecture (ISCA), 2010. Google ScholarDigital Library
- J.Hartigan. Clustering Algorithms. Wiley, 1975. Google ScholarDigital Library
- A. Krioukov, P. Mohan, S. Alspaugh, L. Keys, D. E. Culler, and R. H. Katz. NapSAC: Design and implementation of a power-proportional web cluster. ACM Computer Communication Review, 41(1), 2011. Google ScholarDigital Library
- W. Lang, J. M. Patel, and S. Shankar. Wimpy node clusters: What about non-wimpy workloads? In Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2010. Google ScholarDigital Library
- K. Lim, P. Ranganathan, J. Chang, C. Patel, T. Mudge, and S. Reinhardt. Understanding and Designing New Server Architectures for Emerging Warehouse-Computing Environments. In Proceedings of the 35th Annual International Symposium on Computer Architecture (ISCA), pages 315--326, 2008. Google ScholarDigital Library
- M. D. Linderman, J. D. Collins, H. Wang, and T. H. Meng. Merge: A programming model for heterogeneous multi-core systems. In Proceedings of the 13th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2008. Google ScholarDigital Library
- Netflix movies data. http://www.netflixprize.com/download.Google Scholar
- C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins. Pig latin: a not-so-foreign language for data processing. In Proceedings of the 2008 international conference on Management Of Data, SIGMOD, pages 1099--1110, 2008. Google ScholarDigital Library
- M. M. Rafique, N. Ravi, S. Cadambi, S. T. Chakradhar, and A. R. Butt. Power Management for Heterogeneous Clusters: An Experimental Study. In Proceedings of the IEEE International Conference on Green Computing, 2011. Google ScholarDigital Library
- C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis. Evaluating MapReduce for Multi-core and Multiprocessor Systems. In 13th International Symposium on High Performance Computer Architecture, HPCA, pages 13--24, 2007. Google ScholarDigital Library
- SeaMicro, Inc. http://www.seamicro.com.Google Scholar
- A. Vahdat, M. Al-Fares, N. Farrington, R. N. Mysore, G. Porter, and S. Radhakrishnan. Scale-Out Networking in the Data Center. IEEE Micro, 30:29--41, July 2010. Google ScholarDigital Library
- D. Weld. Lecture notes on MapReduce (based on Jeff Dean's slides). http://rakaposhi.eas.asu.edu/cse494/notes/s07-map-reduce.ppt, 2007.Google Scholar
- X-RIME: Hadoop based large scale social network analysis. http://xrime.sourceforge.net/.Google Scholar
- H.-C. Yang, A. Dasdan, R.-L. Hsiao, and D. S. Parker. Map-reduce-merge: Simplified relational data processing on large clusters. In Proceedings of the SIGMOD international conference on Management Of Data, 2007. Google ScholarDigital Library
- Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. In Proceedings of International Symposium on Operating System Design and Implementation (OSDI), 2008. Google ScholarDigital Library
- M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, and I. Stoica. Delay Scheduling: A simple technique for achieving locality and fairness in cluster scheduling. In Proceedings of the 5th European conference on Computer systems, EuroSys '10, pages 265--278, 2010. Google ScholarDigital Library
- M. Zaharia, A. Konwinski, A. Joseph, R. Katz, and I. Stoica. Improving MapReduce performance in heterogeneous environments. In Proceedings of the Usenix Symposium on Operating Systems Design and Implementation (OSDI), 2008. Google ScholarDigital Library
- Hadoop rebalancer. http://hadoop.apache.org/common/docs/r0.17.2/hdfs_user_guide.html#Rebalancer.Google Scholar
Index Terms
- Tarazu: optimizing MapReduce on heterogeneous clusters
Recommendations
Tarazu: optimizing MapReduce on heterogeneous clusters
ASPLOS '12Data center-scale clusters are evolving towards heterogeneous hardware for power, cost, differentiated price-performance, and other reasons. MapReduce is a well-known programming model to process large amount of data on data center-scale clusters. Most ...
Tarazu: optimizing MapReduce on heterogeneous clusters
ASPLOS '12Data center-scale clusters are evolving towards heterogeneous hardware for power, cost, differentiated price-performance, and other reasons. MapReduce is a well-known programming model to process large amount of data on data center-scale clusters. Most ...
Performance Modeling of MapReduce Jobs in Heterogeneous Cloud Environments
CLOUD '13: Proceedings of the 2013 IEEE Sixth International Conference on Cloud ComputingMany companies start using Hadoop for advanced data analytics over large datasets. While a traditional Hadoop cluster deployment assumes a homogeneous cluster, many enterprise clusters are grown incrementally over time, and might have a variety of ...
Comments