Parallel processing of data

Abstract

Parallel processing of data may include a set of map processes and a set of reduce processes. Each map process may include at least one map thread. Map threads may access distinct input data blocks assigned to the map process, and may apply an application specific map operation to the input data blocks to produce key-value pairs. Each map process may include a multiblock combiner configured to apply a combining operation to values associated with common keys in the key-value pairs to produce combined values, and to output intermediate data including pairs of keys and combined values. Each reduce process may be configured to access the intermediate data output by the multiblock combiners. For each key, an application specific reduce operation may be applied to the combined values associated with the key to produce output data.

What is claimed is: 
     
       1. A method for parallel processing of data in a distributed operation, the method comprising:
 assigning a first input data block and a second input data block to a map process in a set of map processes for execution; 
 applying an application specific map operation to data in the first input data block to produce a first set of key-value pairs; 
 applying the application specific map operation to data in the second input data block to produce a second set of key-value pairs; 
 wherein the first set of key-value pairs and the second set of key-value pairs include at least one key common to the first set of key-value pairs and the second set of key-value pairs; 
 applying a combining operation to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs to produce a combined value; 
 determining whether an output condition occurs based on at least one of:
 (i) determining that a memory usage threshold is reached, 
 (ii) determining that processing of the first input data block and the second input data block is complete, or 
 (iii) receiving a command indicating that intermediate data should be output; and 
 
 in response to determining that the output condition has occurred, outputting, from the set of map processes, intermediate data including one or more pairs of keys and combined values for processing in a reduce phase of the distributed operation. 
 
     
     
       2. The method of  claim 1 , wherein applying the application specific map operation to data in the first input data block and the second input data block to produce a first set of key-value pairs and second set of key-value pairs, respectively, includes converting the key-value pairs from a native data format other than strings into a set of strings, and the method comprises:
 identifying the at least one key common to the set of key-value pairs and the second set of key-value pairs, which includes parsing the set of strings. 
 
     
     
       3. The method of  claim 1 , wherein the combining operation is applied to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs as the key-value pairs are produced by applying the application specific map operation to data in the first input data block and the second input data block. 
     
     
       4. The method of  claim 1 , wherein the combining operation is applied to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs after the first set of key-value pairs and the second set of key-value pairs are produced. 
     
     
       5. The method of  claim 1 , comprising:
 implementing a master process for coordinating processing among the set of map processes and a set of reduce processes of the reduce phase, wherein the coordinating comprises assigning input data blocks to individual map processes in the set of map processes. 
 
     
     
       6. The method of  claim 1 , wherein at least two of the map processes operate simultaneously. 
     
     
       7. The method of  claim 1 , wherein the command comprises a flush command. 
     
     
       8. A system for parallel processing of data, the system comprising:
 one or more processing devices; 
 one or more storage devices storing instructions that, when executed by the one or more processing devices, cause the one or more processing devices to perform operations comprising:
 assigning a first input data block and a second input data block to a map process in a set of map processes for execution; 
 applying an application specific map operation to data in the first input data block to produce a first set of key-value pairs; 
 applying the application specific map operation to data in the second input data block to produce a second set of key-value pairs; 
 wherein the first set of key-value pairs and the second set of key-value pairs include at least one key common to the first set of key-value pairs and the second set of key-value pairs; 
 applying a combining operation to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs to produce a combined value; 
 determining whether an output condition occurs based on at least one of:
 (i) determining that a memory usage threshold is reached, 
 (ii) determining that processing of the first input data block and the second input data block is complete, or 
 (iii) receiving a command indicating that intermediate data should be output; and 
 
 in response to determining that the output condition has occurred, outputting, from the set of map processes, intermediate data including one or more pairs of keys and combined values for processing in a reduce phase of the distributed operation. 
 
 
     
     
       9. The system of  claim 8 , wherein applying the application specific map operation to data in the first input data block and the second input data block to produce a first set of key-value pairs and second set of key-value pairs, respectively, includes converting the key-value pairs from a native data format other than strings into a set of strings, and the operations comprise:
 identifying the at least one key common to the set of key-value pairs and the second set of key-value pairs, which includes parsing the set of strings. 
 
     
     
       10. The system of  claim 8 , wherein the combining operation is applied to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs as the key-value pairs are produced by applying the application specific map operation to data in the first input data block and the second input data block. 
     
     
       11. The system of  claim 8 , wherein the combining operation is applied to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs after the first set of key-value pairs and the second set of key-value pairs are produced. 
     
     
       12. The system of  claim 8 , the operations comprising:
 implementing a master process for coordinating processing among the set of map processes and a set of reduce processes of the reduce phase, wherein the coordinating comprises assigning input data blocks to individual map processes in the set of map processes. 
 
     
     
       13. The system of  claim 8 , wherein at least two of the map processes operate simultaneously. 
     
     
       14. The system of  claim 8 , wherein the command comprises a flush command. 
     
     
       15. A non-transitory, computer-readable medium storing instructions, operable when executed, to cause one or more processors to perform operations comprising:
 assigning a first input data block and a second input data block to a map process in a set of map processes for execution; 
 applying an application specific map operation to data in the first input data block to produce a first set of key-value pairs; 
 applying the application specific map operation to data in the second input data block to produce a second set of key-value pairs; 
 wherein the first set of key-value pairs and the second set of key-value pairs include at least one key common to the first set of key-value pairs and the second set of key-value pairs; 
 applying a combining operation to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs to produce a combined value; 
 determining whether an output condition occurs based on at least one of:
 (i) determining that a memory usage threshold is reached, 
 (ii) determining that processing of the first input data block and the second input data block is complete, or 
 (iii) receiving a command indicating that intermediate data should be output; and 
 
 in response to determining that the output condition has occurred, outputting, from the set of map processes, intermediate data including one or more pairs of keys and combined values for processing in a reduce phase of the distributed operation. 
 
     
     
       16. The computer-readable medium of  claim 15 , wherein applying the application specific map operation to data in the first input data block and the second input data block to produce a first set of key-value pairs and second set of key-value pairs, respectively, includes converting the key-value pairs from a native data format other than strings into a set of strings, and the operations comprise:
 identifying the at least one key common to the set of key-value pairs and the second set of key-value pairs, which includes parsing the set of strings. 
 
     
     
       17. The computer-readable medium of  claim 15 , wherein the combining operation is applied to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs as the key-value pairs are produced by applying the application specific map operation to data in the first input data block and the second input data block. 
     
     
       18. The computer-readable medium of  claim 15 , wherein the combining operation is applied to values associated with the common key in the first set of key-value pairs and the second set of key-value pairs after the first set of key-value pairs and the second set of key-value pairs are produced. 
     
     
       19. The computer-readable medium of  claim 15 , the operations comprising:
 implementing a master process for coordinating processing among the set of map processes and a set of reduce processes of the reduce phase, wherein the coordinating comprises assigning input data blocks to individual map processes in the set of map processes. 
 
     
     
       20. The computer-readable medium of  claim 15 , wherein the command comprises a flush command.