CN102096599A

Movatterモバイル変換

Info

Publication number: CN102096599A
Application number: CN2009102426741A
Authority: CN
Inventors: 孙宏伟; 郭磊涛; 卢正新
Original assignee: China Mobile Communications Group Co Ltd
Current assignee: China Mobile Communications Group Co Ltd
Priority date: 2009-12-14
Filing date: 2009-12-14
Publication date: 2011-06-15

Abstract

本发明公开了一种多队列任务调度方法以及相关系统和设备，用以解决现有多队列任务调度过程中不支持队列的优先级，导致无法对各作业队列进行差异化资源配置的问题。所述多队列任务调度方法，包括：调度节点在接收到任务执行节点发送的任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列；在判断结果为是时，所述调度节点从资源使用率小于所述使用率阈值的作业队列中调度任务给所述任务执行节点，在判断结果为否时，所述调度节点从优先级最高的作业队列中调度任务给所述任务执行节点。

The invention discloses a multi-queue task scheduling method and related systems and equipment, which are used to solve the problem that the prior multi-queue task scheduling process does not support the priority of the queues, resulting in the inability to perform differentiated resource allocation for each job queue. The multi-queue task scheduling method includes: when the scheduling node receives the task acquisition request sent by the task execution node, it judges whether there is a job queue whose resource usage rate is less than the set usage rate threshold; when the judgment result is yes, the The scheduling node schedules a task to the task execution node from the job queue whose resource usage rate is less than the usage rate threshold, and when the judgment result is no, the scheduling node schedules a task from the job queue with the highest priority to the task execution node.

Description

Translated fromChinese

技术领域technical field

本发明涉及通信领域的数据处理技术，尤其涉及一种多队列任务调度方法及相关系统和设备。The present invention relates to data processing technology in the communication field, in particular to a multi-queue task scheduling method and related systems and equipment.

背景技术Background technique

MapReduce是一种分布式的用于处理大规模数据集的并行编程系统，通过定义相应的映射(Map)和化简(Reduce)函数即可实现分布式数据处理的功能。MapReduce系统包括调度节点(JobTracker)和若干任务执行节点(TaskTracker)，其网络架构如图1所示，其中：客户端(Client)用于将用户布置的并行处理作业(Job)提交至调度节点；调度节点自动将客户端提交的作业分解为多个具有相同处理功能(但输入数据可能不同)的Map任务和多个具有相同处理功能(但处理的数据可能不同)的Reduce任务，其中，Map任务的输出数据作为Reduce任务的输入数据，并将任务调度给任务执行节点；任务执行节点向调度节点请求任务并执行请求到的任务，任务执行节点在任务执行之后向调度节点上报状态信息。MapReduce is a distributed parallel programming system for processing large-scale data sets. By defining the corresponding mapping (Map) and simplification (Reduce) functions, the function of distributed data processing can be realized. The MapReduce system includes a scheduling node (JobTracker) and several task execution nodes (TaskTracker), and its network architecture is shown in Figure 1, wherein: the client (Client) is used to submit the parallel processing job (Job) arranged by the user to the scheduling node; The scheduling node automatically decomposes the job submitted by the client into multiple Map tasks with the same processing function (but the input data may be different) and multiple Reduce tasks with the same processing function (but the processed data may be different). Among them, the Map task The output data of the Reduce task is used as the input data of the Reduce task, and the task is scheduled to the task execution node; the task execution node requests the task from the scheduling node and executes the requested task, and the task execution node reports the status information to the scheduling node after the task is executed.

客户端将作业提交给MapReduce系统中的调度节点后，调度节点将作业插入一个作业队列，并负责作业的分解和任务的调度，调度节点可以维护一个或多个作业队列。现有技术中，提供了一种应用于MapReduce系统的多队列任务调度方案，由调度节点维护多个作业队列，每个作业被插入其中一个作业队列中，预先为每个作业队列分配集群资源的一部分作为配额资源，配额资源可以由作业队列随意支配，为所有作业队列分配的配额资源之外的自由资源可以分配给任意作业队列。调度节点从资源使用率(正在使用资源量与配额资源量之比)最低的作业队列中调度任务，针对任一作业队列，按照先进先出(FIFO)原则即按照作业提交的先后顺序调度相应作业的任务。After the client submits the job to the scheduling node in the MapReduce system, the scheduling node inserts the job into a job queue and is responsible for job decomposition and task scheduling. The scheduling node can maintain one or more job queues. In the prior art, a multi-queue task scheduling scheme applied to the MapReduce system is provided. The scheduling node maintains multiple job queues, each job is inserted into one of the job queues, and cluster resources are allocated to each job queue in advance. A part is used as quota resources, which can be freely controlled by job queues, and free resources other than the quota resources allocated for all job queues can be allocated to any job queue. The scheduling node schedules tasks from the job queue with the lowest resource utilization rate (the ratio of the amount of resources being used to the amount of quota resources). For any job queue, the corresponding jobs are scheduled according to the first-in-first-out (FIFO) principle, that is, in the order in which the jobs are submitted. task.

虽然作业队列内的作业具有优先级，但是现有技术中提供的应用于MapReduce系统的多队列任务调度方案，不支持队列的优先级，调度任务时仅考虑各作业队列的资源使用率以及作业队列内各作业提交的先后顺序，导致无法对各作业队列进行差异化资源配置，可能使得某些高优先级作业不能被及时调度运行，尤其是处于高资源使用率的作业队列中的高优先级作业不能被及时调度运行。Although the jobs in the job queue have priority, the multi-queue task scheduling scheme applied to the MapReduce system provided in the prior art does not support the priority of the queue, and only considers the resource usage of each job queue and the job queue when scheduling tasks. The order in which jobs are submitted within the system makes it impossible to perform differentiated resource allocation for each job queue, which may prevent some high-priority jobs from being scheduled to run in a timely manner, especially high-priority jobs in job queues with high resource usage Cannot be scheduled to run in time.

