用于对计算集群或云计算平台的资源节点执行资源调度的方法和装置

相关申请案交叉引用

本申请要求于2019年12月19日递交的申请号为16/720,410、发明名称为“用于对计算集群或云计算平台的资源节点执行资源调度的方法和装置(METHODS AND APPARATUSFOR RESOURCE SCHEDULING OF RESOURCE NODES OF A COMPUTING CLUSTER OR A CLOUDCOMPUTING PLATFORM)”的美国专利申请的优先权，其全部内容通过引用结合在本申请中。

技术领域

本发明大体涉及对计算机集群或云计算平台的资源节点执行资源调度的领域。

背景技术

计算机集群和云计算平台按需提供计算机系统资源。计算机集群和云计算平台的计算机系统资源通常组织为资源节点。资源节点可以是计算机集群中的物理机、云计算平台中的虚拟机或主机等。每个资源节点可以通过一组节点属性来表征，这些节点属性可以包括中央处理器(central processing unit，CPU)内核电压值(称为“vcore值”)、内存值等。

计算机集群和云计算平台的众多用户发送用于在计算机集群或云计算平台中的一组资源节点上执行的计算机作业。计算机作业通常争用计算机集群或云计算平台的可用资源节点。每个计算机作业可以包括一个或多个任务。为了将可用资源节点分配给任务，可能需要考虑任务中提供的各种需求以及各种资源调度方法。

任务可以指定不同的资源需求。例如，一个任务可以将期望的资源需求指定为资源节点的vcore值和内存值。该任务还可以指定局部性约束，该局部性约束标识可以执行该任务的一组“候选节点”。此外，在将可用资源节点分配给任务时，资源管理器可能需要考虑各种附加的优化准则，例如：调度吞吐量、总体利用率、公平性和/或负载均衡。

因此，资源管理器需要根据资源节点的可用性、众多节点属性以及众多需求和约束，高效地将计算机作业中包含的任务分配给资源节点。用于对计算机作业的任务进行资源调度的传统系统和方法实现得很简单，因此，传统系统和方法对计算机作业的任务执行的资源调度可能很耗时。例如，为了给单个任务选择资源节点，调度延迟可能是|N|阶(称为“O(|N|)”)，其中，N是计算机集群或云计算平台中的资源节点的集合，|N|表示计算机集群或云计算平台中的资源节点的总数。

发明内容

本发明的目的在于提供用于对计算机集群或云计算平台的资源节点执行资源调度的方法和装置，以克服现有技术的不便。

本文所描述的用于对计算机集群或云计算平台的资源节点执行资源调度的装置和方法可以有助于改进对计算机集群或云计算平台的资源节点执行的资源调度，以便高效地为计算机作业中包含的任务分配资源节点。本文所描述的方法和系统可以有助于高效地从资源节点池中为接收的一组计算机作业任务中的每个任务选择资源节点。本技术考虑的因素包括所述资源节点的可用性、各种节点属性和在所述任务中接收的各种规范。为了本发明的目的，任务是计算机作业的资源请求单元。

根据本发明的目的，本发明的一个方面提供了一种方法，所述方法包括：接收节点集中的节点的节点标识符，并接收所述节点标识符中的每一个的节点属性的值；从客户端设备接收任务，所述任务指定任务参数的值；生成节点图结构，所述节点图结构具有包括至少一个节点标识符的至少一个节点图结构顶点，所述至少一个节点图结构顶点映射到坐标空间，所述至少一个节点标识符中的每一个使用所述节点属性的所述值映射到所述坐标空间以确定节点坐标；通过使用所述任务参数的所述值将所述任务映射到所述坐标空间以确定任务坐标；通过分析位于所述任务的适合区域内的所述至少一个节点图结构顶点，确定第一节点的第一节点标识符，所述适合区域在所述坐标空间中具有大于等于每个任务坐标的坐标；将所述第一节点标识符映射到所述任务以生成调度方案；将所述调度方案传输到调度引擎，以调度所述任务在所述第一节点上执行。

确定所述第一节点标识符还可以包括：确定所述第一节点标识符是否映射到所述至少一个节点图结构顶点。

所述任务可以指定至少一个候选节点标识符。确定所述第一节点标识符还可以包括：确定所述第一节点标识符是否与所述至少一个候选节点标识符中的一个相同。

在至少一个实施例中，所述方法还可以包括：根据随所述任务接收的节点属性偏好确定分析所述节点图结构顶点的顺序。

在至少一个实施例中，所述方法还可以包括：根据资源调度策略确定分析所述节点图结构顶点的顺序，所述资源调度策略为LeastFit调度策略、BestFit调度策略、随机调度策略和具有预留的LeastFit调度策略中的一种。

在一些实施例中，所述节点图结构具有至少两个节点图结构顶点映射到所述坐标空间的不同子空间。分析所述至少两个节点图结构顶点可以从位于所述任务的所述适合区域内且在所述坐标空间的至少一个维度中具有最大坐标的节点图结构顶点开始。换言之，遍历所述节点图结构以确定所述第一节点标识符可以从位于所述任务的适合区域内且在所述任务的所述适合区域内具有最大坐标的节点图结构顶点开始。在一些实施例中，所述节点图结构可以是节点树图结构。在一些实施例中，所述遍历可以从所述节点树结构的根节点开始。

分析所述至少两个节点图结构顶点可以从位于所述任务的适合区域内且在所述坐标空间的至少一个维度中具有最小坐标的节点图结构顶点开始。换言之，遍历所述节点图结构以确定所述第一节点标识符可以从位于所述任务的适合区域内且具有最小坐标的节点图结构顶点开始。

所述任务参数的所述值可以包括中央处理器(central processing unit，CPU)内核电压值、内存值、内存输入/输出带宽和网络参数值中的至少两个。

为了确定所述节点坐标和所述任务坐标，可以将所述节点属性的所述值中的至少一个和所述任务参数的所述值中的至少一个除以粒度参数。

所述节点中的每一个的所述节点坐标可以通过进一步使用所述节点中的每一个的所述任务的预留数据和其它任务的预留数据来确定。所述节点中的每一个的所述节点坐标可以取决于所述节点中的每一个的所述任务的所述预留数据和其它任务的所述预留数据。

将所述节点和所述至少一个节点图结构顶点映射到所述坐标系还可以包括：从所述节点坐标中扣除针对每个节点属性为其它任务预留的资源量。

确定所述第一节点标识符还可以包括：确定所述第一节点是否匹配至少一个搜索准则。

