BLOCK-LEVEL SINGLE INSTANCING

• US 20100299490A1
• Filed: 12/28/2009
• Published: 11/25/2010
• Est. Priority Date: 05/22/2009
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: Vijayan, Manoj K., Attarde, Deepak R., Kottomtharayil, Rajiv
• Granted Patent: US 8,578,120 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Described in detail herein are systems and methods for single instancing blocks of data in a data storage system. For example, the data storage system may include multiple computing devices (e.g., client computing devices) that store primary data. The data storage system may also include a secondary storage computing device, a single instance database, and one or more storage devices that store copies of the primary data (e.g., secondary copies, tertiary copies, etc.). The secondary storage computing device receives blocks of data from the computing devices and accesses the single instance database to determine whether the blocks of data are unique (meaning that no instances of the blocks of data are stored on the storage devices). If a block of data is unique, the single instance database stores it on a storage device. If not, the secondary storage computing device can avoid storing the block of data on the storage devices.

Claims

1. A computing system for reclaiming storage space on one or more storage devices having native file systems, wherein the storage space is utilized by one or more logical containers to store deduplicated blocks of data, wherein locations of the deduplicated blocks of data in the logical containers are not tracked by the native file systems of the storage devices, the computing system comprising:

one or more storage devices storing on physical media—

one or more logical containers that include multiple deduplicated blocks of data that correspond to data objects; and

one or more data structures that indicate whether the blocks of data are referred to;

one or more databases storing information indicating whether the blocks of data are referred to; and

a secondary storage computing device programmed to—

receive an indication to remove a first set of blocks of data from a first logical container;

for each of the blocks of data in the first set—

determine, from the databases, whether the block of data is referred to; and

if the block of data is not referred to, update the data structures to indicate that the block of data is not referred to;

determine from the data structures that a threshold number of contiguous blocks of data in the first logical container that are not referred to has been reached; and

make available for storage portions of the one or more physical media corresponding to the contiguous blocks of data in the first logical container,

wherein the data structures and the databases are not part of the native file systems of the storage devices

2. The computing system of claim 1, wherein the information stored by the databases includes, for a block of data, either a reference count of a number of references to the block of data, or information from which the reference count can be derived, and wherein the secondary storage computing device is further programmed to, for each of the blocks of data in the first set:

determine the reference count for the block of data; and

if the reference count of the block of data is zero, update the data structures to indicate that the block of data is not referred to.

3. The computing system of claim 1, wherein the secondary storage computing device is further programmed to:

either make available for storage an intermediate portion of the first logical container;

or

truncate the first logical container.

4. The computing system of claim 1, wherein the one or more logical containers correspond to one or more container files and the one or more data structures correspond to one or more index files.

5. The computing system of claim 1, wherein the secondary storage computing device is further programmed to:

make available for storage portions of the one or more physical media corresponding to the first set of blocks of data in the first logical container;

determine a first data object that is referred to by at least one of the blocks of data in the first set; and

update the databases to indicate that the first data object is not referred to by any of the blocks of data in the first set.

6. The computing system of claim 1, wherein the first set of blocks of data in the first logical container was created as a result of a first storage operation.

7. The computing system of claim 1, wherein the first set of blocks of data corresponds to a file.

8. A method of reclaiming storage space on one or more storage devices, wherein the storage space is utilized by one or more logical containers to store deduplicated blocks of data, and wherein the method is performed by a computing system having a processor and memory, the method comprising:

receiving an indication to remove a first data object, wherein the first data object is stored as multiple first blocks of data in at least a first logical container;

accessing, by the computing system, a first data structure that indicates whether the first data object is referred to;

determining that the first data object is not referred to;

determining from a second data structure that a first number of multiple contiguous second blocks of data in the first logical container that are not referred to has been reached; and

after determining that the first number has been reached, specifying as available for storage a portion of the first logical container corresponding to the multiple contiguous second blocks of data.

9. The method of claim 8, wherein the storage devices have native file systems, wherein locations of the deduplicated blocks of data in the logical containers are not tracked by the native file systems of the storage devices, and wherein the first and second data structures are not part of the native file systems of the storage devices.

10. The method of claim 8, wherein the first data structure includes, for each of the multiple first blocks of data, either a reference count of a number of references to each block of data, or information from which the reference count can be derived, and wherein the method further comprises, for each block of data of the multiple first blocks of data:

determining the reference count for the block of data; and

if the reference count of the block of data is zero, updating the second data structure to indicate that the block of data is not referred to.

11. The method of claim 8, wherein specifying as available for storage a portion of the first logical container corresponding to the multiple contiguous second blocks of data includes either specifying as available for storage an intermediate portion of the first logical container or truncating the first logical container.

12. The method of claim 8, further comprising storing an indication in the second data structure that the multiple first blocks of data are not referred to.

13. The method of claim 8, wherein the contiguous multiple second blocks of data include at least one of the multiple first blocks of data.

14. The method of claim 8, wherein specifying as available for storage a portion of the first logical container corresponding to the multiple contiguous second blocks of data includes removing the multiple first blocks of data from the first logical container, and wherein the method further comprises:

determining a second data object that is referred to by at least one of the multiple first blocks of data; and

updating the first data structure to indicate that the second data object is not referred to by any of the multiple first blocks of data.

15. The method of claim 8, wherein the first data object was created as a result of a first data storage operation.

16. The method of claim 8, wherein the first data object corresponds to a first file.

17. A computing system for reclaiming storage space on one or more means for storing, wherein the storage space is utilized by one or more logical containers to store deduplicated blocks of data, the computing system comprising:

