Opportunistic job processing of input data divided into partitions and distributed amongst task level managers via a peer-to-peer mechanism supplied by a cluster cache

Patent metadata

Field	Value
Publication number	US-11282004-B1
Application number	US-201816229886-A
Country	US
Kind code	B1
Filing date	Dec 21, 2018
Priority date	Mar 28, 2011
Publication date	Mar 22, 2022
Grant date	Mar 22, 2022

Abstract

A global-level manager access a work order from a client and parameters associated with the work order. A service level agreement to meet the work order parameters is determined. The service level agreement includes a price. An indication is received from the client that the service level agreement is accepted. The one or more input files are partitioned into multiple shards, and the work order into multiple jobs. The jobs are distributed among a plurality of clusters to be processed using underutilized computing resources in the clusters. The job outputs are combined to form the work order output. The jobs are monitored to insure that the deadline for completion of the work order will be met.

First claim

What is claimed is:

1. A method for using a multi-tiered model for job distribution and completion, the method comprising:
receiving, by a cluster-level manager associated with a group of processes running on one or more processors that form a cluster, one or more input shards, wherein each of the one or more input shards (i) originate from a global-level manager and (ii) are generated based on processing, by the global-level manager, of a work order received by the global-level manager;
storing, by the cluster-level manager, the one or more input shards in a cluster cache, the cluster cache supplying a peer-to-peer mechanism for transferring the one or more input shards between the cluster cache and a plurality of task-level managers;
determining, by the cluster-level manager and based on a priority level associated with the one or more input shards, that the cluster-level manager is to delegate the one or more received input shards to a particular task-level manager of the plurality of task-level managers, including
identifying the particular task-level manager of the plurality of task level-managers based on one or more respective attributes of the plurality of task level-managers;

transferring, using the peer-to-peer mechanism from the cluster cache to the particular task-level manager identified by the cluster-level manager, the one or more received input shards;
generating, based on processing of the one or more input shards by the particular task-level manager or a computing cluster managed by the particular task-level manager, one or more output shards;
providing, by the particular task-level manager, the one or more output shards directly to a central storage; and
collecting, by the global-level manager, the output shards from the central storage.

2. The method of claim 1 , wherein the global level manager is configured to generate an output file in response to the work order based on the global level manager's assembling of received output shards from a plurality of cluster-level managers, wherein the received output shards from the plurality of cluster-level managers include the one or more received output shards from the cluster-level manager.

3. The method of claim 1 , the method further comprising:
receiving, by a cluster-level manager, one or more second input shards, wherein each of the one or more second input shards (i) originate from the global-level manager and (ii) are generated based on processing, by the global-level manager, of the work order or a different work order received by the global-level manager;
determining, by the cluster-level manager and based on a priority level associated with the one or more second input shards, that the cluster-manager is to process the one or more second input shards without delegating execution of the one or more second input shards to a task-level manager;
generating, by the cluster-level manager and based on processing of the one or more second input shards, one or more second output shards based on the cluster-level manager's processing of the one or more second input shards; and
providing, by the cluster-level manager, the one or more second output shards to the global-level manager.

4. The method of claim 3 , wherein the global level manager is configured to generate an output file in response to the work order based on the global-level manager's assembling of received output shards from a plurality of cluster-level managers, wherein the received output shards from the plurality of cluster-level managers include the one or more second output shards from the cluster-level manager.

5. The method of claim 3 , wherein determining, by the cluster-level manager and based on a priority level associated with the one or more second input shards, that the cluster-manager is to process the one or more second input shards without delegating execution of the one or more second input shards to a task-level manager comprises:
determining, by the cluster-level manager, that the one or more second input shards have been assigned a second level of priority that is higher than a threshold level of priority; and
determining by the cluster-level manager, to process the one or more second input shards without delegating the one or more second input shards to the task-level manager.

6. The method of claim 1 , wherein determining, by the cluster-level manager and based on a priority level associated with the one or more input shards, that the cluster-manager is to delegate the one or more received input shards to a task-level manager comprises:
determining, by the cluster-level manager, that the one or more input shards have been assigned a first level of priority that is lower than a threshold level of priority; and
delegating, by the cluster-level manager, the one or more input shards for processing by the task-level manager.

7. The method of claim 1 , wherein determining comprises determining, by the cluster-level manager and based on a priority level associated with the one or more input shards and completion deadline included in the work order.

8. The method of claim 1 , comprising adjusting processing throughput to meet a completion deadline.

9. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by one or more computers, to cause the one or more computers to perform the operations comprising:
receiving, by a cluster-level manager associated with a group of processes running on one or more processors that form a cluster, one or more input shards, wherein each of the one or more input shards (i) originate from a global-level manager and (ii) are generated based on processing, by the global-level manager, of a work order received by the global-level manager;
storing, by the cluster-level manager, the one or more input shards in a cluster cache, the cluster cache supplying a peer-to-peer mechanism for transferring the one or more input shards between the cluster cache and a plurality of task-level managers;
determining, by the cluster-level manager and based on a priority level associated with the one or more input shards, that the cluster-level manager is to delegate the one or more received input shards to a particular task-level manager of the plurality of task-level managers including
identifying the particular task-level manager of the plurality of task level-managers based on one or more respective attributes of the plurality of task level-managers;

transferring, using the peer-to-peer mechanism from the cluster cache to the particular task-level manager identified by the cluster-level manager, the one or more received input shards;
generating, based on processing of the one or more input shards by the particular task-level manager or a computing cluster managed by the particular task-level manager, one or more output shards;
providing, by the particular task-level manager, the one or more output shards directly to a central storage; and
collecting, by the global-level manager, the output shards from the central storage.

10. The system of claim 9 , wherein the global level manager is configured to generate an output file in response to the work order based on the global level manager's assembling of received output shards from a plurality of cluster-level managers, wherein the received output shards from the plurality of cluster-level managers include the one or more received output shards from the cluster-level manager.

11. The system of claim 9 , the operations further comprising:
receiving, by a cluster-level manager, one or more second input shards, wherein each of the one or more second input shards (i) originate from the global-level manager

Assignees

• Google Llc

Inventors

• Konerding David
• Breckenridge Jordan M
• Belov Daniel

Classifications

• G06Q10/06315

  Needs-based resource requirements planning or analysis · CPC title

• G06F9/485

  Task life-cycle, e.g. stopping, restarting, resuming execution (G06F9/4881 takes precedence) · CPC title

• G06F9/468

  Specific access rights for resources, e.g. using capability register · CPC title

• G06F9/541

  via adapters, e.g. between incompatible applications · CPC title

• G06Q10/06311 Primary

  Scheduling, planning or task assignment for a person or group · CPC title