Low-latency cluster scheduling framework for large-scale short-time tasks

doi:10.11772/j.issn.1001-9081.2020101566

Abstract

Abstract: There are always some tasks with short duration and high concurrency in the large-scale data analysis environment. How to schedule these concurrent jobs with low-latency requirement is a hot research topic. In some existing cluster resource management frameworks, the centralized schedulers cannot meet the low-latency requirement due to the bottleneck of the master node, and some distributed schedulers achieve the low-latency task scheduling, but has shortcomings in the optimal resource allocation and resource allocation conflict. By considering the needs for large-scale real-time jobs, a distributed cluster resource scheduling framework was designed and implemented to meet the low-latency requirement of large-scale data processing. Firstly, a two-stage scheduling framework and an optimized two-stage multi-path scheduling framework were proposed. Secondly, aiming at some resource conflict problems in two-stage multi-path scheduling, a task transfer mechanism based on load balancing was proposed to solve the load imbalance problems among computing nodes. At last, the task scheduling framework for large-scale clusters was simulated and verified by using actual load and a simulated scheduler. For the actual load, the scheduling delay of the proposed framework is controlled within 12% of that of the ideal scheduling. In the simulated environment, this framework has the delay of short-time tasks reduced by more than 40% compared with the centralized scheduler.

Key words: low-latency, distributed scheduling, two-stage scheduling, load balancing, greedy scheduling

摘要： 大规模数据分析环境中，经常存在一些持续时间较短、并行度较大的任务。如何调度这些低延迟要求的并发作业是目前研究的一个热点。现有的一些集群资源管理框架中，集中式调度器由于主节点的瓶颈无法达到低延迟的要求，而一些分布式调度器虽然达成了低延迟的任务调度，但在最优资源分配以及资源分配冲突方面存在一定的不足。从大规模实时作业的需求出发，设计和实现了一个分布式的集群资源调度框架，以满足大规模数据处理的低延迟要求。首先提出了两阶段调度框架以及优化后的两阶段多路调度框架；然后针对两阶段多路调度过程中存在的一些资源冲突问题，提出了基于负载平衡的任务转移机制，从而解决了各个计算节点的负载不平衡问题；最后使用实际负载以及一个模拟调度器对大规模集群中的任务调度框架进行了模拟和验证。对于实际负载，所提框架的调度延迟控制在理想调度的12%以内；在模拟环境下，该框架与集中式调度器相比在短时间任务的延迟上能够减少40%以上。

关键词: 低延迟, 分布式调度, 两阶段调度, 负载平衡, 贪心调度

CLC Number:

TP311.13

ZHAO Quan, TANG Xiaochun, ZHU Ziyu, MAO Anqi, LI Zhanhuai. Low-latency cluster scheduling framework for large-scale short-time tasks[J]. Journal of Computer Applications, 2021, 41(8): 2396-2405.

赵全, 汤小春, 朱紫钰, 毛安琪, 李战怀. 大规模短时间任务的低延迟集群调度框架[J]. 计算机应用, 2021, 41(8): 2396-2405.

References

