减少Hadoop集群中网络队头阻塞的调度算法

doi:10.11896/jsjkx.210900117

Abstract

Abstract: Users of big data analytics systems want the execution time of tasks to be as short as possible.However,during task execution,both network and computational moments may become resource bottlenecks that hinder task execution.Through the observation and analysis of the big data analysis system,the following conclusions are drawn:1)the data-parallel framework should switch between multiple working modes depending on the current resource bottlenecks;2)the scheduling of subtasks should fully consider the new tasks that may arrive in the future,not only the currently submitted tasks.Based on the above observations,a new task scheduling system Duopoly is designed and implemented,which consists of two parts:cans,a network scheduler that senses computational resources,and nats,a sub-task scheduler that senses network resources.The effectiveness of Duopoly is evaluated by small-scale physical clusters and large-scale simulation experiments,and the experimental results show that Duopoly can reduce the average task completion time by 37.30%~76.16% compared with existing work.

Key words: Hadoop cluster, Head-of-line blocking, Job scheduling, Network scheduling

CLC Number:

TP393

TIAN Bing-chuan, TIAN Chen, ZHOU Yu-hang, CHEN Gui-hai, DOU Wan-chun. Reducing Head-of-Line Blocking on Network in Hadoop Clusters[J].Computer Science, 2022, 49(3): 11-22.

References

