research-article

Efficient shuffle management with SCache for DAG computing frameworks

Authors:

Haibing GuanAuthors Info & Claims

PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 305 - 316

https://doi.org/10.1145/3178487.3178510

Published: 10 February 2018 Publication History

Abstract

In large-scale data-parallel analytics, shuffle, or the cross-network read and aggregation of partitioned data between tasks with data dependencies, usually brings in large overhead. To reduce shuffle overhead, we present SCache, an open source plug-in system that particularly focuses on shuffle optimization. By extracting and analyzing shuffle dependencies prior to the actual task execution, SCache can adopt heuristic pre-scheduling combining with shuffle size prediction to pre-fetch shuffle data and balance load on each node. Meanwhile, SCache takes full advantage of the system memory to accelerate the shuffle process. We have implemented SCache and customized Spark to use it as the external shuffle service and co-scheduler. The performance of SCache is evaluated with both simulations and testbed experiments on a 50-node Amazon EC2 cluster. Those evaluations have demonstrated that, by incorporating SCache, the shuffle overhead of Spark can be reduced by nearly 89%, and the overall completion time of TPC-DS queries improves 40% on average.

References

[1]

Faraz Ahmad, Srimat T Chakradhar, Anand Raghunathan, and TN Vijaykumar. 2014. ShuffleWatcher: Shuffle-aware Scheduling in Multi-tenant MapReduce Clusters. In USENIX Annual Technical Conference. 1--12.

Digital Library

[2]

Ganesh Ananthanarayanan, Ali Ghodsi, Andrew Wang, Dhruba Borthakur, Srikanth Kandula, Scott Shenker, and Ion Stoica. 2012. PAC-Man: Coordinated memory caching for parallel jobs. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 20--20.

Digital Library

[3]

Ganesh Ananthanarayanan, Srikanth Kandula, Albert G Greenberg, Ion Stoica, Yi Lu, Bikas Saha, and Edward Harris. 2010. Reining in the Outliers in Map-Reduce Clusters using Mantri. In OSDI, Vol. 10. 24.

Digital Library

[4]

Apache. 2017. Apache Hadoop. (2017). http://hadoop.apache.com/

[5]

Apache. 2017. Apache Hadoop Tutorial. (2017). http://hadoop.apache.org/docs/current/hadoop-mapreduce-client/hadoop-mapreduce-client-core/MapReduceTutorial.html

[6]

Apache. 2017. Apache Spark 1.6.2 Configuration. (2017). http://spark.apache.org/docs/1.6.2/configuration.html

[7]

Shivnath Babu. 2010. Towards Automatic Optimization of MapReduce Programs. In Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC '10). ACM, New York, NY, USA, 137--142.

Digital Library

[8]

Laszlo A. Belady. 1966. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal 5, 2 (1966), 78--101.

Digital Library

[9]

Dazhao Cheng, Jia Rao, Yanfei Guo, and Xiaobo Zhou. 2014. Improving MapReduce performance in heterogeneous environments with adaptive task tuning. In Proceedings of the 15th International Middleware Conference. ACM, 97--108.

Digital Library

[10]

