SYSTEM AND METHOD FOR STORING REDUNDANT INFORMATION

• US 20160124658A1
• Filed: 01/11/2016
• Published: 05/05/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
• Granted Patent: US 10,061,535 B2
• Time in Patent Office: Days
• 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 method performed by a computer system of storing a single-instance copy on a sequential storage medium, 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 according to a hashing algorithm;

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 only one of the substantially identical data objects; and

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

storing the copy of the only one of the substantially identical data objects on a sequential storage medium; and

storing the at least one reference to the copy of the substantially identical data objects after storing the copy of the only one of the substantially identical data objects on the sequential storage medium.

2. The method of claim 1,

wherein receiving or accessing multiple data objects from a computer network includes receiving or accessing 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 storing the at least one reference to the copy of the substantially identical data objects after storing the copy of the only one of the substantially identical data objects on the sequential storage medium includes storing the information identifying the logical locations.

3. The method of claim 1,

wherein storing the at least one reference to the copy of the substantially identical data objects after storing the copy of the only one of the substantially identical data objects on the sequential storage medium includes storing a reference count to track a number of references that refer to the copy of one of the substantially identical data objects.

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:

an identifier of the data object, information indicating whether the data object is stored as a copy or a reference to a copy, and an identifier of a source copy when the data object is stored as a reference to the source copy.

6. The method of claim 1, wherein storing, on the random-access storage medium, the single-instance copy of the multiple data objects includes storing the single-instance copy of the multiple data objects using an index that comprises, for each of the multiple data objects:

an identifier of the data object, information indicating whether the data object is stored as a copy or a reference to a copy, and an identifier of a source copy when the data object is stored as a reference to the source copy.

7. The method of claim 1, wherein receiving or accessing multiple data objects from a computer network 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, before storing the information identifying the logical locations on the sequential storage medium, an index that comprises, for each of the multiple data objects;

an identifier of the data object, information indicating whether the data object is stored as a copy or a reference to a copy, and an identifier of a source copy when the data object is stored as a reference to the source copy.

8. The method of claim 1, wherein at least some of the multiple data objects are of different types or formats, and wherein the different types or formats correspond to documents, email messages, and configuration settings.

9. A method performed by a computer system of storing a de-duplicated copy of data objects on a sequential storage medium, comprising:

receiving one or more data objects in a hierarchy,

wherein some of the data objects are identified as identical based on hashing;

storing, on a random-access storage medium, a de-duplicated copy of the one or more data objects, wherein the de-duplicated 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

storing the de-duplicated copy of the one or more data objects on the random-access storage medium, 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.

10. The method of claim 9, wherein the data objects are of at least two different object types, and wherein the different types or formats correspond to documents, email messages, or configuration settings.

11. The method of claim 9, wherein at least one of the data objects has an archive file format.

12. A non-transitory computer-readable medium containing instructions for controlling a computer system to execute a method of storing a copy on a sequential storage medium, the method comprising:

receiving or accessing multiple data objects from a computer network;

wherein some of the multiple data objects are identified as identical based on hashing;

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

wherein the copy contains a copy of only one of the identified as identical data objects; and

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

storing the copy of the only one of the identified as identical data objects on a sequential storage medium; and

storing the at least one reference to the copy of the identified as identical data objects after storing the copy of the only one of the identified as identical data objects on the sequential storage medium.

13. The non-transitory computer-readable medium of claim 12,

wherein receiving or accessing multiple data objects from a computer network includes receiving or accessing 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 storing the at least one reference to the copy of the identified as identical data objects after storing the copy of the only one of the identified as identical data objects on the sequential storage medium includes storing the information identifying the logical locations.

14. The non-transitory computer-readable medium of claim 12,

wherein storing the at least one reference to the copy of the identified as identical data objects after storing the copy of the only one of the identified as identical data objects on the sequential storage medium includes storing a reference count to track a number of references that refer to the copy of one of the identified as identical data objects.

15. The non-transitory computer-readable medium of claim 12, wherein a reference to the copy of one of the identified as 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.

16. The non-transitory computer-readable medium of claim 12, further comprising

maintaining an index on the random-access storage medium, wherein the index comprises, for each of the multiple data objects:

an identifier of the data object, information indicating whether the data object is stored as a copy or a reference to a copy, and an identifier of a source copy when the data object is stored as a reference to the source copy.

17. The non-transitory computer-readable medium of claim 12, wherein storing, on the random-access storage medium, the single-instance copy of the multiple data objects includes storing the single-instance copy of the multiple data objects using an index that comprises, for each of the multiple data objects:

an identifier of the data object, information indicating whether the data object is stored as a copy or a reference to a copy, and an identifier of a source copy when the data object is stored as a reference to the source copy.

18. The non-transitory computer-readable medium of claim 12, wherein receiving or accessing multiple data objects from a computer network 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, before storing the information identifying the logical locations on the sequential storage medium, an index that comprises, for each of the multiple data objects;

an identifier of the data object, information indicating whether the data object is stored as a copy or a reference to a copy, and an identifier of a source copy when the data object is stored as a reference to the source copy.

19. The non-transitory computer-readable medium of claim 12, wherein at least some of the multiple data objects are of different types or formats, and wherein the different types or formats correspond to documents, email messages, and configuration settings.