Self-referential deduplication

• US 9,075,532 B1
• Filed: 04/23/2010
• Issued: 07/07/2015
• Est. Priority Date: 04/23/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Bromley, Graham
• Primary Examiner(s): Rigol, Yaima
• Application Number:
  US12/766,177
• Time in Patent Office: 1,901 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A first value is calculated as a function of data in an n^th data block of a backup copy. The first value is then compared with each of a plurality of values in a plurality of entries, respectively, of a first data structure. The plurality of entries in the first data structure include a plurality of pointers, respectively, that correspond to a plurality of data blocks, respectively, in a storage system. If the first value compares equally to a value contained in one of the plurality of entries of the first data structure, a pointer of the one entry is added to an n^th entry of a second data structure. This pointer corresponds to a copy of the n^th data block that is stored in the storage system. If the first value does not compare equally with any value contained in the plurality of entries of the first data structure, (1) the n^th data block is stored in the storage system, and (2) a first pointer is added to the n^th entry of the second data structure. The first pointer corresponds to the n^th data block that is stored in the storage system. Eventually the second data structure is stored in the storage system after adding the pointer or the first pointer to the n^th entry.

Claims

1. A method comprising:

deduplicating data, wherein the deduplicating comprises;

calculating a first value as a function of data in an n^th data block of a backup copy comprising a number, z, of data blocks, where n is a number from 1 to z;

comparing the first value with each of a plurality of values in a plurality of entries, respectively, of a first data structure, the plurality of entries comprising a plurality of pointers, respectively, that identify a plurality of locations, respectively, where a plurality of data blocks, respectively, are physically stored in a storage system;

if the first value compares equally to a value contained in one of the plurality of entries of the first data structure, then a copy of the n^th data block was previously stored in the storage system and as a result the method further comprises adding a pointer to the one entry to an n^th entry of a second data structure, wherein the pointer identifies where the copy of the n^th data block is stored in the storage system;

if the first value does not compare equally with any value contained in the plurality of entries of the first data structure, (1) storing the n^th data block in the storage system, and (2) adding a first pointer to the n^th entry of the second data structure, wherein the first pointer identifies where the n^th data block is stored in the storage system;

storing the second data structure in the storage system after adding the pointer or the first pointer to the n^th entry;

wherein the first pointer enables a computer system to retrieve the n^th data block from the storage system without referencing the first data structure during data reflation, and

wherein the pointer enables the computer system to retrieve the copy of the n^th data block from the storage system without referencing the first data structure during reflation.

2. The method of claim 1, wherein a first computer system calculates the first value, a second computer system accesses the first data structure using the first value, and wherein the first and second computer systems are coupled together via a communication link.

3. The method of claim 2, further comprising the first computer system generating and sending a request to the second computer system via the communication link, the request comprising the first value.

4. The method of claim 2, wherein at least one other data block of the backup copy is stored as part of a first data object in the storage system, and wherein the method further comprises the first computer system recreating the backup copy using the first data object and the second data structure, wherein the first computer system recreates the backup copy independent of the second computer system.

5. The method of claim 1, wherein at least one data block of the backup copy is stored as part of a first data object in the storage system.

6. The method of claim 5, further comprising an act of migrating the first data object and the second data structure to a second storage system.

7. The method of claim 6, further comprising an act of recreating the backup copy using the first data object and the second data structure of the second storage system.

8. The method of claim 1, wherein the second data structure includes only pointers to data blocks stored in the storage system.

9. The method of claim 1, wherein

the first data structure is stored in a second storage system operably coupled to an appliance,

the appliance accesses the second storage system in order to deduplicate data, and

the appliance is separate from the first storage system.

10. The method of claim 9, wherein the appliance is not needed for the computer system to retrieve the n^th data block from the storage system.

11. A non-transitory computer readable medium comprising program instructions, wherein the program instructions are executable by one or more processors to implement a method, the method comprising:

deduplicating data, wherein the deduplicating comprises;

calculating a first value as a function of data in an n^th data block of a backup copy that comprises a number, z, of data blocks, where n is a number from 1 to z;

if the first value compares equally to a value contained in one of a plurality of entries of a first data structure, adding a pointer to the one entry to an n^th entry of a second data structure, wherein the pointer identifies where a copy of the n^th data block is physically stored in a storage system;

if the first value does not compare equally with any value contained in the plurality of entries of the first data structure, (1) storing the n^th data block in the storage system, and (2) adding a first pointer to the n^th entry of the second data structure, wherein the first pointer identifies where the n^th data block is physically stored in the storage system;

storing the second data structure in the storage system after adding the pointer or the first pointer to the n^th entry;

wherein the first pointer enables a computer system to retrieve the n^th data block from the storage system without referencing the first data structure during reflation, and

wherein the pointer enables the computer system to retrieve the copy of the n^th data block from the storage system without referencing the first data structure during reflation.

12. The non-transitory computer readable medium of claim 11, wherein the method further comprises comparing the first value with each of a plurality of values in the plurality of entries, respectively, of the first data structure, the plurality of entries comprising a plurality of pointers, respectively, that identify a plurality of locations, respectively, where a plurality of data blocks, respectively, are physically stored in the storage system.

13. The non-transitory computer readable medium of claim 11, wherein at least one data block of the backup copy is stored as part of a first data object in the storage system.

14. The non-transitory computer readable medium of claim 13, further comprising an act of recreating the backup copy using the second data structure and the first data object.

15. The non-transitory computer readable medium of claim 11, further comprising an act of generating and sending a request comprising the first value.

16. An apparatus comprising:

a first computer system coupled to a second computer system via a communication link, wherein;

the first computer system is configured to calculate a first value as a function of data in an n^th data block of a backup copy that comprises a number, z, of data blocks, where n is a number from 1 to z;

the second computer system is configured to compare the first value with each of a plurality of values in a plurality of entries, respectively, of a first data structure, the plurality of entries comprising a plurality of pointers, respectively, that identify a plurality of locations, respectively, where a plurality of data blocks, respectively, are physically stored in a storage system;

if the first value compares equally to a value contained in one of the plurality of entries of the first data structure, the first computer system is configured to add a pointer to the one entry to an n^th entry of a second data structure, wherein the pointer identifies where a copy of the n^th data block is stored in the storage system;

if the first value does not compare equally with any value contained in the plurality of entries of the first data structure, the first computer system is configured to (1) store the n^th data block in the storage system, and (2) add a first pointer to the n^th entry of the second data structure, wherein the first pointer identifies where the n^th data block is stored in the storage system;

the first computer system is configured to store the second data structure in the storage system after adding the pointer or the first pointer to the n^th entry;

wherein the first pointer enables a computer system to retrieve the n^th data block from the storage system without referencing the first data structure during reflation, and

wherein the pointer enables the computer system to retrieve the copy of the n^th data block from the storage system without referencing the first data structure during reflation.

17. The apparatus of claim 16, wherein the first computer system is configured to generate and send a request to the second computer system via the communication link, the request comprising the first value.

18. The apparatus of claim 16, wherein the first computer system is configured to store a first data object in the storage system, wherein at least one other data block of the backup copy is contained in the first data object, and wherein the first computer system is configured to recreate the backup copy using the first data object and the second data structure, wherein the first computer system is configured to recreate the backup copy independent of the second computer system.

19. The apparatus of claim 16, further comprising a third computer system configured to migrate the first data object and the second data structure from the storage system to a second storage system.

20. The apparatus of claim 19, further comprising a fourth computer system configured to recreate the backup copy using the first data object and the second data structure of the second storage system.