means for storing—

one or more logical containers that include multiple deduplicated blocks of data that correspond to data objects;

one or more first data structures that indicate whether the blocks of data are referred to by other data objects; and

one or more second data structures that indicate whether the blocks of data are referred to by other data objects;

means for receiving an indication to remove a first set of blocks of data from a first logical container;

means for determining whether a block of data is referred to, for each of the blocks of data in the first set;

means for updating the second data structures to indicate that a block of data is not referred to, for each of the blocks of data in the first set that is not referred to;

means for determining from the second data structures that a first number of contiguous blocks of data in the first logical container that are not referred to has been reached; and

means for specifying as available for storage portions of the one or more physical media corresponding to the contiguous blocks of data in the first logical container.

18. The computing system of claim 17, wherein the means for storing has a native file system, wherein locations of the deduplicated blocks of data in the logical containers are not tracked by the native file system of the means for storing, and wherein the first and second data structures do not form part of the native file system of the means for storing.

19. The computing system of claim 17, wherein:

the one or more first data structures include either a reference count of a number of references to a given block of data, or information from which the reference count can be derived,

the means for determining whether a block of data is referred to includes means for determining a reference count for the block of data, and

the means for updating the second data structures updates the second data structures if the reference count for the block of data is zero.

20. The computing system of claim 17, wherein the means for specifying as available for storage portions of the one or more physical media includes:

means for specifying as available for storage portions of the one or more physical media corresponding to the contiguous blocks of data located at an intermediate portion of the first logical container; and

means for specifying as available for storage portions of the one or more physical media corresponding to the contiguous blocks of data located at an extremity of the first logical container.

21. The computing system of claim 17, wherein the first set of blocks of data was created as a result of a first storage operation.

22. The computer system of claim 17, wherein the first set of blocks of data corresponds to a first file.

23. A system for storing a single instance of a block of data in a data storage network, wherein the data storage network includes multiple storage devices coupled via a computer network, and wherein the computer network also couples to one or more computing devices having file systems on which files are stored, the system comprising:

one or more storage devices storing multiple blocks of data in one or more container files, wherein a file stored on a file system of a computing device is comprised in one or more blocks of data;

one or more single instance databases storing, for at least some of the multiple blocks of data, an identifier of the block of data and a location of the block of data in a container file; and

a secondary storage computing device configured to—

receive data corresponding to one or more data storage jobs from the one or more computing devices, wherein a data storage job is performed on one or more files stored on the file systems of the one or more computing devices, and wherein the received data includes—

multiple blocks of data indicated to be eligible for single instancing; and

multiple items of data not indicated to be eligible for single instancing;

for at least some of the multiple blocks of data indicated to be eligible for single instancing—

determine an identifier of the block of data;

determine if the single instance database already stores the identifier;

when the single instance database already stores the identifier, determine a location of the corresponding block of data in a container file and store a reference to the location; and

when the single instance database does not already store the identifier, store the block of data in a container file;

for at least some of the multiple items of data not indicated to be eligible for single instancing, store the items of data in a metadata file; and

maintain an index file that indicates whether the multiple blocks of data in the one or more container files are referred to.

24. The system of claim 23, wherein the secondary storage computing device receives the data corresponding to the one or more data storage jobs from the one or more computing devices in one or more data streams, and wherein a data stream includes:

multiple stream data items, wherein the multiple stream data items include multiple blocks of data indicated to be eligible for single instancing and multiple items of data not indicated to be eligible for single instancing;

multiple stream header items, each stream header item containing metadata describing an associated stream data item, the metadata including an indication of whether the stream data item includes data indicated to be eligible for single instancing; and

multiple identifiers of the multiple blocks of data indicated to be eligible for single instancing.

25. The system of claim 23, further comprising the one or more computing devices, wherein the one or more computing devices are configured to:

access files on which the one or more data storage jobs are performed;

determine a first set of files that are not eligible for single instancing and a second set of files that are eligible for single instancing, wherein the first set of files includes multiple items of data, and wherein the second set of files are comprised in multiple blocks of data;

for at least some of the multiple blocks of data—

generate the identifier for the block of data; and

associate the identifier with the block of data; and

provide the first and second sets of files to the secondary storage computing device.

26-32. -32. (canceled)

33. A method of single instancing multiple blocks of data, wherein the method is performed by a first computing device having a processor and memory, the method comprising:

for at least some of multiple blocks of data indicated to be eligible for single instancing included in data received from a set of one or more computing devices distinct from the first computing device, wherein the one or more computing devices have file systems storing files that comprise one or more blocks of data—

determining an identifier of the block of data;

accessing, by the first computing device, a data structure that stores, for a set of blocks of data stored in one or more logical containers on one or more storage devices, an identifier of the block of data and a location of the block of data in a logical container;

determining, based upon the identifier of the block of data and access to the data structure, if the block of data should be stored;

when the block of data should not be stored, determining a location of an already stored instance of the block of data in a logical container and storing a reference to the location; and

when the block of data should be stored, storing the block of data in a logical container; and

maintaining a block reference data structure that indicates whether blocks of data in the one or more logical containers are referred to.

34. The method of claim 33, wherein the received data includes multiple items of data not indicated to be eligible for single instancing, and wherein the method further comprises, for at least some of the multiple items of data not indicated to be eligible for single instancing, storing the items of data in a metadata logical container.

35. The method of claim 33, wherein the data includes the identifiers for at least some of the multiple blocks of data indicated to be eligible for single instancing.

36-47. -47. (canceled)