根据本发明的其它方面，提供了一种用于资源调度的装置。所述装置包括：处理器；存储器，用于存储指令，当所述指令由所述处理器执行时，使得所述装置：接收节点集中的节点的节点标识符，并接收所述节点标识符中的每一个的节点属性的值；从客户端设备接收任务，所述任务指定任务参数的值；生成节点图结构，所述节点图结构具有包括至少一个节点标识符的至少一个节点图结构顶点，所述至少一个节点图结构顶点映射到坐标空间，所述至少一个节点标识符中的每一个使用所述节点属性的所述值映射到所述坐标空间以确定节点坐标；通过使用所述任务参数的所述值将所述任务映射到所述坐标空间以确定任务坐标；通过分析位于所述任务的适合区域内的所述至少一个节点图结构顶点，确定第一节点的第一节点标识符，所述适合区域在所述坐标空间中具有大于等于每个任务坐标的坐标；将所述第一节点标识符映射到所述任务以生成调度方案；将所述调度方案传输到调度引擎，以调度所述任务在所述第一节点上执行。

确定所述第一节点标识符时，所述处理器还可以用于：确定所述第一节点标识符是否映射到所述至少一个节点图结构顶点。

所述任务可以指定至少一个候选节点标识符；确定所述第一节点标识符时，所述处理器还可以用于：确定所述第一节点标识符是否与所述至少一个候选节点标识符中的一个相同。

所述处理器还可以用于：根据随所述任务接收的节点属性偏好确定分析所述节点图结构顶点的顺序。

所述处理器还可以用于：根据资源调度策略确定分析所述节点图结构顶点的顺序，所述资源调度策略为LeastFit调度策略、BestFit调度策略、随机调度策略和LeastFitwith Reservation调度策略中的一种。

所述节点图结构可以具有至少两个节点图结构顶点映射到所述坐标空间的不同子空间，并且所述处理器可以用于从位于所述任务的所述适合区域内且在所述坐标空间的至少一个维度中具有最大坐标的节点图结构顶点开始分析所述至少两个节点图结构顶点。在一些实施例中，所述节点图结构可以是节点树图结构。在一些实施例中，所述遍历可以从所述节点树结构的根节点开始。

所述节点图结构可以具有至少两个节点图结构顶点映射到所述坐标空间的不同子空间，并且所述处理器可以用于从位于所述任务的适合区域内且在所述坐标空间的至少一个维度中具有最小坐标的节点图结构顶点开始分析所述至少两个节点图结构顶点。

为了确定所述节点坐标和所述任务坐标，可以将所述节点属性的所述值中的至少一个和所述任务参数的所述值中的至少一个除以粒度参数。所述节点中的每一个的所述节点坐标可以通过进一步使用所述节点中的每一个的所述任务的预留数据和其它任务的预留数据来确定。将所述节点和相应的至少一个节点图结构顶点映射到所述坐标系时，所述处理器还可以用于：从所述节点坐标中扣除针对每个节点属性为其它任务预留的资源量。确定所述第一节点标识符时，所述处理器还可以用于：确定所述第一节点是否匹配至少一个搜索准则。

根据本发明的其它方面，提供了一种方法，所述方法包括：接收节点集中的节点的节点标识符，并接收所述节点标识符中的每一个的节点属性的值；接收一系列任务，每个任务指定任务参数的值；生成节点图结构，所述节点图结构具有至少一个节点图结构顶点，所述至少一个节点图结构顶点映射到坐标空间；将每个任务映射到所述坐标空间；通过分析位于每个任务的适合区域内的所述至少一个节点图结构顶点，确定第一节点的第一节点标识符；将所述第一节点标识符映射到每个任务以生成调度方案。

本发明各实现方式均具有上述目的和/或方面中的至少一个，但不一定具有所有这些目的和/或方面。应理解，由于试图实现上述目的而提出的本发明的一些方面可能不满足此目的和/或可能满足本文未具体叙述的其它目的。

通过以下描述、附图和所附权利要求书，本发明各实现方式的附加和/或替代特征、方面和优点是显而易见的。

附图说明

结合附图，通过以下详细描述，本发明的特征和优点是显而易见的，在附图中：

图1示出了适于实现本技术的非限制性实施例的装置的示意图；

图2示出了本技术的非限制性实施例提供的资源调度例程和由该资源调度例程生成的调度方案；

图3描绘了本技术的非限制性实施例提供的坐标空间的非限制性示例，其中DistBuckets实例映射到该坐标空间；

图4A至图4P示出了本发明各实施例提供的使用LeastFit调度策略的资源调度方法的几个实现步骤；

图5A至图5P示出了本发明各实施例提供的使用BestFit调度策略的资源调度方法的各个执行步骤；

图6A至图6H示出了本发明各实施例提供的使用LeastFit调度策略和粒度的资源调度方法的各个执行步骤；

图7示出了本发明各实施例提供的资源调度方法的流程图。

应当理解，在整个附图和对应的描述中，相似的特征由相同的附图标记标识。此外，还应当理解，附图和随后的描述仅用于说明性目的，并且此类公开不限制权利要求的范围。

具体实施方式

本发明旨在解决当前技术的至少一些缺陷。具体地，本发明描述了使用索引数据结构(在本文中称为“DistBuckets结构”)进行资源调度的方法和系统。本文中描述的方法和结构将可用资源节点映射到DistBuckets结构。

使用本文中描述的方法和结构可以有助于加速各种资源调度策略的实现。例如，此类资源调度策略可以是LeastFit调度策略、BestFit调度策略、随机调度策略、具有预留的LeastFit调度策略及其组合。本文中描述的方法和结构还可以加速各种基本操作的执行，例如查找、插入和删除。DistBuckets结构可以考虑各种节点属性，例如vcore和内存。在许多情况下，为一个任务调度一个节点的运行时成本为O(1)。

本文中提及的术语“计算机集群”是指一组松散耦合的计算机，它们通过协同工作执行从多个用户接收的作业或计算机作业任务。所述集群可以位于数据中心内，也可以跨多个数据中心部署。

本文中提及的术语“云计算平台”是指一组松散耦合的虚拟机，它们通过协同工作执行从多个用户接收的计算机作业或包含在计算机作业中的任务。云计算平台可以位于数据中心内，也可以跨多个数据中心部署。

本文中提及的术语“用户”和“客户端设备”是指可以请求执行计算机作业并向调度引擎发送包含在计算机作业中的任务的电子设备。

本文中使用的术语“公共函数”是指可以在其所属的索引数据结构(例如，本文中所述的DistBuckets结构)内部和外部使用的函数。