发明内容Contents of the invention

本发明提供一种多队列任务调度方法以及数据处理系统和调度节点设备，用以解决现有多队列任务调度过程中不支持队列的优先级，导致无法对各作业队列进行差异化资源配置的问题。The present invention provides a multi-queue task scheduling method, a data processing system and a scheduling node device, which are used to solve the problem that the priority of queues is not supported in the existing multi-queue task scheduling process, resulting in the inability to perform differentiated resource allocation for each job queue .

本发明提供一种多队列任务调度方法，包括：The present invention provides a multi-queue task scheduling method, including:

调度节点在接收到任务执行节点发送的任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列；When the scheduling node receives the task acquisition request sent by the task execution node, it judges whether there is a job queue whose resource utilization rate is less than the set utilization rate threshold;

在判断结果为是时，所述调度节点从资源使用率小于所述使用率阈值的作业队列中调度任务给所述任务执行节点，在判断结果为否时，所述调度节点从优先级最高的作业队列中调度任务给所述任务执行节点。When the judgment result is yes, the scheduling node schedules tasks to the task execution node from the job queue whose resource usage rate is less than the usage rate threshold; Tasks are scheduled in the job queue to the task execution nodes.

本发明提供一种数据处理系统，包括调度节点和若干任务执行节点，所述调度节点维护多个作业队列，并且每个队列配置有优先级，其中：The present invention provides a data processing system, including a scheduling node and several task execution nodes, the scheduling node maintains multiple job queues, and each queue is configured with a priority, wherein:

所述任务执行节点，用于向所述调度节点发送任务获取请求；The task execution node is configured to send a task acquisition request to the scheduling node;

所述调度节点，用于在接收到任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列，在判断结果为是时，从资源使用率小于所述使用率阈值的作业队列中调度任务给所述任务执行节点，在判断结果为否时，从优先级最高的作业队列中调度任务给所述任务执行节点。The scheduling node is configured to, when receiving a task acquisition request, judge whether there is a job queue whose resource usage rate is less than a set usage rate threshold, and when the judgment result is yes, select the job queue whose resource usage rate is less than the usage rate threshold The task is scheduled in the job queue to the task execution node, and when the judgment result is negative, the task is scheduled to the task execution node from the job queue with the highest priority.

本发明提供一种调度节点设备，包括控制模块、第一调度模块和第二调度模块，其中：The present invention provides a scheduling node device, including a control module, a first scheduling module and a second scheduling module, wherein:

所述控制模块，用于在接收到任务执行节点发送的任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列，在判断结果为是时，触发所述第一调度模块，在判断结果为否时，触发所述第二调度模块；The control module is configured to, when receiving a task acquisition request sent by a task execution node, determine whether there is a job queue whose resource utilization rate is less than a set utilization rate threshold, and trigger the first scheduling when the determination result is yes A module that triggers the second scheduling module when the judgment result is negative;

所述第一调度模块，用于从资源使用率小于所述使用率阈值的作业队列中调度任务给所述任务执行节点；The first scheduling module is configured to schedule tasks to the task execution node from the job queue whose resource usage rate is less than the usage rate threshold;

所述第二调度模块，用于从优先级最高的作业队列中调度任务给所述任务执行节点。The second scheduling module is configured to schedule tasks from the job queue with the highest priority to the task execution node.

本发明提供的多队列任务调度方法及相关系统和设备，在作业队列中引入优先级，使得在各作业队列的资源使用率均不小于设定的使用率阈值的情况下，从优先级最高的作业队列中调度任务，通过将自由资源优先分配给高优先级的作业队列，保证高优先级作业队列中的作业能够被及时调度运行；如果存在资源使用率小于使用率阈值的作业队列，则从上述作业队列中调度任务，通过需要回收资源的作业队列优先于无需回收资源的作业队列，使得各作业队列的配额资源得以保证，优化了系统的资源配置。The multi-queue task scheduling method and related systems and devices provided by the present invention introduce priorities into the job queues, so that when the resource usage rates of each job queue are not less than the set usage rate threshold, the job with the highest priority Scheduling tasks in the job queue, by first assigning free resources to the high-priority job queue, to ensure that the jobs in the high-priority job queue can be scheduled and run in time; In the scheduling tasks in the above job queues, the job queues that need to recycle resources are given priority over the job queues that do not need to recycle resources, so that the quota resources of each job queue can be guaranteed, and the resource allocation of the system is optimized.

本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在所写的说明书、权利要求书、以及附图中所特别指出的结构来实现和获得。Additional features and advantages of the invention will be set forth in the description which follows, and in part will be apparent from the description, or may be learned by practice of the invention. The objectives and other advantages of the invention may be realized and attained by the structure particularly pointed out in the written description and claims hereof as well as the appended drawings.

附图说明Description of drawings

图1为现有技术中MapReduce系统的网络架构示意图；Fig. 1 is the network architecture schematic diagram of MapReduce system in the prior art;

图2为本发明实施例提供的MapReduce系统的结构示意图；Fig. 2 is the structural representation of the MapReduce system that the embodiment of the present invention provides;

图3为本发明实施例提供的多队列任务调度方法流程图；FIG. 3 is a flowchart of a multi-queue task scheduling method provided by an embodiment of the present invention;

图4为本发明实施例一提供的多队列任务调度处理流程图；FIG. 4 is a flow chart of multi-queue task scheduling provided by Embodiment 1 of the present invention;

