System and Method for Large-Scale Data Processing Using an Application-Independent Framework

• US 20100122065A1
• Filed: 01/12/2010
• Published: 05/13/2010
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Dean, Jeffrey
• Granted Patent: US 8,612,510 B2
• Time in Patent Office: Days
• US Class Current: 712/203
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

A large-scale data processing system and method for processing data in a distributed and parallel processing environment. The system includes an application-independent framework for processing data having a plurality of application-independent map modules and reduce modules. These application-independent modules use application-independent operators to automatically handle parallelization of computations across the distributed and parallel processing environment when performing user-specified data processing operations. The system also includes a plurality of user-specified, application-specific operators, for use with the application-independent framework to perform a user-specified data processing operation on a user-specified set of input files. The application-specific operators include: a map operator and a reduce operator. The map operator is applied by the application-independent map modules to input data in the user-specified set of input files to produce intermediate data values. The reduce operator is applied by the application-independent reduce modules to process the intermediate data values to produce final output data.

Claims

1. A system for large-scale processing of data in a distributed and parallel processing environment including a set of interconnected computing systems, comprising:

an application-independent framework for processing data, including;

a plurality of application-independent map modules; and

,

a plurality of application-independent reduce modules, wherein the application-independent map modules and application-independent reduce modules use application-independent operators to automatically handle parallelization of computations across the distributed and parallel processing environment when performing user-specified data processing operations; and

a plurality of user-specified, application-specific operators, for use with the application-independent framework to perform a user-specified data processing operation on a user-specified set of input files, the application-specific operators including;

a map operator, wherein the map operator is applied by the application-independent map modules to input data in the user-specified set of input files to produce intermediate data values; and

a reduce operator, wherein the reduce operator is applied by the application-independent reduce modules to process the intermediate data values to produce final output data for the user-specified data processing operation.

2. The system of claim 1, wherein the application-independent framework for processing data further includes a set of intermediate data structures distributed among a plurality of the interconnected computing systems for storing the intermediate data values.

3. The system of claim 1, wherein:

the application-independent framework for processing data further includes a set of intermediate data structures for storing the intermediate data values; and

the plurality of user-specified, application-specific operators further comprise a partition operator, and the partition operator is applied to at least a subset of the intermediate data values to specify, for each respective intermediate data value in the subset of intermediate data values, a respective intermediate data structure of the set of intermediate data structures in which to store the respective intermediate data value.

4. The system of claim 1, wherein:

the plurality of user-specified, application-specific operators further comprise a combiner operator; and

the combiner operator is applied by the application-independent map modules in conjunction with the map operator to produce the intermediate data values by combining a plurality of initial data values produced by the application of the map operator to the input data.

5. The system of claim 1, wherein the application independent framework for processing data further includes:

a plurality of worker processes, each worker process including one of the application-independent map modules and one of the application-independent reduce modules; and

an application-independent supervisory process for;

determining, for the user-specified data processing operation, a plurality of data processing tasks including a plurality of map tasks specifying input data to be processed into intermediate data values and a plurality of reduce tasks specifying intermediate data values to be processed into final output data; and

assigning the data processing tasks to idle ones of the worker processes.

6. The system of claim 5, wherein:

the number of map tasks exceeds in number the plurality of processes to which the supervisory process can assign map tasks; and

the application-independent supervisory process maintains status information with respect to map tasks awaiting assignment to a worker process.

7. The system of claim 5, wherein:

the set of interconnected computer systems are grouped into a plurality of datacenters; and

when assigning the data processing tasks to idle ones of the worker processes, the supervisory process preferentially assigns data processing tasks for data stored on computer systems in a respective datacenter to worker processes that are running on computer systems in the respective datacenter.

8. The system of claim 1, wherein the application-independent framework for processing data further includes application-independent operators that automatically provide fault tolerance when performing user-specified data processing operations.

9. The system of claim 1, wherein the application-independent framework for processing data further includes application-independent operators that automatically handle I/O scheduling when performing user-specified data processing operations.

10. A method of performing large-scale processing of data in a distributed and parallel processing environment comprising:

receiving, from a user, a plurality of user-specified, application-specific operators, for use with an application-independent framework to perform a user-specified data processing operation on a user-specified set of input files, the application-specific operators including a map operator and a reduce operator; and

processing data on a set of interconnected computer systems in the application-independent framework, each of the computer systems comprising one or more processors and memory, the application independent framework including;

a plurality of application-independent map modules; and

,

a plurality of application-independent reduce modules, wherein the application-independent map modules and application-independent reduce modules use application-independent operators to automatically handle parallelization of computations across the distributed and parallel processing environment when performing user-specified data processing operations;