Mosharaf Chowdhury and Ion Stoica. 2015. Efficient Coflow Scheduling Without Prior Knowledge. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication (SIGCOMM '15). ACM, New York, NY, USA, 393--406.

Digital Library

[11]

Mosharaf Chowdhury, Matei Zaharia, Justin Ma, Michael I Jordan, and Ion Stoica. 2011. Managing data transfers in computer clusters with orchestra. In ACM SIGCOMM Computer Communication Review, Vol. 41. ACM, 98--109.

Digital Library

[12]

Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. 2014. Efficient coflow scheduling with varys. In ACM SIGCOMM Computer Communication Review, Vol. 44. ACM, 443--454.

Digital Library

[13]

Eslam Elnikety, Tamer Elsayed, and Hany E Ramadan. 2011. iHadoop: asynchronous iterations for MapReduce. In Cloud Computing Technology and Science (CloudCom), 2011 IEEE Third International Conference on. IEEE, 81--90.

Digital Library

[14]

Brad Fitzpatrick. 2004. Distributed Caching with Memcached. Linux J. 2004, 124 (Aug. 2004), 5-. http://dl.acm.org/citation.cfm?id=1012889.1012894

Digital Library

[15]

Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003. The Google file system. In ACM SIGOPS operating systems review, Vol. 37. ACM, 29--43.

Digital Library

[16]

Benjamin Gufler, Nikolaus Augsten, Angelika Reiser, and Alfons Kemper. 2012. Load balancing in mapreduce based on scalable cardinality estimates. In Data Engineering (ICDE), 2012 IEEE 28th International Conference on. IEEE, 522--533.

Digital Library

[17]

Herodotos Herodotou, Harold Lim, Gang Luo, Nedyalko Borisov, Liang Dong, Fatma Bilgen Cetin, and Shivnath Babu. 2011. Starfish: A Self-tuning System for Big Data Analytics. In Cidr, Vol. 11. 261--272.

[18]

Ewan Higgs, Animesh Trivedi, and Jeff Zhang. 2017. Spark Terasort. (2017). https://github.com/ehiggs/spark-terasort

[19]

Patrick Hunt, Mahadev Konar, Flavio Paiva Junqueira, and Benjamin Reed. 2010. ZooKeeper: Wait-free Coordination for Internet-scale Systems. In USENIX Annual Technical Conference, Vol. 8. 9.

Digital Library

[20]

Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, Vol. 41. ACM, 59--72.

Digital Library

[21]

Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg. 2009. Quincy: fair scheduling for distributed computing clusters. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles. ACM, 261--276.

Digital Library

[22]

Steven Y Ko, Imranul Hoque, Brian Cho, and Indranil Gupta. 2009. On Availability of Intermediate Data in Cloud Computations. In HotOS.

Digital Library

[23]

YongChul Kwon, Magdalena Balazinska, Bill Howe, and Jerome Rolia. 2012. Skewtune: mitigating skew in mapreduce applications. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, 25--36.

Digital Library

[24]

Haoyuan Li, Ali Ghodsi, Matei Zaharia, Scott Shenker, and Ion Stoica. 2014. Tachyon: Reliable, memory speed storage for cluster computing frameworks. In Proceedings of the ACM Symposium on Cloud Computing. ACM, 1--15.

Digital Library

[25]

Diego Ongaro, Stephen M Rumble, Ryan Stutsman, John Ousterhout, and Mendel Rosenblum. 2011. Fast crash recovery in RAMCloud. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 29--41.

Digital Library

[26]

Kay Ousterhout, Ryan Rasti, Sylvia Ratnasamy, Scott Shenker, Byung-Gon Chun, and V ICSI. 2015. Making Sense of Performance in Data Analytics Frameworks. In NSDI, Vol. 15. 293--307.

Digital Library

[27]

Bikas Saha, Hitesh Shah, Siddharth Seth, Gopal Vijayaraghavan, Arun Murthy, and Carlo Curino. 2015. Apache tez: A unifying framework for modeling and building data processing applications. In Proceedings of the 2015 ACM SIGMOD international conference on Management of Data. ACM, 1357--1369.

Digital Library

[28]

Jian Tan, Alicia Chin, Zane Zhenhua Hu, Yonggang Hu, Shicong Meng, Xiaoqiao Meng, and Li Zhang. 2014. Dynmr: Dynamic mapreduce with reducetask interleaving and maptask backfilling. In Proceedings of the Ninth European Conference on Computer Systems. ACM, 2.

Digital Library

[29]

TPC. 2017. TPC Benchmark DS (TPC-DS): The Benchmark Standard for decision support solutions including Big Data. (2017). http://www.tpc.org/tpcds/

[30]

Abhishek Verma, Ludmila Cherkasova, and Roy H Campbell. 2011. Resource provisioning framework for mapreduce jobs with performance goals. In ACM/IFIP/USENIX International Conference on Distributed Systems Platforms and Open Distributed Processing. Springer, 165--186.

Digital Library

[31]

Jeffrey S Vitter. 1985. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS) 11, 1 (1985), 37--57.

Digital Library

[32]

Yandong Wang, Jian Tan, Weikuan Yu, Li Zhang, Xiaoqiao Meng, and Xiaobing Li. 2013. Preemptive ReduceTask Scheduling for Fair and Fast Job Completion. In ICAC. 279--289.

[33]

David P Williamson and David B Shmoys. 2010. The Design of Approximation Algorithms. 2010. preprint http://www.designofapproxalgs.com (2010).

Digital Library

[34]