图5为本发明实施例二提供的多队列任务调度处理流程图；FIG. 5 is a flow chart of multi-queue task scheduling processing provided by Embodiment 2 of the present invention;

图6为本发明实施例提供的调度节点设备的结构框图。FIG. 6 is a structural block diagram of a scheduling node device provided by an embodiment of the present invention.

具体实施方式Detailed ways

本发明实施例针对现有多队列任务调度过程中不支持队列的优先级，导致无法对各作业队列进行差异化资源配置的问题，提供了一种多队列任务调度方法，通过将自由资源优先分配给高优先级的作业队列，保证其中的作业能够被及时调度运行。本发明实施例提供的多队列任务调度方法不仅适用于MapReduce系统，还可适用于与MapReduce系统具有类似结构的其它数据处理系统，要求数据处理系统包括调度节点和若干任务执行节点，调度节点用于任务调度，任务执行节点用于执行调度节点为其调度的任务。本发明实施例将以MapReduce系统为例进行说明。The embodiment of the present invention aims at the problem that the priority of queues is not supported in the existing multi-queue task scheduling process, resulting in the inability to perform differentiated resource allocation for each job queue, and provides a multi-queue task scheduling method, which allocates free resources preferentially Give high-priority job queues to ensure that the jobs in them can be scheduled and run in time. The multi-queue task scheduling method provided by the embodiment of the present invention is not only applicable to the MapReduce system, but also applicable to other data processing systems with a similar structure to the MapReduce system. The data processing system is required to include a scheduling node and a number of task execution nodes. The scheduling node is used for Task scheduling, the task execution node is used to execute the tasks scheduled by the scheduling node. The embodiment of the present invention will be described by taking the MapReduce system as an example.

以下结合说明书附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明，并且在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。The preferred embodiments of the present invention will be described below in conjunction with the accompanying drawings. It should be understood that the preferred embodiments described here are only used to illustrate and explain the present invention, and are not intended to limit the present invention, and in the absence of conflict, the present invention The embodiments and the features in the embodiments can be combined with each other.

如图2所示，本发明实施例提供的MapReduce系统包括调度节点201和若干任务执行节点202，其中，调度节点201维护多个作业队列，并且每个队列配置有优先级，其中每一个作业队列可以与一个或多个用户相对应，其中：As shown in Figure 2, the MapReduce system provided by the embodiment of the present invention includes ascheduling node 201 and severaltask execution nodes 202, wherein, thescheduling node 201 maintains a plurality of job queues, and each queue is configured with a priority, wherein each job queue Can correspond to one or more users, where:

任务执行节点202，用于向调度节点201发送任务获取请求；Thetask execution node 202 is configured to send a task acquisition request to thescheduling node 201;

调度节点201，用于在接收到任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列，在判断结果为是时，从资源使用率小于所述使用率阈值的作业队列中调度任务给所述任务执行节点，在判断结果为否时，从优先级最高的作业队列中调度任务给任务执行节点201。Thescheduling node 201 is configured to, when receiving a task acquisition request, judge whether there is a job queue whose resource usage rate is less than a set usage rate threshold, and if the judgment result is yes, select the jobs whose resource usage rate is lower than the usage rate threshold The tasks in the queue are scheduled to the task execution node, and when the judgment result is negative, the task is scheduled to thetask execution node 201 from the job queue with the highest priority.

具体实施中，调度节点201，具体用于在判断结果为是时，从资源使用率小于使用率阈值的作业队列中的资源使用率最低的作业队列中调度任务给任务执行节点202。In specific implementation, thescheduling node 201 is specifically configured to schedule tasks to thetask execution node 202 from the job queue with the lowest resource usage rate among the job queues whose resource usage rate is lower than the usage rate threshold when the judgment result is yes.

具体实施中，任务执行节点202发送的任务获取请求中携带当前成功执行的任务所对应作业队列的标识信息；以及，In a specific implementation, the task acquisition request sent by thetask execution node 202 carries the identification information of the job queue corresponding to the currently successfully executed task; and,

调度节点201，具体用于在判断结果为是时，进一步判断资源使用率小于所述使用率阈值的作业队列中是否包括该标识信息标示的作业队列，如果是，从标识信息标示的作业队列中调度任务给任务执行节点，如果否，从资源使用率小于使用率阈值的作业队列中的资源使用率最低的作业队列中调度任务给所述任务执行节点。Thescheduling node 201 is specifically configured to, when the judgment result is yes, further judge whether the job queue marked by the identification information is included in the job queue whose resource usage rate is less than the usage rate threshold, and if so, select the job queue from the job queue marked by the identification information Scheduling the task to the task execution node, if not, dispatching the task to the task execution node from the job queue with the lowest resource utilization rate among the job queues whose resource utilization rate is less than the utilization rate threshold.

具体实施中，任务执行节点202可以通过与调度节点201之间的交互获取当前成功执行的任务所对应作业队列的标识信息，则：In specific implementation, thetask execution node 202 can obtain the identification information of the job queue corresponding to the currently successfully executed task through interaction with thescheduling node 201, then:

任务执行节点202，还用于在成功执行当前任务之后，向调度节点201上报成功执行任务状态信息；Thetask execution node 202 is further configured to report successful task execution status information to thescheduling node 201 after successfully executing the current task;

调度节点201，还用于在接收到成功执行任务状态信息时，向任务执行节点202返回当前成功执行的任务所对应作业队列的标识信息。Thescheduling node 201 is further configured to return to thetask execution node 202 the identification information of the job queue corresponding to the currently successfully executed task when receiving the status information of the successfully executed task.

