Sequential cooperation between map and reduce phases to improve data locality

• US 8,924,978 B2
• Filed: 08/30/2012
• Issued: 12/30/2014
• Est. Priority Date: 06/18/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Meng, Xiaoqiao, Tan, Jian, Zhang, Li
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Sun, Charlie
• Application Number:
  US13/599,486
• Publication Number:
  US 20130339966A1
• Time in Patent Office: 852 Days
• Field of Search: 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5013 Request control
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

Methods and arrangements for task scheduling. At least one job is assimilated from at least one node, each job comprising at least a map phase and a reduce phase, each of the map and reduce phases comprising at least one task. Progress of a map phase of at least one job is compared with progress of a reduce phase of at least one job. Launching of a task of a reduce phase of at least one job is scheduled in response to progress of the reduce phase of at least one job being less than progress of the map phase of at least one job.

Claims

1. An apparatus comprising:

at least one processor; and

a computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising;

computer readable program code configured to assimilate at least one job from at least one node, each job of the at least one job comprising at least a map phase and a reduce phase, each of the map and reduce phases comprising at least one task;

computer readable program code configured to compare a percentage of completed map tasks of a map phase of the at least one job with a percentage of started reducers of a the reduce phase of the at least one job; and

computer readable program code configured to schedule incremental launching of a the at least one task of a reduce phase of at least one job in response to the percentage of started reducers of the reduce phase of the at least one job being less than the percentage of completed map tasks of the map phase of the at least one job.

2. A computer program product comprising:

a computer readable storage medium, not including a signal, having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to assimilate at least one job from at least one node, each job of the at least one job comprising at least a map phase and a reduce phase, each of the map and reduce phases comprising at least one task;

computer readable program code configured to compare the percentage of completed map tasks of a map phase of the at least one job with the percentage of started reducers of a the reduce phase of the at least one job; and

computer readable program code configured to schedule incremental launching of a the at least one task of a reduce phase of at least one job in response to the percentage of started reducers of the reduce phase of the at least one job being less than the percentage of completed map tasks of the map phase of the at least one job.

3. The computer program product according to claim 2, wherein said computer readable program code is configured to assess a viability of a launch of the at least one task of the reduce phase of the at least one job.

4. The computer program product according to claim 3, wherein said computer readable program code is configured to launch the at least one task of the reduce phase of the at least one job in response to an assessed viability of a launch.

5. The computer program product according to claim 3, wherein said computer readable program code is configured to delay launch of the at least one task of the reduce phase of the at least one job in response to an assessed non-viability of a launch.

6. The computer program product according to claim 2, wherein said computer readable program code is configured to compare progress in response to a heartbeat from the at least one node.

7. The computer program product according to claim 2, wherein:

each of the map and reduce phases of the each job comprises a plurality of tasks;

wherein said computer readable program code is configured to compare a completion percentage of tasks of the map phase of the at least one job with a function of a completion percentage of tasks of the reduce phase of the at least one job.

8. The computer program product according to claim 2, wherein said computer readable program code is configured to calculate a mismatch value which characterizes a progress difference between the at least one task of the map phase of the at least one job with the at least one task of the reduce phase of the at least one job.

9. The computer program product according to claim 2, wherein said computer readable program code is configured to schedule launching of a task of a map phase of the at least one job in response to the percentage of started reducers of the reduce phase of the at least one job not being less than the percentage of completed map tasks of the map phase of the at least one job.

10. The computer program product according to claim 9, wherein said computer readable program code is configured to assess availability of local input data of a node.

11. The computer program product according to claim 10, wherein said computer readable program code is configured to launch a task of the map phase of the at least one job in response to an assessed availability of local input data at a node.

12. The computer program product according to claim 10, wherein said computer readable program code is configured, in response to an assessed non-availability of local input data at the at least one node, to:

determine a probability factor with respect to the at least one other node; and

randomly launch a task of the map phase of the at least one job based on the probability factor.

13. The computer program product according to claim 12, wherein said computer readable program code is configured to determine the probability factor via:

assessing availability of local input data at the at least one other node;

assessing capability of the at least one other node to run a task of the map phase; and

determining a quantity of at least one pending task of the map phase of the at least one job.