Optimizing the de-duplication rate for a backup stream

• US 8,315,985 B1
• Filed: 12/18/2008
• Issued: 11/20/2012
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Zeis, Michael, Gipp, Stephan Kurt, Ohr, James, Elling, Dean, DesJardin, William
• Primary Examiner(s): Lewis, Cheryl
• Assistant Examiner(s): Waldron, Scott A
• Application Number:
  US12/338,563
• Time in Patent Office: 1,433 Days
• Field of Search: 707/687, 707/692, 707/698, 707/664, 707/753
• US Class Current: 707/664
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A method and apparatus for optimizing a de-duplication rate for backup streams is described. In one embodiment, the method for optimizing data de-duplication using an extent mapping of a backup stream includes processing a backup stream to access an extent mapping associated with a plurality of data files, wherein the plurality of the data files are arranged within the backup stream and examining the extent mapping to identify at least one extent group within the backup stream, wherein the plurality of the data files are de-duplicated using at least one location of the at least one extent group.

Claims

1. A method comprising:

generating extent group information, wherein

the generating uses metadata extracted from a partition within a backup stream,

the extent group information comprises

information identifying one or more extent groups associated with a single data file of a plurality of data files,

the data files are arranged within the backup stream, and

each of the one or more extent groups comprises

a plurality of extents associated with the single data file;

prepending the extent group information to the backup stream;

modifying an extent mapping by translating at least one offset relative to the partition into at least one offset relative to the backup stream, wherein

the extent mapping comprises

information identifying the data files;

processing the partition within the backup stream, wherein

the processing comprises

sorting the data files according to a starting extent location of each data file of the data files,

identifying a first data file within the backup stream, wherein

the identifying the first data file locates the starting extent of the first data file, using the extent group information,

identifying a second data file within the backup stream, wherein

the identifying the second data file locates the starting extent of the second data file, using the extent group information, and

determining whether the second data file is redundant, wherein

the determining comprises

 

determining whether the second data file is a redundant data file of the first data file,

the starting extent of the each data file of the data files is identified by a first extent group within the extent group information, and

the first extent group comprises

 

information identifying one or more extents of the each data file of the data files; and

de-duplicating the backup stream, wherein

the de-duplicating is performed in response to a determination that the second data file is redundant, and

the de-duplicating comprises

removing at least one extent group associated with the second data file from the backup stream.

2. The method of claim 1, wherein the extent group information comprises at least one location of the first extent group.

3. The method of claim 1, wherein the extent group information further comprises:

a size and an offset of a first extent for the each data file of the data files.

4. The method of claim 1, further comprising:

communicating the extent group information to a de-duplication engine, wherein

the de-duplication engine is configured to de-duplicate the backup stream using at least one location of the at least one extent group, in response to receiving the extent group information.

5. The method of claim 1, further comprising:

identifying at least one of at least one contiguous data block or at least one near-contiguous data block associated with a data file of the plurality of data files within a single segment of the backup stream.

6. The method of claim 1, wherein

the at least one extent group further comprises at least one of at least one contiguous data block or at least one near-contiguous data block associated with a data file of the plurality of data files within a single segment of the backup stream.

7. An apparatus comprising:

a central processing unit (CPU); and

a manager configured to be coupled to the CPU and further configured to

generate extent group information, wherein

the generating uses metadata extracted from a partition within a backup stream,

the extent group information comprises

information identifying one or more extent groups associated with a single data file of a plurality of data files,

the data files are arranged within the backup stream, and

each of the one or more extent groups comprises

a plurality of extents associated with the single data file;

prepend the extent group information to the backup stream;

modify an extent mapping by translating at least one offset relative to the partition into at least one offset relative to the backup stream, wherein

the extent mapping comprises

information identifying the data files;

process the partition within the backup stream, wherein

the manager is configured to process the partition within the backup stream by virtue of being configured to

sort the data files according to a starting extent location of each data file of the data files,

identify a first data file within the backup stream by locating the starting extent of the first data file, using the extent group information,