本文中提及的术语“资源节点”(也称为“节点”)是指资源实体，例如计算机集群中的计算机或云计算平台中的虚拟机。每个资源节点具有唯一的节点标识符(在本文中也称为“节点ID”)。每个资源节点可以通过节点属性的值来表征，例如：中央处理器(centralprocessing unit，CPU)内核电压值(称为“vcore值”)、内存值、可以永久存储数据的任何类型内存的内存输入/输出带宽(换言之，可以从内存中检索多少数据以及检索这些数据的速度有多快)、网络参数值、图形处理器(graphics processing unit，GPU)参数值，例如电压值和时钟速度值。资源节点还可以通过其可用性来表征：资源节点可以是可用的，也可以是已完全或部分预留的。

本文中提及的“计算机作业”(也称为“作业”)可以在位于计算机集群或云计算平台中的一个节点或一组节点中执行。术语“任务”在本文中是指作业的资源请求单元。每个作业可以包括一个任务或多个任务。一个任务只能在一个节点上执行。作业可以具有可以在不同节点上执行的各种不同任务。

执行时，任务需要消耗一定量的资源。调度引擎接收的任务可以根据可以执行该任务的资源节点的节点属性指定相对应的一个或多个任务参数。例如，一个任务可以指定它可以在具有2个vcore和16千兆(gigabit，GB)内存的节点上执行。此外，每个任务还可以指定“局部性约束”。本文中提及的术语“局部性约束”是指可以执行任务的一个节点或一组节点。

在谈及分析节点图结构顶点、节点树结构的根节点、节点树结构(的根节点)的子节点以及节点树结构的叶节点时，本文中提及的术语“分析”、“探索”、“访问”在本文中可以互换使用。分析节点图结构顶点、节点树结构的根节点、节点树结构(的根节点)的子节点以及节点树结构的叶节点包括：对节点图结构顶点、节点树结构的根节点、节点树结构(的根节点)的子节点以及节点树结构的叶节点分别进行访问、内容读取和内容使用。

在谈及分析节点图结构和节点树结构时，本文中提及的术语“分析”和“遍历”在本文中可以互换使用。分析和称为“遍历”节点图结构是指对节点图结构的节点图结构顶点进行分析(或采用其它术语，访问或探索)的过程。分析和称为“遍历”节点树结构是指对节点树结构的根节点、子节点和叶节点进行分析(或采用其它术语，访问或探索)的过程。

图1示出了适于实现本技术的非限制性实施例的装置100的示意图。装置100包括处理器137和存储器(未示出)。装置100的所述存储器存储可由处理器137执行的指令。可由处理器137执行的所述指令可以存储在位于装置100中的非瞬时性存储介质(未示出)中。所述指令包括资源管理器(resource manager，RM)130的指令。

图1还示出了运行计算机应用(未示出)的客户端设备120。所述计算机应用向装置100发送任务125。当RM 130的所述指令由所述装置的处理器137执行时，使得RM 130将从客户端设备120接收的任务125分配给节点110。

RM 130还包括调度引擎135。调度引擎135包括可由装置100的处理器137执行的指令，以执行本文描述的各种方法。

装置100还可以包括数据库140。数据库140可以存储数据，所述数据可以包括本文描述的各种参数等。

当RM 130的指令由处理器137执行时，RM 130从客户端设备120接收任务125，从节点110和/或从其它源(未示出)接收节点数据115。节点数据115包括一组节点ID和其它数据，例如节点属性，如下所述。RM 130将任务125分配给节点110。

本文描述的方法可以由调度引擎135的资源调度例程(resource schedulingroutine，RSR)160执行。

图2示出了本技术的各种实施例提供的RSR 160和由RSR 160生成的调度方案150。RSR 160根据接收到的节点数据115和任务125生成调度方案150。调度方案150将每个任务(在调度方案150中描绘为t1、t2等)映射到一个节点(在调度方案150中描绘为n1、n2等)，同时满足下文所述的各种准则。在本文中，调度方案150在表1和表10的伪码中也称为调度方案“A”。

除了每个节点ID之外，RSR 160接收的节点数据115还包括对应于节点110中的每一个的所述节点属性的值。

RSR 160接收的所述节点属性指定所述对应节点的可用节点属性的最大值。当所述节点由RSR 160分配时，不能超过所述可用节点属性的所述最大值。例如，如果所述节点属性中的一个(例如内存)指定为2GB，则分配的任务在其中执行时使用的内存不能超过2GB。

在本文中，节点属性的数量也称为“资源维度的数量”。资源维度的数量确定资源节点可以映射到的坐标空间的维度的数量，如下所述。在本文中的表1和表10中呈现的伪码中，D是资源维度的数量。

在本文中的表1至表4、表7和表8、表10中呈现的伪码中，R是将每个节点n∈N映射为其以D维向量R(n)表示的可用性的资源函数。R

RSR 160接收的每个任务都指定任务ID(在本文呈现的伪码中称为id)和任务参数的值。在本文呈现的伪码中，任务表示为t。任务ID是指唯一的任务标识符。

任务参数对应于节点属性，例如可以是：vcore值、内存值、可以永久存储数据的任何类型内存的内存输入/输出带宽(换言之，可以从内存中检索多少数据以及检索这些数据的速度有多快)、网络参数值和GPU参数值，例如电压值和时钟速度值。

RM 130接收并因此由RSR 160接收的任务参数的值指定执行相应任务所需的资源节点的期望节点属性。该组任务参数也可以称为相应任务的“可用性约束”。

在本文中的表1至表4、表7、表10中呈现的伪码中，Q是将每个任务t∈T映射到其以D维向量Q(t)表示的请求资源的请求函数。Q

RSR 160也可以接收搜索准则。例如，RSR 160接收的搜索准则可以是优化目标，例如最大完工时间(换言之，完成一组任务中的所有任务的执行所花费的总时间)、调度吞吐量(换言之，每时间单位内完成的总工作量)、资源节点的总体利用率、公平性(换言之，每个任务的CPU时间相等，或者根据每个任务的优先级和工作量分配适当的时间)和负载均衡(换言之，在资源节点之间高效和/或均匀地分配任务)。搜索准则可以从调度引擎135接收。搜索准则可以是调度引擎135的参数，可以取决于所述调度引擎的配置和/或可以由系统管理员设置。

除了任务参数之外，RSR 160还可以随每个任务接收一组候选节点。所述一组候选节点指定可用于容纳所述任务的一组节点及其对应的候选节点标识符。所述一组候选节点也可以称为相应任务的“局部性约束”。

在本文中的表1、表2、表4、表9、表10中呈现的伪码中，L是将每个任务t∈T映射到其候选节点集

另参考图1，为了将节点110调度到任务115，首先需要根据各种比较规则对节点110进行排序，然后根据可用性约束和局部性约束来选择节点110。

