SCALABLE MECHANISM FOR DETECTION OF COMMONALITY IN A DEDUPLICATED DATA SET

• US 20110082840A1
• Filed: 10/06/2009
• Published: 04/07/2011
• Est. Priority Date: 10/06/2009
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Ocarina Networks, Inc. (Dell Technologies Inc.)
• Inventors: Jayaraman, Vinod
• Granted Patent: US 8,862,559 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity

Abstract

Mechanisms are provided for efficiently determining commonality in a deduplicated data set in a scalable manner regardless of the number of deduplicated files or the number of stored segments. Information is generated and maintained during deduplication to allow scalable and efficient determination of data segments shared in a particular file, other files sharing data segments included in a particular file, the number of files sharing a data segment, etc. Data need not be expanded or uncompressed. Deduplication processing can be validated and verified during commonality detection.

Claims

1. A method, comprising:

generating a filemap corresponding to a deduplicated file using a processor included in a deduplication system, the filemap including a plurality of filemap indices, a plurality of offsets to identify a plurality of data segments in the deduplicated file, and a plurality of lname entries identifying last files having placed a reference to corresponding data segments in the deduplicated file;

modifying a datastore suitcase, the datastore suitcase including an index portion and a data portion, the data portion holding a plurality of datastore indices corresponding to the filemap indices, a plurality of deduplicated data segments, and a last file entry identifying last files having placed a reference to deduplicated data segments.

2. The method of claim 1, wherein a first file has a first filemap with a NULL lname entry corresponding to a first data segment if the first deduplicated file was the last file to have placed a reference to the first data segment.

3. The method of claim 1, wherein the datastore suitcase further comprises a plurality of reference counts corresponding to a plurality of deduplicated data segments.

4. The method of claim 1, wherein the reference counts correspond to the number of files sharing corresponding deduplicated data segments.

5. The method of claim 1, wherein files sharing a particular data segment can be determined by accessing the last file entry for the particular data segment and traversing referencing filemaps until NULL entries are identified.

6. The method of claim 5, wherein filenames corresponding to lnames are identified.

7. The method of claim 1, wherein all files having data segments in common with a particular file are identified by analyzing a filemap for the particular file and identifying last file entries in the datastore suitcase for the data segments in the particular file.

8. The method of claim 1, wherein referencing filemaps are traversed until NULL entries are identified.

9. A system, comprising:

a deduplication system processor configured to generate a filemap corresponding to a deduplicated file, the filemap including a plurality of filemap indices, a plurality of offsets to identify a plurality of data segments in the deduplicated file, and a plurality of lname entries identifying last files having placed a reference to corresponding data segments in the deduplicated file;

a storage device configured to hold a datastore suitcase modified by the deduplication system processor, the datastore suitcase including an index portion and a data portion, the data portion holding a plurality of datastore indices corresponding to the filemap indices, a plurality of deduplicated data segments, and a last file entry identifying last files having placed a reference to deduplicated data segments.

10. The system of claim 9, wherein a first file has a first filemap with a NULL lname entry corresponding to a first data segment if the first deduplicated file was the last file to have placed a reference to the first data segment.

11. The system of claim 9, wherein the datastore suitcase further comprises a plurality of reference counts corresponding to a plurality of deduplicated data segments.

12. The system of claim 9, wherein the reference counts correspond to the number of files sharing corresponding deduplicated data segments.

13. The system of claim 9, wherein files sharing a particular data segment can be determined by accessing the last file entry for the particular data segment and traversing referencing filemaps until NULL entries are identified.

14. The system of claim 13, wherein filenames corresponding to lnames are identified.

15. The system of claim 9, wherein all files having data segments in common with a particular file are identified by analyzing a filemap for the particular file and identifying last file entries in the datastore suitcase for the data segments in the particular file.

16. The system of claim 9, wherein referencing filemaps are traversed until NULL entries are identified.

17. A computer readable medium having computer code embodied therein, the computer readable medium, comprising:

computer code for generating a filemap corresponding to a deduplicated file using a processor included in a deduplication system, the filemap including a plurality of filemap indices, a plurality of offsets to identify a plurality of data segments in the deduplicated file, and a plurality of lname entries identifying last files having placed a reference to corresponding data segments in the deduplicated file;

computer code modifying a datastore suitcase, the datastore suitcase including an index portion and a data portion, the data portion holding a plurality of datastore indices corresponding to the filemap indices, a plurality of deduplicated data segments, and a last file entry identifying last files having placed a reference to deduplicated data segments.

18. The computer readable medium of claim 17, wherein a first file has a first filemap with a NULL lname entry corresponding to a first data segment if the first deduplicated file was the last file to have placed a reference to the first data segment.

19. The computer readable medium of claim 17, wherein the datastore suitcase further comprises a plurality of reference counts corresponding to a plurality of deduplicated data segments.

20. The computer readable medium of claim 17, wherein the reference counts correspond to the number of files sharing corresponding deduplicated data segments.