Method and system for performing an operation using map reduce
View Patent ↗The present invention provides a computer implemented method for performing an application specific operation on a dataset over a distributed computing system. The computer implemented method includes collecting a set of application specific refining data present in a data stream of the dataset in a first map phase by the distributed computing system, resetting the data stream of the dataset to a beginning position by the distributed computing system, and generating one or more resultant data elements using the set of application specific refining data in a second map phase, by the distributed computing system.
1. A computer implemented method for performing an application specific operation using map reducers to perform parallel computations to aggregate values of key value pairs in multiple distributed datasets having splits across multiple computer systems of a distributed computing system, the computer implemented method comprising:
performing with one or more processors of the multiple computer systems included in the distributed computing system by executing instructions:
collecting a set of application specific refining data present in a data stream of multiple splits of the dataset in a first map phase, wherein the multiple splits of the dataset reside on respective ones of the multiple computer systems in the distributed computing system;
on each of the computer systems where at least one split of the dataset resides, executing one or more map functions of one or more mappers for the splits of the dataset, executing the map function of the mapper comprises:
iterating over input key value pairs present in the splits of the data stream;
applying the map function to the key value input pairs;
identifying distinct keys across the datasets and the splits;
joining the datasets based on the distinct keys;
generating intermediate output key value pairs after applying the map function and join; and
merging the intermediate output key value pairs into a single sorted stream;
resetting the data stream of the one or more splits of the dataset to a beginning position by the distributed computing system to prepare for reuse of executing the one or more map reducers;
executing one or more map reducers to aggregate the values in the key value pairs split across the multiple computer systems, wherein executing the one or more map reducers comprises:
fetching the intermediate output key value pairs that share a key;
applying a reduce function on the intermediate output key value pairs that share the key to aggregate the values of the intermediate output key value pairs generated by the one or more map functions; and
generating one or more resultant data elements using the set of application specific refining data in a second map phase that consolidates keys in the key value pairs that share the key and pairing the shared key with the aggregate of the values paired with the shared key; and
writing the one or more resultant data elements to a datastore.
2. The computer implemented method as claimed in claim 1 , further comprising reducing, by the distributed computing system, the one or more resultant data elements to form a resultant dataset in a reduce phase.
3. The computer implemented method as claimed in claim 1 , further comprising generating one or more intermediate data elements based on the set of application specific refining data in a third map phase by the distributed computing system prior to the generating the one or more resultant data elements, wherein the one or more intermediate data elements are used for generating the one or more resultant data elements.
4. The computer implemented method as claimed in claim 1 , wherein:
the application specific operation is a join operation over the dataset and another dataset; and
the application specific refining data comprises one or more distinct join keys.
5. The computer implemented method as claimed in claim 4 , further comprising generating a look up table based on the one or more distinct join keys by the distributed computing system, wherein the look-up table comprises a set of data elements corresponding to the one or more distinct join keys, from the another dataset.
6. The computer implemented method as claimed in claim 5 , wherein each resultant data element of the one or more resultant data elements is generated by joining a data element of another dataset with a corresponding data element of the dataset using the look-up table.
7. A system for performing an application specific operation using one or more map reducers to perform parallel computations to aggregate values of key value pairs in multiple distributed datasets having splits across multiple, interconnected computer nodes of a distributed computing system, wherein the dataset comprises one or more splits, the system comprising:
a computer cluster comprising:
the set of interconnected computer nodes, each computer node of the set of interconnected computers nodes having one or more processors and memory;
wherein multiple splits are distributed on the set of interconnected computer nodes in the computer cluster and wherein the set of interconnected computer nodes comprises:
one or more mappers, wherein each mapper from the one or more mappers is configured to:
collect a set of application specific refining data present in a data stream of multiple splits of the dataset in a first map phase, wherein the multiple splits of the dataset reside on multiple computer systems in the distributed computing system; and
on each of the interconnected computer nodes where at least one split of the dataset resides, execute one or more map functions for the splits of the dataset, wherein to execute the one or more map functions of the mapper comprises:
iterate over input key value pairs present in the splits of the data stream;
apply the map function to the key value input pairs;
identify distinct keys across the datasets and the splits;
join the datasets based on the distinct keys;
generate intermediate output key value pairs after applying the map function and join; and
merge the intermediate output key value pairs into a single sorted stream;
one or more reset modules configured to reset the data stream of the one or more splits of the dataset to a beginning position by the distributed computing system to prepare for reuse of executing one or more map reducers;
the one or more map reducers to aggregate the values in the key value pairs split across the multiple computer nodes, wherein the one or map reducers are configured to:
fetch the intermediate output key value pairs that share a key; and
apply a reduce function on the intermediate output key value pairs that share the key to aggregate the values of the intermediate output key value pairs generated by the one or more map functions; and
generate one or more resultant data elements using the set of application specific refining data in a second map phase that consolidates keys in the key value pairs that share the key and pairing the shared key with the aggregate of the values paired with the shared key; and
a writing module to write the one or more resultant data elements to a datastore.
8. The system as claimed in claim 7 , wherein the set of interconnected computer nodes further comprises:
one or more map reducers for aggregating the one or more resultant data elements in a reduce phase to form a resultant dataset, and for applying at least one application-specific reduce operation to the resultant dataset.
9. The system as claimed in claim 7 , wherein the set of interconnected computer nodes further comprises:
one or more look up table generators, wherein each look up table generator is configured to generate a look up table using the set of application specific refining data.
10. The system as claimed in claim 7 , wherein the one or more resultant data elements form a resultant dataset in a reduce phase.
11. The system as claimed in claim 7 , wherein the set of interconnected computer nodes is further configured to:
generate one or more intermediate data elements based on the set of application specific refining data in a third map phase by the distributed computing system prior to the generating the one or more resultant data elements, wherein the one or more intermediate data elements are used for generating the one or more resultant data elements.
12. The system as claimed in claim 7 , wherein
the application specific operation is a join operation over the dataset and another dataset; and
the application specific refining data comprises one or more distinct join keys.
13. The system as claimed in claim 7 , wherein the set of interconnected computer nodes is further configured to:
generate a look up table based on the one or more distinct join keys by the distributed computing system, wherein the look-up table comprises a set of data elements corresponding to the one or more distinct join keys, from the another dataset.
14. The system as claimed in claim 13 , wherein each resultant data element of the one or more resultant data elements is generated by joining a data element of another dataset with a corresponding data element of the dataset using the look-up table.
15. A non-transitory, computer readable program product comprising code stored therein for performing an application specific operation using map reducers to perform parallel computations to aggregate values of key value pairs in multiple distributed datasets having splits across multiple computer systems of a distributed computing system, wherein the code is executable by one or more processors of multiple computer systems included in the distributed computing system to:
collect a set of application specific refining data present in a data stream of multiple splits of the dataset in a first map phase, wherein the multiple splits of the dataset reside on multiple computer systems in the distributed computing system;
on each of the computer systems where at least one split of the dataset resides, execute one or more map functions of one or more mappers for the splits of the dataset, to execute the map function of the mapper comprises:
iterate over input key value pairs present in the splits of the data stream;
apply the map function to the key value input pairs;
identify distinct keys across the datasets and the splits;
join the datasets based on the distinct keys;
generate intermediate output key value pairs after applying the map function and join; and
merge the intermediate output key value pairs into a single sorted stream;
resetting the data stream of the one or more splits of the dataset to a beginning position by the distributed computing system to prepare for reuse of executing the one or more map reducers;
execute one or more map reducers to aggregate the values in the key value pairs split across the multiple computer systems, wherein executing the one or more map reducers comprises:
fetching the intermediate output key value pairs that share a key;
applying a reduce function on the intermediate output key value pairs that share the key to aggregate the values of the intermediate output key value pairs generated by the one or more map functions; and
generating one or more resultant data elements using the set of application specific refining data in a second map phase, by the distributed computing system; and
writing the one or more resultant data elements to a datastore.
16. The computer readable program product as claimed in claim 15 , wherein the code is executable by one or more processors of one or more computer systems included in the distributed computing system to:
reduce, by the distributed computing system, the one or more resultant data elements to form a resultant dataset in a reduce phase.
17. The computer readable program product as claimed in claim 15 , wherein the code is executable by one or more processors of one or more computer systems included in the distributed computing system to:
generate one or more intermediate data elements based on the set of application specific refining data in a third map phase by the distributed computing system prior to the generating the one or more resultant data elements, wherein the one or more intermediate data elements are used for generating the one or more resultant data elements.
18. The computer readable program product as claimed in claim 15 , wherein:
the application specific operation is a join operation over the dataset and another dataset; and
the application specific refining data comprises one or more distinct join keys.
19. The computer readable program product as claimed in claim 15 , wherein the code is executable by one or more processors of one or more computer systems included in the distributed computing system to:
generate a look up table based on the one or more distinct join keys by the distributed computing system, wherein the look-up table comprises a set of data elements corresponding to the one or more distinct join keys, from the another dataset.
20. The computer readable program product as claimed in claim 19 , wherein each resultant data element of the one or more resultant data elements is generated by joining a data element of another dataset with a corresponding data element of the dataset using the look-up table.