Fast deduplication data verification

• US 10,496,615 B2
• Filed: 06/29/2016
• Issued: 12/03/2019
• 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,452
• Publication Number:
  US 20160306820A1
• Time in Patent Office: 1,252 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 synchronization of deduplication information, 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 stores, for a first data chunk identified in a primary table, a first value and a second value, wherein the first value is based on first primary identifications of first data blocks in the first data chunk and the second value comprises a sum of squared first primary identifications;

retrieve, from a secondary storage subsystem, a first single instance file (SFile) associated with the first data chunk;

determine a first SFile value based on second primary identifications of second data blocks stored in the first SFile;

determine a second SFile value based on the second primary identifications of the second data blocks stored in the first SFile;

compare the first value with the first SFile value and the second value with the second SFile value; and

determine that the primary table and the first SFile are synched in response to a determination that the first value matches the first SFile value and the second value matches the second SFile value.

2. The networked information management system of claim 1, wherein the computer hardware is further configured to determine that the primary table and the first SFile are not synched in response to a determination that the first value does not match the first SFile value or the second value does not match the second SFile value.

3. 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.

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

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

6. The networked information management system of claim 1, wherein the first value comprises a sum of the first primary identifications.

7. The networked information management system of claim 6, wherein the first SFile value comprises a sum of the second primary identifications.

8. The networked information management system of claim 1, wherein the second SFile value comprises a sum of squared second primary identifications.

9. The networked information management system of claim 1, wherein the deduplication chunk table stores the first value, the second value, a set of other first values for other data chunks, and a set of other second values for the other data chunks.

10. The networked information management system of claim 9, wherein the computer hardware is further configured to determine whether the primary table and other SFiles associated with the other data chunks are synched based on the set of other first values and the set of other second values.

11. A computer-implemented method for verifying synchronization of deduplication information, the computer-implemented method comprising:

retrieving, from an electronically stored deduplication database, a deduplication chunk table, wherein the deduplication chunk table stores, for a first data chunk identified in a primary table, a first value and a second value, wherein the first value is based on first primary identifications of first data blocks in the first data chunk and the second value comprises a sum of squared first primary identifications;

retrieving, from a secondary storage subsystem, a first single instance file (SFile) associated with the first data chunk;

determining a first SFile value based on second primary identifications of second data blocks stored in the first SFile;

determining a second SFile value based on the second primary identifications of the second data blocks stored in the first SFile;

comparing the first value with the first SFile value and the second value with the second SFile value; and

determining that the primary table and the first SFile are synched in response to a determination that the first value matches the first SFile value and the second value matches the second SFile value.

12. The computer-implemented method of claim 11, further comprising determining that the primary table and the first SFile are not synched in response to a determination that the first value does not match the first SFile value or the second value does not match the second SFile value.

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

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

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

16. The computer-implemented method of claim 11, wherein the first value comprises a sum of the first primary identifications.

17. The computer-implemented method of claim 16, wherein the first SFile value comprises a sum of the second primary identifications.

18. The computer-implemented method of claim 11, wherein the second SFile value comprises a sum of squared second primary identifications.

19. The computer-implemented method of claim 11, wherein the deduplication chunk table stores the first value, the second value, a set of other first values for other data chunks, and a set of other second values for the other data chunks.

20. The computer-implemented method of claim 19, further comprising determining whether the primary table and other SFiles associated with the other data chunks are synched based on the set of other first values and the set of other second values.