基于上述MapReduce系统的具体结构和各节点的功能，结合说明书附图3对多队列任务调度方法进行详细描述。如图3所示，应用于MapReduce系统的多队列任务调度方法，具体包括：Based on the specific structure of the above-mentioned MapReduce system and the functions of each node, the multi-queue task scheduling method will be described in detail in combination with Figure 3 of the specification. As shown in Figure 3, the multi-queue task scheduling method applied to the MapReduce system specifically includes:

S301、调度节点在接收到任务执行节点发送的任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列；S301. When the scheduling node receives the task acquisition request sent by the task execution node, it judges whether there is a job queue whose resource utilization rate is less than the set utilization rate threshold;

S302、在判断结果为是时，调度节点从资源使用率小于使用率阈值的作业队列中为任务执行节点调度任务，在判断结果为否时，调度节点从优先级最高的作业队列中调度任务给任务执行节点。S302. When the judgment result is Yes, the scheduling node schedules tasks for the task execution node from the job queues whose resource usage rate is less than the usage threshold; when the judgment result is No, the scheduling node schedules tasks from the job queue with the highest priority to task execution node.

资源使用率为作业队列的正在使用资源量与配额资源量之比，具体实施中，使用率阈值一般设定为1。The resource usage rate is the ratio of the amount of resources being used in the job queue to the amount of allocated resources. In specific implementations, the usage rate threshold is generally set to 1.

上述多队列任务调度方法在作业队列中引入优先级，在保证各作业队列的配额资源的基础上，将自由资源优先分配给高优先级的作业队列，从而保证了高优先级作业队列中的作业优先被调度运行，同时优化了系统的资源配置。The above multi-queue task scheduling method introduces priority in the job queue, and on the basis of ensuring the quota resources of each job queue, the free resources are allocated to the high-priority job queue first, thus ensuring that the jobs in the high-priority job queue Priority is scheduled to run, while optimizing the resource allocation of the system.

各作业队列之间支持集群资源的共享和抢占，共享是指作业队列的配额资源没有被完全使用时，空闲的配额资源和系统中的自由资源可以分配给其它作业队列使用；抢占是指当有新任务需要调度的时候，作业队列可以抢占被其它作业队列占用的配额资源。基于不同的共享和抢占策略，本发明实施例提供了两种较佳的作业队列排序原则，并基于每一种作业队列排序原则提供了相应的多队列任务调度处理流程。Each job queue supports the sharing and preemption of cluster resources. Sharing means that when the quota resources of the job queue are not fully used, the idle quota resources and free resources in the system can be allocated to other job queues for use; preemption means that when there are When a new task needs to be scheduled, the job queue can preempt the quota resources occupied by other job queues. Based on different sharing and preemption strategies, the embodiment of the present invention provides two preferred job queue sorting principles, and provides a corresponding multi-queue task scheduling process based on each job queue sorting principle.

实施例一Embodiment one

本实施例提供的作业队列排序原则，包括如下内容：The job queue sorting principles provided in this embodiment include the following:

需要回收资源的作业队列优先于无需回收资源的作业队列，如果作业队列的资源使用率小于设定的使用率阈值，则该作业队列为需要回收资源的队列，如果作业队列的资源使用率大于或等于设定的使用率阈值，则该作业队列为无需回收资源的队列；Job queues that need to reclaim resources are prioritized over job queues that do not need to be reclaimed. If the resource usage of the job queue is less than the set usage threshold, the job queue is a queue that needs to reclaim resources. If the resource usage of the job queue is greater than or is equal to the set usage threshold, the job queue is a queue that does not need to reclaim resources;

需要回收资源的作业队列按资源使用率由低到高排序；The job queues that need to reclaim resources are sorted by resource usage from low to high;

无需回收资源的作业队列按优先级由高到低排序，优先级相同的作业队列，再按资源使用率由低到高排序。The job queues that do not need to reclaim resources are sorted by priority from high to low, and the job queues with the same priority are sorted by resource usage from low to high.

基于上述作业队列排序原则，本实施例提供了相应的多队列任务调度处理流程，如图4所示，包括如下步骤：Based on the above-mentioned job queue sorting principle, this embodiment provides a corresponding multi-queue task scheduling process, as shown in Figure 4, including the following steps:

S401、任务执行节点向调度节点发送任务获取请求；S401. The task execution node sends a task acquisition request to the scheduling node;

S402、调度节点在接收到任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列，也就是说是否存在需要回收资源的作业队列，如果是，执行S403，如果否，执行404；S402. When the scheduling node receives the task acquisition request, it judges whether there is a job queue whose resource usage rate is lower than the set usage rate threshold, that is to say, whether there is a job queue that needs to recycle resources. If yes, execute S403. If not, Execute 404;

S403、调度节点从资源使用率小于使用率阈值的作业队列中的资源使用率最低的作业队列中调度任务给任务执行节点，流程结束；S403. The scheduling node schedules the task to the task execution node from the job queue with the lowest resource usage rate among the job queues whose resource usage rate is less than the usage rate threshold, and the process ends;

具体实施中，调度节点可以将资源使用率小于使用率阈值的各作业队列按照资源使用率由低到高排序，并将排序结果保存在资源使用率队列中，再从排在资源使用率队列头部的作业队列中调度任务给任务执行节点；In specific implementation, the scheduling node can sort the job queues whose resource usage rate is less than the usage rate threshold from low to high resource usage rate, and save the sorting results in the resource usage rate queue, and then rank them at the head of the resource usage rate queue Scheduling tasks in the internal job queue to task execution nodes;

S404、调度节点从优先级最高的作业队列中调度任务给任务执行节点，流程结束；S404. The scheduling node schedules tasks from the job queue with the highest priority to the task execution node, and the process ends;

