Removal of reference information for storage blocks in a deduplication system

• US 10,248,656 B2
• Filed: 06/18/2015
• Issued: 04/02/2019
• Est. Priority Date: 06/18/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aronovich, Lior, Kredi, Amir
• Primary Examiner(s): Pyo, Monica M
• Application Number:
  US14/743,600
• Publication Number:
  US 20160371295A1
• Time in Patent Office: 1,384 Days
• Field of Search: 707692, 707756, 707693
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• 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

Abstract

Various embodiments for managing data in a data storage having data deduplication. For a back reference data structure incorporating reference information for at least one user data segment to a storage block, a user data segment identification (ID) representative of the at least one user data segment is removed from the back reference data structure.

Claims

1. A method for managing data in a data storage having data deduplication, comprising:

under control of a processor and memory having executable instructions, performing;

for a back reference data structure incorporating reference information for at least one user data segment to a storage block, removing, by the processor, a user data segment identification (ID) representative of the at least one user data segment from the back reference data structure, the storage block being associated with both a reference counter and the user data segment ID of the back reference data structure;

wherein the removal of the user data segment ID is performed in response to determining that the at least one user data segment no longer references the storage block caused by failed data, thereby maintaining the back reference data structure so as to facilitate an efficient search operation for recovering or reclaiming the failed data within the data storage;

configuring the back reference data structure by partitioning the back reference data structure as form type bits specifying a type of the ID representative of the at least one user data segment, and storage bits storing the ID of a representation of the ID thereof;

defining a plurality of form types corresponding to the form type bits;

defining a first form type structure incorporating a full representation of the ID of the at least one user data segment to be stored in the back reference data structure;

storing the defined first form type structure in the back reference data structure;

defining second, intermediate form type structures implementing a hashed form of the at least one user data segment ID to be stored in the back reference data structure;

storing the defined second, intermediate form type structures in the back reference data structure;

defining a third form type structure implementing a representation of the at least one user data segment ID as a bit bucket in a hash table of the at least one user data segment to be stored in the back reference data structure; and

storing the third form type structure in the back reference data structure;

wherein a total number of the at least one user data segment ID increases as a bit per ID correspondingly decreases when migrating from the first form type through the second form types to the third form type.

2. The method of claim 1, wherein the user data segment ID is removed from the back reference data structure if the back reference data structure contains an initial form type of the user data segment ID in the back reference data structure.

3. The method of claim 1, further including examining the reference counter of the storage block following removal of the user data segment ID.

4. The method of claim 3, wherein if the reference counter is determined to be zero, resetting a current form type in the back reference data structure to the initial form type.

5. The method of claim 3, further including decrementing the reference counter in response to verifying that a value of the reference counter and a number of the user data segment IDs in the back reference data structure are equivalent.

6. The method of claim 5, further including removing the user data segment ID from the back reference data structure if there was not a previous state where the number of user data segment IDs in the back reference data structure was lower than the value of the reference counter.

7. The method of claim 6, further including converting the removed user data segment ID to a form corresponding to the form of the back reference data structure, and removing the converted form from the back reference data structure.

8. The method of claim 1, further including converting the form type of the back reference data structure prior to removal of the user data segment ID to an additional form type following removal of the user data segment ID if a count of remaining user data segment IDs in the back reference data structure reaches a predetermined lower threshold, thereby increasing a resolution of the back reference data structure.

9. A system for managing data in a data storage having data deduplication, comprising:

a memory device; and

a processor executing instructions stored in the memory device, wherein when executing the instructions, the processor;

for a back reference data structure incorporating reference information for at least one user data segment to a storage block, removes a user data segment identification (ID) representative of the at least one user data segment from the back reference data structure, the storage block being associated with both a reference counter and the user data segment ID of the back reference data structure;

wherein the removal of the user data segment ID is performed in response to determining that the at least one user data segment no longer references the storage block caused by failed data, thereby maintaining the back reference data structure so as to facilitate an efficient search operation for recovering or reclaiming the failed data within the data storage;

configures the back reference data structure by partitioning the back reference data structure as form type bits specifying a type of the ID representative of the at least one user data segment, and storage bits storing the ID of a representation of the ID thereof;

defines a plurality of form types corresponding to the form type bits;

defines a first form type structure incorporating a full representation of the ID of the at least one user data segment to be stored in the back reference data structure;

stores the defined first form type structure in the back reference data structure;

