Methods and apparatus for IO sizing based task throttling

• US 9,798,584 B1
• Filed: 09/29/2015
• Issued: 10/24/2017
• Est. Priority Date: 09/29/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Kulkarni, Gururaj, Mandic, Vladimir
• Primary Examiner(s): Kim, Sisley
• Application Number:
  US14/869,777
• Time in Patent Office: 756 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Methods and apparatuses select service tasks according to allocations of an available usage rate of a common processing resource are described. An ordering relationship is updated among the service tasks. E service task can have a rate of usage of the common processing resource. Each service may be associated with one of multiple task types. An allocation of the available rate of usage may be determined among the task types. The allocation can indicate a portion of the available rate of usage for each task type. The service tasks may be selected according to the allocation and the ordering relationship. At least one of the selected service tasks is associated with each task type associated with the service tasks.

Claims

1. A machine-readable non-transitory storage medium having instructions therein, which when executed by a machine, cause the machine to perform operations comprising:

updating an ordering relationship among a plurality of service tasks, wherein execution of each service task depends on a usage of a common processing resource, each service task having a rate of usage of the common processing resource, each service task associated with one of a plurality of task types, wherein the common processing resource having an available rate of usage, wherein each task type has a priority, and wherein the ordering relationship is updated based on a combination of the priority and the usage rate of each service task;

determining an allocation of the available rate of usage among the task types, the allocation indicating a portion of the available rate of usage for each of task type associated with the service tasks;

selecting one or more of the service tasks for execution according to the allocation and the ordering relationship among the plurality of service tasks, wherein at least one of the selected service task(s) is associated with each task type associated with the service tasks;

executing the selected service task(s) to update data stored in a device via the common processing resource, wherein the device includes a storage component storing the data in a file system;

calculating a maximum resource usage associated with the file system, wherein the maximum resource usage indicates a maximum number of transactions per unit time associated with the file system; and

dividing and distributing the maximum resource usage associated with the file system among the selected service task(s) in accordance with an ordering relationship among the selected service task(s).

2. The medium of claim 1, wherein the operations further comprise:

identifying the available rate of usage based on the maximum number of transactions with the file system per unit time.

3. The medium of claim 2, wherein the common processing resource includes an input/output interface to the device, and wherein the rate of usage represents a number of input/output requests to the input/output interface for the transactions.

4. The medium of claim 2, wherein the identifying comprises:

tracking the number of input/output requests dynamically during runtime, wherein the maximum number of transactions per unit time is determined based on a history of the number of input/output requests tracked.

5. The medium of claim 4, wherein zero or more service tasks are currently running, wherein the available rate of usage is inversely related to a sum of rates of usage associated with the currently running service tasks and wherein the available rate of usage is no more than a value determined by the maximum number of transactions per unit time.

6. The medium of claim 1, wherein the ordering relationship is updated dynamically while the selected service tasks are being executed.

7. The medium of claim 6, wherein the ordering relationship is directly related to the priority associated with each service task.

8. The medium of claim 6, wherein the ordering relationship is inversely related to the rate of usage of each service task.

9. The medium of claim 6, wherein where each service task is received for the execution at an arrival time, wherein the ordering relationship is updated based on the arrival time of each service task and wherein the ordering relationship is directly related to the arrival time of each service task.

10. The medium of claim 9, wherein the ordering relationship is updated in response to receiving at least one of the service tasks.

11. The medium of claim 1, wherein the determination of the allocation comprises:

maintaining an allocation table specifying target allocations of the available usage rate for different subsets of the plurality of task types, wherein the task types associated with the service tasks correspond to one of the subsets of the plurality of task types and wherein the allocation corresponds to a particular one of the target allocation for the one subset of the plurality of task types.

12. The medium of claim 11, wherein the target allocations depends on a measure of current working environment, wherein the portion is substantially evenly allocated among each task type associated with the service tasks if the measure indicates a work load of the current working environment below a threshold value.

13. The medium of claim 1, wherein the selected service tasks includes a number of service tasks of a particular task type associated with the service tasks, and wherein the selection comprises:

identifying the number of service tasks of the particular task type from the service tasks following the ordering relationship, wherein a combination of usage rates of the number of service tasks is constrained by a portion of the available rate of usage for the particular task type indicated in the allocation.

14. The medium of claim 13, wherein the combination includes a sum of the usage rates of the number of service tasks.

15. The medium of claim 1, wherein one or more service tasks are currently being executed, and wherein a particular one of the currently executed service tasks completes, the operations further comprising:

monitoring rates of usage of the common processing resources by the currently executed service tasks;