具体实施中，调度节点可以将各作业队列按照优先级由高到低排序，并将排序结果保存在优先级队列中，再从排在优先级队列头部的作业队列中调度任务给任务执行节点。In the specific implementation, the scheduling node can sort the job queues from high to low according to the priority, and save the sorting results in the priority queue, and then schedule tasks from the job queue at the head of the priority queue to the task execution node .

举例进行说明。Use an example to illustrate.

假设调度节点维护三个作业队列Q1、Q2、Q3，各作业队列Q1、Q2、Q3对应的优先级分别为W₁、W₂、W₃，其中W₁＞W₂＞W₃，资源总量为200，每个作业队列的资源配额量为50，并且当前每个作业队列正在使用资源量分别为90、60和50，假设使用率阈值为1，则：Assume that the scheduling node maintains three job queues Q1, Q2, and Q3, and the priorities corresponding to each job queue Q1, Q2, and Q3 are W₁ , W₂ , and W₃ respectively, where W₁ >W₂ >W₃ , and the total amount of resources is 200, the resource quota of each job queue is 50, and the resources currently being used by each job queue are 90, 60, and 50 respectively, assuming that the usage threshold is 1, then:

如果作业队列Q2中的一个任务被业务执行节点成功执行，业务执行节点继续向调度节点请求任务，当前作业队列Q1、Q2、Q3的资源使用率分别为90/50、59/50、50/50，作业队列Q1、Q2、Q3均不需要回收资源，根据作业队列排序原则，从优先级最高的作业队列Q1中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为91、59和50。If a task in the job queue Q2 is successfully executed by the business execution node, the business execution node continues to request the task from the scheduling node, and the resource usage rates of the current job queues Q1, Q2, and Q3 are 90/50, 59/50, and 50/50 respectively , the job queues Q1, Q2, and Q3 do not need to recycle resources. According to the job queue sorting principle, tasks are scheduled from the job queue Q1 with the highest priority to the task execution node. After the task scheduling, the amount of resources being used by each job queue is 91 respectively. , 59 and 50.

假设调度节点维护三个作业队列Q1、Q2、Q3，各作业队列Q1、Q2、Q3对应的优先级分别为W₁、W₂、W₃，其中W₁＞W₂＞W₃，资源总量为200，每个作业队列的资源配额量为50，并且当前每个作业队列正在使用资源量分别为120、50和30，假设使用率阈值为1，则：Assume that the scheduling node maintains three job queues Q1, Q2, and Q3, and the priorities corresponding to each job queue Q1, Q2, and Q3 are W₁ , W₂ , and W₃ respectively, where W₁ >W₂ >W₃ , and the total amount of resources is 200, the resource quota of each job queue is 50, and the resources currently being used by each job queue are 120, 50, and 30 respectively, assuming that the usage threshold is 1, then:

情况一、如果作业队列Q1中的一个任务被业务执行节点成功执行，业务执行节点继续向调度节点请求任务，当前作业队列Q1、Q2、Q3的资源使用率分别为119/50、50/50、30/50，作业队列Q3需要回收资源，作业队列Q1、Q2不需要回收资源，根据作业队列排序原则，从作业队列Q3中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为119、50和31，作业队列Q3从作业队列Q1中回收了一个资源。Situation 1: If a task in the job queue Q1 is successfully executed by the business execution node, the business execution node continues to request tasks from the scheduling node, and the resource usage rates of the current job queues Q1, Q2, and Q3 are 119/50, 50/50, 30/50, job queue Q3 needs to recycle resources, job queues Q1 and Q2 do not need to recycle resources, according to the principle of job queue sorting, schedule tasks from job queue Q3 to task execution nodes, after task scheduling, each job queue is using resources 119, 50, and 31 respectively, the job queue Q3 has reclaimed a resource from the job queue Q1.

情况二、如果作业队列Q2中的一个任务被业务执行节点成功执行，业务执行节点继续向调度节点请求任务，当前作业队列Q1、Q2、Q3的资源使用率分别为120/50、49/50、30/50，作业队列Q2、Q3需要回收资源，并且作业队列Q3的资源使用率低于作业队列Q2的资源使用率，作业队列Q1不需要回收资源，根据作业队列排序原则，从作业队列Q3中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为120、49和31，作业队列Q3从作业队列Q2中回收了一个资源，使得当前作业队列Q2、Q3的资源使用率均低于1。Case 2: If a task in the job queue Q2 is successfully executed by the business execution node, the business execution node continues to request the task from the scheduling node, and the resource utilization rates of the current job queues Q1, Q2, and Q3 are 120/50, 49/50, 30/50, job queues Q2 and Q3 need to recycle resources, and the resource usage rate of job queue Q3 is lower than that of job queue Q2, job queue Q1 does not need to recycle resources, according to the principle of job queue sorting, from job queue Q3 Scheduling tasks to task execution nodes. After task scheduling, the amount of resources being used by each job queue is 120, 49, and 31 respectively. Job queue Q3 reclaims a resource from job queue Q2, so that the current resource usage of job queues Q2 and Q3 are lower than 1.

情况三、如果作业队列Q3中的一个任务被业务执行节点成功执行，业务执行节点继续向调度节点请求任务，当前作业队列Q1、Q2、Q3的资源使用率分别为120/50、50/50、29/50，作业队列Q3需要回收资源，作业队列Q1、Q2不需要回收资源，根据作业队列排序原则，从作业队列Q3中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为120、50和30，与任务执行前的状态相同。Case 3: If a task in the job queue Q3 is successfully executed by the business execution node, the business execution node continues to request tasks from the scheduling node, and the resource utilization rates of the current job queues Q1, Q2, and Q3 are 120/50, 50/50, 29/50, job queue Q3 needs to recycle resources, job queues Q1 and Q2 do not need to recycle resources, according to the principle of job queue sorting, schedule tasks from job queue Q3 to task execution nodes, after task scheduling, each job queue is using resources They are 120, 50 and 30 respectively, which are the same as the state before the task execution.

