System and method for large-scale data processing using an application-independent framework

1. 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 plurality of worker processes executing on the set of interconnected computing systems;

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

determining, for 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;

a set of application-independent map functions, executed by a first subset of the plurality of worker processes, for reading portions of the input files containing data, and for producing intermediate data values by applying at least one user-specified, application-specific map operation to the data, wherein the set of application-independent map functions are independent of the at least one user-specified, application-specific map operation;

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 functions, distinct from the set of application-independent map functions, the set of application-independent reduce functions executed by a second subset of the plurality of worker processes for producing the final output data by applying at least one user-specified, application-specific reduce operation to the intermediate data values, wherein the set of application-independent reduce functions are independent of the at least one user-specified, application-specific reduce operation.

2. The system of claim 1 , 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.

3. The system of claim 1 , 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.

4. The system of claim 1 , 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.

5. The system of claim 1 , 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.

6. The system of claim 1 , wherein:

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

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.

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

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

9. 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:

executing a plurality of worker processes;

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

determining, for 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: using a set of application-independent map functions, executed by a first subset of the plurality of worker processes, to read portions of the input files containing data and produce intermediate data values by applying at least one user-specified, application-specific map operation to the data;

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 functions, distinct from the set of application-independent map functions, to produce the final output data by applying at least one user-specified, application-specific reduce operation to the intermediate data values, wherein the set of application-independent reduce functions are executed by a second subset of the plurality of worker processes;

wherein the set of application-independent map functions and the set of application-independent reduce functions are independent of application-specific operators and operations including the at least one user-specified, application-specific map operation and the at least one user-specified, application-specific reduce operation.

10. The method of claim 9 , including applying a partition operation to at least a subset of the intermediate data values, wherein 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.

11. The method of claim 9 , 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.

12. The method of claim 9 , 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.

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

execute a plurality of worker processes on the set of interconnected computing systems;

execute an application-independent supervisory process on the set of interconnected computing systems, for:

determining, for 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;

use a set of application-independent map functions, executed by a first subset of the plurality of worker processes, to read portions of the input files containing data and produce intermediate data values by applying at least one user-specified, application-specific map operation to the data;

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 functions, distinct from the set of application-independent map functions, to produce the final output data by applying at least one user-specified, application-specific reduce operation to the intermediate data values, wherein the set of application-independent reduce functions are executed by a second subset of the plurality of worker processes;

wherein the set of application-independent map functions and the set of application-independent reduce functions are independent of application-specific operators and operations, including the at least one user-specified, application-specific map operation and the at least one user-specified, application-specific reduce operation.

14. The non-transitory computer readable storage medium of claim 13 , wherein one or more programs further comprise instructions to be executed by the plurality of processors so as to apply a partition operation to at least a subset of the intermediate data values, wherein 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 non-transitory computer readable storage medium of claim 13 , 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 non-transitory computer readable storage medium of claim 13 , 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.