Chenning Xie, Rong Chen, Haibing Guan, Binyu Zang, and Haibo Chen. 2015. SYNC or ASYNC: Time to Fuse for Distributed Graph-parallel Computation. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015). ACM, New York, NY, USA, 194--204.

Digital Library

[35]

Matei Zaharia, Dhruba Borthakur, Joydeep Sen Sarma, Khaled Elmeleegy, Scott Shenker, and Ion Stoica. 2010. Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling. In Proceedings of the 5th European conference on Computer systems. ACM, 265--278.

Digital Library

[36]

Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2--2.

Digital Library

[37]

Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. 2016. Apache Spark: A Unified Engine for Big Data Processing. Commun. ACM 59, 11 (Oct. 2016), 56--65.

Digital Library

Cited By

Jia XYao ZPeng CZhao ZLei BLiu ELi XHe ZWang YZou XZhao CChu JWang JMiao CSekar VYu MSeneviratne AVeitch D(2024)Turbo: Efficient Communication Framework for Large-scale Data Processing ClusterProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672241(540-553)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672241
Wu SChen HJin HIbrahim S(2022)Shadow: Exploiting the Power of Choice for Efficient Shuffling in MapReduceIEEE Transactions on Big Data10.1109/TBDATA.2019.29434738:1(253-267)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TBDATA.2019.2943473
Cheng YWu CLiu YRen RXu HYang BQi Z(2020)OPS: Optimized Shuffle Management System for Apache SparkProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404430(1-11)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3404397.3404430
Show More Cited By

Index Terms

Efficient shuffle management with SCache for DAG computing frameworks
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
      1. Cloud computing

Recommendations

Efficient shuffle management with SCache for DAG computing frameworks
PPoPP '18

In large-scale data-parallel analytics, shuffle, or the cross-network read and aggregation of partitioned data between tasks with data dependencies, usually brings in large overhead. To reduce shuffle overhead, we present SCache, an open source plug-in ...
Some refinements of Stanley's shuffle theorem
Abstract
We give a combinatorial proof of Stanley's shuffle theorem by using the insertion lemma of Haglund, Loehr and Remmel. Based on this combinatorial construction, we establish several refinements of Stanley's shuffle theorem.
Supporting Data Shuffle Between Threads in OpenMP
OpenMP: Portable Multi-Level Parallelism on Modern Systems
Abstract
Both NVIDIA and AMD GPUs provide shuffle or permutation instructions to enable direct data movement between private registers of different threads. Since it doesn’t involve the shared memory or global memory on the device which are slower than ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 2018

442 pages

ISBN:9781450349826

DOI:10.1145/3178487

General Chair:
Andreas Krall
Vienna University of Technology, Austria
,
Program Chair:
Thomas R. Gross
ETH Zürich, Switzerland

ACM SIGPLAN Notices Volume 53, Issue 1
PPoPP '18
January 2018
426 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3200691
Editor:
Matthew Fluet
Rodchester Institude of Technology
Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 February 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National NSF of China
National Key Research & Development Program of China

Conference

PPoPP '18

Sponsor:

PPoPP '18: 23nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 24 - 28, 2018

Vienna, Austria

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
534
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)3

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jia XYao ZPeng CZhao ZLei BLiu ELi XHe ZWang YZou XZhao CChu JWang JMiao CSekar VYu MSeneviratne AVeitch D(2024)Turbo: Efficient Communication Framework for Large-scale Data Processing ClusterProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672241(540-553)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672241
Wu SChen HJin HIbrahim S(2022)Shadow: Exploiting the Power of Choice for Efficient Shuffling in MapReduceIEEE Transactions on Big Data10.1109/TBDATA.2019.29434738:1(253-267)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TBDATA.2019.2943473
Cheng YWu CLiu YRen RXu HYang BQi Z(2020)OPS: Optimized Shuffle Management System for Apache SparkProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404430(1-11)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3404397.3404430
Pan FXiong JShen YWang TJiang D(2018)H-Scheduler: Storage-Aware Task Scheduling for Heterogeneous-Storage Spark Clusters2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/PADSW.2018.8644650(1-9)Online publication date: Dec-2018
https://doi.org/10.1109/PADSW.2018.8644650
Shen YXiong JJiang D(2021)Using Vectorized Execution to Improve SQL Query Performance on SparkProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3472495(1-11)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3472456.3472495

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten