Transparent efficiency for in-memory execution of map reduce job sequences

Abstract

Executing a map reduce sequence may comprise executing all jobs in the sequence by a collection of a plurality of processes with each process running zero or more mappers, combiners, partitioners and reducers for each job, and transparently sharing heap state between the jobs to improve metrics associated with the job. Processes may communicate among themselves to coordinate completion of map, shuffle and reduce phases, and completion of said all jobs in the sequence.

We claim: 
     
         1 . A method for executing a map reduce sequence, comprising:
 executing, by one or more processors, all jobs in the sequence by a collection of a plurality of processes with each process running zero or more mappers, combiners, partitioners and reducers for each job, and transparently sharing heap state between the jobs to improve metrics associated with the job; and   communicating among the processes to coordinate completion of map, shuffle and reduce phases, and completion of said all jobs in the sequence.   
     
     
         2 . The method of  claim 1 , wherein the transparently sharing of the heap state comprises employing a cache memory comprising an association of input descriptors to an in-memory representation of a key value sequence obtained by running a corresponding input format descriptor on the input descriptor, and an association of output descriptors with the in-memory representation of the key value sequence consumed by the corresponding output format descriptor to produce the data associated with the output descriptor. 
     
     
         3 . The method of  claim 2 , further comprising:
 fulfilling reads from the input descriptor using the input format descriptor from the cached value associated with the input descriptor; and   fulfilling reads from the output descriptor using the input format descriptor by using the cached value associated with the output descriptor.   
     
     
         4 . The method of  claim 2 , wherein a copy is made of the key value pairs emitted by the mapper before the key value pairs are added to the cache, unless it can be established that the mapper does not reuse the key value pair it has emitted. 
     
     
         5 . The method of  claim 2 , wherein the key value pairs are transmitted in the shuffle, unless it can be established that the mapper does not reuse the key value pair it has emitted. 
     
     
         6 . The method of  claim 4 , wherein whether the mapper does not reuse the key value pairs it has emitted is established by using a flag submitted in a job configuration. 
     
     
         7 . The method of  claim 4 , wherein whether the mapper does not reuse the key value pairs it has emitted is established by analyzing a code of the mapper. 
     
     
         8 . The method of  claim 2 , wherein a copy is made of the key value pairs emitted by the reducer before the key value pairs are added to the cache, unless it can be established that the reducer does not reuse the key value pair it has emitted. 
     
     
         9 . The method of  claim 8 , wherein the reducer does not reuse the key value pair it has emitted is established by using a flag submitted in a job configuration. 
     
     
         10 . The method of  claim 8 , wherein the reducer does not reuse the key value pair it has emitted is established by analyzing a code of the reducer. 
     
     
         11 . The method of  claim 2 , wherein a copy is made of the key value pairs emitted by the combiner before the key value pairs are added to the cache, unless it can be established that the combiner does not reuse the key value pair it has emitted. 
     
     
         12 . The method of  claim 11 , wherein the combiner does not reuse the key value pair it has emitted is established by using a flag submitted in a job configuration. 
     
     
         13 . The method of  claim 11 , wherein the combiner does not reuse the key value pair it has emitted is established by analyzing a code of the reducer. 
     
     
         14 . The method of  claim 4 , further comprising:
 performing de-duplication so that fewer copies of a key or value is sent from one of the processes to another one of the processes, regardless of a number of copies of the key or value intended to be sent from said one of the processes to said another one of the processes.   
     
     
         15 . The method of  claim 14 , wherein the fewer copies of a key is one copy of the key. 
     
     
         16 . The method of  claim 14 , wherein communication from one of the processes to another one of the processes occur in batches. 
     
     
         17 . The method of  claim 1 , further comprising:
 shuffling key value pairs in the cache memory between the mappers.   
     
     
         18 . The method of  claim 1 , further comprising:
 guaranteeing that across all jobs in the sequence the same partition number is mapped to the same place.   
     
     
         19 . The method of  claim 1 , wherein mapping from a partition number to a process is determined by a first job in the sequence requires the mapping. 
     
     
         20 . The method of  claim 1 , wherein mapping from a partition number to a process is determined before a first job in the sequence requires the mapping. 
     
     
         21 . A method for executing a map reduce sequence, comprising:
 executing, by one or more processors, all jobs in the sequence by a collection of a plurality of processes with each process running zero or more mappers, combiners, partitioners and reducers for each job;   employing a cache memory comprising an association of input descriptors to an in-memory representation of a key value sequence obtained by running a corresponding input format descriptor on the input descriptor, and an association of output descriptors with the in-memory representation of the key value sequence consumed by the corresponding output format descriptor to produce the data associated with the output descriptor, to enable transparently sharing heap state between the jobs; and   communicating among the processes to coordinate completion of map, shuffle and reduce phases, and completion of said all jobs in the sequence.   
     
     
         22 . The method of  claim 21 , wherein a copy is made of the key value pairs emitted by the mapper before the key value pairs are added to the cache, unless it can be established that the mapper does not reuse the key value pair it has emitted. 
     
     
         23 . The method of  claim 21 , wherein the key value pairs are transmitted in the shuffle, unless it can be established that the mapper does not reuse the key value pair it has emitted. 
     
     
         24 . The method of  claim 21 , wherein a copy is made of the key value pairs emitted by the reducer before the key value pairs are added to the cache, unless it can be established that the reducer does not reuse the key value pair it has emitted. 
     
     
         25 . The method of  claim 21 , wherein a copy is made of the key value pairs emitted by the combiner before the key value pairs are added to the cache, unless it can be established that the combiner does not reuse the key value pair it has emitted.