集群资源管理及回填技术
|
摘要
随着互联网的高速发展和大数据的广泛运用,无论是科学计算还是社会工业,都越来越依赖于强大的计算能力,对服务器性能的要求也越来越高。计算机集群系统具有处理速度快、可靠性高,可扩展性好等诸多优点,成为了服务器的主流。而集群资源的合理分配和高效的作业调度算法在提高系统整体资源利用率,作业吞吐量和程序性能等方面发挥着重要作用。基于现有的资源管理模型和应用需求,本文研究和分析了集群资源组织管理方法,作业调度关键技术,并对目前主要的三种回填策略对提高集群资源利用率方面的运用进行了阐述和对比。
With the rapid development of the Internet and the widespread use of big data, both sci-entific computing and social industry are increasingly relying on powerful computing power, and the requirements for server performance are getting higher and higher. The computer cluster system has the advantages of fast processing speed, high reliability, and good scalabil-ity, and has become the mainstream of the server. The rational allocation of cluster resources and efficient job scheduling algorithms play an important role in improving overall system resource utilization, job throughput and program performance.Based on the existing resource management model and application requirements, this paper studies and analyzes the cluster resource organization management mode, the key tech-nology of job scheduling, and expounds and compares the current three backfilling strategies to improve the utilization of cluster resources.
With the rapid development of the Internet and the widespread use of big data, both sci-entific computing and social industry are increasingly relying on powerful computing power, and the requirements for server performance are getting higher and higher. The computer cluster system has the advantages of fast processing speed, high reliability, and good scalabil-ity, and has become the mainstream of the server. The rational allocation of cluster resources and efficient job scheduling algorithms play an important role in improving overall system resource utilization, job throughput and program performance.Based on the existing resource management model and application requirements, this paper studies and analyzes the cluster resource organization management mode, the key tech-nology of job scheduling, and expounds and compares the current three backfilling strategies to improve the utilization of cluster resources.
引文
[1] Kavas Avi, feitelson Dror G. Comparting Windows NT, Linux, and QNX as the basis for cluster systems.Concurrency Computation Practice and Experience,2001,13(15):1303-1332.
[2] Keren A, Bark A. Opportunity cost algorithms for reduction of I/O and interprocess communication overhead in a computing cluster. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(1):39-50.
[3] Apache Hadoop.[EB/OL]http://hadoop.apache.org/,[2018-07-20].
[4] HTCondor.[EB/OL]http://research.cs.wisc.edu/htcondor/manual/,[2018-07-20].
[5] MAO H,HU S Q,ZHANG Z Z,et al.A load-driven task scheduler with adaptive DSC for mapReduce[C]Proceedings of IEEE/ACM International Conference on Green Computing and Communications(GreenCom2011),August 4-5,2011,Chengdu,China,201.
[6] GHODSI A,ZAHRIA M,HINDMAN B,et al.Dominant resource fairness:fair allocation of multiple resource types[C]Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation,NSDI,March 30-April1,2011,Boston,2011.
[7]梁李印.阿里Hadoop集群架构及服务体系[C/OL]/Hadoop与大数据技术大会(HOBTC 2012).http://hbtc2012.hadooper.cn,2012.
[8] Max-min fairness[EB/OL]http://en.wikipedia.org/wiki/Max-min_fairness.
[9] DEMERS A,KESHAV S,SHENKER S.Analysis and simulation of a fair queueing algorithm[C]Proceedings of the ACM Symposium on Communications Architectures&Protocols, 1989.
[10] WALDSPURGER C A,WEIHL W E.Lotteryscheduling:flexible proportional-share resource management[C]Proceedings of the first USENIX Symposium on Operating Systems Design and Implementation(OSDI),November14-17,1994,Monterey, 1994.
[11] CAPRITA B,CHAN W C,NIEH J,et al.Group ratio round-robin:O(1)proportional share scheduling for uniprocessor and multiprocessor systems[C]Proceedings of the 2005 USENIX Annual Technical Conference.Anaheim,US A,2005.
[12] JON C R B,ZHANG H.WF2 Q:worst_case fair weighted fair queueing[C]Proceedings of 15th IEEE INFOCOM'96,March 24-28,1996,San Francisco, 1996.
[13] PAWAN G.,GUO X G,HARRICK M V,et al.Starttime fair queueing:a scheduling algorithm for Integrated services packet switching networks[C]Proceedings of the ACM SIGCOMM96 Conference on Applications. Stanford,USA, 1996.
[14] STOICA I,SHENKER S,ZHANG H.Core-stateless fair queueing:qchieving qpproxinately fair bandwith allocations in high speed networks[C]Proceedings of the ACM SIGCOMM1998 Conference on Applications.Vancouver, 1998.
[15] SUN X,SU S,XU P,et al.Multi-dimensional Resource Integrated Scheduling In a Shared Data Center[C]Proceedings of 31st IEEE International Conference on Distributed Computing Systems Workshops(ICDCS2011Workshops).Minneapolis,US A,2011.
[16] JOE-WONG C,SEN S,LAN T,et al.Multi-Resource Allocation:Fairness-Efficiency Tradeoffs in a Unifying Framework[C]Proceedings of the IEEE INFOCOM2012.2012,Orlando,USA,2012.
[17] SCHWARZKOPF M,KONWINSKI A,ABD-EL-MALEK M.Omega:flexible,scalable schedulers for large compute clusters[C]Proceedings of Eighth Eurosys Conference2013,EuroSy s'13.Prague,2013.
[18] DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]Proceedings of the 6thUSENIX Symposium on Networked Systems Design and Implementation,OSDI.San Francisco,USA,2004.
[19] HINDMAN B,KONWINSI A,ZAHARIA M,et al.Mesos:aplatform for fine-grained resource sharing in the data center[C]Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation,NSDI.Boston,US A,2011.
[20] MURTHY A C,DOUGLAS C,KONAR M,et al. Architecture of next generation Apache Hadoop MapReduce framework[R]Technique report,Apache Hadoop,2011.
[21] VINOD K V,ARUN C M,CHRIS D,et al.Apache Hadoop YARN:yet another resource negotiator[C]Proceedings of ACM Symposium on Cloud Computing.Santa Clara,CA,2013.
[22] Hadoop On Demand. http://hadoop.apache.org/docs/stable/hod_scheduler.html.
[23] ZAHRIA M,BORTHAKUR D,JOYDEEP S S,et al.Job scheduling for multi-user MapReduce cluster[R] EECS Department,University of California,Berkeley,2009.
[24]王明阳,洪爵,冯圣中.面向多用户的集群资源部署策略[J]Journal of Integration Technology,2013(3):2-2.
[25] GUNHO L.Resource allocation and scheduling in heterogeneous cloud environments[D]Electrical Engineering and Computer Sciences,Berkeley:University of California,2012.
[26] SHOKRIPOUR A,OTHMAN M,IBRAHIM H,et al.New method for scheduling heterogeneous multi-installment systems[C]Proceedings of Future Generation Computer Systems,2012.
[27] GHANBARIA S,OTHMAN M.A priority based job scheduling algorithm in cloud computing[C]Proceedings of Procedia Engineering,2012.
[28] SALEHHI M A,JAVADI B,BUYYA R.Preemptionaware admission control in a virtualized grid federation[C]Proceedings of the 26th IEEE International Conference on Advanced Information Networking and Application(AINA2012), 2012.
[29] SU W T,WU S M.Node capability aware resource provisioning in a heterogeneous cloud[C]Proceedings of the 1st IEEE International Conference on Communications(ICCC2012),2012.
[30] ZAHRIA M,BORTHAKUR D JOYDEEP S S,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.Paris, 2010.
[31] ISARD M,VIJAYAN P,CURREY J,et al.Quincy:fair scheduling for distributed computing clusters[C]Proceedings of the ACM SIGOPS22th Symposium on Operating Systems Principles,October 11-14,2009,Big Sky, Montana,2009.
[32] HUA Z J,XU X S,YANG S Q,et al.Research and implementation of local priority scheduling algorithm for MapReduce[C]Proceedings of the 9th China Academic Communication Association Annual Meeting,2012.
[33] Adaptive Scheduler. http://issues.apache.org/jira/browse/MAPREDUCE-1380.
[34] Learning Scheduler. http://issues.apache.org/jira/browse/MAPREDUCE-1439.
[35] SANDHOLM T,LAI K.Dynamic proportional share scheduling in Hadoop[C]Proceedings of the 15th Workshop on Job Scheduling Strategies for Parallel Processing,2010.
[36] C. Gomez-Martin et al. Fattened backfilling:An improved strategy for job scheduling in parallel systems[J] Parallel Distrib. Comput. 97(2016)69-77.
[37] Dror G. Feitel-son, Ahuva Mu'alem Weil. Utilization and Predictability in Scheduling the IBM SP2 with Backfilling[J] 1063-7133/98@1998 IEEE. 542-546.
[38] Talby D, Feitelson D G. Supporting Priorities and Improving Utilization of the IBM SP Scheduler Using Slack-Based Backfilling[C] International Symposium on Parallel Processing and the, Symposium on Parallel and Distributed Processing. IEEE Computer Society, 1999:513.
[39] Jr,William A,Mahood C L,West J E. Scheduling Jobs on Parallel Systems Using a Relaxed Backfill Strategy[M]Job Scheduling Strategies for Parallel Processing. Springer Berlin Heidelberg, 2002:88-102.
[40] Nissimov A, Feitelson D G. Probabilistic backfilling[C]International Conference on Job Scheduling Strategies for Parallel Processing. Springer-Verlag, 2007:102-115.
[41] Lawson B G, Smirni E, Puiu D. Self-Adapting Backfilling Scheduling for Parallel Systems[J] 2002:583-592.
[2] Keren A, Bark A. Opportunity cost algorithms for reduction of I/O and interprocess communication overhead in a computing cluster. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(1):39-50.
[3] Apache Hadoop.[EB/OL]http://hadoop.apache.org/,[2018-07-20].
[4] HTCondor.[EB/OL]http://research.cs.wisc.edu/htcondor/manual/,[2018-07-20].
[5] MAO H,HU S Q,ZHANG Z Z,et al.A load-driven task scheduler with adaptive DSC for mapReduce[C]Proceedings of IEEE/ACM International Conference on Green Computing and Communications(GreenCom2011),August 4-5,2011,Chengdu,China,201.
[6] GHODSI A,ZAHRIA M,HINDMAN B,et al.Dominant resource fairness:fair allocation of multiple resource types[C]Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation,NSDI,March 30-April1,2011,Boston,2011.
[7]梁李印.阿里Hadoop集群架构及服务体系[C/OL]/Hadoop与大数据技术大会(HOBTC 2012).http://hbtc2012.hadooper.cn,2012.
[8] Max-min fairness[EB/OL]http://en.wikipedia.org/wiki/Max-min_fairness.
[9] DEMERS A,KESHAV S,SHENKER S.Analysis and simulation of a fair queueing algorithm[C]Proceedings of the ACM Symposium on Communications Architectures&Protocols, 1989.
[10] WALDSPURGER C A,WEIHL W E.Lotteryscheduling:flexible proportional-share resource management[C]Proceedings of the first USENIX Symposium on Operating Systems Design and Implementation(OSDI),November14-17,1994,Monterey, 1994.
[11] CAPRITA B,CHAN W C,NIEH J,et al.Group ratio round-robin:O(1)proportional share scheduling for uniprocessor and multiprocessor systems[C]Proceedings of the 2005 USENIX Annual Technical Conference.Anaheim,US A,2005.
[12] JON C R B,ZHANG H.WF2 Q:worst_case fair weighted fair queueing[C]Proceedings of 15th IEEE INFOCOM'96,March 24-28,1996,San Francisco, 1996.
[13] PAWAN G.,GUO X G,HARRICK M V,et al.Starttime fair queueing:a scheduling algorithm for Integrated services packet switching networks[C]Proceedings of the ACM SIGCOMM96 Conference on Applications. Stanford,USA, 1996.
[14] STOICA I,SHENKER S,ZHANG H.Core-stateless fair queueing:qchieving qpproxinately fair bandwith allocations in high speed networks[C]Proceedings of the ACM SIGCOMM1998 Conference on Applications.Vancouver, 1998.
[15] SUN X,SU S,XU P,et al.Multi-dimensional Resource Integrated Scheduling In a Shared Data Center[C]Proceedings of 31st IEEE International Conference on Distributed Computing Systems Workshops(ICDCS2011Workshops).Minneapolis,US A,2011.
[16] JOE-WONG C,SEN S,LAN T,et al.Multi-Resource Allocation:Fairness-Efficiency Tradeoffs in a Unifying Framework[C]Proceedings of the IEEE INFOCOM2012.2012,Orlando,USA,2012.
[17] SCHWARZKOPF M,KONWINSKI A,ABD-EL-MALEK M.Omega:flexible,scalable schedulers for large compute clusters[C]Proceedings of Eighth Eurosys Conference2013,EuroSy s'13.Prague,2013.
[18] DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]Proceedings of the 6thUSENIX Symposium on Networked Systems Design and Implementation,OSDI.San Francisco,USA,2004.
[19] HINDMAN B,KONWINSI A,ZAHARIA M,et al.Mesos:aplatform for fine-grained resource sharing in the data center[C]Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation,NSDI.Boston,US A,2011.
[20] MURTHY A C,DOUGLAS C,KONAR M,et al. Architecture of next generation Apache Hadoop MapReduce framework[R]Technique report,Apache Hadoop,2011.
[21] VINOD K V,ARUN C M,CHRIS D,et al.Apache Hadoop YARN:yet another resource negotiator[C]Proceedings of ACM Symposium on Cloud Computing.Santa Clara,CA,2013.
[22] Hadoop On Demand. http://hadoop.apache.org/docs/stable/hod_scheduler.html.
[23] ZAHRIA M,BORTHAKUR D,JOYDEEP S S,et al.Job scheduling for multi-user MapReduce cluster[R] EECS Department,University of California,Berkeley,2009.
[24]王明阳,洪爵,冯圣中.面向多用户的集群资源部署策略[J]Journal of Integration Technology,2013(3):2-2.
[25] GUNHO L.Resource allocation and scheduling in heterogeneous cloud environments[D]Electrical Engineering and Computer Sciences,Berkeley:University of California,2012.
[26] SHOKRIPOUR A,OTHMAN M,IBRAHIM H,et al.New method for scheduling heterogeneous multi-installment systems[C]Proceedings of Future Generation Computer Systems,2012.
[27] GHANBARIA S,OTHMAN M.A priority based job scheduling algorithm in cloud computing[C]Proceedings of Procedia Engineering,2012.
[28] SALEHHI M A,JAVADI B,BUYYA R.Preemptionaware admission control in a virtualized grid federation[C]Proceedings of the 26th IEEE International Conference on Advanced Information Networking and Application(AINA2012), 2012.
[29] SU W T,WU S M.Node capability aware resource provisioning in a heterogeneous cloud[C]Proceedings of the 1st IEEE International Conference on Communications(ICCC2012),2012.
[30] ZAHRIA M,BORTHAKUR D JOYDEEP S S,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.Paris, 2010.
[31] ISARD M,VIJAYAN P,CURREY J,et al.Quincy:fair scheduling for distributed computing clusters[C]Proceedings of the ACM SIGOPS22th Symposium on Operating Systems Principles,October 11-14,2009,Big Sky, Montana,2009.
[32] HUA Z J,XU X S,YANG S Q,et al.Research and implementation of local priority scheduling algorithm for MapReduce[C]Proceedings of the 9th China Academic Communication Association Annual Meeting,2012.
[33] Adaptive Scheduler. http://issues.apache.org/jira/browse/MAPREDUCE-1380.
[34] Learning Scheduler. http://issues.apache.org/jira/browse/MAPREDUCE-1439.
[35] SANDHOLM T,LAI K.Dynamic proportional share scheduling in Hadoop[C]Proceedings of the 15th Workshop on Job Scheduling Strategies for Parallel Processing,2010.
[36] C. Gomez-Martin et al. Fattened backfilling:An improved strategy for job scheduling in parallel systems[J] Parallel Distrib. Comput. 97(2016)69-77.
[37] Dror G. Feitel-son, Ahuva Mu'alem Weil. Utilization and Predictability in Scheduling the IBM SP2 with Backfilling[J] 1063-7133/98@1998 IEEE. 542-546.
[38] Talby D, Feitelson D G. Supporting Priorities and Improving Utilization of the IBM SP Scheduler Using Slack-Based Backfilling[C] International Symposium on Parallel Processing and the, Symposium on Parallel and Distributed Processing. IEEE Computer Society, 1999:513.
[39] Jr,William A,Mahood C L,West J E. Scheduling Jobs on Parallel Systems Using a Relaxed Backfill Strategy[M]Job Scheduling Strategies for Parallel Processing. Springer Berlin Heidelberg, 2002:88-102.
[40] Nissimov A, Feitelson D G. Probabilistic backfilling[C]International Conference on Job Scheduling Strategies for Parallel Processing. Springer-Verlag, 2007:102-115.
[41] Lawson B G, Smirni E, Puiu D. Self-Adapting Backfilling Scheduling for Parallel Systems[J] 2002:583-592.