Fast deduplication data verification

• US 10,614,049 B2
• Filed: 06/29/2016
• Issued: 04/07/2020
• Est. Priority Date: 09/16/2014
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Agrawal, Saurabh, Vijayan, Manoj Kumar
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US15/197,420
• Publication Number:
  US 20160306829A1
• Time in Patent Office: 1,378 Days
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

An information management system provides a data deduplication system that uses a primary table, a deduplication chunk table, and a chunk integrity table to ensure that a referenced deduplicated data block is only verified once during the data verification of a backup or other replication operation. The data deduplication system may reduce the computational and storage overhead associated with traditional data verification processes. The primary table, the deduplication chunk table, and the chunk integrity table, all of which are stored in a deduplication database, can also ensure synchronization between the deduplication database and secondary storage devices.

Claims

1. A networked information management system configured to verify integrity of deduplication data, the networked information management system comprising:

a storage manager comprising computer hardware configured to;

retrieve, from an electronically stored deduplication database, a deduplication chunk table, wherein the deduplication chunk table identifies a first data chunk;

retrieve, from a secondary storage subsystem, a first single instance file (SFile) associated with the first data chunk, wherein the first SFile comprises a plurality of SFile containers that each store one or more data blocks;

for each SFile container in the plurality of SFile containers,

perform a data integrity verification of corresponding one or more data blocks of the respective SFile container,

wherein the data integrity verification includes determining whether the corresponding one or more data blocks of the respective SFile container is readable, and

store a value representing a result of the data integrity verification of the corresponding one or more data blocks of the respective SFile container in association with an entry corresponding to the first data chunk in a chunk integrity table;

receive request to verify integrity of at least one data blocks referenced in the plurality of SFile containers; and

for each data block of the at least one data blocks,

determine that a first link in the first data chunk references the data block of a corresponding SFile container in the plurality of SFile containers, and

verify integrity of the data block of the corresponding SFile container by performing a lookup of the chunk integrity table to determine whether the block is verified instead of by analyzing the data block of the corresponding SFile container.

2. The networked information management system of claim 1, wherein the computer hardware is further configured to, for each SFile container in the plurality of SFile containers, store a zero bit in association with the entry corresponding to the first data chunk in the chunk integrity table in response to a determination that least one of the corresponding one or more data blocks of the respective SFile container cannot be verified.

3. The networked information management system of claim 1, wherein the computer hardware is further configured to, for each SFile container in the plurality of SFile containers, store a one bit in association with the entry corresponding to the first data chunk in the chunk integrity table in response to a determination that all of the corresponding one or more data blocks of the respective SFile container can be verified.

4. The networked information management system of claim 1, wherein the computer hardware is further configured to retrieve the deduplication chunk table in response to a request to verify data in a backup.

5. The networked information management system of claim 4, wherein the computer hardware is further configured to cause the chunk integrity table to be deleted from the electronically stored deduplication database after verification of the data in the backup is complete.

6. The networked information management system of claim 1, wherein the corresponding SFile container in the plurality of SFile containers is verified if the one or more data blocks stored in the corresponding SFile container are also decompressible, and decryptable.

7. The networked information management system of claim 1, wherein, for each SFile container in the plurality of SFile containers, the corresponding one or more data blocks of the respective SFile container are referenced by one or more links in the first data chunk.

8. The networked information management system of claim 1, wherein the stored values allow the storage manager to verify the integrity of the data stored in the first data chunk without having to verify the one or more data blocks in the plurality of SFile containers more than once.

9. The networked information management system of claim 1, wherein the computer hardware is further configured to retrieve the corresponding SFile based on an SFile index stored in the first data chunk.

10. The networked information management system of claim 1, wherein the deduplication chunk table identifies the first data chunk and a set of other data chunks.

11. The networked information management system of claim 10, wherein the computer hardware is further configured to:

perform a verification of other SFile containers of other SFiles associated with the other data chunks; and

store results of the verification of the other SFile containers in the chunk integrity table.

12. A computer-implemented method for verifying integrity of deduplication data, the computer-implemented method comprising:

retrieving, from an electronically stored deduplication database, a deduplication chunk table, wherein the deduplication chunk table identifies a first data chunk;

retrieving, from a secondary storage subsystem, a first single instance file (SFile) associated with the first data chunk, wherein the first SFile comprises a plurality of SFile containers that each store one or more data blocks;

for each SFile container in the plurality of SFile containers,

performing a data integrity verification of corresponding one or more data blocks of the respective SFile container,

wherein the data integrity verification includes determining whether the corresponding one or more data blocks of the respective SFile container is readable, and

storing a value representing a result of the data integrity verification of the corresponding one or more data blocks of the respective SFile container in association with an entry corresponding to the first data chunk in a chunk integrity table;

identifying a request to verify integrity of at least one data blocks referenced in one or more SFile containers in the plurality of the SFile containers; and

for each data block of the at least one data blocks,

determining that a first link in the first data chunk references a data block of a corresponding SFile container in the plurality of SFile containers, and

verifying integrity of the data block of the corresponding SFile container by performing a lookup of the chunk integrity table to determine whether the data block is verified.

13. The computer-implemented method of claim 12, further comprising, for each SFile container in the plurality of SFile containers, storing a zero bit in association with the entry corresponding to the first data chunk in the chunk integrity table in response to a determination that least one of the corresponding one or more data blocks of the respective SFile container cannot be verified.

14. The computer-implemented method of claim 12, further comprising, for each SFile container in the plurality of SFile containers, storing a one bit in association with the entry corresponding to the first data chunk in the chunk integrity table in response to a determination that all of the corresponding one or more data blocks of the respective SFile container can be verified.

15. The computer-implemented method of claim 12, further comprising retrieving the deduplication chunk table in response to a request to verify data in a backup.

16. The computer-implemented method of claim 15, further comprising causing the chunk integrity table to be deleted from the electronically stored deduplication database after verification of the data in the backup is complete.

17. The computer-implemented method of claim 12, wherein the corresponding SFile container in the plurality of SFile containers is verified if the one or more data blocks stored in the corresponding SFile container are also decompressible, and decryptable.

18. The computer-implemented method of claim 12, wherein, for each SFile container in the plurality of SFile containers, the corresponding one or more data blocks of the respective SFile container are referenced by one or more links in the first data chunk.

19. The computer-implemented method of claim 12, wherein the stored values allow the storage manager to verify the integrity of the data stored in the first data chunk without having to verify the one or more data blocks in the plurality of SFile containers more than once.

20. The computer-implemented method of claim 12, further comprising retrieving the first SFile based on an SFile index stored in the first data chunk.