Estimating a performance parameter of a job having map and reduce tasks after a failure

• US 9,244,751 B2
• Filed: 05/31/2011
• Issued: 01/26/2016
• Est. Priority Date: 05/31/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Cherkasova, Ludmila, Verma, Abhishek
• Primary Examiner(s): McCarthy, Christopher
• Application Number:
  US14/118,520
• Publication Number:
  US 20140089727A1
• Time in Patent Office: 1,701 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 11/3404 for parallel or distributed programming
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

A job profile includes characteristics of a job to be executed, where the characteristics of the job profile relate to map tasks and reduce tasks of the job, and where the map tasks produce intermediate results based on input data, and the reduce tasks produce an output based on the intermediate results. In response to a failure in a system, numbers of failed map tasks and reduce tasks of the job based on a time of the failure are computed, and numbers of remaining map tasks and reduce tasks are computed. A performance model is provided, and a performance parameter of the job is estimated using the performance model.

Claims

1. A method comprising:

receiving, by a system comprising a processor, a job profile that includes characteristics of a job to be executed, wherein the characteristics of the job profile relate to map tasks and reduce tasks of the job, wherein the map tasks produce intermediate results based on input data, and the reduce tasks produce an output based on the intermediate results;

in response to an indication of a failure in the system associated with execution of the job, computing, by the system, numbers of failed map tasks and failed reduce tasks of the job based on a time of the failure, wherein the indication of the failure comprises an indication that a computing node of plural computing nodes has failed;

computing, by the system, numbers of remaining map tasks and remaining reduce tasks based on the numbers of failed map tasks and failed reduce tasks;

providing, by the system, a performance model based on the job profile, the computed numbers of remaining map tasks and remaining reduce tasks, and an allocated amount of resources for the job, wherein providing the performance model is based on the allocated amount of resources that has been reduced from a previous allocation of resources due to the failure; and

estimating, by the system, a performance parameter of the job using the performance model.

2. The method of claim 1, wherein the indication comprises a time indication regarding the time of the failure.

3. The method of claim 2, further comprising:

based on the time of failure, determining whether the failure is during a map stage or reduce stage, where the map tasks of the job are performed during the map stage, and wherein the reduce tasks of the job are performed in the reduce stage.

4. The method of claim 3, wherein, based on the failure occurring during the map stage, the computed number of failed reduce tasks is zero.

5. The method of claim 3, wherein, based on the failure occurring during the reduce stage, the computed number of failed map tasks is equal to a number of the map tasks of the job in the map stage divided by a number of worker nodes for executing map and reduce tasks.

6. The method of claim 1, wherein estimating the performance parameter comprises estimating a time duration of the job.

7. An article comprising at least one non-transitory machine-readable storage medium storing instructions that upon execution cause a system to:

receive a job profile that includes characteristics of a job to be executed, wherein the characteristics of the job profile relate to map tasks and reduce tasks of the job, wherein the map tasks produce intermediate results based on input data, and the reduce tasks produce an output based on the intermediate results;

in response to an indication of a failure in the system associated with execution of the job, compute numbers of failed map tasks and failed reduce tasks of the job based on a time of the failure;

compute numbers of remaining map tasks and remaining reduce tasks based on the numbers of failed map tasks and failed reduce tasks;

determine whether resources of the system are to be replenished after the failure;

provide a performance model based on the job profile, the computed numbers of remaining map tasks and remaining reduce tasks, and an allocated amount of resources for the job, wherein providing the performance model is based on the allocated amount of resources after the replenishing of resources; and

estimate a performance parameter of the job using the performance model.

8. The article of claim 7, wherein the indication of the failure comprises an indication that a computing node of plural computing nodes has failed.

9. The article of claim 7, wherein the indication comprises a time indication regarding the time of the failure.

10. The article of claim 7, wherein estimating the performance parameter comprises estimating a time duration of the job.

11. A system comprising:

a storage medium to store a job profile that includes characteristics of a job to be executed, wherein the characteristics of the job profile relate to map tasks and reduce tasks of the job, wherein the map tasks produce intermediate results based on input data, and the reduce tasks produce an output based on the intermediate results; and

at least one processor to;

detect occurrence of a failure in the system;

in response to detecting the failure, determine whether the failure occurred during a map stage or a reduce stage, wherein the map tasks are to be performed during the map stage, and the reduce tasks are to be performed during the reduce stage;

compute a number of failed map tasks and a number of failed reduce tasks dependent upon whether the failure occurred during the map stage or the reduce stage;

compute a number of remaining map tasks and a number of remaining reduce tasks based on the numbers of failed map tasks and failed reduce tasks;

update a performance model using the numbers of remaining map tasks and remaining reduce tasks; and

estimate a performance parameter of the job using the updated performance model.

12. The system of claim 11, wherein the at least one processor is to further:

receive an indication of a time of the failure,

wherein determining whether the failure occurred during the map stage or the reduce stage is based on comparing the time of the failure with a time bound associated with the map stage.

13. The system of claim 11, wherein the at least one processor is to maintain, in the performance model, an allocation of resources equal to an initial allocation of resources for the job in response to an indication that failed resources are to be replenished.

14. The system of claim 11, wherein the performance parameter is a time duration of the job.

15. A system comprising:

a storage medium to store a job profile that includes characteristics of a job to be executed, wherein the characteristics of the job profile relate to map tasks and reduce tasks of the job, wherein the map tasks produce intermediate results based on input data, and the reduce tasks produce an output based on the intermediate results; and

at least one processor to;

detect occurrence of a failure in the system;

in response to detecting the failure, compute a number of failed map tasks and a number of failed reduce tasks based on a time of the failure;

compute a number of remaining map tasks and a number of remaining reduce tasks based on the numbers of failed map tasks and failed reduce tasks;

update a performance model using the numbers of remaining map tasks and remaining reduce tasks and in response to an indication that failed resources are not to be replenished, wherein the update of the performance model includes reducing allocations of resources; and

estimate a performance parameter of the job using the updated performance model.

16. The system of claim 15, wherein the performance parameter is a time duration of the job.