Management of intermediate data spills during the shuffle phase of a map-reduce job

• US 9,740,706 B2
• Filed: 06/21/2016
• Issued: 08/22/2017
• Est. Priority Date: 06/03/2013
• Status: Active Grant

• Current Assignee: Zettaset Incorporated
• Original Assignee: Zettaset Incorporated
• Inventors: Cramer, Michael J., Christian, Brian P.
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): TESSEMA, AIDA Z
• Application Number:
  US15/188,182
• Publication Number:
  US 20160299919A1
• Time in Patent Office: 427 Days
• Field of Search: 707827
• CPC Class Codes: G06F 16/183 Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

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).

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), said spilling managed by a spilling protocol utilizing at least one popularity attribute of said key-value pairs (ki,vi);

(d) said popularity attribute of said key-value pairs (ki,vi) determined in accordance with at least one element selected from the group consisting of relevance ranking of said key-value pairs (ki,vi) to a topic of interest, number of times that said key-value pairs (ki,vi) are used in computations and level of trust of data sources from which said key-value pairs (ki,vi) were obtained;

(e) 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);

wherein said distributed computer system executes a post-shuffle phase of said map-reduce job to produce an output of said map-reduce job.

2. The distributed computer system of claim 1, wherein said storage resources comprise heterogeneous storage resources recognized as block storage devices by said distributed computer system.

3. The distributed computer system of claim 2, wherein said heterogeneous storage resources include at least two members of the group consisting of SATA, HDD, RAID, SSD, Optical drives, Cloud, tape and general block storage devices.

4. The distributed computer system of claim 2, further comprising a tag assigned by said spilling protocol, said tag containing a logical unit number (LUN) of said block storage devices storing those amongst said keyed partitions (Ki,PRTj) that are related to most popular amongst said key-value pairs (ki,vi).

5. The distributed computer system of claim 1, wherein said distributed file system comprises a distributed file system usable by Hadoop.

6. The distributed computer system of claim 1, wherein said spilling protocol is managed by a task tracker of said map-reduce job.

7. The distributed computer system of claim 6, wherein in response to a request from one amongst said reduce nodes to said task tracker, a servlet associated with said task tracker sends a pointer to said keyed partitions (Ki,PRTj).

8. The distributed computer system of claim 1, wherein said storage resources are segmented into cluster segments and said map-reduce job is performed on each of said cluster segments.

9. The distributed computer system of claim 1, wherein said spilling protocol utilizes an assignment order to said storage resources for said spilling, based on said at least one popularity attribute.

10. The distributed computer system of claim 1, wherein said spilling protocol spills to fastest amongst said storage resources, those amongst said keyed-partitions (Ki,PRTj) that are related to most popular amongst said key-value pairs (ki,vi).

11. The distributed computer system of claim 1, wherein said output comprises partial results of said map-reduce job, and said output produced while said map-reduce job is still in progress.

12. A method for spill management during a shuffle phase of a map-reduce job that is performed on distributed files of a distributed computer system, said method comprising:

(a) identifying key-value pairs (ki,vi) related to input data associated with said map-reduce job;

(b) executing a pre-shuffle phase of said map-reduce job on said input data, said pre-shuffle phase performed on a number of map nodes of said distributed computer system, said pre-shuffle phase generating 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) determining said popularity attribute of said key-value pairs (ki,vi) in accordance with at least one element selected from the group consisting of relevance ranking of said key-value pairs (ki,vi) to a topic of interest, number of times that said key-value pairs (ki,vi) are used in computations and level of trust of data sources from which said key-value pairs (ki,vi) were obtained;

(e) spilling said intermediate data over storage resources of said distributed computer system in accordance with said spilling protocol;

(f) providing said spilling protocol to a number of reduce nodes of said distributed computer system to enable said reduce nodes to locate and access said intermediate data during said shuffle phase; and

(g) performing a post-shuffle phase of said map-reduce job to produce a partial output of said map-reduce job.

13. The method of claim 12, wherein said spilling protocol utilizes an assignment order to said storage resources for said spilling, based on said at least one popularity attribute.

14. The method of claim 12, wherein said storage resources comprise heterogeneous storage resources recognized as block storage devices by said distributed computer system.

15. The method of claim 14, wherein said heterogeneous storage resources include at least two members of the group consisting of SATA, HDD, RAID, SSD, Optical drives, Cloud, tape and general block storage devices.

16. The method of claim 14, wherein said spilling protocol assigns a tag containing a logical unit number (LUN) of said block storage devices storing that portion of said intermediate data which is related to most popular amongst said key-value pairs (ki,vi).

17. The method of claim 12, wherein said distributed file system comprises a distributed file system usable by Hadoop.

18. The method of claim 12 further utilizing a search-ranking algorithm in the determination of said popularity attribute.

19. A method for spill management during a shuffle phase of a map-reduce job that is performed on distributed files in a distributed computer system, said method comprising:

(a) identifying key-value pairs (ki,vi) related to input data associated with said map-reduce job;

(b) performing on a number of map nodes of said distributed computer system a pre-shuffle phase of said map-reduce job on said input data, said pre-shuffle phase generating 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) determining said popularity attribute of said key-value pairs (ki,vi) in accordance with at least two elements selected from the group consisting of search ranking of said key-value pairs (ki,vi), relevance ranking of said key-value pairs (ki,vi) to a topic of interest, number of times that said key-value pairs (ki,vi) are used in computations and level of trust of data sources from which said key-value pairs (ki,vi) were obtained;

(e) spilling said intermediate data over storage resources of said distributed computer system in accordance with said spilling protocol;

(f) providing said spilling protocol to a number of reduce nodes of said distributed computer system to enable said reduce nodes to locate and access said intermediate data during said shuffle phase; and

(g) performing a post-shuffle phase of said map-reduce job for producing an output list of said map-reduce job.

20. The method of claim 19 performing said producing of said output list while said map-reduce job is still in progress, and said output list comprising partial results from said map-reduce job.