Resource allocation for computer processing

Patent metadata

Field	Value
Publication number	US-10558501-B2
Application number	US-201615395225-A
Country	US
Kind code	B2
Filing date	Dec 30, 2016
Priority date	Mar 4, 2016
Publication date	Feb 11, 2020
Grant date	Feb 11, 2020

Abstract

A job that receives as input a data stream is executed. For the job, it is iteratively determined a backlog growth over a first period of time; a backlog volume; and whether to adjust a quantity of processing resources. For each iteration for which the quantity of processing resources allocated to the job are determined to be adjusted, adjusting the quantity of processing resources allocated to the job. For each iteration for which the quantity of processing resources allocated to the job are determined not to be adjusted, maintaining the quantity of processing resources allocated to the job.

First claim

What is claimed is:

1. A method implemented in a computer system, the method comprising:
executing, in a computer system that comprises multiple processing resources, a job that receives as input a data stream, wherein the amount of data in the data stream is unbounded;
iteratively determining, for the job:
a backlog growth over a first period of time, wherein the backlog growth is a measure of a growth of unprocessed data in the received data stream that is to be input into the job, and wherein the backlog growth is measured in terms of a change to a data size;
a backlog volume that is a measure of unprocessed data in the received data stream that is to be input into the job, and wherein the backlog volume is measured in terms of a data size;
determining, based on the backlog growth and the backlog volume, whether to adjust a quantity of processing resources allocated to the job, wherein, for an iteration of the determination the backlog growth is determined to be zero or negative and the backlog volume is determined to be at a target;
determining that the quantity of processing resources allocated to the job are determined not to be adjusted in response to the backlog growth being determined to be zero or negative and the backlog volume determined to be at a target;
for each iteration for which the quantity of processing resources allocated to the job are determined to be adjusted, adjusting the quantity of processing resources allocated to the job, wherein adjusting the quantity of processing resources further comprises determining whether to reduce the processing resources and if it is determined to reduce said processing resources determining how far to reduce the allocation of processing resources, wherein processor utilization is used as a proxy of whether the system can handle a next lower level of allocated processing resources; and
for each iteration for which the quantity of processing resources allocated to the job are determined not to be adjusted, maintaining the quantity of processing resources allocated to the job.

2. The method of claim 1 , wherein, for an iteration of the determination:
the backlog growth is determined to be zero or negative;
the backlog volume is determined to be below a target;
determining that the quantity of processing resources allocated to the job are determined to be adjusted in response to the backlog growth being determined to be zero or negative and the backlog volume determined to be below a target; and
wherein adjusting the quantity of processing resources allocated to the job comprises reducing the quantity of processing resources allocated to the job in response to the backlog growth being determined to be zero or negative and the backlog volume determined to be below a target.

3. The method of claim 1 , wherein, for an iteration of the determination:
the backlog growth is determined to be zero or negative;
the backlog volume is determined to be above a target;
determining that the quantity of processing resources allocated to the job are determined to be adjusted in response to the backlog growth being determined to be zero or negative and the backlog volume determined to be above a target; and
wherein adjusting the quantity of processing resources allocated to the job comprises increasing the quantity of processing resources allocated to the job in response to the backlog growth being determined to be zero or negative and the backlog volume determined to be above a target.

4. The method of claim 1 , wherein, for an iteration of the determination:
the backlog growth is determined to be positive;
the backlog volume is determined to be below a target
determining that the quantity of processing resources allocated to the job are determined not to be adjusted in response to the backlog growth being determined to be positive and the backlog volume determined to be below a target.

5. The method of claim 1 , wherein, for an iteration of the determination:
the backlog growth is determined to be positive;
the backlog volume is determined to be not below a target
determining that the quantity of processing resources allocated to the job are determined to be adjusted in response to the backlog growth being determined to be positive and the backlog volume determined to be not below a target; and
wherein adjusting the quantity of processing resources allocated to the job comprises increasing the quantity of processing resources allocated to the job in response to the backlog growth being determined to be positive and the backlog volume determined to be not below a target.

6. The method of claim 1 , wherein units of the data size are at least one of the group consisting of bits, bytes, megabytes, gigabytes, records, and cardinality.

7. The method of claim 1 , wherein units of the data size are at least one of the group consisting of bits, bytes, megabytes, gigabytes, records, and cardinality.

8. The method of claim 1 , the method further comprising:
iteratively determining, for the job, a processor utilization;
wherein iteratively determining whether to adjust a quantity of processing resources allocated to the job is further based on the processor utilization.

9. The method of claim 8 , wherein:
wherein, for an iteration of the determination:
the processor utilization is below a value;
determining that the quantity of processing resources allocated to the job are determined to be adjusted in response to the processor utilization being determined to be below a value; and

wherein adjusting the quantity of processing resources allocated to the job comprises reducing the quantity of processing resources allocated to the job in response to the processor utilization being determined to be below a value.

10. The method of claim 9 , where in reducing the quantity of processing resources allocated to the job in response to the processor utilization being determined to be below a value comprises reducing a discrete number of resources allocated to the job, the discrete number being based on the processor utilization.

11. The method of claim 10 , wherein the discrete number is a number of computer memory disks.

12. The method of claim 1 , wherein determining, based on the backlog growth and the backlog volume, whether to adjust a quantity of processing resources allocated to the job comprises smoothing the determining that results in oscillation of quantity of processing resources allocated to the job.

13. The method of claim 12 , wherein smoothing the determining comprises waiting for a second period of time.

14. The method of claim 12 , wherein smoothing the determining comprises averaging a plurality of determinations whether to adjust a quantity of processing resources allocated to the job.

15. A system comprising:
one or more processors configured to execute computer program instructions; and
one or more computer storage media encoded with computer program instructions that, when executed by one or more processors, cause a computer device to perform operations comprising:
executing, in a computer system that comprises multiple processing resources, a job that receives as input a data stream, wherein the amount of data in the data stream is unbounded;
iteratively determining, for the job:
a backlog growth over a first period of time, wherein the backlog growth is a measure of a growth of unprocessed data in the received data stream that is to be input into the job, and wherein the backlog growth is measured in terms of a change to a data size;
a backlog volume that is a measure of unprocessed data in the received data stream that is to be inpu

Assignees

• Google Llc

Inventors

• Bradshaw Robert
• Moctezuma Rafael De Jesús Fernández
• Mills Daniel
• Mcveety Samuel Green
• Whittle Samuel Carl
• Maksimenka Andrei
• Arad Cosmin Ionel
• Shields Mark Brian
• Nover Harris Samuel
• Fahndrich Manuel Alfred
• Gardner Jeffrey Paul
• Shmulyan Mikhail
• Lax Reuven
• Altay Ahmet
• Chambers Craig D

Classifications

• G06F9/5011

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• G06F9/5061

  Partitioning or combining of resources · CPC title

• G06F9/5016

  the resource being the memory · CPC title

• G06F9/505 Primary

  considering the load · CPC title

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title