# US 12,223,349 B2 · Utilization-aware resource scheduling in a distributed computing cluster > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,223,349 B2 - Document ID: US12223349B2 - Status: Granted - Kind: B2 - Application number: 17/379,742 - Filed: 2021-07-19 - Published: 2021-11-11 - Granted: 2025-02-11 - Earliest claimed: 2016-09-14 - Assignees: Cloudera, Inc. - Applicants: Cloudera, Inc. - Inventors: Karthik Kambatla - Web page: https://patentgrep.com/patent/US12223349B2 ## CPC - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU] - G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)} - G06F 9/505: {considering the load} - G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)} - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F 2209/483: Multiproc - G06F 2209/5021: Priority - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Embodiments are disclosed for a utilization-aware approach to cluster scheduling, to address this resource fragmentation and to improve cluster utilization and job throughput. In some embodiments a resource manager at a master node considers actual usage of running tasks and schedules opportunistic work on underutilized worker nodes. The resource manager monitors resource usage on these nodes and preempts opportunistic containers in the event this over-subscription becomes untenable. In doing so, the resource manager effectively utilizes wasted resources, while minimizing adverse effects on regularly scheduled tasks. ## Claims ### Claim 1 A method comprising: receiving information indicative of actual computing resource utilization at a worker node, the worker node having allocated a first-tier resource container to process a first task and a second-tier resource container to process a second task; allocating an opportunistic third-tier resource container at the worker node to process a third task, in response to determining that the actual computing resource utilization at the worker node has decreased below a first threshold since a time that the first-tier resource container and the second-tier resource container were allocated based on summing (i) unutilized resource slack occurring within at least one of the first-tier resource container and the second-tier resource container and (ii) an amount of unutilized unallocated resources at the worker node; wherein the opportunistic third-tier resource container includes at least a portion of the unutilized resource slack occurring within the at least one of the first-tier resource container and the second-tier resource container, and wherein the opportunistic third-tier resource container, having a lower tier status than the first-tier resource container and the second-tier resource container, is subject to de-allocation to the first-tier resource container and the second-tier resource container if the actual computing resource utilization at the worker node rises above a second threshold that is offset below a utilization capacity associated with the worker node; determining whether the actual computing resource utilization is between the second threshold and the utilization capacity associated with the worker node; and deallocating the opportunistic third-tier resource container in response to determining that the actual computing resource utilization is between the second threshold and the utilization capacity such that said deallocating occurs prior to the actual computing resource utilization reaching the utilization capacity associated with the worker node. ### Claim 2 (depends on 1) The method of claim 1, wherein the opportunistic third-tier resource container is allocated to process the third task after determining that the third task allows processing by opportunistic third-tier resources. ### Claim 3 (depends on 1) The method of claim 1, further comprising: determining whether to de-allocate the opportunistic third-tier resource container based on a periodic heartbeat signal of the received information. ### Claim 4 (depends on 3) The method of claim 3, wherein determining whether to de-allocate the opportunistic third-tier resource container includes: determining whether the actual computing resource utilization has risen above the second threshold when the periodic heartbeat signal is received. ### Claim 5 (depends on 1) The method of claim 1, wherein the received information includes values for the first threshold and/or the second threshold. ### Claim 6 (depends on 1) The method of claim 1, wherein the first threshold is based on the utilization capacity associated with the worker node. ### Claim 7 (depends on 6) The method of claim 6, wherein the first threshold is further based on a variable over-allocation parameter. ### Claim 8 (depends on 1) The method of claim 1, wherein the second threshold is further based on a variable preemption parameter. ### Claim 9 (depends on 1) The method of claim 1, further comprising: setting the first threshold and/or the second threshold based on the received information. ### Claim 10 (depends on 1) The method of claim 1, further comprising: adjusting the first threshold and/or the second threshold in response to changes in the actual computing resource utilization. ### Claim 11 (depends on 1) The method of claim 1, wherein the second threshold is higher than the first threshold. ### Claim 12 (depends on 1) The method of claim 1, wherein the first threshold and/or the second threshold are specific to the worker node and are different from thresholds of other worker nodes in a distributed computing cluster. ### Claim 13 A system comprising: a processor; and a memory having instructions stored thereon, which when executed by the processor, cause the system to: receive information indicative of actual computing resource utilization at a worker node, the worker node having allocated a first-tier resource container to process a first task and a second-tier resource container to process a second task; and allocate an opportunistic third-tier resource container at the worker node to process a third task, in response to determining that the actual computing resource utilization at the worker node has decreased below a first threshold since a time that the first-tier resource container and the second-tier resource container were allocated based on summing (i) unutilized resource slack occurring within at least one of the first-tier resource container and the second-tier resource container and (ii) an amount of unutilized unallocated resources at the worker node; wherein the opportunistic third-tier resource container includes at least a portion of the unutilized resource slack occurring within the at least one of the first-tier resource container and the second-tier resource container, and wherein the opportunistic third-tier resource container, having a lower tier status than the first-tier resource container and the second-tier resource container, is subject to de-allocation to the first-tier resource container and the second-tier resource container if the actual computing resource utilization at the worker node rises above a second threshold that is offset below a utilization capacity associated with the worker node; determine whether the actual computing resource utilization is between the second threshold and the utilization capacity associated with the worker node; and deallocate the opportunistic third-tier resource container in response to determining that the actual computing resource utilization is between the second threshold and the utilization capacity such that said deallocation occurs prior to the actual computing resource utilization reaching the utilization capacity associated with the worker node. ### Claim 14 (depends on 13) The system of claim 13, wherein the memory has further instructions stored thereon, which when executed by the processor, cause the system to further: allocate a second opportunistic third-tier resource container at the worker node to process a fourth task in response to determining that the actual computing resource utilization at the worker node is below a third threshold, wherein the second opportunistic third-tier resource container includes at least a second portion of the unutilized resource slack occurring within the at least one of the first-tier resource container and the second-tier resource container, and wherein the second opportunistic third-tier resource container, having a lower tier status than the first-tier resource container and/or the second-tier resource container, is subject to de-allocation if the actual computing resource utilization at the worker node rises above a fourth threshold. ### Claim 15 (depends on 14) The system of claim 14, wherein the third threshold is the same as the first threshold, and wherein the fourth threshold is the same as the second threshold. ### Claim 16 (depends on 13) The system of claim 13, wherein computing resources at the worker node include one or more of processing, memory, data storage, I/O, and/or network resources. ### Claim 17 A non-transitory computer readable medium storing instructions, execution of which by a computer system, cause the computer system to: receive information indicative of actual computing resource utilization at a worker node, the worker node having allocated a first-tier resource container to process a first task and a second-tier resource container to process a second task; and allocate an opportunistic third-tier resource container at the worker node to process a third task in response to determining that the actual computing resource utilization at the worker node has decreased below a first threshold since a time that the first-tier resource container and the second-tier resource container were allocated based on summing (i) unutilized resource slack occurring within at least one of the first-tier resource container and the second-tier resource container and (ii) an amount of unutilized unallocated resources at the worker node; wherein the opportunistic third-tier resource container includes at least a portion of the unutilized resource slack occurring within the at least one of the first-tier resource container and the second-tier resource container, and wherein the opportunistic third-tier resource container, having a lower tier status than the first-tier resource_container and the second-tier resource container, is subject to de-allocation to the first-tier resource container and the second-tier resource container if the actual computing resource utilization at the worker node rises above a second threshold that is offset below a utilization capacity associated with the worker node; determine whether the actual computing resource utilization is between the second threshold and the utilization capacity associated with the worker node; and deallocate the opportunistic third-tier resource container in response to determining that the actual computing resource utilization is between the second threshold and the utilization capacity such that said deallocating occurs prior to the actual computing resource utilization reaching the utilization capacity associated with the worker node. ### Claim 18 (depends on 17) The non-transitory computer readable medium of claim 17, storing further instructions, execution of which by the computer system, cause the computer system to further: receive a request to process a particular task, wherein the request includes an indication of whether to allow processing of the particular task using the opportunistic third-tier resource container.