identify a second data file within the backup stream by locating the starting extent of the second data file, using the extent group information, and

determining whether the second data file is redundant by determining whether the second data file is a redundant data file of the first data file, wherein

 

the starting extent of the each data file of the data files is identified by a first extent group within the extent group information, and

 

the first extent group comprises

 

information identifying one or more extents of the each data file of the data files; and

de-duplicate the backup stream, in response to a determination that the second data file is redundant, wherein

the manager is configured to de-duplicate the backup stream by virtue of being configured to

remove at least one extent group associated with the second data file from the backup stream.

8. The apparatus of claim 7, wherein the extent group information further comprises:

a size and an offset of a first extent for the each data file of the data files.

9. The apparatus of claim 7, further comprising:

a de-duplication engine, wherein

the manager is configured to communicate the extent group information to the de-duplication engine, and

the de-duplication engine is configured to de-duplicate the backup stream using at least one location of the at least one extent group, in response to receiving the extent group information.

10. The apparatus of claim 7, wherein the extent group information comprises:

at least one location of the first extent group.

11. The apparatus of claim 7, wherein the manager is further configured to:

identify at least one of at least one contiguous data block or at least one near-contiguous data block associated with a data file of the plurality of data files within a single segment of the backup stream.

12. The apparatus of claim 7, wherein

the at least one extent group further comprises at least one of at least one contiguous data block or at least one near-contiguous data block associated with a data file of the plurality of data files within a single segment of the backup stream.

13. A system comprising:

a plurality of clients, wherein

each client comprises a plurality of data files;

a server, coupled to the plurality of clients and comprising

a manager, configured to

generate extent group information, wherein the group information comprises

generate extent group information, wherein

the generating uses metadata extracted from a partition within a backup stream,

the extent group information comprises

 

information identifying one or more extent groups associated with a single data file of a plurality of data files,

the data files are arranged within the backup stream, and

each of the one or more extent groups comprises

 

a plurality of extents associated with the single data file;

prepend the extent group information to the backup stream;

modify an extent mapping by translating at least one offset relative to the partition into at least one offset relative to the backup stream, wherein

the extent mapping comprises

 

information identifying the data files;

process the partition within the backup stream, wherein

the manager is configured to process the partition within the backup stream by virtue of being configured to

 

sort the data files according to a starting extent location of each data file of the data files,

 

identify a first data file within the backup stream by locating the starting extent of the first data file, using the extent group information,

 

identify a second data file within the backup stream by locating the starting extent of the second data file, using the extent group information, and

 

determining whether the second data file is redundant by determining whether the second data file is a redundant data file of the first data file, wherein

 

the starting extent of the each data file of the data files is identified by a first extent group within the extent group information, and

 

the first extent group comprises

 

information identifying one or more extents of the each data file of the data files; and

de-duplicate the backup stream, in response to a determination that the second data file is redundant, wherein

the manager is configured to de-duplicate the backup stream by virtue of being configured to

 

remove at least one extent group associated with the second data file from the backup stream; and

a storage pool, coupled to the server and configured to store a de-duplicated backup image.

14. The system of claim 13, wherein the extent group information comprises:

at least one location of the first extent group.

15. The system of claim 13, wherein the extent group information further comprises:

a size and an offset of a first extent for the each data file of the data files.

16. The system of claim 13, further comprising:

a de-duplication engine, wherein

the manager is configured to communicate the extent group information to the de-duplication engine, and

the de-duplication engine is configured to de-duplicate the backup stream using at least one location of the at least one extent group, in response to receiving the extent group information.

17. The system of claim 13, wherein the manager is further configured to:

identify at least one of at least one contiguous data block or at least one near-contiguous data block associated with a data file of the plurality of data files within a single segment of the backup stream.

18. The system of claim 13, wherein

the at least one extent group further comprises at least one of at least one contiguous data block or at least one near-contiguous data block associated with a data file of the plurality of data files within a single segment of the backup stream.