Management of intermediate data spills during the shuffle phase of a map-reduce job
First Claim
1. A distributed computer system configured for spill management during a shuffle phase of a map-reduce job performed by said distributed computer system on distributed files, said distributed computer system comprising:
- a) key-value pairs (ki,vi) belonging to said distributed files on which said map-reduce job is performed;
b) a number of map nodes for performing a pre-shuffle phase of said map-reduce job on said key value pairs (ki,vi) to generate keyed partitions (Ki,PRTj);
c) storage resources for spilling said keyed partitions (Ki,PRTj) in accordance with a spilling protocol based on at least one popularity attribute of said key-value pairs (ki,vi);
d) a number of reduce nodes provided with said spilling protocol to enable said reduce nodes to locate and access said keyed partitions (Ki,PRTj) during said shuffle phase by utilizing a path to said keyed partitions (Ki,PRTj), said path sent in the header of an empty HTTP message;
e) said keyed partitions (Ki,PRTj) stored in a shared directory under a mount point, said shared directory accessible by said map nodes and said reduce nodes;
whereinsaid distributed computer system executes a post-shuffle phase of said map-reduce job to produce an output list of said map-reduce job.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and a method for spill management during the shuffle phase of a map-reduce job performed in a distributed computer system on distributed files. A spilling protocol is provided for handling the spilling of intermediate data based on at least one popularity attribute of key-value pairs of the input data on which the map-reduce job is performed. The spilling protocol includes an assignment order to storage resources belonging to the computer system based on the at least one popularity attribute. The protocol can be deployed in computer systems with heterogeneous storage resources. Additionally, pointers or tags can be assigned to improve shuffle phase performance. The distributed file systems that are most suitable are ones usable by Hadoop, e.g., Hadoop Distributed File System (HDFS).
-
Citations
20 Claims
-
1. A distributed computer system configured for spill management during a shuffle phase of a map-reduce job performed by said distributed computer system on distributed files, said distributed computer system comprising:
-
a) key-value pairs (ki,vi) belonging to said distributed files on which said map-reduce job is performed; b) a number of map nodes for performing a pre-shuffle phase of said map-reduce job on said key value pairs (ki,vi) to generate keyed partitions (Ki,PRTj); c) storage resources for spilling said keyed partitions (Ki,PRTj) in accordance with a spilling protocol based on at least one popularity attribute of said key-value pairs (ki,vi); d) a number of reduce nodes provided with said spilling protocol to enable said reduce nodes to locate and access said keyed partitions (Ki,PRTj) during said shuffle phase by utilizing a path to said keyed partitions (Ki,PRTj), said path sent in the header of an empty HTTP message; e) said keyed partitions (Ki,PRTj) stored in a shared directory under a mount point, said shared directory accessible by said map nodes and said reduce nodes;
whereinsaid distributed computer system executes a post-shuffle phase of said map-reduce job to produce an output list of said map-reduce job. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for spill management during a shuffle phase of a map-reduce job that is performed in a distributed computer system on distributed files, said method comprising:
-
a) identifying as key-value pairs (ki,vi) input data associated with said map-reduce job; b) performing a pre-shuffle phase of said map-reduce job on said input data on a number of map nodes of said distributed computer system to generate intermediate data; c) providing a spilling protocol for said intermediate data based on at least one popularity attribute of said key-value pairs (ki,vi); d) spilling said intermediate data over storage resources of said distributed computer system in accordance with said spilling protocol by storing said intermediate data in a shared directory under a mount point, said shared directory accessible by said map nodes and a number of reduce nodes; e) providing a task tracker of said map-reduce job to send a Fully Qualified Domain Name (FQDN) path to said intermediate data in a header of an HTTP message; f) providing said reduce nodes with said spilling protocol and accessing said intermediate data utilizing said FQDN path during said shuffle phase; and g) performing a post-shuffle phase of said map-reduce job to produce an output list of said map-reduce job. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method for spill management during a shuffle phase of a map-reduce job that is performed in a distributed computer system on distributed files, said method comprising:
-
a) identifying as key-value pairs (ki,vi) input data associated with said map-reduce job; b) performing a pre-shuffle phase of said map-reduce job on said input data on a number of map nodes of said distributed computer system to generate intermediate data; c) providing a spilling protocol for said intermediate data for assigning at least one popularity attribute of said key-value pairs (ki,vi); d) spilling said intermediate data over storage resources of said distributed computer system in accordance with said spilling protocol by storing said intermediate data in a shared directory under a mount point, said shared directory accessible by said map nodes and a plurality of reduce nodes; e) providing a task tracker of said map-reduce job to send a path to said intermediate data in a header of an empty HTTP message; f) locating and accessing said intermediate data for said reduce nodes by utilizing said path during said shuffle phase; and g) performing a post-shuffle phase of said map-reduce job to produce an output list of said map-reduce job. - View Dependent Claims (20)
-
Specification