表1示出了本发明各实施例提供的用于实现顺序资源调度例程(sequentialresource scheduling routine，SeqRSR)的伪码。SeqRSR是RSR 160实现的非限制性示例。

RSR 160接收以下各项作为输入：资源维度的数量D、一组节点N、一系列任务T、资源函数R、请求函数Q和局部性函数L。在一些实施例中，一系列任务T中的任务t的序号越小可以指示在调度中的优先级越高。

RSR 160接收资源函数R，资源函数R将每个节点n∈N映射到其以D维向量

在表1中，第1行以空调度方案A开始。在第2行，执行初始化。当执行表1的第3行至第6行时，RSR 160通过按顺序迭代所有任务来构建调度方案A。

在每一次迭代时，对于一系列任务T中的每个任务t，RSR 160尝试确定匹配节点n。匹配节点n是一组节点N中满足任务t的可用性约束的节点。任务t的可用性约束意味着在任一节点上调度的任务t不超过该节点针对所有任务参数的可用性。

在一些实施例中，任务t可以请求匹配节点n也满足局部性约束。局部性约束意味着每个任务t∈T的选定节点是任务t中指定的候选节点集L(t)中的节点之一，如果候选节点集L(t)不是该任务的NIL。

在表1的第4行，RSR 160调用函数schedule()来为任务t调度节点n。在第5行，将新的任务节点对添加到调度方案A。在第6行处，RSR 160更新相关数据结构。

RSR 160将函数schedule()、initialize()和update()声明为虚函数。这些函数可以由具有特定调度策略的特定资源调度进程覆盖。

表1中的函数schedule(t)负责选择节点n∈N来调度任务t∈T。函数schedule(t)的简单实现(例如传统实现)可能必须扫描整个节点集N来调度单个任务。这很耗时，尤其是因为触发函数schedule(t)的次数对应于一系列任务T中的任务总数。

在本发明的至少一个实施例中，当执行表1中的函数schedule(t)时，RSR 160确定节点集N的适合节点。所述适合节点是满足给定任务t的可用性约束的节点。在一些实施例中，所述适合节点也满足给定任务t的局部性约束。

函数schedule(t)的实现依赖于相应任务t中请求的资源调度策略。所述资源调度策略可以由系统管理员定义。资源调度策略可以从现有技术中采用，例如：LeastFit调度策略、BestFit调度策略、FirstFit调度策略、NextFit调度策略或随机调度策略。为了将任务映射到节点，其中一个调度策略在所述适合节点中选择所述节点。

LeastFit调度策略将任务t调度(映射)到所有适合节点中可用性最高的节点。在一个节点调度一个任务后，下一个任务可以使用该节点的剩余资源。使用LeastFit调度策略可以促使所有节点之间的负载均衡。

BestFit调度策略将任务t调度到适合节点中可用性最低的节点。BestFit用于查找可用性尽可能接近任务t的实际请求的节点。

FirstFit调度策略将任务t调度到在基于迭代的搜索中找到的第一个适合节点n。

NextFit调度策略是FirstFit的变体。NextFit从FirstFit开始以查找适合节点，但是，当为下一个任务调用时，NextFit从它在上一个任务中停止的位置开始搜索，而不是从所有节点列表的开头开始搜索。

随机调度策略将任务t随机调度到适合节点n。

在本技术的至少一个实施例中，RSR 160中的schedule(t)函数生成并执行索引数据结构，在本文中索引数据结构称为分布式桶(distributed buckets，DistBuckets)结构。

表2描述了本发明各实施例提供的伪码中的DistBuckets结构的DistBuckets子例程(在本文中也称为“函数”)和DistBuckets成员字段。

表2的DistBuckets结构是索引数据结构。DistBuckets结构在此按照面向对象的设计原则进行描述。DistBuckets结构也可以称为“DistBuckets类”。DistBuckets结构可以通过高效的重用实现RSR 160的各种函数。

在本技术的一些实施例中，一组DistBuckets实例具有图层次结构。每个DistBuckets实例B可以是DistBuckets结构的顶点。在一些实施例中，DistBuckets结构可以具有树层次结构，其中，DistBuckets实例B是DistBuckets结构的根实例、子实例和叶实例。DistBuckets结构的根实例在本文中称为“根DistBuckets实例”。DistBuckets结构的根实例的子实例在本文中称为“子DistBuckets实例”。DistBuckets结构的叶实例在本文中称为“叶DistBuckets实例”。表2中的DistBuckets结构有五个公共成员函数：三个基本(也称为“基础”)函数和两个辅助函数。三个基本函数是add()函数、remove()函数和getNodeCoord()函数。DistBuckets结构还有三个成员字段。

DistBuckets函数可以作为公共函数执行，因此DistBuckets函数可以在DistBuckets结构的内部和外部使用。

每个DistBuckets结构B包括一组节点。DistBuckets结构的函数add(n)通过将节点n添加到DistBuckets实例B来更新DistBuckets实例B的元素。DistBuckets结构的函数remove(n)通过从DistBuckets实例B移除节点n来更新DistBuckets实例B的元素。

RSR 160将每个DistBuckets实例B映射到特定坐标向量，因此映射到多维坐标空间的特定子空间。RSR 160还根据节点属性的值并通过使用索引将接收的节点集的节点ID中的每一个映射到一个或多个DistBuckets实例。这种多维索引可以有助于提高搜索与接收的任务匹配的节点的速度。

图3描绘了本技术的非限制性实施例提供的坐标空间300的非限制性示例，其中17个DistBuckets实例映射到坐标空间300。

如上所述，可能有许多节点属性和许多任务参数。在本文的图3至图6K中提供的非限制性示例中，节点属性为节点vcore值和节点内存值。类似地，在本文的图3至图6K中提供的非限制性示例中，任务参数为任务vcore值和任务内存值。应理解，本文描述的技术可以应用于任意数量的节点属性和任务参数，因此可以使用任意维数的坐标空间。

表2的DistBuckets结构用于将每个节点并因此将节点ID映射到坐标空间300中的坐标。表2的DistBuckets结构的函数使用节点属性的值作为节点坐标，对节点标识符在坐标空间中的位置进行唯一确定。

坐标空间的维数可以由RM 130接收的节点数据115中的节点属性的数量定义。DistBuckets结构的维数可以对应于接收的节点数据中的节点属性的数量和/或接收的任务数据中的任务参数的数量。

参考图3，坐标空间300的每个维度对应一个节点属性。坐标空间300的维度为：vcore数和内存。

节点在二维坐标空间300中的位置由节点坐标(v,m)定义，其中，“v”对应于vcore数，“m”对应于该节点的内存量。

