System and method for efficient large-scale data processing

• US 7,650,331 B1
• Filed: 06/18/2004
• Issued: 01/19/2010
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Dean, Jeffrey, Ghemawat, Sanjay
• Primary Examiner(s): Pham; Hung Q
• Assistant Examiner(s): CHEUNG, HUBERT G
• Application Number:
  US10/871,244
• Time in Patent Office: 2,041 Days
• Field of Search: None
• US Class Current: 712/203
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

A large-scale data processing system and method includes one or more application-independent map modules configured to read input data and to apply at least one application-specific map operation to the input data to produce intermediate data values, wherein the map operation is automatically parallelized across multiple processors in the parallel processing environment. A plurality of intermediate data structures are used to store the intermediate data values. One or more application-independent reduce modules are configured to retrieve the intermediate data values and to apply at least one application-specific reduce operation to the intermediate data values to provide output data.

Claims

1. A system for large-scale processing of data, comprising:

a plurality of processes executing on a plurality of interconnected processors;

the plurality of processes including a master process, for coordinating a data processing job for processing a set of input data, and worker processes;

the master process, in response to a request to perform the data processing job, assigning input data blocks of the set of input data to respective ones of the worker processes;

each of a first plurality of the worker processes including an application-independent map module for retrieving a respective input data block assigned to the worker process by the master process and applying an application-specific map operation to the respective input data block to produce intermediate data values, wherein at least a subset of the intermediate data values each comprises a key/value pair, and wherein at least two of the first plurality of the worker processes operate simultaneously so as to perform the application-specific map operation in parallel on distinct, respective input data blocks;

a partition operator for processing the produced intermediate data values to produce a plurality of intermediate data sets, wherein each respective intermediate data set includes all key/value pairs for a distinct set of respective keys, and wherein at least one of the respective intermediate data sets includes respective ones of the key/value pairs produced by a plurality of the first plurality of the worker processes; and

each of a second plurality of the worker processes including an application-independent reduce module for retrieving data, the retrieved data comprising at least a subset of the key/value pairs from a respective intermediate data set of the plurality of intermediate data sets and applying an application-specific reduce operation to the retrieved data to produce final output data corresponding to the distinct set of respective keys in the respective intermediate data set of the plurality of intermediate data sets, and wherein at least two of the second plurality of the worker processes operate simultaneously so as to perform the application-specific reduce operation in parallel on multiple respective subsets of the produced intermediate data values.

2. The system of claim 1, wherein each of the worker processes includes a map process thread and a reduce process thread, the map process thread configured to execute the application-independent map module and the reduce process thread configured to execute the application-independent reduce module.

3. The system of claim 1, wherein the master process is configured to automatically determine a number of distinct map tasks and a number of distinct reduce tasks to perform the data processing job, and to automatically assign the distinct map tasks and the distinct reduce tasks to the worker processes in accordance with availability of the worker processes executing on the interconnected processors such that some of the distinct map tasks and some of the distinct reduce tasks are assigned to worker processes later, during performance of the data processing job, than other ones of the distinct map tasks and the distinct reduce tasks.

4. The system of claim 3, wherein the number of distinct map tasks exceeds in number the first plurality of the worker processes to which the master process can assign the distinct map tasks, and wherein the master process maintains status information with respect to the distinct map tasks awaiting assignment to one of the first plurality of worker processes.

5. The system of claim 3, wherein the master process is configured to maintain a task status table, denoting for each of the distinct map tasks and each of the distinct reduce tasks one of the worker processes, if any, to which each of the distinct map tasks or each of the distinct reduce tasks has been assigned, and a status of each of the distinct map tasks or each of the distinct reduce tasks.

6. The system of claim 5, wherein the master process is further configured to maintain a process status tables, denoting which of the worker processes has been assigned one of the distinct map tasks, and which of the worker processes has been assigned one of the distinct reduce tasks, and a status of each of the worker processes.

7. The system of claim 5, wherein the application-specific map operation includes an application-specific combiner operation for combining initial data values produced by the application-specific map operation so as to produce the intermediate data values.

8. The system of claim 5, wherein the application-specific map operation includes an application-specific combiner operation for combining initial data values produced by the application-specific map operation having shared keys so as to produce the intermediate data values.

9. A method of performing a large-scale data processing job, comprising:

executing a plurality of processes on a plurality of interconnected processors, the plurality of processes including a master process for coordinating the large-scale data processing job for processing a set of input data, and worker processes;

in the master process, in response to a request to perform the large-scale data processing job, assigning input data blocks of the set of input data to respective ones of the worker processes;

in each of a first plurality of the worker processes, executing an application-independent map module to retrieve a respective input data block assigned to the worker process by the master process and to apply an application-specific map operation to the respective input data block to produce intermediate data values, wherein at least a subset of the intermediate data values each comprises a key/value pair, and wherein at least two of the first plurality of the worker processes operate simultaneously so as to perform the application-specific map operation in parallel on distinct, respective input data blocks;

using a partition operator to process the produced intermediate data values to produce a plurality of intermediate data sets, wherein each respective intermediate data set includes all key/value pairs for a distinct set of respective keys, and wherein at least one of the respective intermediate data sets includes respective ones of the key/value pairs produced by a plurality of the first plurality of the worker processes; and

in each of a second plurality of the worker processes, executing an application-independent reduce module to retrieve data, the retrieved data comprising at least a subset of the key/value pairs from a respective intermediate data set of the plurality of intermediate data sets and applying an application-specific reduce operation to the retrieved data to produce final output data corresponding to the distinct set of respective keys in the respective intermediate data set of the plurality of intermediate data sets, and wherein at least two of the second plurality of the worker processes operate simultaneously so as to perform the application-specific reduce operation in parallel on multiple respective subsets of the produced intermediate data values.

10. The method of claim 9, wherein each of the worker processes includes a map process thread and a reduce process thread, the map process for executing the application-independent map module and the reduce process thread for executing the application-independent reduce module.

11. The method of claim 9, wherein the master process maintains a task status table, denoting for each of the distinct map tasks and each of the distinct reduce tasks the respective ones of the worker processes, if any, to which each of the distinct map tasks or each of the distinct reduce tasks has been assigned, and a status of each of the distinct map tasks or each of the distinct reduce tasks.

12. The method of claim 11, wherein the master process maintains a process status table, denoting which of the worker processes has been assigned one of the distinct map tasks, and which of the worker processes has been assigned one of the distinct reduce tasks, and a status of each of the worker processes.

13. The method of claim 9, wherein the application-specific map operation includes an application-specific combiner operation for combining initial data values produced by the application-specific map operation so as to produce the intermediate data values.

14. The method of claim 9, wherein the application-specific map operation includes an application-specific combiner operation for combining initial data values produced by the application-specific map operation having shared keys so as to produce the intermediate data values.

15. The method of claim 9, including, in the master process, automatically determining a number of distinct map tasks and a number of distinct reduce tasks to perform the data processing job, and automatically assigning the distinct map tasks and the distinct reduce tasks to the worker processes in accordance with availability of the worker processes such that some of the distinct map tasks and some of the distinct reduce tasks are assigned to worker processes later, during performance of the large-scale data processing job, than other ones of the distinct map tasks and the distinct reduce tasks.

16. The method of claim 15, wherein the number of distinct map tasks exceeds in number the first plurality of the worker processes to which the master process can assign the distinct map tasks, and wherein the method includes, in the master process, maintaining status information with respect to the distinct map tasks awaiting assignment to one of the first plurality of worker processes.