Deduplicated data processing hierarchical rate control in a data deduplication system

• US 10,255,306 B2
• Filed: 11/29/2017
• Issued: 04/09/2019
• Est. Priority Date: 03/10/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: David, Johnny, Halumi, Afief, Tamary, Lior
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US15/825,357
• Publication Number:
  US 20180081915A1
• Time in Patent Office: 496 Days
• Field of Search: 707609, 707821, 707692, 707693, 707792, 707793, 709225, 718104, 712202, 712201, 705 712
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

For deduplicated data processing hierarchical rate control in a data deduplication system in a computing storage environment, priorities in a hierarchal structure are propagated by defining a relationship between each of a plurality of maintenance tasks and using a resource distribution function for managing and dividing resources between the plurality of maintenance tasks based on a priority for each maintenance task. Each one of the plurality of maintenance tasks is defined to be one of above, below, and at a same level in the hierarchal structure as compared to another one of the plurality of maintenance tasks. The hierarchal structure comprises a tree structure having a plurality of leaf nodes that are actual task and branch nodes that are virtual tasks.

Claims

1. A method for deduplicated data processing hierarchical rate control in a data deduplication system using at least one processor in a computing environment, the method comprising:

propagating priorities in a hierarchal structure by defining a relationship between each of a plurality of maintenance tasks and using a resource distribution function for managing and dividing resources between the plurality of maintenance tasks based on a priority for each maintenance task;

wherein at least one of the plurality of maintenance tasks comprises a garbage collection operation; and

defining each one of the plurality of maintenance tasks to be one of above, below, and at a same level in the hierarchal structure as compared to another one of the plurality of maintenance tasks, wherein the hierarchal structure is a tree structure having a plurality of leaf nodes that are actual task and branch nodes that are virtual tasks.

2. The method of claim 1, further including using by the resource distribution function a plurality of parameters, wherein the plurality of parameters include a total number of resources assigned to a parent task, a priority of each one of the plurality of maintenance tasks, a default distribution of resources parameter.

3. The method of claim 2, further including allocating an array that contains a reverse polish notation (RPN) for calculating the priority of a root of the hierarchal structure and storing at each level of the hierarchal structure a calculated priority result in the branch nodes for preventing a traversal of the hierarchal structure.

4. The method of claim 3, further including adjusting resources allocated to a root task in the hierarchal structure for coordinating resource consumption of the plurality of maintenance tasks and allowing a minimum amount of the resources to be used for one of the plurality of maintenance tasks.

5. The method of claim 4, further including using the priorities of each one of the plurality of maintenance tasks as a hint for indicating which of the plurality of maintenance tasks are most important.

6. The method of claim 1, further including controlling, by a central controller, a rate of work by each of the plurality of maintenance tasks in a computing system.

7. A system deduplicated data processing hierarchical rate control in a data deduplication system in a computing environment, the system comprising:

the data deduplication system;

a central controller in the data deduplication system;

at least one processor device controlling the data deduplication system and the central controller and operable in the computing environment, wherein at least one processor device;

propagates priorities in a hierarchal structure by defining a relationship between each of a plurality of maintenance tasks and using a resource distribution function for managing and dividing resources between the plurality of maintenance tasks based on a priority for each maintenance task;

wherein at least one of the plurality of maintenance tasks comprises a garbage collection operation; and

defines each one of the plurality of maintenance tasks to be one of above, below, and at a same level in the hierarchal structure as compared to another one of the plurality of maintenance tasks, wherein the hierarchal structure is a tree structure having a plurality of leaf nodes that are actual task and branch nodes that are virtual tasks.

8. The system of claim 7, wherein the at least one processor device uses by the resource distribution function a plurality of parameters, wherein the plurality of parameters include a total number of resources assigned to a parent task, a priority of each one of the plurality of maintenance tasks, a default distribution of resources parameter.

9. The system of claim 8, wherein the at least one processor device allocates an array that contains a reverse polish notation (RPN) for calculating the priority of a root of the hierarchal structure and storing at each level of the hierarchal structure a calculated priority result in the branch nodes for preventing a traversal of the hierarchal structure.

10. The system of claim 9, wherein the at least one processor device adjusts resources allocated to a root task in the hierarchal structure for coordinating resource consumption of the plurality of maintenance tasks and allowing a minimum amount of the resources to be used for one of the plurality of maintenance tasks.

11. The system of claim 10, wherein the at least one processor device uses the priorities of each one of the plurality of maintenance tasks as a hint for indicating which of the plurality of maintenance tasks are most important.

12. The system of claim 7, wherein the at least one processor device controls a rate of work by each of the plurality of maintenance tasks in a computing system.

13. A computer program product for deduplicated data processing hierarchical rate control in a data deduplication system in a computing environment by at least one processor device, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

an executable portion that propagates priorities in a hierarchal structure by defining a relationship between each of a plurality of maintenance tasks and using a resource distribution function for managing and dividing resources between the plurality of maintenance tasks based on a priority for each maintenance task;

wherein at least one of the plurality of maintenance tasks comprises a garbage collection operation; and

an executable portion that defines each one of the plurality of maintenance tasks to be one of above, below, and at a same level in the hierarchal structure as compared to another one of the plurality of maintenance tasks, wherein the hierarchal structure is a tree structure having a plurality of leaf nodes that are actual task and branch nodes that are virtual tasks.

14. The computer program product of claim 13, further including an executable portion that uses by the resource distribution function a plurality of parameters, wherein the plurality of parameters include a total number of resources assigned to a parent task, a priority of each one of the plurality of maintenance tasks, a default distribution of resources parameter.

15. The computer program product of claim 14, further including an executable portion that allocates an array that contains a reverse polish notation (RPN) for calculating the priority of a root of the hierarchal structure and storing at each level of the hierarchal structure a calculated priority result in the branch nodes for preventing a traversal of the hierarchal structure.

16. The computer program product of claim 15, further including an executable portion that adjusts resources allocated to a root task in the hierarchal structure for coordinating resource consumption of the plurality of maintenance tasks and allowing a minimum amount of the resources to be used for one of the plurality of maintenance tasks.

17. The computer program product of claim 16, further including an executable portion that uses the priorities of each one of the plurality of maintenance tasks as a hint for indicating which of the plurality of maintenance tasks are most important.

18. The computer program product of claim 13, further including an executable portion that controls a rate of work by each of the plurality of maintenance tasks in a computing system.