Systems and methods for managing single instancing data

• US 9,015,181 B2
• Filed: 09/23/2009
• Issued: 04/21/2015
• Est. Priority Date: 09/26/2008
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Kottomtharayil, Rajiv, Attarde, Deepak R., Vijayan, Manoj K.
• Primary Examiner(s): Pham, Khanh
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US12/565,576
• Publication Number:
  US 20100082672A1
• Time in Patent Office: 2,036 Days
• Field of Search: 707/609, 707/705, 707/758
• US Class Current: 707/758
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files

Abstract

Described in detail herein are systems and methods for managing single instancing data. Using a single instance database and other constructs (e.g. sparse files), data density on archival media (e.g. magnetic tape) is improved, and the number of files per storage operation is reduced. According to one aspect of a method for managing single instancing data, for each storage operation, a chunk folder is created on a storage device that stores single instancing data. The chunk folder contains three files: 1) a file that contains data objects that have been single instanced; 2) a file that contains data objects that have not been eligible for single instancing; and 3) a metadata file used to track the location of data objects within the other files. A second storage operation subsequent to a first storage operation contains references to data objects in the chunk folder created by the first storage operation instead of the data objects themselves.

Claims

1. A method of deduplicating data performed by one or more computing systems, each computing system having a processor and memory, the method comprising:

receiving an indication of a first storage operation;

creating a first directory associated with the first storage operation, wherein the first directory includes three files,

wherein the first file of the first directory stores data associated with the first storage operation, and wherein the data in the first file is de-duplicated,

wherein the second file of the first directory stores data associated with the first storage operation, and wherein the data in the second file is not de-duplicated,

wherein the third file of the first directory stores a first data structure that includes information identifying file locations of data within the first file corresponding to data in the second file, and

wherein the data stored in the first and second files of the first directory is not tracked by file systems of the one or more computing systems;

receiving a first set of multiple, discrete data objects associated with the first storage operation,

wherein each of the multiple data objects of the first set include a header portion and a payload portion;

determining, by the one or more computing systems, that the payload portion of a first data object of the first set has already been stored in the first file of the first directory, and

updating the first data structure to track the location of the payload portion of the first data object;

storing the header portion of the first data object in the second file of the first directory; and

determining, by the one or more computing systems, that the payload portion of a second data object of the first set has not already been stored in the first file of the first directory, and both

storing the payload portion of the second data object in the first file of the first directory and

updating the first data structure to track the location of the payload portion of the second data object; and

storing the header portion of the second data object in the second file of the first directory.

2. The method of claim 1, further comprising:

receiving an indication of a second storage operation;

creating a second directory associated with the second storage operation,

wherein the second directory includes three files,

wherein the first file of the second directory stores data associated with the second storage operation that is de-duplicated,

wherein the second file of the second directory stores data associated with the second storage operation that is not de-duplicated,

wherein the third file of the second directory stores a second data structure that includes information identifying locations of data in the second directory, and

wherein the data stored in the first and second files of the second directory is not tracked by file systems of the one or more computing systems;

receiving a second set of multiple data objects associated with the second storage operation, each of the multiple data objects of the second set including a header portion and a payload portion;

determining that the payload portion of a third data object of the second set has already been stored in the first file of the first directory or in the first file of the second directory and updating the second data structure to track the location of the payload portion of the third data object; and

determining that the payload portion of a fourth data object of the second set has not already been stored in the first file of the first directory or in the first file of the second directory and both storing the payload portion of the fourth data object in the first file of the second directory and updating the second data structure to track the location of the payload portion of the fourth data object.

3. The method of claim 1, further comprising:

determining that a size of the payload portion of a third data object of the first set does not exceed a threshold; and

storing the payload portion of the third data object in the second file of the first directory,

regardless of whether the payload portion of the third data object has already been stored in the second file of the first directory.

4. The method of claim 1, wherein the first file is configured as a sparse file.

5. The method of claim 1, wherein the first directory is located on one or more sequentially accessed media.

6. The method of claim 1, wherein the multiple data objects of the first set are blocks of data that comprise one or more files.

7. A computer-implemented method for copying multiple files to a secondary storage device, wherein the secondary storage device is coupled to a computer executing a file system, the method comprising:

receiving a copy operation request to copy n number of files to the secondary storage device,

wherein each of the n number of files includes metadata and data, and

