Block-level single instancing

Patent metadata

Field	Value
Publication number	US-11455212-B2
Application number	US-202117169257-A
Country	US
Kind code	B2
Filing date	Feb 5, 2021
Priority date	May 22, 2009
Publication date	Sep 27, 2022
Grant date	Sep 27, 2022

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.

First claim

We claim:

1. A system for storing a single instance of a data block in a data storage network, the system comprising:
one or more computing devices, the one or more computing devices configured to:
access files on which one or more data storage jobs are performed;
determine a first set of one or more files that are not eligible for single instancing and a second set of one or more files that are eligible for single instancing, wherein the first and second set of one or more files are determined according to one or more parameters provided in an information management policy associated with the one or more computing devices;
divide the first and second set of one or more files into multiple data blocks; and
provide the multiple data blocks to a secondary storage computing device; and

the secondary storage computing device configured to:
receive the multiple data blocks from the one or more computing devices in one or more data streams,
wherein the one or more data streams comprises multiple stream header items, wherein each stream header item containing an indication of whether associated data block is eligible for single instancing.

2. The system of claim 1 , wherein the secondary storage computing device comprises one or more memory buffers,
wherein each of the one or more memory buffers has a size that is greater than a size of a data block but is less than ten times the size of the data block, and
wherein the secondary storage computing device is further configured to store multiple data blocks indicated to be eligible for single instancing in the one or more memory buffers.

3. The system of claim 1 , wherein the secondary storage computing device is further configured to, for at least some of the multiple data blocks indicated to be eligible for single instancing, generate a unique identifier for each data block.

4. The system of claim 1 , wherein the indication is a single flag.

5. The system of claim 1 , further comprising:
one or more storage devices storing multiple data blocks in one or more container files;
one or more single instance databases storing, for at least some of the multiple data blocks,
an identifier of a stored data block, and
a location of the stored data block in a container file; and

one or more index files storing, for at least some of the multiple data blocks, an indication whether the stored data block is referred to in one or more metadata files on the one or more storage devices.

6. The system of claim 5 , wherein the secondary storage computing device is further configured to:
receive an indication to delete one or more data blocks stored in the one or more container files; and
for at least some of the one or more data blocks indicated to be deleted:
determine a reference count of the data block; and
when the reference count of the data block is zero, update one or more index files to indicate that the data block is not referred to; and
when a threshold number of contiguous data blocks in a container file that are not referred to is reached, make available for storage portions of one or more physical media corresponding to the threshold number of contiguous data blocks.

7. The system of claim 5 , wherein the one or more single instance databases maintain:
a data structure storing, for at least some of the multiple data blocks, a location of a reference to the data block.

8. The system of claim 1 , wherein the secondary storage computing device is further configured to:
determine if a container file contains any referenced data blocks; and
when the container file does not contain any referenced data blocks, delete the container file.

9. The system of claim 1 , wherein a file is determined to be eligible for single instancing when the file is a system file, an application file, or a user file.

10. The system of claim 1 , wherein a file is determined to be ineligible for single instancing when the file comprises metadata.

11. The system of claim 10 , wherein the metadata is one of:
access control lists (ACLs),
disk partition information,
Master File Table (MFT), and
File Allocation Table (FAT) information.

12. A method for storing a single instance of a data block in a data storage network, the method comprising:
accessing files on which one or more data storage jobs are performed;
determining a first set of one or more files that are not eligible for single instancing and a second set of one or more files that are eligible for single instancing, wherein the first and second set of one or more files are determined according to one or more parameters provided in an information management policy assigned to a storage device storing the files;
dividing the first and second set of one or more files into multiple data blocks; and
providing the multiple data blocks to a secondary storage computing device in one or more data streams,
wherein the one or more data streams comprises multiple stream header items, wherein each stream header item containing an indication of whether associated data block is eligible for single instancing.

13. The method of claim 12 , wherein the method further comprises generating a unique identifier for each data block.

14. The method of claim 12 , wherein the method further comprises:
receiving an indication to delete one or more data blocks stored in a secondary storage device; and
for at least some of the one or more data blocks indicated to be deleted:
determine a reference count of the data block; and
when the reference count of the data block is zero, update one or more index files to indicate that the data block is not referred to; and
when a threshold number of contiguous data blocks in a container file that are not referred to is reached, make available for storage portions of one or more physical media corresponding to the threshold number of contiguous data blocks.

15. The method of claim 14 , wherein the method further comprises:
determining if a container file contains any referenced data blocks; and
when the container file does not contain any referenced data blocks, deleting the container file.

16. The method of claim 12 , wherein a file is determined to be eligible for single instancing when the file is a system file, an application file, or a user file.

17. The method of claim 12 , wherein a file is determined to be ineligible for single instancing when the file comprises metadata.

18. A system for storing a single instance of a data block in a data storage network, the system comprising:
one or more computing devices, one or more computing devices configured to:
access files on which one or more data storage jobs are performed;
determine a first set of one or more files that are not eligible for single instancing and a second set of one or more files that are eligible for single instancing, wherein the first and second set of one or more files are determined according to one or more parameters provided in an information management policy associated with the one or more computing devices;
divide the first and second set of one or more files into multiple data blocks; and
provide the multiple data blocks to a secondary storage computing device in one or more data streams,
wherein the one or more data streams comprises multiple stream header items, wherein each stream header item containing an indication of whether associated data block is eligible for single instancing.

Assignees

• Commvault Systems Inc

Inventors

• Attarde Deepak Raghunath
• Kottomtharayil Rajiv
• Vijayan Manoj Kumar

Classifications

• G06F11/1469

  Backup restoration techniques · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F16/1752

  based on file chunks · CPC title

• G06F11/1464

  for networked environments · CPC title

• G06F3/064

  Management of blocks · CPC title