Multitier deduplication systems and methods

• US 8,898,114 B1
• Filed: 08/25/2011
• Issued: 11/25/2014
• Est. Priority Date: 08/27/2010
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Dell Software, Inc. (Dell Technologies Inc.)
• Inventors: Feathergill, David Allen, Mattox, Jason
• Primary Examiner(s): REYES, MARIELA D
• Application Number:
  US13/218,362
• Time in Patent Office: 1,188 Days
• Field of Search: 707/648, 707/653
• US Class Current: 707/648
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 2201/83 the solution involving signatures

Abstract

Multitier deduplication can reduce the amount of bandwidth and storage resources used during deduplication. In certain embodiments, the system can determine if a data block is stored in a first archive data storage. If so, the system can skip the data block. If not, the system can determine if the data block is stored or identified in a second archive data storage. In various implementations, the first archive data storage can be local to the system and the second archive data storage can be a global archive that may be remote from the system. The system can create a map of a plurality of backups stored at the first archive enabling the system to quickly check multiple archives. The multitier data deduplication can filter out inactive data blocks during or before performing the deduplication process.

Claims

1. A system for deduplicating a backup archive, the system comprising:

a computer system comprising computer hardware, the computer system programmed to implement;

a deduplication module configured to;

access one or more block directories associated with one or more backup archives at an archive data store, wherein the one or more block directories include fingerprints of data blocks associated with the one or more backup archives, and wherein at least one of the one or more backup archives is associated with a data store;

create a composite block map based at least in part on the one or more block directories, wherein the composite block map includes fingerprints of each data block stored at the archive data store; and

access one or more data blocks from the data store and for each of the one or more data blocks, the deduplication module is further configured to;

create a fingerprint for the data block;

determine whether the fingerprint exists in the composite block map of the archive data store;

in response to determining that the fingerprint does not exist in the composite block map, determine whether the fingerprint exists in a global deduplication data store, wherein the global deduplication data store is separate from the archive data store and the composite block map; and

in response to determining that the fingerprint does not exist in the global deduplication data store, identify the data block for backup storage; and

a backup module configured to;

backup each of the data blocks identified for backup storage as a target archive at the archive data store; and

store the fingerprint associated with each of the data blocks identified for backup storage at a target block directory associated with the target archive.

2. The system of claim 1, wherein the fingerprint includes one or more of a checksum and a hash.

3. The system of claim 1, wherein the one or more backup archives or the target archive include one or more of a full archive, an incremental archive, and a differential archive.

4. The system of claim 1, wherein the deduplication module is further configured to:

create a map of the active and the inactive data blocks of the one or more data blocks from the data store; and

access the data blocks identified as active in the map and to not access the data blocks identified as inactive in the map.

5. The system of claim 1, wherein at least one of the one or more data blocks is associated with a virtual machine file.

6. The system of claim 1, in response to determining that the fingerprint exists in the composite block map, the deduplication module is further configured to update the target block directory to point to the location of the block associated with the fingerprint at the archive data store.

7. The system of claim 1, in response to determining that the fingerprint exists in the global deduplication data store, the deduplication module is further configured to update the target block directory to point to the location of the block associated with the fingerprint at the global deduplication data store.

8. The system of claim 1, wherein the backup module is further configured to:

remove each data block from the target archive not identified for backup storage by the deduplication module, and

remove each fingerprint from the target block directory associated with each removed data block.

9. A method of deduplicating a backup archive, the method comprising:

by a computer system comprising computer hardware;

accessing one or more block directories associated with one or more archives at an archive data store, wherein the one or more block directories include fingerprints of data blocks associated with the one or more archives, and wherein at least one of the one or more archives is associated with a data store;

creating a composite block map based at least in part on the one or more block directories, wherein the composite block map includes fingerprints of each data block stored at the archive data store; and

accessing one or more data blocks from the data store and for each of the one or more data blocks;

creating a fingerprint for the data block;

determining whether the fingerprint exists in the composite block map of the archive data store;

in response to determining that the fingerprint does not exist in the composite block map, determining whether the fingerprint exists in a global deduplication data store, wherein the global deduplication data store is separate from the archive data store and the composite block map;

in response to determining that the fingerprint does not exist in the global deduplication data store, backing up the data block as part of a target archive at the archive data store; and

storing the fingerprint associated with the data block storage at a target block directory associated with the target archive.

10. The method of claim 9, further comprising:

creating a map of the active and the inactive data blocks of the one or more data blocks from the data store, and

accessing the data blocks identified as active in the map while not accessing the data blocks identified as inactive in the map.

11. The method of claim 9, wherein in response to determining that the fingerprint exists in the composite block map, the method further comprises updating the target block directory to point to the location of the block associated with the fingerprint at the archive data store.

12. The method of claim 9, wherein in response to determining that the fingerprint exists in the global deduplication data store, the method further comprises updating the target block directory to point to the location of the block associated with the fingerprint at the global deduplication data store.

13. The method of claim 9, wherein in response to determining that the fingerprint exists in the composite block map, the method further comprises:

removing the data block from the target archive, and

removing the fingerprint from the target block directory.

14. The method of claim 9, wherein in response to determining that the fingerprint exists in the global deduplication data store, the method further comprises:

removing the data block from the target archive, and

removing the fingerprint from the target block directory.

15. A non-transitory computer-readable storage medium comprising computer-executable instructions configured to implement a method of deduplicating a backup archive, the method comprising:

accessing one or more block directories associated with one or more archives at a first archive data store, wherein the one or more block directories include fingerprints of data blocks associated with the one or more archives, and wherein at least one of the one or more archives is associated with a data store;

creating a composite block map based at least in part on the one or more block directories, wherein the composite block map includes fingerprints of each data block stored at the first archive data store; and

accessing one or more data blocks from the data store and for each of the one or more data blocks;

creating a fingerprint for the data block;

determining whether the fingerprint exists in the composite block map of the first archive data store;

in response to determining that the fingerprint does not exist in the composite block map, determining whether the fingerprint exists in a second archive data store, wherein the second archive data store is separate from the first archive data store and the composite block map;

in response to determining that the fingerprint does not exist in the second archive data store, backing up the data block as part of a target archive at the first archive data store; and

storing the fingerprint associated with the data block storage at a target block directory associated with the target archive.

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

creating a map of the active and the inactive data blocks of the one or more data blocks from the data store, and

accessing the data blocks identified as active in the map while not accessing the data blocks identified as inactive in the map.

17. The non-transitory computer-readable storage medium of claim 15, wherein in response to determining that the fingerprint exists in the composite block map, the method further comprises updating the target block directory to point to the location of the block associated with the fingerprint at the first archive data store.

18. The non-transitory computer-readable storage medium of claim 15, wherein in response to determining that the fingerprint exists in the second archive data store, the method further comprises updating the target block directory to point to the location of the block associated with the fingerprint at the second archive data store.

19. The non-transitory computer-readable storage medium of claim 15, wherein in response to determining that the fingerprint exists in the composite block map, the method further comprises:

removing the data block from the target archive, and

removing the fingerprint from the target block directory.

20. The non-transitory computer-readable storage medium of claim 15, wherein in response to determining that the fingerprint exists in the second archive data store, the method further comprises:

removing the data block from the target archive, and

removing the fingerprint from the target block directory.