SELF-HEALING BY HASH-BASED DEDUPLICATION

• US 20150012503A1
• Filed: 07/08/2013
• Published: 01/08/2015
• Est. Priority Date: 07/08/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: AKIRAV, Shay H., HIRSCH, Michael
• Granted Patent: US 9,928,248 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• 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

For self-healing in a hash-based deduplication system using a processor device in a computing environment, deduplication digests of data and a corresponding list of the deduplication digests in a table of contents (TOC) are maintained for the self-healing of data that is lost or unreadable. The input data digests are compared to the TOC if directed to data that is lost or unreadable, and the input data digests are used to repair the one of lost and unreadable data.

Claims

1. A method for self-healing in a hash-based deduplication system using a processor device in a computing environment, the method comprising:

maintaining deduplication digests of data with a corresponding list of the deduplication digests in a table of contents (TOC) for the self-healing of data that is one of lost and unreadable; and

comparing input data digests to the TOC if directed to data that is one of lost and unreadable and using the input data digests to repair the one of lost and unreadable data.

2. The method of claim 1, further including storing by each one of a plurality of user-level stored entities a deduplication digest of data belonging to each one of the plurality of user-level stored entities with the corresponding list of the deduplication digest in the TOC, wherein the TOC is a list of references to storage blocks in a common storage area where each entry lists one of a block and range of the storage blocks and an offset and range within one of the block and list of blocks, and wherein the data in the one of the plurality of user-level stored entities is a concatenation of the data in the offset and range within one of the block and list of blocks that are listed in the list of references to storage blocks.

3. The method of claim 2, further including performing one of:

determining the data is one of lost and unreadable data,

adding the deduplication digests of the data determined to be the one of lost and unreadable data to a damaged digest list,

repairing a data sequence represented by a digest in the damaged digests list, wherein a repaired deduplication digest is removed from the damaged digests list, and

mapping the repaired deduplication digest to a repaired digests map for indicating to those of the plurality of user-level stored entities, having the data referred to by the repaired deduplication digest, a storage location of the data of the repaired deduplication digest.

4. The method of claim 3, further including performing one of:

reading one of the storage blocks,

determining the one of the storage blocks is damaged if unable to be read,

using the list of the deduplication digests that belong to one of the plurality of user-level stored entities to ascertain which of the deduplication digests are stored in the damaged one of the storage blocks if the one of the storage blocks in unable to be read,

identifying and recovering the data having a hash value in each of the deduplication digests stored in the damaged one of the storage blocks,

searching in the repaired digests map for each one of the deduplication digests stored in the damaged one of the storage blocks that are not able to be read,

indicating which of an alternative storage block must be read to locate the data that has a similar hash value if the one of the deduplication digests is located in the repaired digests map, and

reporting an error if the one of the deduplication digests stored in the damaged one of the storage blocks that are not able to be read is not located in the repaired digests map.

5. The method of claim 1, further including using a digest-to-block mapping module to map the deduplication digest to a storage location used to store the deduplication digest, wherein the digest-to-block mapping module is one of a global index module and a series of structures, wherein the data in one of a plurality of user-level stored entities is a concatenation of the data in storage blocks that are found using the deduplication digests as keys to search the digest-to-block mapping module.

6. The method of claim 1, further including performing at least one of:

determining if the digest-to-block mapping module contains an entry for a deduplication digest,

using the digest-to-block mapping module to look up a storage block containing the deduplication digest in the digest-to-block mapping module, and

removing the deduplication digest from the digest-to-block mapping module.

7. The method of claim 1, further including inputting into the list of the deduplication digests a new deduplication digest.

8. A system for self-healing in a hash-based deduplication system in a computing environment, the system comprising:

the hash-based deduplication system;

a plurality of user-level stored entities in the hash-based deduplication system;

storage blocks in the hash-based deduplication system;

a digest-to-block mapping module in the hash-based deduplication system;

a repaired digest map in the hash-based deduplication system;

a plurality of lists in the hash-based deduplication system, wherein the plurality of lists includes at least a corresponding list of the deduplication digests in a table of contents (TOC) and a damaged deduplication digests list; and

at least one processor device operable in the hash-based deduplication system, wherein the at least one processor device;

maintains deduplication digests of data with the corresponding list of the deduplication digests in the TOC for the self-healing of data that is one of lost and unreadable, and

compares input data digests to the TOC if directed to data that is one of lost and unreadable and using the input data digests to repair the one of lost and unreadable data.

9. The system of claim 8, wherein the at least one processor device stores by each one of the plurality of user-level stored entities a deduplication digest of data belonging to each one of the plurality of user-level stored entities with the corresponding list of the deduplication digest in the TOC, wherein the TOC is a list of references to storage blocks in a common storage area where each entry lists one of a block and range of the storage blocks and an offset and range within one of the block and list of blocks, and wherein the data in the one of the plurality of user-level stored entities is a concatenation of the data in the offset and range within one of the block and list of blocks that are listed in the list of references to storage blocks.

10. The system of claim 9, wherein the at least one processor device performs one of:

determining the data is the one of lost and unreadable data,