defines second, intermediate form type structures implementing a hashed form of the at least one user data segment ID to be stored in the back reference data structure;

stores the defined second, intermediate form type structures in the back reference data structure;

defines a third form type structure implementing a representation of the at least one user data segment ID as a bit bucket in a hash table of the at least one user data segment to be stored in the back reference data structure; and

stores the third form type structure in the back reference data structure;

wherein a total number of user data segment IDs increases as a bit per ID correspondingly decreases when migrating from the first form type through the second form types to the third form type.

10. The system of claim 9, wherein the user data segment ID is removed from the back reference data structure if the back reference data structure contains an initial form type of the user data segment ID in the back reference data structure.

11. The system of claim 9, wherein the processor examines the reference counter of the storage block following removal of the user data segment ID.

12. The system of claim 11, wherein the processor, if the reference counter is determined to be zero, resets a current form type in the back reference data structure to the initial form type.

13. The system of claim 11, wherein the processor decrements the reference counter in response to verifying that a value of the reference counter and a number of the user data segment IDs in the back reference data structure are equivalent.

14. The system of claim 13, wherein the processor removes the user data segment ID from the back reference data structure if there was not a previous state where the number of user data segment IDs in the back reference data structure was lower than the value of the reference counter.

15. The system of claim 14, wherein the processor converts the removed user data segment ID to a form corresponding to the form of the back reference data structure, and removes the converted form from the back reference data structure.

16. The system of claim 9, wherein the processor converts the form type of the back reference data structure prior to removal of user data segment ID to an additional form type following removal of the user data segment ID if a count of remaining user data segment IDs in the back reference data structure reaches a predetermined lower threshold, thereby increasing a resolution of the back reference data structure.

17. A computer program product for managing data in a data storage having data deduplication, 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:

a first executable portion that;

for a back reference data structure incorporating reference information for at least one user data segment to a storage block, removes, by the processor, a user data segment identification (ID) representative of the at least one user data segment from the back reference data structure, the storage block being associated with both a reference counter and the user data segment ID of the back reference data structure;

wherein the removal of the user data segment ID is performed in response to determining that the at least one user data segment no longer references the storage block caused by failed data, thereby maintaining the back reference data structure so as to facilitate an efficient search operation for recovering or reclaiming the failed data within the data storage;

configures the back reference data structure by partitioning the back reference data structure as form type bits specifying a type of the ID representative of the at least one user data segment, and storage bits storing the ID of a representation of the ID thereof;

defines a plurality of form types corresponding to the form type bits;

defines a first form type structure incorporating a full representation of the ID of the at least one user data segment to be stored in the back reference data structure;

stores the defined first form type structure in the back reference data structure;

defines second, intermediate form type structures implementing a hashed form of the at least one user data segment ID to be stored in the back reference data structure;

stores the defined second, intermediate form type structures in the back reference data structure;

defines a third form type structure implementing a representation of the at least one user data segment ID as a bit bucket in a hash table of the at least one user data segment to be stored in the back reference data structure; and

stores the third form type structure in the back reference data structure;

wherein a total number of the at least one user data segment ID increases as a bit per ID correspondingly decreases when migrating from the first form type through the second form types to the third form type.

18. The computer program product of claim 17, wherein the user data segment ID is removed from the back reference data structure if the back reference data structure contains an initial form type of the user data segment ID in the back reference data structure.

19. The computer program product of claim 17, further including a second executable portion that examines the reference counter of the storage block following removal of the user data segment ID.

20. The computer program product of claim 19, further including a third executable portion that, if the reference counter is determined to be zero, resets a current form type in the back reference data structure to the initial form type.

21. The computer program product of claim 20, further including a third executable portion that decrements the reference counter in response to verifying that a value of the reference counter and a number of the user data segment IDs in the back reference data structure are equivalent.

22. The computer program product of claim 21, further including a fourth executable portion that removes the user data segment ID from the back reference data structure if there was not a previous state where the number of user data segment IDs in the back reference data structure was lower than the value of the reference counter.

23. The computer program product of claim 22, further including a fifth executable portion that converts the removed user data segment ID to a form corresponding to the form of the back reference data structure, and removes the converted form from the back reference data structure.

24. The computer program product of claim 17, further including a third executable portion that converts the form type of the back reference data structure prior to removal of user data segment ID to an additional form type following removal of the user data segment ID if a count of remaining user data segment IDs in the back reference data structure reaches a predetermined lower threshold, thereby increasing a resolution of the back reference data structure.