两个或多个节点可以具有相同的节点可用性，因此可以映射到坐标空间300中的相同位置。每个DistBuckets实例310可以包括节点，其节点属性对应于DistBuckets实例310的坐标(v,m)：v个vcore和m内存。

一个非限制性示例是，RM 130接收节点数据，该节点数据包括节点ID和节点集320的节点属性的对应值。图3所示的节点集320可以描述如下：

N＝{a(4V,4G),b(4V,2G),c(3V,5G),d(3V,5G),

e(6V,1G),f(4V,1G),g(3V,3G),h(6V,3G),

p(6V,4G),q(1V,3G),u(5V,5G),v(5V,2G)}, (1)

其中，每个节点具有节点ID，后跟表示相应节点在两个维度上的可用性的值：两个节点属性(例如vcore和内存)的值。

例如，名称“b(4V,2G)”是指具有节点ID“b”、4个vcore和2GB可用内存的节点。

RSR 160用于使用节点属性的值将接收的节点集的节点ID映射到坐标空间300，以确定在坐标空间300中的节点坐标。

在图3中，节点c和d(表示为{c、d})具有属性(3V,5G)，RSR 160可以确定节点c和d在坐标空间300中具有坐标(3,5)。RSR 160用于将节点c和d映射到具有坐标(3V,5G)的DistBuckets实例311，因为节点c和节点d均具有3个vcore和5GB内存。

参考表2，表2中的第29行至第31行显示每个DistBuckets实例B具有三个成员字段。表2中DistBuckets结构的成员字段B.x是指DistBuckets实例B的坐标向量，定义多维坐标空间中的子空间。每个坐标向量包括一组坐标。例如，在图3中，坐标为(3,5)的DistBuckets实例对应于二维坐标空间300中具有单个坐标向量(3,5)的子空间。

应理解，坐标空间300中的“子空间”可以为坐标空间300中的某个位置，也可以包括坐标空间300的坐标范围内的多个位置。例如，坐标空间300的子空间可以包括坐标空间300中具有坐标向量{(6,1),(6,2),(6,3),(6,4),…}的位置。

参考图3和表2，根据节点n的可用性R(n)，RSR 160使用函数getNodeCoord(n)将节点n映射到位于多维坐标空间中坐标为x

在表2中，DistBuckets结构的成员字段B.elements表示DistBuckets实例B的一组节点。属于B.elements的每个节点n(换言之，n∈B.elements)可以在B.x定义的子空间中具有节点坐标x

表2中的成员字段B.children包括作为DistBuckets实例B的子实例的DistBuckets实例的列表。DistBuckets实例的字段“children”共同定义DistBuckets实例的层次结构，该层次结构具有从一般到特定的顺序。