adding the deduplication digests of the data determined to be the one of lost and unreadable data to the damaged digest list,

repairing a data sequence represented by a digest in the damaged digests list, wherein a repaired deduplication digest is removed from the damaged digests list, and

mapping the repaired deduplication digest to the repaired digests map for indicating to those of the plurality of user-level stored entities, having the data referred to by the repaired deduplication digest, a storage location of the data of the repaired deduplication digest.

11. The system of claim 10, wherein the at least one processor device performs one of:

reading one of the storage blocks,

determining the one of the storage blocks is damaged if unable to be read,

using the list of the deduplication digests that belong to one of the plurality of user-level stored entities to ascertain which of the deduplication digests are stored in the damaged one of the storage blocks if the one of the storage blocks in unable to be read, and

identifying and recovering the data having a hash value in each of the deduplication digests stored in the damaged one of the storage blocks,

searching in the repaired digests map for each one of the deduplication digests stored in the damaged one of the storage blocks that are not able to be read,

indicating which of an alternative storage block must be read to locate the data that has a similar hash value if the one of the deduplication digests is located in the repaired digests map, and

reporting an error if the one of the deduplication digests stored in the damaged one of the storage blocks that are not able to be read is not located in the repaired digests map

12. The system of claim 8, wherein the at least one processor device uses the digest-to-block mapping module to map the deduplication digest to a storage location used to store the deduplication digest, wherein the digest-to-block mapping module is one of a global index module and a series of structures, wherein the data in one of a plurality of user-level stored entities is a concatenation of the data in storage blocks that are found using the deduplication digests as keys to search the digest-to-block mapping module.

13. The system of claim 8, wherein the at least one processor device performs at least one of:

determining if the digest-to-block mapping module contains an entry for a deduplication digest,

using the digest-to-block mapping module to look up a storage block containing the deduplication digest in the digest-to-block mapping module, and

removing the deduplication digest from the digest-to-block mapping module.

14. The system of claim 8, wherein the at least one processor device inputs into the list of the deduplication digests a new deduplication digest.

15. A computer program product for self-healing in a hash-based deduplication system by a processor device, the computer program product comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion that maintains deduplication digests of data with a corresponding list of the deduplication digests in a table of contents (TOC) for the self-healing of data that is one of lost and unreadable; and

a second executable portion that comparing input data digests to the TOC if directed to data that is one of lost and unreadable and using the input data digests to repair the one of lost and unreadable data.

16. The computer program product of claim 15, further includes a third executable portion that stores by each one of a plurality of user-level stored entities a deduplication digest of data belonging to each one of the plurality of user-level stored entities with the corresponding list of the deduplication digest in the TOC, wherein the TOC is a list of references to storage blocks in a common storage area where each entry lists one of a block and range of the storage blocks and an offset and range within one of the block and list of blocks, and wherein the data in the one of the plurality of user-level stored entities is a concatenation of the data in the offset and range within one of the block and list of blocks that are listed in the list of references to storage blocks.

17. The computer program product of claim 16, further includes a fourth executable portion that performs one of:

determining the data is the one of lost and unreadable data,

adding the deduplication digests of the data determined to be the one of lost and unreadable data to a damaged digest list,

repairing a data sequence represented by a digest in the damaged digests list, wherein a repaired deduplication digest is removed from the damaged digests list, and

mapping the repaired deduplication digest to a repaired digests map for indicating to those of the plurality of user-level stored entities, having the data referred to by the repaired deduplication digest, a storage location of the data of the repaired deduplication digest.

18. The computer program product of claim 17, further includes a fifth executable portion that performs one of:

reading one of the storage blocks,

determining the one of the storage blocks is damaged if unable to be read,

using the list of the deduplication digests that belong to one of the plurality of user-level stored entities to ascertain which of the deduplication digests are stored in the damaged one of the storage blocks if the one of the storage blocks in unable to be read,

identifying and recovering the data having a hash value in each of the deduplication digests stored in the damaged one of the storage blocks,

searching in the repaired digests map for each one of the deduplication digests stored in the damaged one of the storage blocks that are not able to be read,

indicating which of an alternative storage block must be read to locate the data that has a similar hash value if the one of the deduplication digests is located in the repaired digests map, and

reporting an error if the one of the deduplication digests stored in the damaged one of the storage blocks that are not able to be read is not located in the repaired digests map.

19. The computer program product of claim 17, further includes a fifth executable portion that uses a digest-to-block mapping module to map the deduplication digest to a storage location used to store the deduplication digest, wherein the digest-to-block mapping module is one of a global index module and a series of structures, wherein the data in one of a plurality of user-level stored entities is a concatenation of the data in storage blocks that are found using the deduplication digests as keys to search the digest-to-block mapping module.

20. The computer program product of claim 17, further includes a fifth executable portion that performs at least one of:

determining if the digest-to-block mapping module contains an entry for a deduplication digest,

using the digest-to-block mapping module to look up a storage block containing the deduplication digest in the digest-to-block mapping module,

removing the deduplication digest from the digest-to-block mapping module, and

inputting into the list of the deduplication digests a new deduplication digest.