[1] CARBONE P, KATSIFODIMOS A, EWEN S, et al. Apache FlinkTM:stream and batch processing in a single engine[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering,2015,36(4):28-38.
[2] AKIDAU T,BRADSHAW R,CHAMBERS C,et al. The dataflow model:a practical approach to balancing correctness,latency,and cost in massive-scale,unbounded,out-of-order data processing[J]. Proceedings of the VLDB Endowment,2015,8(12):1792-1803.
[3] CHANDRASEKARAN S,COOPER O,DESHPANDE A,et al. TelegraphCQ:continuous dataflow processing[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York:ACM,2003:668.
[4] XIN R S,GONZALEZ J E,FRANKLIN M J,et al. GraphX:a resilient distributed graph system on spark[C]//Proceedings of the 1st International Workshop on Graph Data Management Experiences and Systems. New York:ACM,2013:No. 2.
[5] 郝春亮, 沈捷, 张珩, 等. 大数据背景下集群调度结构与研究进展[J]. 计算机研究与发展,2018,55(1):53-70.(HAO C L, SHEN J,ZHANG H,et al. Structures and state-of-art research of cluster scheduling in big data background[J]. Journal of Computer Research and Development,2018,55(1):53-70.)
[6] MELNIK S,GUBAREV A,LONG J J,et al. Dremel:interactive analysis of web-scale datasets[J]. Communications of the ACM, 2011,54(6):114-123.
[7] EAGER D L,LAZOWSKA E D,ZAHORJAN J. Adaptive load sharing in homogeneous distributed systems[J]. IEEE Transactions on Software Engineering,1986,SE-12(5):662-675.
[8] 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 Conference on Networked Systems Design and Implementation. Berkeley:USENIX Association,2012:15-28.
[9] CHAMBERS C,RANIWALA A,PERRY F,et al. FlumeJava:easy,efficient data-parallel pipelines[J]. ACM SIGPLAN Notices, 2010,45(6):363-375.
[10] ISARD M,BUDIU M,YU Y,et al. Dryad:distributed dataparallel programs from sequential building blocks[C]//Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems. New York:ACM, 2007:59-72.
[11] HINDMAN B,KONWINSKI A,ZAHARIA M,et al. Mesos:a platform for fine-grained resource sharing in the data center[C]//Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley:USENIX Association, 2011:295-308.
[12] VAVILAPALLI V K, MURTHY A C, DOUGLAS C, et al. Apache Hadoop YARN:yet another resource negotiator[C]//Proceedings of the 4th Annual Symposium on Cloud Computing. New York:ACM,2013:No. 5.
[13] YOO A B,JETTE M A,GRONDONA M. SLURM:simple Linux utility for resource management[C]//Proceedings of the 2003 Workshop on Job Scheduling Strategies for Parallel Processing, LNCS 2862. Berlin:Springer,2003:44-60.
[14] KARANASOS K,RAO S,CURINO C,et al. Mercury:hybrid centralized and distributed scheduling in large shared clusters[C]//Proceedings of 2015 USENIX Annual Technical Conference. Berkeley:USENIX Association,2015:485-497.
[15] SCHWARZKOPF M,KONWINSKI A,ABD-EL-MALEK M,et al. Omega:flexible,scalable schedulers for large compute clusters[C]//Proceedings of the 8th ACM European Conference on Computer Systems. New York:ACM,2013:351-364.
[16] OUSTERHOUT K,WENDELL P,ZAHARIA M,et al. Sparrow:distributed,low latency scheduling[C]//Proceedings of the 24th ACM Symposium on Operating Systems Principles. New York:ACM,2013:69-84.
[17] ZAHARIA M,BORTHAKUR D,SEN SARMA J,et al. Delay scheduling:a simple technique for achieving locality and fairness in cluster scheduling[C]//Proceedings of the 5th European Conference on Computer Systems. New York:ACM, 2010:265-278.
[18] 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. New York:ACM,2009:261-276.
[19] GODER A,SPIRIDONOV A,WANG Y. Bistro:scheduling dataparallel jobs against live production systems[C]//Proceedings of the 2015 USENIX Conference on USENIX Annual Technical Conference. Berkeley:USENIX Association,2015:459-471.
[20] BOUTIN E,EKANAYAKE J,LIN W,et al. Apollo:scalable and coordinated scheduling for cloud-scale computing[C]//Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation. Berkeley:USENIX Association, 2014:285-300.
[21] DELIMITROU C, SANCHEZ D, KOZYRAKIS C. Tarcil:reconciling scheduling speed and quality in large shared clusters[C]//Proceedings of the 6th ACM Symposium on Cloud Computing. New York:ACM,2015:97-110.
[22] DELGADO P,DINU F,KERMARREC A M,et al. Hawk:hybrid datacenter scheduling[C]//Proceedings of the 2015 USENIX Annual Technical Conference. Berkeley,CA:USENIX Association,2015:499-510.
[23] DELGADO P,DIDONA D,DINU F,et al. Job-aware scheduling in eagle:Divide and stick to your probes[C]//Proceedings of the 7th ACM Symposium on Cloud Computing. New York:ACM, 2016:497-509.
[24] RASLEY J,KARANASOS K,KANDULA S,et al. Efficient queue management for cluster scheduling[C]//Proceedings of the 11th European Conference on Computer Systems. New York:ACM,2016:No. 36.
[25] LITZKOW M J,LIVNY M,MUTKA M W. Condor-a hunter of idle workstations[C]//Proceedings of the 8th International Conference on Distributed Computing Systems. Piscataway:IEEE,1988:104-111.
[26] WANG K,LIU N,SADOOGHI I,et al. Overcoming Hadoop scaling limitations through distributed task execution[C]//Proceedings of the 2015 IEEE International Conference on Cluster Computing. Piscataway:IEEE,2015:236-245.
[27] 汤小春. 基于集群技术的作业管理系统的研究与实现[D]. 西安:西北工业大学,2001:127.(TANG X C. The research and implementation of job management system based on cluster technology[D]. Xi' an:Northwestern Polytechnical University, 2001:127.)
[28] BRENT A. The Network Queueing System (NQS)[EB/OL].[2019-10-02]. http://gnqs.sourceforge.net/docs/papers/mnqs_papers/original_cosmic_nqs_paper.htm.
[29] GHODSI A, ZAHARIA M, HINDMAN B, et al. Dominant resource fairness:fair allocation of multiple resource types[C]//Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley:USENIX Association, 2011:323-336.