Granted Patent B1

US 8,886,605 · App. 13/526,168 · Granted Nov 11, 2014

Inventors: Weibao Wu (Vadnais Heights, MN); Xianbo Zhang (Madison, WI)

Assignee: Symantec Operating Corporation

G06F17/30156

Abstract

Claims (110)

1. A computer-implemented method comprising:

generating a fingerprint corresponding to a first file-data segment of a file, wherein

the file comprises a plurality of file-data segments;

accessing a mapping table, wherein

the mapping table comprises a plurality of entries, wherein

each of the plurality of entries comprises

a fingerprint of a previously-stored data segment stored within at least one content storage volume, and

a storage location of the previously-stored data segment within the at least one content storage volume;

determining, for the first file-data segment, whether the fingerprint corresponding to the first file-data segment is equivalent to the fingerprint of any previously-stored data segment;

storing the first file-data segment in contiguous memory in the at least one content storage volume, wherein

the storing is performed in response to determining that the fingerprint corresponding to the first file-data segment is not equivalent to the fingerprint of any previously-stored data segment; and

updating the mapping table, wherein

the mapping table is updated, in response to a determination that the fingerprint of the first file-data segment is not equivalent to the fingerprint of any previously-stored data segment, to indicate a first storage location of the first file-data segment within the at least one content storage volume.

2. The computer-implemented method of claim 1 , wherein the at least one content storage volume is coupled to a deduplication server.

3. The computer-implemented method of claim 1 , further comprising:

accessing the mapping table, after the updating, to determine that more than one copy of the first file-data segment is being stored within the at least one content storage volume.

4. The computer-implemented method of claim 1 , further comprising:

performing a second update of the mapping table, wherein

the mapping table is updated a second time to indicate a removal of the first file-data segment from the first storage location, and

the performing the second update of the mapping table is performed in response to detecting that the first file-data segment is being removed from the first storage location.

5. The computer-implemented method of claim 1 , wherein a relocation of the first file-data segment to a second storage location comprises:

storing a duplicate copy of the first file-data segment at the second storage location, and

removing the first file-data segment from the first storage location.

6. The method of claim 1 , wherein

each of the plurality of entries further comprises

a fingerprint for a respective file-data segment of the plurality of file-data segments, and

a location of the respective file-data segment within the at least one content storage volume, and

the each of the pluralities of entries corresponds to a different file-data segment of the plurality of file-data segments.

7. The method of claim 1 , wherein:

the first file-data segment at the first storage location is deleted based on the accessing the mapping table.

8. The method of claim 1 , further comprising:

analyzing information to determine whether a number of disk seeks necessary to retrieve a plurality of potentially-new data segments exceeds a predetermined threshold;

storing the plurality of potentially-new data segments in contiguous locations in memory, wherein

the storing is performed in response to a determination that the number of disk seeks necessary to retrieve the plurality of potentially-new data segments exceeds the predetermined threshold; and

replacing at least one previously-stored data segment that corresponds to one of the plurality of potentially-new data segments, wherein

the replacing comprises

removing said previously-stored data segment from memory, and

updating the mapping table to indicate a new location of said previously-stored data segment.

9. A non-transitory computer readable storage medium, wherein the non-transitory computer readable storage medium comprises instructions, executable by at least one processor, and configured to:

generate a fingerprint corresponding to a first file-data segment of a file, wherein

the file comprises a plurality of file-data segments;

access a mapping table, wherein

the mapping table comprises a plurality of entries, wherein

each of the plurality of entries comprises

a fingerprint of a previously-stored data segment stored within at least one content storage volume, and

a storage location of the previously-stored data segment within the at least one content storage volume; and

determine, for the first file-data segment, whether the fingerprint corresponding to the first file-data segment is equivalent to the fingerprint of any previously-stored data segment;

store the first file-data segment in contiguous memory in the at least one content storage volume, wherein

the first file-data segment is stored in response to a determination that the fingerprint corresponding to the first file-data segment is not equivalent to the fingerprint of any previously-stored data segment; and

update the mapping table, wherein

the mapping table is updated, in response to the determination that the fingerprint corresponding to the first file-data segment is not equivalent to the fingerprint of any previously-stored data segment, to indicate a first storage location of the first file-data segment within the at least one content storage volume.

10. The non-transitory computer readable storage medium of claim 9 , wherein the at least one content storage volume is coupled to a deduplication server.

11. The non-transitory computer readable storage medium of claim 9 , wherein the instructions are further configured to:

access the mapping table, after the update, to determine that more than one copy of the first file-data segment is being stored within the at least one content storage volume.

12. The non-transitory computer readable storage medium of claim 9 , wherein the instructions are further configured to:

