SYSTEM AND METHOD FOR STORING REDUNDANT INFORMATION

• US 20140233366A1
• Filed: 04/28/2014
• Published: 08/21/2014
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Prahlad, Anand, Gokhale, Parag, Kottomtharayil, Rajiv, Vijayan, Manoj Kumar, Attarde, Deepak Raghunath
• Granted Patent: US 9,236,079 B2
• Time in Patent Office: Days
• US Class Current: 369/85
• 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 of storing a single-instance copy on a sequential storage medium such as magnetic tape, wherein the single instance copy is created from copies of original data objects, the method comprising:

receiving or accessing multiple data objects from a computer network,

wherein some of the multiple data objects are substantially identical;

storing, on a random-access storage medium, a single-instance copy of the multiple data objects,

wherein the single-instance copy contains a copy of one of the substantially identical data objects and not copies of the remaining substantially identical data objects, and

wherein the random-access storage medium includes at least one reference to the copy of one of the substantially identical data objects; and

providing for storage, on a sequential storage medium, the copy of one of the substantially identical data objects, and the at least one reference to the copy of the substantially identical data objects, in that order.

2. The method of claim 1,

wherein the receiving includes receiving multiple data objects from multiple, different logical locations within a computer network,

wherein the single-instance copy contains information identifying the logical locations, and

wherein the providing includes providing for storage the information identifying the logical locations.

3. The method of claim 1,

wherein the storing includes storing a reference count to track a number of references that refer to the copy of one of the substantially identical data objects, and

wherein the providing includes providing for storage the reference count.

4. The method of claim 1, wherein a reference to the copy of one of the substantially identical data objects comprises a media identifier identifying a storage medium on which the copy is stored and an offset within the identified storage medium to the copy.

5. The method of claim 1, further comprising

maintaining an index on the random-access storage medium,

wherein the index comprises, for each of the multiple data objects,

(1) an identifier of the data object,

(2) information indicating whether the data object is stored as a copy or a reference to a copy, and

(3) an identifier of a source copy when the data object is stored as a reference to the source copy.

6. The method of claim 5, wherein the providing for storage is performed based on the index.

7. The method of claim 5,

wherein the receiving includes receiving multiple data objects from multiple, different logical locations within a computer network, and

wherein the single-instance copy contains information identifying the logical locations,

further comprising storing the index before storing information describing the logical locations on the sequential storage medium.

8. A method performed by a computer system of storing a single-instance copy on a sequential storage medium, comprising:

receiving one or more data objects in a hierarchy,

wherein some of the data objects are identical;

storing, on a random-access storage medium, a single-instance copy of the one or more data objects,

wherein the single-instance copy contains information describing—

a first instance of each of the one or more data objects, and

one or more references to the one or more first instances as stored on the random-access storage medium; and

after storing the single-instance copy of the one or more data objects on the random-access storage medium, then storing, on a sequential storage medium, the information describing the hierarchy, the one or more first instances, and the one or more references to the first instances as stored on the sequential storage medium, in that order.

9. A computer system for restoring data from sequential storage medium, wherein the data has been deduplicated, the system comprising:

at least one processor;

at least one data storage device coupled to the at least one processor;

a receiving unit configured to receive a request to restore at least first and second different data objects from a deduplicated copy of the first and second data objects,

wherein the deduplicated copy of the first and second data objects is stored on a sequential storage medium,

wherein the first and second data objects, prior to deduplication and storage on the sequential storage medium, included multiple, identical copies of the first and second data objects, respectively, and

wherein the deduplicated copy contains one instance, stored on the sequential storage medium, the first and second data objects, and information describing one or more references to the one instance of the first and second data objects;

an identifying unit, in response to the received request, configured to—

when a requested first or second data object is stored as an instance, identify a location on the sequential storage medium of the instance of the respective first or second data objects, and

when a requested first or second data object is stored as a reference to an instance, identify a location on the sequential storage medium of the instance of the respective first or second data objects, and

configured to sort the identified locations; and

a restoring unit configured to restore the requested data objects to a random-access storage medium from the sorted locations on the sequential storage medium.

10. The computer system of claim 9, further comprising

a retrieving unit configured to retrieve an index from the sequential storage medium, wherein the index comprises, for each of the first and second data objects:

(1) an identifier of the first or second data object,

(2) information indicating whether the first or second data object is stored as an instance or a reference in the deduplicated copy,

(3) when the first or second data object is stored as a reference, an identifier of a source first or second data object for the reference, respectively, and

(4) a storage location on the sequential storage medium when the first or second data object is stored as an instance.

11. The computer system of claim 10, wherein the identifying unit identifies the locations for the requested first or second data objects from the index, without accessing the references.

12. The computer system of claim 9, wherein the identifying unit is further configured to:

copy a chunk of data on the sequential storage medium corresponding to the requested first or second data object to a random access storage medium,

determine whether the chunk of data contains an instance of the first or second data object or a reference to an instance, and

when the chunk of data contains a reference to an instance, retrieve the instance from the sequential storage medium using the reference.

13. The computer system of claim 9, wherein the information describing a reference to an instance comprises a media identifier identifying a storage medium on which the instance is stored and an offset within the identified storage medium to the instance.

14. The computer system of claim 9, further comprising

a retrieving unit configured to retrieve the information describing an original location of each first or second data object,

wherein the restoring unit is further configured to restore the first or second data objects in accordance with the retrieved information.

15. A computer system for restoring data from a single-instance copy on a sequential storage medium, comprising:

a receiving unit configured to receive a request to restore one or more data objects from a single-instance copy of the data objects on a sequential storage medium,

wherein some of data objects are ore were identical, and

wherein the single-instance copy contains information describing a first instance of each of the one or more data objects, and one or more references to the first instances as stored on the sequential storage medium;

an identifying unit configured to, for each of the one or more data objects—

identify the storage location of the instance when the data object is stored as an instance in the single-instance copy, and

identify the storage location of the first instance when the data object is stored as a reference to a first instance in the single-instance copy; and

a restoring unit configured to restore the one or more data objects on a random-access storage medium in an order of the identified storage locations on the sequential storage medium.

16. A non-transitory computer-readable medium containing instructions for controlling a computer system to execute a method of copying a deduplicated copy of data from a sequential storage medium to a random-access storage medium, the method comprising:

receiving a request to recreate on a random-access storage medium a deduplicated copy of data objects from a sequential medium,

wherein the deduplicated copy contains information describing a first instance of each of the data objects, and one or more references to the first instances as stored on the sequential storage medium;

recreating at least a portion of the deduplicated copy on the random-access storage medium,

wherein the references in the recreated copy refer to first instances as stored on the random-access storage medium;

receiving a request to restore one of the data objects from the deduplicated copy on the random-access medium to a destination location;

determining whether the data object is stored as an instance or a reference in the deduplicated copy on the random-access storage medium; and

when the data object is stored as an instance, storing the instance in the destination location, but when the data object is stored as a reference to a first instance, storing, if necessary, the first instance in the destination location.

17. The non-transitory computer-readable medium of claim 16, wherein a reference to a first instance comprises a media identifier identifying a storage medium on which the first instance is stored and an offset within the storage medium to the first instance.

18. The non-transitory computer-readable medium of claim 16, wherein the method further comprises:

copying an index from the sequential storage medium to the random-access storage medium,

wherein the index comprises, for each of the data objects,

(1) an identifier of the data object, and

(2) information indicating whether the data object is stored as an instance or a reference in the deduplicated copy.

19. The non-transitory computer-readable medium of claim 18, wherein the determining step is performed based on the copied index.