System and method for storing redundant information

• US 7,840,537 B2
• Filed: 12/21/2007
• Issued: 11/23/2010
• Est. Priority Date: 12/22/2006
• Status: Expired due to Fees

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Gokhale, Parag, Kottomtharayil, Rajiv
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Allen; Nicholas E
• Application Number:
  US11/963,623
• Publication Number:
  US 20080243879A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707/652
• US Class Current: 707/652
• 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 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G11B 5/86 Re-recording, i.e. transcribing information from one magnetisable record carrier on to one or more similar or dissimilar record carriers by varying the order of the information G11B27/029, G11B27/036

Abstract

A method and system for reducing storage requirements and speeding up storage operations by reducing the storage of redundant data includes receiving a request that identifies one or more data objects to which to apply a storage operation. For each data object, the storage system determines if the data object contains data that matches another data object to which the storage operation was previously applied. If the data objects do not match, then the storage system performs the storage operation in a usual manner. However, if the data objects do match, then the storage system may avoid performing the storage operation.

Claims

1. A method performed by a computer system for storing data objects to sequential media, wherein the computer system includes a processor and memory, the method comprising:

receiving a set of data objects from multiple computing systems, wherein the set of data objects includes at least two similar data objects;

for at least some of the data objects in the set

determining if a copy of a data object is already stored on random-access media, wherein the determining includes accessing an index that contains, for data objects already stored on the random-access media

an identifier of the data object; and

a location of the data object on the random-access media,

wherein the index is stored on the random-access media;

if the data object is already stored on the random-access media, then identifying a location of the data object on the random-access media and storing on the random-access media a reference to the identified location;

if the data object is not already stored on the random-access media, then storing the data object on the random-access media;

receiving a request to copy the data objects and the references stored on the random-access media to sequential media; and

copying to the sequential media, by the computer system, the data objects and reference data related to the references from the random-access media,

wherein the reference data on the sequential media refer to locations of the data objects on the sequential media.

2. The method of claim 1 wherein the determining comprises:

computing a hash value of the data object; and

comparing the computed hash value to another hash value of a data object previously stored by the system.

3. The method of claim 1 wherein the location associated with the sequential media is a tape that is part of a tape library that includes the destination location.

4. The method of claim 1 wherein storing a reference comprises storing index information containing at least a hash value of the data and a reference count indicating the number of references to the data.

5. The method of claim 1 wherein the reference comprises an address that points to the location different from the source location where the data object is already stored.

6. The method of claim 1 wherein the source location comprises a disk of a client computer system and the destination location comprises a tape library associated with a storage server.

7. The method of claim 1 wherein the source location is a first non-production copy of the data object and the destination location is a secondary non-production copy of the data object.

8. The method of claim 1 wherein the source location is backup data containing multiple instances of the data object.

9. A system for reducing redundant copies of files in a storage environment having sequential media, the system comprising:

a storage operation request component configured to receive requests to perform storage operations on files received from multiple computing systems, wherein files are stored on random-access media;

a digest generation component configured to compute a digest that provides summary of a file that distinguishes it from other files referred to by storage operation requests;

a digest comparison component configured to compare computed digests with previously stored digests to determine if a copy of a file already exists,

wherein the comparing includes accessing an index that contains, for files already stored on the random-access media

the digest of the file; and

a location of the file on the random-access media,

wherein the index is stored on the random-access media, and

when the file is not already stored on the random-access media, then storing the file on the random-access media;

when the file is already stored on the random-access media, then identifying a location of the data object on the random-access media and storing on the random-access media a reference to the identified location; and

a single instance data store configured to store computed digests and files on sequential media such that only one instance of the same file is stored in a set of sequential media that contains multiple references to the same file,

wherein the single instance data store receives a request to copy files and references stored on the random-access media to the sequential media, and

copies to the sequential media files and reference data related to the references from the random-access media,

wherein the reference data on the sequential media refer to locations of the files on the sequential media.

10. The system of claim 9 wherein the storage operation request component comprises a media agent component that stores an index of each of the files and computed digests associated with requests received by the storage operation request component.

11. The system of claim 9 wherein the digest generation computes digests using an MD5 hash algorithm.

12. The system of claim 9 wherein the digest comparison component compares the digest of a file being copied with a digest stored in the single instance data store.

13. The system of claim 9 wherein the single instance data store contains a reference count for each file indicating how many different locations tracked by the single instance data store refer to the file.

14. A non-transitory computer-readable medium containing instructions for controlling a computer system to recover data, wherein the computer system includes a processor and memory, by a method comprising:

retrieving a backup object identifying a data object,

wherein the backup object includes at least one sequential data storage medium, and,

wherein the at least one sequential data storage medium includes a data structure containing header information identifying whether the backup object contains the data object or contains a reference to the data object, and;

determining whether the backup object contains the reference to the data object or contains the data object itself based on the data structure of the at least one sequential data storage medium;

when the backup object refers to the data object stored in a location outside of the at least one sequential data storage medium, then locating the data object at the location outside of the at least one sequential data storage medium and copying the data object to a recovery location,

wherein the recovery location includes random-access data storage media; and

when the backup object contains the data object, copying the data object from the at least one sequential data storage medium to the recovery location,

wherein a first instance of each data object is stored as a of the data object and each additional instance is stored as a reference to the copy of the data object,

wherein the reference is stored on the at least one sequential data storage medium in the data structure, and,

wherein the reference refers to the location on the at least one sequential data storage medium where the copy of the data object is stored.

15. The computer-readable medium of claim 14 wherein copying the data object to the recovery location comprises first copying the data object to an intermediate restored file cache, wherein the restored file cache contains a copy of the data object with any references to other data objects resolved.

16. The computer-readable medium of claim 14 wherein retrieving a backup object comprises retrieving a magnetic tape, and wherein the data structure contains information for building an index of each of the copies of the data objects and references to references to copies of the data objects maintained by the computer system.