wherein the n number of files exceeds a number of files that the file system can operate on without system degradation;

receiving by the computer the n number of files to copy; and

processing by the computer the n number of files by—

copying the metadata of each of the n number of files to a first file in a directory,

wherein the copying is performed without deduplicating the metadata, and

wherein the first file does not contain the data for the n number of files;

copying and deduplicating at least a portion of the data for the n number of files into a second file in the directory,

wherein the second file is separate from the first file, and

wherein the second file does not include the metadata for the n number of files; and

updating a data structure in the directory, wherein the data structure—

tracks, for each of the n number of files, a location of the metadata for that file in the first file, and

tracks, for the at least a portion of the data for the n number of files, a location of the data in the second file.

8. A method of single instancing a large number of data files during a single copy operation that is performed by one or more computing systems, each computing system including a processor and memory, the method comprising:

receiving multiple data files to be copied during a single copy operation;

removing user or access control metadata from at least some of the multiple data files;

for each of the multiple data files, determining if an instance of data in the data file has already been stored;

for each of the multiple data files, if an instance of the data in the data file has not already been stored, then storing the data in a single data file,

wherein the single data file includes the data for each of the multiple data files to be copied during the single copy operation, without duplicate instances for data in the multiple data files that have already been stored;

creating, by the one or more computing systems, an index file associated with the single data file, wherein the index file includes information identifying, for each of the multiple data files, a location of the data in the single data file;

for each of the multiple data files from which user or access control information was removed, storing the removed user or access control metadata in a one and the same user metadata file; and

storing in a single directory associated with the single copy operation, the single data file, the index file, and the user metadata file.

9. The method of claim 8, wherein the single copy operation is a regularly scheduled data archive or backup job, wherein the determining includes, for each of the multiple data files, generating a substantially unique identifier for the data in the data file, and comparing the substantially unique identifier to a stored table of substantially unique identifiers for previously stored data from previously copied data files.

10. The method of claim 8, further comprising:

before the determining, and for each of the multiple data files, determining if the data in the data file satisfies at least one criterion, and

wherein the criterion is whether the data in the data file exceeds a data size threshold.

11. The method of claim 8, further comprising:

at a second time that differs from the first time, at a later time, repeating the receiving, removing, determining, storing, and creating for new data files to be copied during another single copy operation, and storing another single data file with another metadata file in another directory at the later time and based on the repeated receiving, removing, determining, storing, and creating.

12. A method, performed by computing systems, of avoiding the storage of duplicate data, wherein each computing system includes a processor and memory, the method comprising:

receiving an indication to perform a storage operation;

receiving a set of data objects involved in the storage operation;

for each of the data objects in the set, by the one or more computing systems;

determining if the data object satisfies at least one criterion;

if the data object satisfies the at least one criterion, then;

generating an identifier for the data object;

determining, based on the identifier, if an instance of the data object has already been stored;

if an instance of the data object has already been stored, then;

determining the location of the instance of the data object; and

storing a reference to the location of the instance of the data object in a first file in a directory,

 

wherein the first file is configured to store multiple references, and

 

wherein each reference refers to a location of an instance of a data object; and

if an instance of the data object has not already been stored, then storing the data object in a second file in the directory,

wherein the second file is configured to store only a single instance of each data object; and

if the data object does not satisfy the at least one criterion, then storing the data object in a third file in the directory, wherein the third file is configured to store multiple instances of data objects.

13. The method of claim 12, wherein the data object has a type, and wherein determining if the data object satisfies at least one criterion includes determining whether the type of the data object is data.

14. The method of claim 12, wherein the data object has a size, and wherein determining if the data object satisfies at least one criterion includes determining whether the size of the data object exceeds a predetermined size.

15. The method of claim 12, wherein the data object has a size in kilobytes, and wherein determining if the data object satisfies at least one criterion includes determining whether the size of the data object exceeds 64 kilobytes.

16. The method of claim 12, wherein the directory is located on sequential media.

17. The method of claim 12, wherein the directory is a first directory, and wherein the method further comprises:

if an instance of the data object has already been stored, then;

determining the location of the instance of the data object includes determining that the instance of the data object has already been stored in a third file in a second directory, wherein the third file is configured to store only a single instance of each data object; and

storing a reference to the location of the instance of the data object includes storing a reference to the third file in the first file in the first directory.