实施例二Embodiment two

需要回收资源的作业队列优先于无需回收资源的作业队列；Job queues that need to reclaim resources are prioritized over job queues that do not need to reclaim resources;

需要回收资源的作业队列，任务优先分配给当前成功执行的任务对应的作业队列，其它作业队列按资源使用率由低到高排序；For job queues that need to reclaim resources, tasks are assigned to the job queue corresponding to the currently successfully executed task, and other job queues are sorted by resource usage from low to high;

无需回收资源的队列按优先级由高到低排序，优先级相同的作业队列，再按资源使用率由低到高排序。The queues that do not need to reclaim resources are sorted by priority from high to low, and the job queues with the same priority are sorted by resource usage from low to high.

基于上述作业队列排序原则，本实施例提供了相应的多队列任务调度处理流程，如图5所示，包括如下步骤：Based on the above-mentioned job queue sorting principles, this embodiment provides a corresponding multi-queue task scheduling process, as shown in Figure 5, including the following steps:

S501、任务执行节点在成功执行当前任务之后，向调度节点上报成功执行任务状态信息；S501. After the task execution node successfully executes the current task, it reports the task execution status information to the scheduling node;

S502、调度节点接收到成功执行任务状态信息时，向任务执行节点返回当前成功执行的任务所对应作业队列的标识信息；S502. When the scheduling node receives the successfully executed task status information, it returns to the task executing node the identification information of the job queue corresponding to the currently successfully executed task;

S503、任务执行节点向调度节点发送任务获取请求，其中携带当前成功执行的任务所对应作业队列的标识信息；S503. The task execution node sends a task acquisition request to the scheduling node, which carries the identification information of the job queue corresponding to the currently successfully executed task;

S504、调度节点在接收到任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列，也就是说是否存在需要回收资源的作业队列，如果是，执行S505，如果否，执行508；S504. When the scheduling node receives the task acquisition request, it judges whether there is a job queue whose resource usage rate is lower than the set usage rate threshold, that is to say, whether there is a job queue that needs to recycle resources. If yes, execute S505. If not, Execute 508;

S505、调度节点进一步判断资源使用率小于使用率阈值的作业队列中是否包括该标识信息标示的作业队列，如果是，则执行S506，如果否，则执行S507；S505. The scheduling node further determines whether the job queue indicated by the identification information is included in the job queue whose resource usage rate is lower than the usage rate threshold, if yes, execute S506, and if not, execute S507;

S506、调度节点从该标识信息标示的作业队列中调度任务给任务执行节点，流程结束；S506. The scheduling node schedules tasks from the job queue indicated by the identification information to the task execution node, and the process ends;

S507、调度节点从资源使用率小于使用率阈值的作业队列中的资源使用率最低的作业队列中调度任务给任务执行节点，流程结束；S507. The scheduling node schedules the task to the task execution node from the job queue with the lowest resource usage rate among the job queues whose resource usage rate is less than the usage rate threshold, and the process ends;

S508、调度节点从优先级最高的作业队列中调度任务给任务执行节点，流程结束。S508. The scheduling node schedules tasks from the job queue with the highest priority to the task execution node, and the process ends.

举例进行说明。Use an example to illustrate.

假设调度节点维护三个作业队列Q1、Q2、Q3，各作业队列Q1、Q2、Q3对应的优先级分别为W₁、W₂、W₃，各作业队列Q1、Q2、Q3的标识信息分别为01、02、03，其中W₁＞W₂＞W₃，资源总量为200，每个作业队列的资源配额量为50，并且当前每个作业队列正在使用资源量分别为120、50和30，假设使用率阈值为1，则：Assuming that the scheduling node maintains three job queues Q1, Q2, and Q3, the priorities corresponding to each job queue Q1, Q2, and Q3 are W₁ , W₂ , and W₃ respectively, and the identification information of each job queue Q1, Q2, and Q3 are 01, 02, and 03, where W₁ >W₂ >W₃ , the total amount of resources is 200, the resource quota of each job queue is 50, and the resources currently being used by each job queue are 120, 50, and 30 respectively , assuming the usage threshold is 1, then:

情况一、如果作业队列Q1中的一个任务被业务执行节点成功执行，调度节点在接收到成功执行任务状态信息时，向任务执行节点返回当前成功执行的任务所对应作业队列的标识信息01，业务执行节点继续向调度节点请求任务，其中携带标识信息01，当前作业队列Q1、Q2、Q3的资源使用率分别为119/50、50/50、30/50，作业队列Q3需要回收资源，作业队列Q1、Q2不需要回收资源，根据作业队列排序原则，从作业队列Q3中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为119、50和31，作业队列Q3从作业队列Q1中回收了一个资源。Situation 1: If a task in the job queue Q1 is successfully executed by the business execution node, when the scheduling node receives the status information of the successfully executed task, it returns to the task execution node the identification information 01 of the job queue corresponding to the currently successfully executed task, and the business The execution node continues to request tasks from the scheduling node, which carries the identification information 01. The resource usage rates of the current job queues Q1, Q2, and Q3 are 119/50, 50/50, and 30/50 respectively. The job queue Q3 needs to reclaim resources. The job queue Q1 and Q2 do not need to recycle resources. According to the principle of job queue sorting, tasks are scheduled from job queue Q3 to task execution nodes. A resource is reclaimed in queue Q1.

