Opportunistic job processing in a distributed computer environment

• US 8,935,318 B1
• Filed: 03/28/2012
• Issued: 01/13/2015
• Est. Priority Date: 03/28/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Breckenridge, Jordan M., Belov, Daniel, Konerding, David
• Primary Examiner(s): Beharry, Noel
• Assistant Examiner(s): MUSA, ABDELNABI O
• Application Number:
  US13/432,070
• Time in Patent Office: 1,021 Days
• Field of Search: 709/203, 709/204, 709/205, 709/206, 709/207
• US Class Current: 709/203
• CPC Class Codes: G06F 9/452 Remote windowing, e.g. X-Window System, desktop virtualisation protocols for virtual reality H04L67/131
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/541 via adapters, e.g. between incompatible applications
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis

Abstract

A central storage configured to store one or more input files and an executable file. A work order frontend is configured to receive, from the client, a representational state transfer (RESTful) message that contains a reference to the one or more input files in the central storage. The work order frontend is further configured to transmit, to a global-level manager, a work order. The global-level manager is configured to access the work order. The global-level manager is further configured to partition the one or more input files into multiple shards, the work order into multiple jobs, each job being associated with one or more of the multiple shards and the executable file. The global-level manager is further configured to distribute the jobs among a plurality of clusters.

Claims

1. A system comprising:

one or more processing devices;

a central storage configured to;

store one or more input files from a client;

receive an executable file from a client; and

store the executable file;

one or more storage devices storing instructions that, when executed by the one or more processing devices cause the one or more processing devices to implement;

a work order frontend configured to;

receive, from the client, a representational state transfer (RESTful) message that contains (i) a reference to the one or more input files stored in the central storage and (ii) a reference to the executable file stored in the central storage;

process the received RESTful message to extract (i) the reference to the one or more input files and (ii) the reference to the executable file;

in response to extracting the references, generate a work order that includes (i) the reference to the one or more input files and (ii) the reference to the executable file; and

transmit, to a global-level manager, the work order;

the global-level manager configured to;

access the work order;

partition, using the references to the executable file and the one or more input files, the one or more input files into multiple shards, the work order into multiple jobs, each job being associated with one or more of the multiple shards and the executable file; and

distribute the jobs among a plurality of clusters to be processed using underutilized computing resources in the clusters; and

the plurality of clusters, wherein each cluster includes one or more task level managers configured to process a job distributed to the cluster using underutilized computing resources in the clusters and generate a job output based on the processing.

2. The system of claim 1, wherein the central storage is under the same administrative control as the work order frontend.

3. The system of claim 1, wherein the work order frontend is further configured to provide the client with a graphical user interface to generate the RESTful message and wherein the RESTful message is received through the graphical user interface.

4. The system of claim 3, wherein the graphical user interface is configured to send the one or more input files and the executable file to the central storage.

5. The system of claim 1, wherein:

to distribute the jobs among a plurality of clusters, the global-level manager is configured to distribute the references to the executable file and the one or more input files; and

to process a job distributed to the cluster, the cluster is configured to access, using the references to the executable file and the one or more input files, the executable file and the one or more input files in the central storage.

6. The system of claim 1, wherein the RESTful message is received from the client as part of a Hypertext Transfer Protocol (HTTP) request.

19. The system of claim 1, wherein the executable file is configured to operate on the one or more input files from a client.

20. The system of claim 1, wherein the executable file is configured to operate on one or more of the multiple shards.

21. The system of claim 1, wherein each of the jobs contain the reference to the executable file and references to each of the one or more associated multiple shards.

7. A method performed by one or more processors, the method comprising:

storing, at a central storage, one or more input files from a client;

receiving, an executable file from a client and

storing the executable file;

receiving, at a work order frontend and from a client, a representational state transfer (RESTful) message that contains (i) a reference to the one or more input files in the central storage and (ii) a reference to the executable file stored in the central storage;