the data processing including;

using the application-independent map modules to apply the map operator to input data in the user-specified set of input files to produce intermediate data values; and

using the application-independent reduce modules to apply the reduce operator to process the intermediate data values to produce final output data for the user-specified data processing operation.

11. A computer-readable storage medium storing one or more programs configured for execution by a plurality of processors of a set of interconnected computer systems, the one or more programs comprising instructions to be executed by one or more of the plurality of processors so as to:

receive, from a user, a plurality of user-specified, application-specific operators, for use with an application-independent framework to perform a user-specified data processing operation on a user-specified set of input files, the application-specific operators including a map operator and a reduce operator; and

process data on a set of interconnected computer systems in the application-independent framework, each of the computer systems comprising one or more processors and memory, the application independent framework including;

a plurality of application-independent map modules; and

,

a plurality of application-independent reduce modules, wherein the application-independent map modules and application-independent reduce modules use application-independent operators to automatically handle parallelization of computations across the distributed and parallel processing environment when performing user-specified data processing operations;

wherein;

the application-independent map modules include instructions to be executed by one or more of the plurality of processors so as to apply the map operator to input data in the user-specified set of input files to produce intermediate data values; and

the application-independent reduce modules include instructions to be executed by one or more of the plurality of processors so as to apply the reduce operator to process the intermediate data values to produce final output data for the user-specified data processing operation.

12. A system for large-scale processing of data in a distributed and parallel processing environment, comprising:

a set of interconnected computing systems, each having one or more processors and memory, the set of interconnected computing systems including;

a set of application-independent map modules for reading portions of input files containing data, and for applying at least one user-specified, application-specific map operation to the data to produce intermediate data values;

a set of intermediate data structures distributed among a plurality of the interconnected computing systems for storing the intermediate data values; and

a set of application-independent reduce modules for applying at least one user-specified, application-specific reduce operation to the intermediate data values to produce final output data.

13. The system of claim 12, wherein at least one of the map and reduce operations is automatically parallelized across multiple processors in the distributed and parallel processing environment using an application-independent methodology.

14. The system of claim 12, wherein the set of interconnected computing systems applies a partition operation to at least a subset of the intermediate data values, and for each respective intermediate data value in the at least a subset of the intermediate data values, the partition operation specifies a respective intermediate data structure of the set of intermediate data structures in which to store the respective intermediate data value.

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

16. The system of claim 12, further comprising:

a plurality of worker processes executing on the set of interconnected computing systems, each worker process including one of the application-independent map modules and one of the application-independent reduce modules; and

an application-independent supervisory process executing on the set of interconnected computing systems, for;

determining, for the input files, a plurality of data processing tasks including a plurality of map tasks specifying data from the input files to be processed into intermediate data values and a plurality of reduce tasks specifying intermediate data values to be processed into final output data; and

assigning the data processing tasks to idle ones of the worker processes.

17. The system of claim 16, wherein:

the number of map tasks exceeds in number the plurality of processes to which the supervisory process can assign map tasks; and

the supervisory process maintains status information with respect to map tasks awaiting assignment to a worker process.

18. The system of claim 16, wherein:

the set of interconnected computer systems are grouped into a plurality of datacenters; and

when assigning the data processing tasks to idle ones of the worker processes, the supervisory process preferentially assigns data processing tasks for data stored on computer systems in a respective datacenter to worker processes that are running on computer systems in the respective datacenter.

19. The system of claim 12, wherein the map and reduce operations are implemented on different processors coupled to a distributed network.

20. The system of claim 19, wherein the final output data is written to a file system on the distributed network.

21. A method of performing large-scale processing of data in a distributed and parallel processing environment, comprising:

at a set of interconnected computing systems, each having one or more processors and memory;

using a set of application-independent map modules to read portions of input files containing data and apply at least one user-specified, application-specific map operation to the data to produce intermediate data values;

storing the intermediate data values in a set of intermediate data structures distributed among a plurality of the interconnected computing systems; and

using a set of application-independent reduce modules to apply at least one user-specified, application-specific reduce operation to the intermediate data values to produce final output data.

22. A computer readable storage medium storing one or more programs configured for execution by a plurality processors of a set of interconnected computing systems, comprising instructions to be executed by the plurality of processors so as to:

use a set of application-independent map modules to read portions of input files containing data and apply at least one user-specified, application-specific map operation to the data to produce intermediate data values;

store the intermediate data values in a set of intermediate data structures distributed among a plurality of the interconnected computing systems; and

use a set of application-independent reduce modules to apply at least one user-specified, application-specific reduce operation to the intermediate data values to produce final output data.