Verifying a file in a system with duplicate segment elimination using segmention-independent checksums

• US 7,624,335 B1
• Filed: 10/13/2005
• Issued: 11/24/2009
• Est. Priority Date: 10/13/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Maheshwari, Umesh, Patterson, R. Hugo
• Primary Examiner(s): Abraham; Esaw T
• Application Number:
  US11/251,627
• Time in Patent Office: 1,503 Days
• Field of Search: 714/6, 714/15, 714/758, 714/799, 714/805, 714/807
• US Class Current: 714/807
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00

Abstract

Verifying a file in a system with duplicate segment elimination is disclosed. A data file is segmented into a plurality of distinct data segments, and a checksum is computed for each of the plurality of distinct data segments. A constructed data file checksum is constructed from the checksums of each of the plurality of distinct data segments, and, it is determined if a checksum of the data file is the same as the constructed data file checksum.

Claims

1. A method for verifying a file in a system with duplicate segment elimination comprising:

segmenting a data file into a plurality of distinct data segments

storing the data file in a data storage system, wherein storing the data file comprises checking to determine whether one or more of the plurality of distinct data segments is the same as a data segment that has been stored previously in the data storage system, and in the event that one of the plurality of distinct data segments is not the same as a segment already stored, storing the one of the plurality of distinct data segments, and in the event that one of the plurality of distinct data segments is the same as a data segment that has been stored previously in the data storage system, storing a reference to the data segment that has been stored previously in place of the one of the plurality of distinct data segments;

computing, using a processor, a checksum for each of the plurality of distinct data segments;

constructing a constructed data file checksum from the checksums of each of the plurality of distinct data segments; and

determining if a checksum of the data file is the same as the constructed data file checksum.

2. A method as in claim 1, further including, in the event that the checksum of the data file is the same as the constructed data file checksum, indicating that the data file and the plurality of distinct data segments have been verified as being equivalent.

3. A method as in claim 1, wherein the checksum is a composable hash.

4. A method as in claim 1, wherein the checksum is a 1-byte XOR.

5. A method as in claim 1, wherein the checksum is a 4-byte XOR.

6. A method as in claim 1, wherein the checksum is a byte-wise sum.

7. A method as in claim 1, wherein the checksum is a Rabin fingerprint.

8. A method as in claim 1, wherein the checksum of the data file is computed by a source system.

9. A method as in claim 1, wherein the checksum of the data file is computed by a storage system.

10. A system for verifying a file in a system with duplicate segment elimination comprising:

a processor configured to;

segment a data file into a plurality of distinct data segments

store the data file in a data storage system, wherein storing the data file comprises checking to determine whether one or more of the plurality of distinct data segments is the same as a data segment that has been stored previously in the data storage system, and in the event that one of the plurality of distinct data segments is not the same as a segment already stored, storing the one of the plurality of distinct data segments, and in the event that one of the plurality of distinct data segments is the same as a data segment that has been stored previously in the data storage system, storing a reference to the data segment that has been stored previously in place of the one of the plurality of distinct data segments;

compute a checksum for each of the plurality of distinct data segments;

construct a constructed data file checksum from the checksums of each of the plurality of distinct data segments; and

determine if a checksum of the data file is the same as the constructed data file checksum; and

a memory coupled to the processor and configured to provide instructions to the processor.

11. A system as in claim 10, wherein the processor is further configured to, in the event that the checksum of the data file is the same as the constructed data file checksum, indicate that the data file and the plurality of distinct data segments have been verified as being equivalent.

12. A system as in claim 10, wherein the checksum is a composable hash.

13. A system as in claim 10, wherein the checksum is a 1-byte XOR.

14. A system as in claim 10, wherein the checksum is a 4-byte XOR.

15. A system as in claim 10, wherein the checksum is a byte-wise sum.

16. A system as in claim 10, wherein the checksum is a Rabin fingerprint.

17. A system as in claim 10, wherein the checksum of the data file is computed by a source system.

18. A system as in claim 10, wherein the checksum of the data file is computed by a storage system.

19. A computer program product for verifying a file in a system with duplicate segment elimination, the computer program product being embodied in a computer readable storage medium and comprising computer instructions that when executed, cause a computer to perform the following:

segment a data file into a plurality of distinct data segments

store the data file in a data storage system wherein storing the data file comprises checking to determine whether one or more of the plurality of distinct data segments is the same as a data segment that has been stored previously in the data storage system, and in the event that one of the plurality of distinct data segments is not the same as a segment already stored, storing the one of the plurality of distinct data segments, and in the event that one of the plurality of distinct data segments is the same as a data segment that has been stored previously in the data storage system, storing a reference to the data segment that has been stored previously in place of the one of the plurality of distinct data segments;

computing a checksum for each of the plurality of distinct data segments;

constructing a constructed data file checksum from the checksums of each of the plurality of distinct data segments; and

determining if a checksum of the data file is the same as the constructed data file checksum.

20. A computer program product as recited in claim 19, the computer program product further comprising computer instructions for, in the event that the checksum of the data file is the same as the constructed data file checksum, indicating that the data file and the plurality of distinct data segments have been verified as being equivalent.

21. A computer program product as recited in claim 19, the computer program product further comprising computer instructions for receiving from a first system at a second system the data file and the secondary identifier of the data file.

22. A computer program product as recited in claim 19, wherein the checksum is a composable hash.

23. A computer program product as recited in claim 19, wherein the checksum is a 1-byte XOR.

24. A computer program product as recited in claim 19, wherein the checksum is a 4-byte XOR.

25. A computer program product as recited in claim 19, wherein the checksum is a byte-wise sum.

26. A computer program product as recited in claim 19, wherein the checksum is a Rabin fingerprint.

27. A computer program product as recited in claim 19, wherein the checksum of the data file is computed by a source system.

28. A computer program product as recited in claim 19, wherein the checksum of the data file is computed by a storage system.