在表2中，坐标x为D维向量。x的第d个条目(用x

x＝(x

换言之，当d≤l时x

例如，坐标向量(5,27,*,*)是维度D＝4且分拆索引l＝2的坐标向量。如果l＝D，则坐标向量x没有通配符“*”，B是叶DistBuckets实例，B.x是叶坐标向量。

如果l

如果l＝0，则坐标向量中的坐标可以全部用通配符“*”表示，B是根DistBuckets实例，B.x是根坐标向量。

在图3中，坐标空间300包括12个节点，这些节点映射到vcore和内存两个维度中的17个DistBuckets实例。每个DistBuckets实例B描绘为矩形(如果DistBuckets实例B是非叶实例)或圆形(如果DistBuckets实例B是叶实例)。

在图3中，B.x和B.elements描绘在每个DistBuckets实例B的矩形和圆形内。箭头表示不同DistBuckets实例之间的子父关系：如果B→B′，则B′是B的子实例，即B′∈B.children。

具有叶坐标向量的叶DistBuckets实例可以映射到多维坐标空间中的位置，每个B.x可以将多维坐标空间中的子空间定义为叶坐标的非空集。如果B.x为叶坐标向量，则叶DistBuckets实例B的子空间为{B.x}，其中，{B.x}为包括单个叶坐标B.x的坐标集。

在图3中，例如，具有坐标(6,4)的子空间为{(6,4)}。如果B.x为非叶坐标向量，则DistBuckets实例B的子空间对应于许多叶坐标的集合。DistBuckets实例B 335具有坐标向量(6,*)时，其子空间包括以下坐标：{(6,0),(6,1),(6,2),(6,3),(6,4),(6,5),...}。

如果DistBuckets实例B为根DistBuckets实例330并且B.x为根坐标向量，则DistBuckets实例B 330的子空间对应于具有所有可能叶坐标向量的整个DistBuckets空间。要将集合运算符应用于坐标，可以将每个坐标隐式转换为其在多维坐标空间300中的对应子空间，例如，

每个DistBuckets实例B包括元素B.elements，它们是节点集N中节点坐标向量等于DistBuckets实例坐标向量的节点的子集。字段B.elements可以表示如下：

其中，x

成员字段B.elements和B.x紧密联系：

在图3中，坐标向量为(3,5)的DistBuckets实例具有B.elements{c、d}。坐标向量为(3,*)的DistBuckets实例具有B.elements{c、d、g}。如果第一DistBuckets实例的坐标向量是第二DistBuckets实例的坐标向量之一，则第二DistBuckets实例在其B.elements字段中包括第一DistBuckets实例的B.elements字段中的所有节点。换言之，可以写成

DistBuckets结构通过字段children对不同DistBuckets实例的从一般到特定的顺序进行递归定义。每个DistBuckets实例B可以包括表示为“B.children”的children字段。每个B.children字段包括DistBuckets实例的children列表。第一DistBuckets实例的每个子实例可以映射到具有坐标向量的子空间，其中该坐标向量比所述第一DistBuckets实例的坐标向量具有更少的通配符“*”。如果DistBuckets实例B为叶实例，则B.children＝NIL。

如果DistBuckets实例B为非叶实例，则DistBuckets实例B的第i个子实例可以表示为B.children[i]或B[i]。假设字段B.x有l个整数值，则每个子B[i].x有(l+1)个整数值：B[i].x的前l个值与B.x相同，B[i].x的第(l+1)个值为i，使得：

B.x＝(x

B[i].x＝(x

可以说B比B[i]更一般，或者说B[i]比B更特定。用集合运算符描述DistBuckets实例之间的关系，例如，可以写成

在图3中，各种坐标和对应的DistBuckets实例组织在分层树中，该分层树有3层。箭头示出了由children定义的从一般到特定的分层关系，箭头指向更不一般(即，更特定)的DistBuckets实例。

在图3中，坐标向量为(*,*)的根DistBuckets实例330具有5个子DistBuckets实例335，其坐标向量为{(1,*),(3,*),(4,*),(5,*),(6,*)}。(5,*)处的DistBuckets实例310有两个子实例：叶DistBuckets实例311、313。叶DistBuckets实例311、313的坐标向量分别为{(5,2),(5,5)}。

在图3中，有6×6＝36个叶坐标。11个叶坐标映射到11个非空DistBuckets实例，例如，坐标向量为(3,5)的叶DistBuckets实例311。

对于每个DistBuckets实例B，不同的子实例总是不相交的，并且所有子实例的并集等于父实例。

B.x＝∪

B.elements＝∪

在图3中，坐标向量为(*,*)的根DistBuckets实例330包括N中的所有节点：根DistBuckets实例330的子实例在它们的elements字段中没有任何公共节点，并且所有子实例的元素的并集产生完整节点集N。

参考表2，函数B.getNodeCoord(n)确定节点n的节点坐标向量x

函数B.add(n)将节点n添加到DistBuckets实例B。在表2的第2行，RSR 160确定节点n的节点坐标向量x

如果节点坐标向量x

在图3中，在根DistBuckets实例330对节点b(4V,2G)调用add()函数后，RSR 160将节点b映射到坐标向量为(*,*)、(4,*)和(4,2)的DistBuckets实例。

当RSR 160执行表2中的函数B.remove(n)时，RSR 160从DistBuckets实例B移除节点n。函数B.remove(n)可以具有类似于函数B.add(n)的代码逻辑。当执行函数B.remove(n)时，RSR 160递归地从DistBuckets实例的B.elements字段和子B[i]的elements字段中移除节点n(而不是添加n)。

DistBuckets结构的两个辅助成员函数为：getTaskCoord()和fits()。两个辅助成员函数都可以提供每次调用O(1)运行时成本。

函数B.getTaskCoord(t)确定任务t的叶任务坐标向量x

函数B.fits(t)确定DistBuckets实例B是否适合任务t。表2的第25行和第26行表明，当由RSR 160执行时，如果满足以下两个条件，函数B.fits(t)可以返回“true”：(1)

如果B.fits(t)返回“true”，则DistBuckets实例B可以称为“适合t的DistBuckets实例”。如果DistBuckets实例B适合任务t，则调度引擎可以将任务t调度到B.elements的一个节点。即使DistBuckets实例B可能适合t，DistBuckets实例B在B.elements中可能仍然没有匹配的节点标识符来调度任务t。

虽然实现DistBuckets结构的方法有很多种，但表2中列出的每个函数，例如add(n)、remove(n)、getNodeCoord(n)、getTaskCoord(t)、fits(t)可以具有恒定的每次调用运行时。换言之，表2中列出的每个函数可以具有O(1)阶的每次调用运行时。

参考图3，二维坐标空间300具有vcore坐标和内存坐标。坐标空间300的大小可以描述为Vmax×Mmax。Vmax和Mmax分别表示一个节点的最大可能vcore值和最大可能内存值。每个坐标空间300可以存储节点集N中的节点标识符的子集。这种实现可能需要给内存预先分配Vmax、Mmax，以及每个附加节点属性的其它最大值。

RSR 160还包括全局变量

表3描述了本发明的至少一个实施例提供的用于初始化和更新RSR 160的全局变量

当RSR 160启动时，如果DistBuckets结构具有树层次结构，则变量初始化函数initialize()初始化对应于根DistBuckets实例330的全局变量

节点集N中的所有节点都添加到全局变量

为了支持恒定数量的DistBuckets实例，使用多项式空间即可。函数initialize()的运行时间可以是O(|N|)阶。在RSR的整个执行过程中，所有update()调用的累积运行时间可以是O(|T|)阶。

表4描述了本技术的至少一个实施例提供的子例程schedule的伪码。表5描述了本技术的至少一个实施例提供的在表4的子例程schedule()中使用的类Iterator的伪码。

子例程schedule()迭代可从

在表4的第1行中，函数(或换言之，“子例程”)schedule()首先创建包含全局变量

通过利用DistBuckets结构的图层次结构，RSR 160可以穷尽搜索坐标空间300，而无需明确列举每个坐标。RSR 160使用图层次结构(例如树层次结构)遍历DistBuckets结构，以确定顶点，例如DistBuckets实例，该顶点包括任务t的匹配节点标识符。

如下文所述，在找到匹配节点标识符之后，RSR 160将匹配节点的匹配节点标识符映射到任务，并将每个任务ID与生成的调度方案150中确定的匹配节点标识符传输到调度引擎135。调度引擎135从RSR 160接收包含任务ID和匹配节点标识符的调度方案150。根据调度方案150，调度引擎135生成用于在节点110上执行任务125的调度。RM 130根据所述调度将所述任务分配给所述节点。

可以使用各种调度策略来识别DistBuckets结构中的匹配DistBuckets实例和匹配节点标识符。可以使用的所述各种调度策略，例如，如下文所述的LeastFit调度策略、BestFit调度策略、FirstFit调度策略、NextFit调度策略或随机调度策略。

LeastFit贪婪地选择所有适合节点中具有最高可用性的节点。为了确定“最高可用性”，RSR 160可以根据向量的字典顺序比较任意两个节点的可用资源。例如，给定两个不同的D维向量α＝(α

如果节点p和节点a各有两个节点属性，例如vcore和内存，并且vcore排在内存之前，p(6V,4G)和a(4V,4G)，则节点p的值大于节点a。换言之，p>a，因为在最重要的维度vcore上，节点p有6V，大于节点a的4V。类似地，节点a(4V,4G)的值大于节点b(4V,2G)，即a(4V,4G)>b(4V,2G)。虽然节点a和节点b在第一个维度vcore上是相等的，但是第二个维度是内存，并且节点a的内存大于节点b。

表6描述了本发明各实施例提供的用于IteratorLeastFit类的伪码，其中IteratorLeastFit类实现DistBuckets结构的LeastFit调度策略。根据源DistBuckets实例B

RSR 160按顺序分析(换言之，“探索”或“访问”)根实例B

如果最近发现的DistBuckets实例是B，则表6的函数next()按特定的顺序分析DistBuckets实例B的子实例。例如，可以选择具有最大可能索引k的适合子B[k]，以实现偏袒更大可用性的LeastFit调度策略。

一旦分析(称为“探索”)了所有适合的B.children，搜索便“回溯”到B的后代，直到达到具有未探索且可能适合的子实例的坐标。这个过程会一直继续下去，直到找到可从B

再次参考表6，每个IteratorLeastFit实例有五个成员字段：从Iterator继承的字段B

构造时(参见表4中的第1行和表6中的第20行)，每个IteratorLeastFit实例根据输入参数定义自己的B

在表6中，IteratorLeastFit结构定义了两个函数：函数next()继承自Iterator，nextChildIter()是辅助函数。

在函数next()中，表6中的第2行，当执行时，使count增加。当B

如果B

在表6的第15行中，函数childIter.next()返回“NIL”，这表示已分析(换言之，“已探索”)所有以B

在表6中，当B

为了确定k，表6的第18行可以从当前索引k开始按降序顺序对多个子调用B

在分析DistBuckets图并在DistBuckets树内搜索适合的节点时，当完全检查了以B为根实例的所有子图时，B可以称为“已完成”。换言之，当B.fits(t)返回“false”时，B可以称为“已完成”，因此无需进一步探索B.children。

当以DistBuckets实例B为源的IteratorLeastFit实例已完成其迭代并分析了该DistBuckets实例是否包括适合节点(在表6中，第7行适用于叶实例情况，第16行适用于非叶实例情况)时，DistBuckets实例B可以称为“已完成”。

RSR 160探索的DistBuckets实例也可以称为“节点图结构顶点”，而多个图结构顶点形成“节点图结构”。所述节点图结构顶点可以是节点图结构根节点、图结构子节点或节点图结构叶节点。在图3中，所述节点图结构包括图结构根节点330、节点图结构子节点335和节点图结构叶节点340。

在图4A至图4P、图5A至图5P、图6A至图6K中，为了说明各种实现步骤，每个DistBuckets实例具有细轮廓线、粗虚轮廓线或粗实轮廓线。每个DistBuckets实例B最初具有白色背景并具有细轮廓线。当DistBuckets实例B被发现后，将B描绘为具有粗虚轮廓线的(灰色)框或圆圈。当DistBuckets实例B为已完成后，DistBuckets实例B以粗实轮廓线和深(黑色)背景示出。

图4A至图4P示出了本发明各实施例提供的资源调度方法的几个实现步骤。所示出的实现步骤是调用IteratorLeastFit的next()函数时针对具有图3所示的坐标向量为(*,*)的根DistBuckets实例和任务t的实现步骤。

如果DistBuckets实例B不适合，则DistBuckets实例B可以在被发现后立即完成(例如，如图4F和图4O所示)。或者，如果B为叶实例，则DistBuckets实例B可以在被发现后立即完成(例如，如图4C、图4D、图4H、图4I、图4L、图4M所示)。当B的iterator选择子B[k]进行进一步迭代时，B[k]被发现。在图4A至图4P中，当B[k]被发现时，从B通向B[k]的箭头470描绘为粗箭头。

在图4A至图4P中，任务455t[(1V,2G),{b,c,e,f}]指定任务参数为1V和2G的请求资源Q(t)＝(1V,2G)。任务455还指定候选节点标识符为b、c、e、f的候选集L(t)＝{b,c,e,f}。任务t的适合区域的边界460示为虚线。任务t的所述适合区域在坐标空间中具有大于等于每个任务坐标的坐标。用数学术语来说，任务t的所述适合区域可以表示为：

图4A至图4P描绘了对具有通配符坐标(*,*)的根DistBuckets实例482三次调用函数next()的实现步骤，其中，DistBuckets实例482在图4A中发现并且在图4P中完成。图4A至图4I描绘了函数next()的第一次调用的步骤，其返回了可用性最高且坐标为(4,2)的第一适合叶DistBuckets实例(在图4I中用勾号484示出)。

图4J至图4L描绘了函数next()的第二次调用的步骤，其返回了坐标为(3,5)的第二适合叶DistBuckets实例(在图4L中用勾号486示出)。图4M至图4P描绘了函数next()的第三次调用的步骤，其返回了“NIL”，标志着迭代的结束。在图4P中，坐标为(*,*)的根DistBuckets实例482显示为具有黑色背景，因为它“已完成”。

再次参考表4，如果

参考表6，函数next()的结果取决于第18行分析B

为了使用BestFit调度策略分析子DistBuckets，RSR 160可以先访问和分析在任务t的适合区域内具有最小可能索引k的适合子B[k]，因为BestFit调度策略偏袒更低的可用性。

为了实现IteratorBestFit，表6可以修改如下：第18行可以替换为“k←min{i|i>k∧B

图5A至图5P示出了本发明各实施例提供的使用BestFit调度策略的资源调度方法的各个执行步骤。该方法的执行包括IteratorBestFit中的函数next()的三次调用，使用与图4A至图4P中相同的节点集N的非限制性示例。

图5A至图5E描绘了IteratorBestFit中函数next()的第一次调用的执行步骤，其返回了可用性最低的第一适合叶DistBuckets实例550，该实例的节点坐标为(3,5)。

图5E至图5H描绘了IteratorBestFit中函数next()的第二次调用的执行步骤，其返回了坐标为(4,2)的第二适合叶DistBuckets实例584。

图5I至图5P描绘了IteratorBestFit中函数next()的第三次调用的执行步骤，其返回了“NIL”，标志着迭代的结束。

再次参考表4和SeqRSR的函数schedule()，如果

RSR 160可以使用表2的DistBuckets结构分别通过节点的资源或任务的请求向量将节点或任务映射到坐标。在一些实施例中，RSR 160可以覆盖getNodeCoord()和getTaskCoord()，并执行各种坐标函数来实现不同的调度策略和优化目标。

在一些实施例中，可以修改坐标向量中坐标的顺序。在一些实施例中，如果内存是任务的主要资源(例如，拥有足够的内存可能比vcore更重要)，则内存可以排在vcore之前。

在一些实施例中，坐标可以通过内存和vcore的高多项式项来修改，例如：R

在一些实施例中，getNodeCoord()和getTaskCoord()可以是具有节点和节点属性及任务和任务参数作为输入以及具有多维坐标向量作为输出的任何函数。在至少一个实施例中，可以使用如下文所述的粒度来计算坐标向量。

表7描述了本发明各实施例提供的函数getNodeCoord()和getTaskCoord()的伪码，这些函数使用粒度确定坐标。

执行函数getNodeCoord()时，RSR 160可以使用D维粒度向量θ＝(θ

例如，粒度参数可以由系统管理员定义。

使用粒度参数θ

粒度参数θ

在一些实施例中，粒度参数可以是资源函数的函数，例如，如上所述的R

图6A至图6H示出了本发明各实施例提供的使用LeastFit调度策略和粒度的资源调度方法的各个执行步骤。在图6A至图6H中，粒度向量为θ＝(2,3)。所述资源调度方法的执行包括调用IteratorLeastFit中的函数next()。节点集N和任务t与在图4A至图4P中相同。

当粒度向量为θ＝(2,3)时，叶DistBuckets实例的总数减为5。为了比较，在图5A至图5P中，其中粒度向量为θ＝(1,1)，叶DistBuckets实例的总数为11。

图6A至图6D描绘了函数next()的第一次调用期间方法的执行步骤，其返回了坐标为(3,1)的叶DistBuckets实例B

图6E至图6G示出了函数next()的第二次调用期间方法的执行步骤，此时RSR 160获得坐标为(2,2)的叶DistBuckets实例B1。坐标为(2,2)的DistBuckets实例包括用于任务t的节点c(3V,5G)。如图4A至图4P所示，与采用粒度θ＝(1,1)选择的节点b(4V,2G)相比，节点c(3V,5G)的可用性更低。因此，当使用大于1的粒度参数时，可能不会首先找到可用性最高的节点。

如图6H所示，在函数next()的第三次调用期间可能会找到坐标为(2,1)的节点。

通常会在资源调度中使用预留，以解决资源请求很大的任务的饥饿问题。RSR 160可以支持对具有DistBuckets结构的LeastFit和其它调度策略的预留。每个节点n最多可以对单个任务t有一个资源预留，只能为任务t调度该资源预留，而每个任务t可以在多个节点上有多个预留。表1的RSR 160可以使用两个附加输入参数和一个附加约束。

R′是预留参数，它将节点集N中的每个节点n(n∈N)映射到其以D维向量R′(n)∈R

L′是预留局部性函数，它将任务集T中的每个任务t(t∈T)映射到对任务t有预留的预留节点子集

如果节点a(4V,4G)对任务t

为了支持具有预留的LeastFit，RSR 160可以具有DistBuckets实例的两个全局变量

如表8所示，为了计算节点n的坐标，

表9描述了具有预留的LeastFit的伪码。在第1行和第2行中，RSR 160分别从

换言之，为了考虑节点预留，节点中的每一个节点的节点坐标可以通过使用节点中的每一个节点的所述任务的预留数据和其它任务的预留数据来确定。将节点和对应的节点图结构顶点映射到坐标系时，RSR 160可以从节点坐标中扣除针对每个节点属性(维度)为其它任务预留的资源量。

虽然上文针对RSR 160描述了DistBuckets结构的有效性，但是DistBuckets结构也可以用在替代资源调度例程中。

表10描述了本发明各实施例提供的通用资源调度例程(generalized resourcescheduling routine，GRSR)的非限制性示例，GRSR是资源调度算法的通用框架。可以实现GRSR来代替RSR 160。

GRSR在第1行以空调度方案A开始，并在第2行至第6行迭代构建A。在每一次迭代时，在第3行，接收任务子集

GRSR可以将selectTasks()和schedule()声明为虚函数，具体的资源调度算法可以通过具体的实现来覆盖这两个虚函数。具体地，schedule()的快速实现可以利用针对各种调度策略的DistBuckets结构。例如，GRSR可以使用多个DistBuckets实例来并行调度多个任务，然后解决潜在的冲突，例如在一个资源节点上过度调度。

图7示出了本发明各实施例提供的计算集群或云计算平台的资源节点的资源调度方法700的流程图。所述方法可以由RSR 160的软件的例程、子例程或引擎执行。用于执行方法700的所述RSR的所述软件的编码也在本领域普通技术人员关于本发明的可理解范围内。方法700包含的步骤可以多于或少于所示和描述的步骤，并且可以按照不同的顺序执行。可由装置100的处理器(未示出)为执行方法700而执行的计算机可读指令可以存储在所述装置的存储器(未示出)或非瞬时性计算机可读介质中。

在步骤710中，RSR 160接收节点集中的节点的节点标识符，并接收所述节点标识符中的每一个的节点属性的值。

在步骤712中，从客户端设备接收指定任务参数值的任务。

在步骤714中，生成节点图结构。所述节点图结构具有至少一个节点图结构顶点，所述至少一个节点图结构顶点通过使用所述节点属性的所述值将节点标识符中的每一个映射到坐标空间，来映射到所述坐标空间，从而确定节点坐标。所述节点图结构具有至少一个节点图结构顶点，所述至少一个节点图结构顶点包括至少一个节点标识符并映射到所述坐标空间。所述至少一个节点标识符中的每一个使用所述节点属性的所述值映射到所述坐标空间，从而确定节点坐标。

在步骤716中，所述任务通过使用所述任务参数的所述值映射到所述坐标空间，从而确定任务坐标。

在步骤718中，通过分析(换言之，探索)位于所述任务的适合区域内的所述至少一个节点图结构顶点，确定第一节点的第一节点标识符。所述第一节点的坐标位于所述任务的所述适合区域内。所述适合区域包括所述坐标空间中大于等于每个任务坐标的坐标。在至少一个实施例中，RSR 160确定映射到节点图结构顶点的节点标识符是否与所述任务中指定的候选标识符中的一个相同。

在一些实施例中，可以根据随所述任务接收的节点属性偏好确定探索所述节点图结构顶点的顺序。在一些实施例中，可以根据资源调度策略确定探索所述节点图结构顶点的顺序，所述资源调度策略为LeastFit调度策略、BestFit调度策略、随机调度策略和预留调度策略中的一种。在探索所述节点图结构的所述节点图结构顶点时，RAR 160遍历所述节点图结构以确定所述匹配节点标识符。

在步骤720中，将所述第一节点标识符映射到所述任务以生成调度方案。

在步骤722中，将所述调度方案传输到调度引擎。

本文描述的系统、装置和方法可以针对各种节点属性(例如vcore和内存)快速实现O(1)阶、查找、插入和删除。

本文描述的技术可以实现同时考虑多个维度(例如vcore、内存和GPU)和局部性约束的各种资源节点选择策略的快速实现。使用本文描述的方法和结构，可以在多维坐标系中执行对用于调度的适合资源节点的搜索，该坐标系将资源节点的资源和任务映射到能够快速调度任务在资源节点上执行的坐标。对适合资源节点的搜索被限制在适合区域内，从而提高了搜索速度。本文描述的技术可以支持适合区域内的各种搜索路径，并能够快速选择用于调度的适合资源节点以执行任务。本文描述的粒度参数可以帮助进一步加快资源节点的资源调度以执行任务。

尽管已经参考本发明的特定特征和实施例描述了本发明，但是明显可以在不脱离本发明的情况下制定本发明的各种修改和组合。因此，说明书和附图仅被视为所附权利要求书限定的对本发明的说明，并且预期覆盖落入本发明的范围内的任何和所有修改、变化、组合或等同物。