System and method for providing load balanced processing

• US 7,386,616 B1
• Filed: 05/27/2003
• Issued: 06/10/2008
• Est. Priority Date: 05/09/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Barroso, Luiz Andre, Henzinger, Monika Hildegard, Wallach, Deborah Anne, Ghemawat, Sanjay, Dean, Jeffrey, Smith, Benjamin Thomas
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): Bruckart; Benjamin R
• Application Number:
  US10/447,256
• Time in Patent Office: 1,841 Days
• Field of Search: 709/213, 709/214, 709/215, 709/223, 709/225, 709/226, 709/216, 715/969, 715/516, 715/734, 715/736
• US Class Current: 709/226
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection

Abstract

A system and method for providing load balanced processing is described. One or more files selected from a set of files are logically duplicated. At least one file and at least one logically duplicated file, is stored at one of a plurality of servers as specified in a load balancing layout. Execution of each operation in an operation stream is scheduled on the server storing at least one staged file required by the operation.

Claims

1. A method of providing load balanced processing of operations, comprising:

receiving a sequence of operation requests from one or more clients;

providing load balanced processing of the sequence of operation requests and avoiding load imbalances among a set of servers, including processing each operation request of the sequence of operation requests in accordance with current workloads of the set of servers, the processing of a respective operation request from a respective client including;

determining a set of files the operation requires;

distributing the operation over a plurality of servers in accordance with the current workloads, including, for each file in a plurality of files, in the set of files, separately determining a current workload for each server having a copy of the file, and dispatching a request that identifies the operation and the file, to a server that has a copy of the file and minimum current workload;

receiving intermediate results from each dispatched request;

processing the intermediate results into a single result set; and

returning the single result set to the respective client.

2. The method of claim 1, wherein determining a current workload for each server having a copy of the file includes determining a number of outstanding operations at each server having a copy of the file.

3. The method of claim 1, further comprising;

prior to receiving the sequence of operation requests;

identifying a plurality of servers;

identifying a plurality of files; and

storing each file onto one or more servers of the plurality of servers;

wherein a layout graph depicting the files and servers includes nodes representing the plurality of servers and edges representing the plurality of files, wherein each edge represents a respective file of the plurality of files and has ends at nodes corresponding to servers storing copies of the respective file, and furthermore wherein every server in the plurality of servers is connected to every other server in the plurality of servers by a sequence of one or more of the edges.

4. The method of claim 3, including constructing the layout graph and storing file copies onto the servers in accordance with the layout graph.

5. The method of claim 3 wherein the files are distributed so that the number of files on any server differs by at most one from the number of files on any other server.

6. The method of claim 3 wherein;

a processing load is calculated for each file; and

the files are assigned to servers to minimize differences between servers with respect to a sum of the processing loads of all of the files stored on each server.

7. The method of claim 3 wherein the edges in the layout graph form a single cycle that includes all of the nodes.

8. A computer readable storage medium storing one or more computer programs to be executed by a computer so as to perform a process, the one or more computer programs comprising:

instructions to receive a sequence of operation requests from one or more clients;

instructions to distribute the operation over a plurality of servers in accordance with the current workloads, including, instructions to provide load balanced processing of the sequence of operation requests and avoiding load imbalances among a set of servers, including instructions to process each operation request of the sequence of operation requests in accordance with current workloads of the set of servers, the instructions to process a respective operation request from a respective client including;

instructions to determine a set of files the operation requires;

instructions to separately determine, for each file in a plurality of files in the set of files, a current workload for each server having a copy of the file, and to dispatch a request that identifies the operation and the file, to a server that has a copy of the file and minimum current workload;

instructions to receive intermediate results from each dispatched request;

instructions to process the intermediate results into a single result set; and

instructions to returning the single result set to the respective client.

9. The computer readable storage medium of claim 8, wherein determining a current workload for each server having a copy of a file in the set of files includes determining a number of outstanding operations at each server having a copy of a file in the set of files.

10. The computer readable storage medium of claim 8, further comprising:

instructions to identify a plurality of servers;

instructions to identify a plurality of files; and

instructions to store each file onto one or more servers of the plurality of servers;

wherein a layout graph depicting the files and servers includes nodes representing the plurality of servers and edges representing the plurality of files, wherein each edge represents a respective file of the plurality of files and has ends at nodes corresponding to servers storing copies of the respective file, and furthermore wherein every server in the plurality of servers is connected to every other server in the plurality of servers by a sequence of one or more of the edges.

11. The computer readable storage medium of claim 10, further including instructions to construct a layout graph and to store file copies onto the servers in accordance with the layout graph.

12. The computer readable storage medium of claim 10, further including instructions to distribute the files so that the number of files on any server differs by at most one from the number of files on any other server.

13. The computer readable storage medium of claim 10, further including;

instructions to calculate a processing load for each file; and

instructions to assign the files to servers to minimize differences between servers with respect to a sum of the processing loads of all of the files stored on each server.

14. The computer readable storage medium of claim 10, further including instructions to form the edges in the layout graph as a single cycle that includes all of the nodes.