Self-healing by hash-based deduplication

• US 9,928,248 B2
• Filed: 07/08/2013
• Issued: 03/27/2018
• 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
• Primary Examiner(s): Yen, Syling
• Assistant Examiner(s): LIN, ALLEN S
• Application Number:
  US13/936,578
• Publication Number:
  US 20150012503A1
• Time in Patent Office: 1,723 Days
• Field of Search: 707692
• 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 within each one of a plurality of user-level stored entities, the user-level stored entities each comprising a file portion of a virtual tape cartridge, such that only the deduplication digests corresponding to the data stored on a given virtual tape cartridge are listed in the TOC of the given virtual tape cartridge;

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;

storing 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 and 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;

determining if a digest-to-block mapping module contains an entry for a deduplication digest, the digest-to-block mapping module searching only for the deduplication digest within the given virtual tape cartridge of which the data for the entry resides;

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 when the storage block is found to be unreadable.

2. The method of claim 1, 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.

3. The method of claim 2, 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.

4. The method of claim 1, further including using 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.

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

6. 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 within each one of a plurality of user-level stored entities, the user-level stored entities each comprising a file portion of a virtual tape cartridge, such that only the deduplication digests corresponding to the data stored on a given virtual tape cartridge are listed in the TOC of the given virtual tape cartridge,

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,

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 and 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

determines if a digest-to-block mapping module contains an entry for a deduplication digest, the digest-to-block mapping module searching only for the deduplication digest within the given virtual tape cartridge of which the data for the entry resides,

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

removes the deduplication digest from the digest-to-block mapping module when the storage block is found to be unreadable.

7. The system of claim 6, 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.

8. The system of claim 7, 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.

9. The system of claim 6, 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.

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

11. A computer program product for self-healing in a hash-based deduplication system by a 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:

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 within each one of a plurality of user-level stored entities, the user-level stored entities each comprising a file portion of a virtual tape cartridge, such that only the deduplication digests corresponding to the data stored on a given virtual tape cartridge are listed in the TOC of the given virtual tape cartridge;

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;

a third executable portion that 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 and 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

a fourth executable portion that determines if a digest-to-block mapping module contains an entry for a deduplication digest, the digest-to-block mapping module searching only for the deduplication digest within the given virtual tape cartridge of which the data for the entry resides;

a fifth executable portion that uses the digest-to-block mapping module to look up a storage block containing the deduplication digest in the digest-to-block mapping module; and

a sixth executable portion that removes the deduplication digest from the digest-to-block mapping module when the storage block is found to be unreadable.

12. The computer program product of claim 11, further includes a sixth 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.

13. The computer program product of claim 12, further includes a seventh 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.

14. The computer program product of claim 12, further includes a seventh 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.

15. The computer program product of claim 12, further includes a seventh executable portion that inputs into the list of the deduplication digests a new deduplication digest.