[1]OUSTERHOUT K,WENDELL P,ZAHARIA M,et al.Spar-row:distributed,low latency scheduling [C]//Proceedings of the 24th Symposium on Operating Systems Principles(SOSP 2013).New York:ACM,2013:69-84.
[2]SHINNAR A,CUNNINGHAM D,SARASWAT V,et al.M3r:increased performance for in-memory hadoop jobs[J].Procee-dings of the VLDB Endowment,2012,5(12):1736-1747.
[3]ZAHARIA M,CHOWDHURY M,DAS T,et al.Resilient distributed datasets:A fault-tolerant abstraction for in-memory cluster computing [C]//Proceedings of the 9th USENIX Confe-rence on Networked Systems Design and Implementation(NSDI 2012).Berkeley:USENIX Association,2012.
[4]TRIVEDI A,STUEDI P,PFEFFERLE J,et al.On the [ir] relevance of network performance for data processing [C]//Proceedings of the 8th USENIX Conference on Hot Topics in Cloud Computing(HotCloud 2016).Berkeley:USENIX Association,2016:126-131.
[5]OUSTERHOUT K,CANEL C,RATNASAMY S,et al.Mono-tasks:Architecting for performance clarity in data analytics frameworks [C]//Proceedings of the 26th Symposium on Ope-rating Systems Principles(SOSP 2017).New York:ACM,2017:184-200.
[6]OUSTERHOUT K,RASTI R,RATNASAMY S,et al.Making sense of performance in data analytics frameworks [C]//Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation(NSDI 2015).Berkeley:USENIX Association,2015:293-307.
[7]CHOWDHURY M,ZAHARIA M,MA J,et al.Managing data transfers in computer clusters with orchestra [C]//Proceedings of the ACM SIGCOMM 2011 Conference(SIGCOMM 2011).New York:ACM,2011:98-109.
[8]DOGAR F R,KARAGIANNIS T,BALLANI H,et al.Decentralized task-aware scheduling for data center networks[J].ACM SIGCOMM Computer Communication Review,2014,44(4):431-442.
[9]CHOWDHURY M,ZHONG Y,STOICA I.Efficient coflowscheduling with varys[J].ACM SIGCOMM Computer Communication Review,2014,44(4):443-454.
[10]CHOWDHURY M,STOICA I.Efficient coflow schedulingwithout prior knowledge[J].ACM SIGCOMM Computer Communication Review,2015,45(4):393-406.
[11]ZAHARIA M,BORTHAKUR D,SARMA J S,et al.Delayscheduling:a simple technique for achieving locality and fairness in cluster scheduling [C]//Proceedings of the 5th European Conference on Computer Systems(EuroSys 2010).New York:ACM,2010:265-278.
[12]ISARD M,PRABHAKARAN V,CURREY J,et al.Quincy:fair scheduling for distributed computing clusters [C]//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles(SOSP 2009).New York:ACM,2009:261-276.
[13]ANANTHANARAYANAN G,KANDULA S,GREENBERGA G,et al.Reining in the outliers in map-reduce clusters using mantri [C]//Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation(OSDI 2010).Berkeley:USENIX Association,2010:265-278.
[14]AHMAD F,CHAKRADHAR S T,RAGHUNATHAN A,et al.Shuffle-aware scheduling in multi-tenant map-reduce clusters [C]//Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference(USENIX ATC 2014).Berkeley:USENIX Association,2014:1-12.
[15]JALAPARTI V,BODIK P,MENACHE I,et al.Network-aware scheduling for data-parallel jobs:Plan when you can[J].ACM SIGCOMM Computer Communication Review,2015,45(4):407-420.
[16]CHEN Y,ALSPAUGH S,KATZ R.Interactive analytical processing in big data systems:A cross-industry study of mapreduce workloads[J].Proceedings of the VLDB Endowment,2012,5(12):1802-1813.
[17]TAN J,CHIN A,HU Z Z.Dynmr:Dynamic mapreduce with reduce task interleaving and maptask backfilling [C]//Procee-dings of the Ninth European Conference on Computer Systems(EuroSys 2014).New York:ACM,2014:1-14.
[18]KAVULYA S,TAN J,GANDHI R,et al.An analysis of traces from a production mapreduce cluster [C]//Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster,Cloud and Grid Computing(CCGRID 2010).Washington:IEEE,2010:94-103.
[19]CHOWDHURY M,KANDULA S,STOICA I.Leveraging endpoint flexibility in data-intensive clusters[J].ACM SIGCOMM Computer Communication Review,2013,43(4):231-242.
[20]CHEN Y,GANAPATHI A,GRIFFITH R,et al.The case forevaluating mapreduce performance using workload suites [C]//Proceedings of the 2011 IEEE 19th Annual International Symposium on Modelling,Analysis,and Simulation of Computer and Telecommunication Systems(MASCOTS 2011).Washington:IEEE,2011:390-399.
[21]COSTA P,DONNELLY A,ROWSTRON A,et al.Camdoop:Exploiting in-network aggregation for big data applications [C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation(NSDI 2012).Berkeley:USENIX Association,2012.
[22]BAI W,CHEN L,CHEN K,et al.Information-agnostic flowscheduling for commodity data centers[C]//Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation(NSDI 2015).Berkeley:USENIX Association,2015:455-468.
[23]PENG Y,CHEN K,WANG G,et al.Hadoopwatch:A first step towards comprehensive traffic forecasting in cloud computing [C]//The 33rd Annual IEEE International Conference on Computer Communications(INFOCOM 2014).Piscataway:IEEE,2014:19-27.
[24]WANG H,CHEN L,CHEN K,et al.Flowprophet:Generic andaccurate traffic prediction for data-parallel cluster computing [C]//International Conference on Distributed Computing Systems(ICDCS 2015).Piscataway:IEEE,2015:349-358.
[25]MUNIR A,HE T,RAGHAVENDRA R,et al.Network scheduling aware task placement in datacenters [C]//Proceedings of the 12th International on Conference on Emerging Networking Experiments and Technologies(CoNEXT 2016).New York:ACM,2016:221-235.
[26]CHANG H,KODIALAM M,KOMPELLA R R,et al.Scheduling in mapreduce-like systems for fast completion time [C]//The 30th IEEE International Conference on Computer Communications(INFOCOM 2011).Piscataway:IEEE,2011:3074-3082.
[27]CHEN F,KODIALAM M,LAKSHMAN T.Joint scheduling of processing and shuffle phases in mapreduce systems [C]//The 31th IEEE International Conference on Computer Communications(INFOCOM 2012).Piscataway:IEEE,2012:1143-1151.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Reducing Head-of-Line Blocking on Network in Hadoop Clusters

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 11

Metrics

Comments

Recommended 0

[1]	XU Yun-qi, HUANG He, JIN Zhong. Application Research on Container Technology in Scientific Computing [J]. Computer Science, 2021, 48(1): 319-325.
[2]	HU Ya-peng, DING Wei-long, WANG Gui-ling. Monitoring and Dispatching Service for Heterogeneous Big Data Computing Frameworks [J]. Computer Science, 2018, 45(6): 67-71.
[3]	LI Zhi-jia, HU Xiang, JIAO Li and WANG Wei-feng. Performance Evaluation of Job Scheduling and InfiniBand Network Interconnection in High Performance Computing System Based on Stochastic Petri Nets [J]. Computer Science, 2015, 42(1): 33-37.
[4]	. Research on Improving Hadoop Job Scheduling Based on Learning Approach [J]. Computer Science, 2012, 39(Z6): 220-222.
[5]	. Research of Job Scheduling Strategy of High-performance Computer Based on Adaptive Power Management [J]. Computer Science, 2012, 39(10): 313-317.
[6]	ZHUO Cui-min LI Lu-qun. Dynamic Job Scheduling Model of Mobile Sensor Sink in Wireless Sensor [J]. Computer Science, 2011, 38(Z10): 356-358.
[7]	HE Jun-Mei ,ZOU Xian-Chun （Faculty of Computer and Information Science, Southwest University, Chongqing 400715）. [J]. Computer Science, 2007, 34(7): 282-283.
[8]	ZHANG Guo-Bin, PAN Jin-Gui （State Key Lab. for Novel Software,Nanjing University, Nanjing 210093）. [J]. Computer Science, 2007, 34(7): 279-281.
[9]	. [J]. Computer Science, 2007, 34(6): 128-130.
[10]	WU Dai-Xian, YANG Juan, QIU Yu-Hui （The Faculty of Computer and Information Science, SWU,Chongqing 400715）. [J]. Computer Science, 2007, 34(3): 254-255.
[11]	. [J]. Computer Science, 2006, 33(2): 35-37.