System and method for storing redundant information

• US 9,236,079 B2
• Filed: 04/28/2014
• Issued: 01/12/2016
• 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
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US14/262,878
• Publication Number:
  US 20140233366A1
• Time in Patent Office: 624 Days
• Field of Search: 707/652
• US Class Current: 1/1
• 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 computer system for restoring data from a 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, had multiple, identical instances, and

wherein the deduplicated copy contains one instance, stored on the sequential storage medium, of 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.

2. The computer system of claim 1, 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.

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

4. The computer system of claim 1, further comprising a recovering unit 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.

5. The computer system of claim 1, 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.

6. The computer system of claim 1, 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.

7. 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 the data objects are or 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.

8. 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 for data restoration, the method comprising:

receiving a request to restore data objects from a deduplicated copy of data objects stored on a sequential storage 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;

in response to the request, 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 to a destination location;

determining whether the data object to be restored 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.

9. The non-transitory computer-readable medium of claim 8, 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, and wherein at least some of the data objects are of different data types or formats.

10. The non-transitory computer-readable medium of claim 8, 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.

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

12. A method for copying a deduplicated copy of data from a sequential storage medium to a random-access storage medium for data restoration, the method comprising:

receiving a request to restore data objects from a deduplicated copy of data objects stored on a sequential storage 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;

in response to the request, 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 to a destination location;

determining whether the data object to be restored 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.

13. The method of claim 12, 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, and wherein at least some of the data objects are of different data types or formats.

14. The method of claim 12, further comprising:

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.

15. The method of claim 14, wherein the determining step is performed based on the copied index.