Virtual defragmentation in a deduplication vault

• US 8,751,454 B1
• Filed: 01/28/2014
• Issued: 06/10/2014
• Est. Priority Date: 01/28/2014
• Status: Active Grant

• Current Assignee: StorageCraft Technology Corporation
• Original Assignee: StorageCraft Technology Corporation
• Inventors: Bushman, Nathan S., Gardner, Andrew Lynn
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/166,569
• Time in Patent Office: 133 Days
• Field of Search: 707600-899
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Virtual defragmentation in a deduplication vault. In one example embodiment, a method of virtual defragmentation in a deduplication vault includes a virtual defragmentation phase. The virtual defragmentation phase includes accessing file system metadata (FSM) blocks included in a backup of allocated blocks of a source storage and reordering block references in the FSM blocks to match the order of the corresponding blocks as stored in a deduplication vault storage.

Claims

1. A method of multiphase deduplication, the method comprising:

a backup phase that includes storing, in a deduplication vault storage, a backup of a source storage, the backup including each unique nonduplicate allocated block from the source storage at a point in time including file system metadata (FSM) blocks and data blocks;

a virtual defragmentation phase that includes accessing the FSM blocks included in the backup and reordering block references in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage; and

a restore phase that is performed after the completion of the virtual defragmentation phase and that includes reading, from the deduplication vault storage, and storing, in a restore storage, each allocated block that was stored in the source storage at the point in time according to the reordered block references in the FSM blocks.

2. The method as recited in claim 1, wherein the virtual defragmentation phase is performed prior to the backup phase.

3. The method as recited in claim 1, wherein the virtual defragmentation phase is at least partially performed during the backup phase.

4. The method as recited in claim 1, wherein the virtual defragmentation phase is performed after the backup phase.

5. The method as recited in claim 1, wherein:

during the virtual defragmentation phase, block references for each set of local duplicate blocks that was stored in the source storage at the point in time is reordered as a run in the reordered block references in the FSM blocks; and

during the restore phase, each of the runs of local duplicate blocks is stored in the restore storage according to the reordered block references in the FSM blocks.

6. The method as recited in claim 1, wherein the reordering of block references in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage includes only the reordering of block references corresponding to the data blocks in the backup and not the reordering of block references corresponding to the FSM blocks in the backup.

7. The method as recited in claim 1, wherein the FSM includes a file system file allocation table (FSFAT) and a file system block allocation map (FSBAM).

8. One or more non-transitory computer-readable media storing one or more programs that cause one or more processors to execute the method as recited in claim 1.

9. A method of multiphase deduplication, the method comprising:

an analysis phase that includes analyzing each allocated block, including file system metadata (FSM) blocks and data blocks, stored in a source storage at a point in time to determine if the block is duplicated in a vault storage;

a backup phase that is performed after completion of the analysis phase and that includes storing, in the vault storage, a backup including each unique nonduplicate allocated block from the source storage; and

a virtual defragmentation phase that includes accessing the FSM blocks that are included in the backup and reordering block references in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage.

10. The method as recited in claim 9, wherein the virtual defragmentation phase is performed at a source system associated with the source storage.

11. The method as recited in claim 9, wherein:

the reordered block references include block references corresponding to the blocks that make up the contents of one or more files of an operating system that is installed in the source storage; and

the one or more files of the operating system are stored in the vault storage in the sequence of a clean install of the operating system.

12. The method as recited in claim 9, wherein:

the reordered block references include block references corresponding to the data blocks that make up the contents of one or more files of a software application that is installed in the source storage; and

the one or more files of the software application are stored in the vault storage in the sequence of a clean install of the software application.

13. The method as recited in claim 9, further comprising a restore phase that is performed after the completion of the virtual defragmentation phase and that includes reading, from the vault storage, and storing, in a restore storage, each allocated block that was stored in the source storage at the point in time according to the reordered block references in the FSM blocks.

14. The method as recited in claim 13, wherein:

during the virtual defragmentation phase, block references for each set of local duplicate blocks that was stored in the source storage at the point in time is reordered as a run in the reordered block references in the FSM blocks; and

during the restore phase, each of the runs of local duplicate blocks is stored in the restore storage according to the reordered block references in the FSM blocks.

15. The method as recited in claim 13, wherein the reordering of block references in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage includes only the reordering of block references corresponding to the data blocks in the backup and not the reordering of block references corresponding to the FSM blocks in the backup.

16. One or more non-transitory computer-readable media storing one or more programs that cause one or more processors to execute the method as recited in claim 9.

17. The method as recited in claim 9, wherein the virtual defragmentation phase is at least partially performed during the backup phase.

18. A method of multiphase deduplication, the method comprising:

an analysis phase that includes analyzing each allocated block, including file system metadata (FSM) blocks and data blocks, stored in a source storage at a point in time to determine if the block is duplicated in a vault storage;

a backup phase that is performed after completion of the analysis phase and that includes storing, in the vault storage, a backup including each unique nonduplicate allocated block from the source storage;

a virtual defragmentation phase that includes accessing the FSM blocks that are included in the backup and reordering block references corresponding to data blocks in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage, the block references for each set of local duplicate data blocks that are included in the backup being reordered as a run in the reordered FSM blocks; and

a restore phase that is performed after the completion of the virtual defragmentation phase and that includes reading, from the vault storage, and storing, in a restore storage, each allocated block that was stored in the source storage at the point in time according to the reordered block references in the FSM blocks, each of the runs of local duplicate data blocks being stored in the restore storage according to the reordered block references in the FSM blocks.

19. One or more non-transitory computer-readable media storing one or more programs that cause one or more processors to execute the method as recited in claim 18.

20. The method as recited in claim 18, wherein the virtual defragmentation phase is at least partially performed during the backup phase.