processing the received RESTful message to extract (i) the reference to the one or more input files and (ii) the reference to the executable file;

in response to extracting the references, generating a work order that includes (i) the reference to the one or more input files and (ii) the reference to the executable file;

transmitting, to a global-level manager, the work order;

partitioning, using the references to the executable file and the one or more input files, the one or more input files into multiple shards, partition the work order into multiple jobs, each job being associated with one or more of the multiple shards and the executable file;

distributing the jobs among a plurality of clusters to be processed using underutilized computing resources in the clusters; and

processing, by one or more task level managers of the plurality of clusters, a job distributed to the cluster using underutilized computing resources in the clusters and generate a job output based on the processing.

8. The method of claim 7, wherein the central storage is under the same administrative control as the work order frontend.

9. The method of claim 7, wherein the work order frontend is further configured to provide the client with a graphical user interface to generate the RESTful message and wherein the RESTful message is received through the graphical user interface.

10. The method of claim 9, wherein the graphical user interface is configured to send the one or more input files and the executable file to the central storage.

11. The method of claim 7, wherein:

distributing the jobs among a plurality of clusters includes distributing the references to the executable file and the one or more input files; and

processing a job distributed to a cluster includes accessing, using the references to the executable file and the one or more input files, the executable file and the one or more input files in the central storage.

12. The method of claim 7, wherein the RESTful message is received from the client as part of a Hypertext Transfer Protocol (HTTP) request.

22. The method of claim 7, wherein the executable file is configured to operate on the one or more input files from a client.

23. The method of claim 7, wherein the executable file is configured to operate on one or more of the multiple shards.

24. The method of claim 7, wherein each of the jobs contain the reference to the executable file and references to each of the one or more associated multiple shards.

13. A system comprising:

one or more processing devices;

a central storage configured to;

store one or more input files from a client;

receive an executable file from a client; and

store the executable file;

a work order frontend configured to;

receive, from the client, a representational state transfer (RESTful) message that contains (i) a reference to the one or more input files in the central storage and (ii) a reference to the executable file stored in the central storage;

process the received RESTful message to extract (i) the reference to the one or more input files and (ii) the reference to the executable file;

in response to extracting the references, generate a work order that includes (i) the reference to the one or more input files and (ii) the reference to the executable file; and

transmit, to a global-level manager, the work order;

the global-level manager configured to;

access the work order;

partition, using the references to the executable file and the one or more input files, the one or more input files into multiple shards, partition the work order into multiple jobs, each job being associated with one or more of the multiple shards and the executable file; and

distribute the jobs among a plurality of clusters to be processed using underutilized computing resources in the clusters; and

the plurality of clusters, wherein each cluster includes one or more task level managers configured to process a job distributed to the cluster using underutilized computing resources in the clusters and generate a job output based on the processing.

14. The system of claim 13, wherein the central storage is under the same administrative control as the work order frontend.

15. The system of claim 13, wherein the work order frontend is further configured to provide the client with a graphical user interface to generate the RESTful message and wherein the RESTful message is received through the graphical user interface.

16. The system of claim 15, wherein the graphical user interface is configured to send the one or more input files and the executable file to the central storage.

17. The system of claim 13, wherein:

to distribute the jobs among a plurality of clusters, the global-level manager is configured to distribute the references to the executable file and the one or more input files; and

to process a job distributed to the cluster, the cluster is configured to access, using the references to the executable file and the one or more input files, the executable file and the one or more input files in the central storage.

18. The system of claim 13, wherein the RESTful message is received from the client as part of a Hypertext Transfer Protocol (HTTP) request.

25. The system of claim 13, wherein the executable file is configured to operate on the one or more input files from a client.

26. The system of claim 13, wherein the executable file is configured to operate on one or more of the multiple shards.

27. The system of claim 13, wherein each of the jobs contain the reference to the executable file and references to each of the one or more associated multiple shards.