perform a second update of the mapping table, wherein

the mapping table is updated a second time to indicate a removal of the first file-data segment from the first storage location, and

the second update of the mapping table is performed in response to detecting that the first file-data segment is being removed from the first storage location.

13. The non-transitory computer readable storage medium of claim 9 , wherein a relocation of the first file-data segment to a second storage location comprises:

storing a duplicate copy of the first file-data segment at the second storage location, and

removing the first file-data segment from the first storage location.

14. An apparatus comprising:

a memory;

a processor;

means for generating a fingerprint corresponding to a first file-data segment of a file, wherein

the file comprises a plurality of file-data segments;

means for accessing a mapping table, wherein

the mapping table comprises a plurality of entries, wherein

each of the plurality of entries comprises

a fingerprint of a previously-stored data segment stored within at least one content storage volume, and

a storage location of the previously-stored data segment within the at least one content storage volume;

means for determining, for the first file-data segment, whether the fingerprint corresponding to the first file-data segment is equivalent to the fingerprint of any previously-stored data segment;

means for storing the first file-data segment in contiguous memory in the at least one content storage volume, wherein

the means for storing is configured to store the first file-data segment in response to determining that the fingerprint corresponding to the first file-data segment is not equivalent to the fingerprint of any previously-stored data segment; and

means for updating the mapping table, wherein

the mapping table is updated, in response to a determination that the fingerprint of the first file-data segment is not equivalent to the fingerprint of any previously-stored data segment, to indicate a first storage location of the first file-data segment within the at least one content storage volume.

15. The apparatus of claim 14 , wherein the at least one content storage volume is coupled to a deduplication server.

16. The apparatus of claim 14 , further comprising:

means for accessing the mapping table, after the updating, to determine that more than one copy of the first file-data segment is stored within the at least one content storage volume.

17. The apparatus of claim 14 , further comprising:

means for performing a second update of the mapping table, wherein

the mapping table is updated a second time to indicate a removal of the first file-data segment from the first storage location, and

the performing the second update of the mapping table is performed in response to detecting that the first file-data segment is being removed from the first storage location.

18. The apparatus of claim 14 , wherein a relocation of the first file-data segment to a second storage location comprises:

storing a duplicate copy of the first file-data segment at the second storage location, and

removing the first file-data segment from the first storage location.

19. A computer-implemented method comprising:

identifying a file on a client, wherein

the file comprises a plurality of file-data segments, and

the plurality of file-data segments corresponds to a plurality of file-data segment fingerprints, respectively, wherein

each of the plurality of file-data segments corresponds to exactly one file-data segment fingerprint among the plurality of file-data segment fingerprints;

transmitting, from the client to a deduplication server, the plurality of file-data segment fingerprints, wherein

the deduplication server is communicatively coupled to a mapping table, wherein the mapping table comprises a plurality of entries, wherein

each of the plurality of entries comprises

a previously-stored fingerprint corresponding to a previously-stored data segment stored in a content storage volume, and

a storage location of the previously-stored data segment in the content storage volume;

analyzing the plurality of file-data segment fingerprints to determine whether at least one of the plurality of file-data segment fingerprints corresponds to one of the previously-stored fingerprints in the mapping table;

returning, to the client, a set of storage locations corresponding to the plurality of file-data segment fingerprints that respectively correspond to one of the previously-stored fingerprints, wherein

the returning is performed in response to a determination that at least one of the plurality of file-data segment fingerprints corresponds to one of the previously-stored fingerprints in the mapping table, and

the set of storage locations comprises one or more of the storage locations in the mapping table; and

evaluating the set of storage locations to determine whether a number of disk seeks necessary to retrieve the plurality of file-data segments comprising the file would exceed a predetermined threshold.

20. The computer-implemented method of claim 19 , further comprising:

sending the plurality of file-data segments comprising the file from the client to the deduplication server, wherein

the sending is performed in response to a determination that the number of disk seeks necessary to retrieve the plurality of file-data segments comprising the file would exceed the predetermined threshold; and

storing the plurality of file-data segments at one or more new storage locations in contiguous memory in the content storage volume.

21. The computer-implemented method of claim 20 , further comprising:

removing the previously-stored data segments that have a fingerprint corresponding to the file-data segment fingerprint of one of the file-data segments stored at said one or more new storage locations in contiguous memory;

updating the mapping table in response to removing said previously-stored data segments, wherein the updating comprises:

accessing each of the entries in the mapping table that comprise the file-data segment fingerprint of one of the previously-stored data segments, and

updating said entry to indicate the new storage location of the previously-stored data segment.

Assignments (12)

Continuity (1)