情况二、如果作业队列Q2中的一个任务被业务执行节点成功执行，调度节点在接收到成功执行任务状态信息时，向任务执行节点返回当前成功执行的任务所对应作业队列的标识信息02，业务执行节点继续向调度节点请求任务，其中携带标识信息02，当前作业队列Q1、Q2、Q3的资源使用率分别为120/50、49/50、30/50，作业队列Q2、Q3需要回收资源，作业队列Q1不需要回收资源，根据作业队列排序原则，由于标识信息02标示的作业队列为Q2且作业队列Q2需要回收资源，从作业队列Q2中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为120、50和30，与任务执行前的状态相同。Case 2: If a task in the job queue Q2 is successfully executed by the business execution node, when the scheduling node receives the status information of the successfully executed task, it returns to the task execution node the identification information 02 of the job queue corresponding to the currently successfully executed task, and the business The execution node continues to request tasks from the scheduling node, which carries the identification information 02. The resource usage rates of the current job queues Q1, Q2, and Q3 are 120/50, 49/50, and 30/50 respectively. The job queues Q2 and Q3 need to reclaim resources. The job queue Q1 does not need to recycle resources. According to the job queue sorting principle, since the job queue marked by the identification information 02 is Q2 and the job queue Q2 needs to reclaim resources, the task is scheduled from the job queue Q2 to the task execution node. After the task is scheduled, each job The amount of resources being used by the queue is 120, 50, and 30 respectively, which is the same as the status before the task execution.

情况三、如果作业队列Q3中的一个任务被业务执行节点成功执行，，调度节点在接收到成功执行任务状态信息时，向任务执行节点返回当前成功执行的任务所对应作业队列的标识信息03，业务执行节点继续向调度节点请求任务，其中携带标识信息03，当前作业队列Q1、Q2、Q3的资源使用率分别为120/50、50/50、29/50，作业队列Q3需要回收资源，作业队列Q1、Q2不需要回收资源，由于标识信息03标示的作业队列为Q3且作业队列Q3需要回收资源，根据作业队列排序原则，从作业队列Q3中调度任务给任务执行节点，任务调度后每个作业队列正在使用资源量分别为120、50和30，与任务执行前的状态相同。Case 3: If a task in the job queue Q3 is successfully executed by the business execution node, when the scheduling node receives the status information of the successfully executed task, it returns to the task execution node the identification information 03 of the job queue corresponding to the currently successfully executed task, The business execution node continues to request tasks from the scheduling node, which carries identification information 03. The resource usage rates of the current job queues Q1, Q2, and Q3 are 120/50, 50/50, and 29/50 respectively. The job queue Q3 needs to recycle resources. Queues Q1 and Q2 do not need to recycle resources. Since the job queue marked by the identification information 03 is Q3 and job queue Q3 needs to recycle resources, according to the job queue sorting principle, tasks are scheduled from job queue Q3 to task execution nodes. After task scheduling, each The amount of resources being used by the job queue is 120, 50, and 30 respectively, which is the same as the status before the task execution.

本发明实施例同时提供了一种调度节点设备，如图6所示，包括控制模块601、第一调度模块602和第二调度模块603，其中：The embodiment of the present invention also provides a scheduling node device, as shown in FIG. 6 , including acontrol module 601, afirst scheduling module 602, and asecond scheduling module 603, wherein:

控制模块601，用于在接收到任务执行节点发送的任务获取请求时，判断是否存在资源使用率小于设定的使用率阈值的作业队列，在判断结果为是时，触发第一调度模块602，在判断结果为否时，触发第二调度模块603；Thecontrol module 601 is configured to, when receiving the task acquisition request sent by the task execution node, judge whether there is a job queue whose resource utilization rate is less than the set utilization rate threshold, and trigger thefirst scheduling module 602 when the judgment result is yes, When the judgment result is no, trigger thesecond scheduling module 603;

第一调度模块602，用于从资源使用率小于使用率阈值的作业队列中调度任务给任务执行节点；Thefirst scheduling module 602 is configured to schedule tasks to task execution nodes from the job queue whose resource usage rate is less than the usage rate threshold;

第二调度模块603，用于从优先级最高的作业队列中调度任务给任务执行节点。Thesecond scheduling module 603 is configured to schedule tasks from the job queue with the highest priority to the task execution node.

其中，第一调度模块602，具体用于从资源使用率小于该使用率阈值的作业队列中的资源使用率最低的作业队列中调度任务给任务执行节点。Wherein, thefirst scheduling module 602 is specifically configured to schedule tasks to task execution nodes from the job queue with the lowest resource usage rate among the job queues whose resource usage rate is less than the usage rate threshold.

第一调度模块602的一种可能结构，具体包括：A possible structure of thefirst scheduling module 602 specifically includes:

判断子模块，用于判断资源使用率小于所述使用率阈值的作业队列中是否包括所述标识信息标示的作业队列，并发送判断结果；A judging submodule, configured to judge whether the job queue marked by the identification information is included in the job queue whose resource usage rate is less than the usage rate threshold, and send the judgment result;

调度子模块，用于如果判断结果为是，从标识信息标示的作业队列中调度任务给任务执行节点，如果判断结果为否，从资源使用率小于使用率阈值的作业队列中的资源使用率最低的作业队列中调度任务给任务执行节点。The scheduling sub-module is used to schedule tasks from the job queue marked by the identification information to the task execution node if the judgment result is yes, and if the judgment result is no, the resource usage rate from the job queue whose resource usage rate is less than the usage rate threshold is the lowest Scheduling tasks in the job queue to task execution nodes.

