System and method for large-scale data processing using an application-independent framework
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/30
G06F-009/54
G06F-009/48
출원번호
US-0099806
(2013-12-06)
등록번호
US-9612883
(2017-04-04)
발명자
/ 주소
Dean, Jeffrey
Ghemawat, Sanjay
출원인 / 주소
Google Inc.
대리인 / 주소
Morgan, Lewis & Bockius LLP
인용정보
피인용 횟수 :
0인용 특허 :
27
초록▼
A large-scale data processing system and method for processing data in a distributed and parallel processing environment is disclosed. The system comprises a set of interconnected computing systems, each having one or more processors and memory. The set of interconnected computing systems include: a
A large-scale data processing system and method for processing data in a distributed and parallel processing environment is disclosed. The system comprises a set of interconnected computing systems, each having one or more processors and memory. The set of interconnected computing systems include: a set of application-independent map modules for reading portions of input files containing data, and for producing intermediate data values by applying at least one user-specified, application-specific map operation to the data; 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, distinct from the plurality of application-independent map modules, for producing final output data by applying at least one user-specified, application-specific reduce operation to the intermediate data values.
대표청구항▼
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
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; andassigning 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; anda 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; andthe 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; andassigning 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; andusing 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; andthe 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; andassigning 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; anduse 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; andthe supervisory process maintains status information with respect to map tasks awaiting assignment to a worker process.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (27)
McMillen Robert J. ; Watson M. Cameron ; Chura David J., Computer system using a master processor to automatically reconfigure faulty switch node that is detected and reported.
Ekanadham Kattamuri ; Moreira Jose Eduardo ; Naik Vijay Krishnarao, Method for resource control in parallel environments using program organization and run-time support.
Bookman,Lawrence A.; Blair,David Albert; Rosenthal,Steven M.; Krawitz,Robert Louis; Beckerle,Michael J.; Callen,Jerry Lee; Razdow,Allen M.; Mudambi,Shyam R., Segmentation and processing of continuous data streams using transactional semantics.
Malewicz, Grzegorz; Dvorsky, Marian; Colohan, Christopher B.; Thomson, Derek P.; Levenberg, Joshua Louis, System and method for limiting the impact of stragglers in large-scale parallel data processing.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.