detecting completion of a particular one of the currently executed tasks, wherein the ordering relationship is updated in response to the detection of the completion of the particular one of the currently executed service tasks; and

updating the available rate of usage based on the rates of usage monitored for remaining ones of the currently executed service tasks.

16. A computer-implemented method, the method comprising:

updating an ordering relationship among a plurality of service tasks, wherein execution of each service task depends on a usage of a common processing resource, each service task having a rate of usage of the common processing resource, each service task associated with one of a plurality of task types, wherein the common processing resource having an available rate of usage, wherein each task type has a priority, and wherein the ordering relationship is updated based on a combination of the priority and the usage rate of each service task;

determining an allocation of the available rate of usage among the task types, the allocation indicating a portion of the available rate of usage for each of task type associated with the service tasks;

selecting one or more of the service tasks for execution according to the allocation and the ordering relationship among the plurality of service tasks, wherein at least one of the selected service task(s) is associated with each task type associated with the service tasks;

executing the selected service task(s) to update data stored in a device via the common processing resource, wherein the device includes a storage component storing the data in a file system;

calculating a maximum resource usage associated with the file system, wherein the maximum resource usage indicates a maximum number of transactions per unit time associated with the file system; and

dividing and distributing the maximum resource usage associated with the file system among the selected service task(s) in accordance with an ordering relationship among the selected service task(s).

17. The method of claim 16, wherein the operations further comprise:

identifying the available rate of usage based on the maximum number of transactions with the file system per unit time.

18. The method of claim 17, wherein the common processing resource includes an input/output interface to the device, and wherein the rate of usage represents a number of input/output requests to the input/output interface for the transactions.

19. The method of claim 17, wherein the identifying comprises:

tracking the number of input/output requests dynamically during runtime, wherein the maximum number of transactions per unit time is determined based on a history of the number of input/output requests tracked.

20. The method of claim 19, wherein zero or more service tasks are currently running, wherein the available rate of usage is inversely related to a sum of rates of usage associated with the currently running service tasks and wherein the available rate of usage is no more than a value determined by the maximum number of transactions per unit time.

21. The method of claim 16, wherein the ordering relationship is updated dynamically while the selected service tasks are being executed.

22. The method of claim 16, wherein the determination of the allocation comprises:

maintaining an allocation table specifying target allocations of the available usage rate for different subsets of the plurality of task types, wherein the task types associated with the service tasks correspond to one of the subsets of the plurality of task types and wherein the allocation corresponds to a particular one of the target allocation for the one subset of the plurality of task types.

23. The method of claim 16, wherein the selected service tasks includes a number of service tasks of a particular task type associated with the service tasks, and wherein the selection comprises:

identifying the number of service tasks of the particular task type from the service tasks following the ordering relationship, wherein a combination of usage rates of the number of service tasks is constrained by a portion of the available rate of usage for the particular task type indicated in the allocation.

24. The method of claim 16, wherein one or more service tasks are currently being executed, and wherein a particular one of the currently executed service tasks completes, the operations further comprising:

monitoring rates of usage of the common processing resources by the currently executed service tasks;

detecting completion of a particular one of the currently executed tasks, wherein the ordering relationship is updated in response to the detection of the completion of the particular one of the currently executed service tasks; and

updating the available rate of usage based on the rates of usage monitored for remaining ones of the currently executed service tasks.

25. A computer system comprising:

a memory storing executable instructions;

a storage device storing data;

a processor coupled to the memory and the storage device to execute the instructions from the memory, the processor being configured to

update an ordering relationship among a plurality of service tasks, wherein execution of each service task depends on a usage of an interface to the storage device, each service task having a rate of usage of the interface, each service task associated with one of a plurality of task types, wherein the interface to the storage device having an available rate of usage, wherein each task type has a priority, and wherein the ordering relationship is updated based on a combination of the priority and the usage rate of each service task;

determine an allocation of the available rate of usage among the task types, the allocation indicating a portion of the available rate of usage for each of task type associated with the service tasks;

select one or more of the service tasks for execution according to the allocation and the ordering relationship among the plurality of service tasks, wherein at least one of the selected service task(s) is associated with each task type associated with the service tasks;

execute the selected service task(s) to update the data stored in the storage device via the interface, wherein the device includes a storage component storing the data in a file system;

calculate a maximum resource usage associated with the file system, wherein the maximum resource usage indicates a maximum number of transactions per unit time associated with the file system; and

divide and distribute the maximum resource usage associated with the file system among the selected service task(s) in accordance with an ordering relationship among the selected service task(s).