需要说明的是，以上调度节点设备的模块划分方式仅是各种可能的模块划分方式中的一种，本领域技术人员应该能够理解，只要使调度节点设备具备上述功能，其是否划分为不同的模块或者如何划分模块，都不会对本发明的保护范围构成限制。It should be noted that the module division method of the above dispatching node device is only one of various possible module division methods, and those skilled in the art should be able to understand that as long as the dispatching node device has the above functions, whether it is divided into different modules The modules or how to divide the modules will not limit the protection scope of the present invention.

本发明实施例提供的多队列任务调度方法及相关系统和设备，在作业队列中引入优先级，在各作业队列的资源使用率均不小于设定的使用率阈值的情况下，从优先级最高的作业队列中调度任务，通过将自由资源优先分配给高优先级的作业队列，保证高优先级作业队列中的作业能够被及时调度运行；如果存在资源使用率小于使用率阈值的作业队列，则从上述作业队列中调度任务，通过需要回收资源的作业队列优先于无需回收资源的作业队列，使得各作业队列的配额资源得以保证，优化了系统的资源配置。In the multi-queue task scheduling method and related systems and devices provided by the embodiments of the present invention, priorities are introduced into the job queues, and when the resource usage rates of each job queue are not less than the set usage rate threshold, the highest priority Scheduling tasks in job queues, by assigning free resources to high-priority job queues first, to ensure that jobs in high-priority job queues can be scheduled and run in time; if there is a job queue with a resource usage rate lower than the usage threshold, then Tasks are scheduled from the above job queues, and the job queues that need to reclaim resources are given priority over those that do not need to reclaim resources, so that the quota resources of each job queue can be guaranteed, and the resource allocation of the system is optimized.

应用于MapReduce系统的基于优先级的多队列任务调度方法也可以参照现有其它数据处理系统中基于优先级的多队列任务调度方法，由调度节点为每个作业队列分配可使用资源，其中可使用资源量为配额资源量和自由资源量之和。调度节点可以根据队列的优先级为每个作业队列分配自由资源，例如以作业队列的优先级为权重为作业队列分配自由资源，为了简化运算，可以采用算术平均算法，具体通过公式 $m_{i} = (n - \overset{I}{\underset{i = 1}{Σ}} t_{i}) * W_{i} / Σ_{i = 1}^{I} W_{i}$ 实现，其中，m_i表示调度节点为第i个作业队列分配的自由资源量，其中t_i表示第i个作业队列的配额资源量，n表示资源总量，W_i表示第i个作业队列的优先级，I表示作业队列的数量。The priority-based multi-queue task scheduling method applied to the MapReduce system can also refer to the priority-based multi-queue task scheduling method in other existing data processing systems, and the scheduling node allocates available resources for each job queue, among which The resource amount is the sum of the quota resource amount and the free resource amount. The scheduling node can allocate free resources for each job queue according to the priority of the queue. For example, the priority of the job queue is used as the weight to allocate free resources for the job queue. In order to simplify the operation, the arithmetic mean algorithm can be used, specifically through the formula $m_{i} = (no - \overset{I}{\underset{i = 1}{Σ}} t_{i}) * W_{i} / Σ_{i = 1}^{I} W_{i}$ Realization, where m_i represents the amount of free resources allocated by the scheduling node for the i-th job queue, where t_i represents the amount of quota resources of the i-th job queue, n represents the total amount of resources, W_i represents the amount of resources allocated by the i-th job queue Priority, I represents the number of job queues.

以调度节点维护三个作业队列Q1、Q2、Q3为例进行说明，假设Q1、Q2、Q3对应的优先级分别为W₁、W₂、W₃，分配给每个作业队列的配额资源量为t₁、t₂、t₃，如果资源总量为n，则为每个作业队列分配的自由资源量如下公式所示：Take the scheduling node maintaining three job queues Q1, Q2, and Q3 as an example. Assume that the priorities corresponding to Q1, Q2, and Q3 are W₁ , W₂ , and W₃ respectively, and the amount of quota resources allocated to each job queue is t₁ , t₂ , t₃ , if the total amount of resources is n, the amount of free resources allocated to each job queue is shown in the following formula:

m₁＝(n-t₁-t₂-t₃)*W₁/(W₁+W₂+W₃)m₁ =(nt₁ -t₂ -t₃ )*W₁ /(W₁ +W₂ +W₃ )

m₂＝(n-t₁-t₂-t₃)*W₂/(W₁+W₂+W₃)m₂ =(nt₁ -t₂ -t₃ )*W₂ /(W₁ +W₂ +W₃ )

m₃＝(n-t₁-t₂-t₃)*W₃/(W₁+W₂+W₃)m₃ =(nt₁ -t₂ -t₃ )*W₃ /(W₁ +W₂ +W₃ )

调度节点为每个作业队列分配的可使用资源量分别为：作业队列Q1的可使用资源量为t₁+m₁、作业队列Q2的可使用资源量为t₂+m₂、作业队列Q3的可使用资源量为t₃+m₃。The amount of available resources allocated by the scheduling node to each job queue is respectively: the amount of available resources of job queue Q1 is t₁ +m₁ , the amount of available resources of job queue Q2 is t₂ +m₂ , and the amount of available resources of job queue Q3 is The amount of available resources is t₃ +m₃ .

本领域的技术人员应明白，本发明的实施例可提供为方法、设备(系统)、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。Those skilled in the art should understand that the embodiments of the present invention may be provided as methods, devices (systems), or computer program products. Accordingly, the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。Obviously, those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and equivalent technologies thereof, the present invention also intends to include these modifications and variations.