# US 8,751,454 B1 · Virtual defragmentation in a deduplication vault

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,751,454 B1
- Document ID: US8751454B1
- Status: Granted
- Kind: B1
- Application number: 14/166,569
- Filed: 2014-01-28
- Granted: 2014-06-10
- Earliest claimed: 2014-01-28
- Assignees: Storagecraft Technology Corporation
- Applicants: Storagecraft Technology Corporation
- Inventors: Nathan S. Bushman; Andrew Lynn Gardner
- Web page: https://patentgrep.com/patent/US8751454B1

## CPC

- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0617: {in relation to availability}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket}
- G06F 11/1453: {using de-duplication of the data}
- G06F 11/1469: {Backup restoration techniques}
- G06F 11/1451: {by selection of backup contents}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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).

### Claim 8 (depends on 1)

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.

### Claim 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.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 9)

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.

### Claim 12 (depends on 9)

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.

### Claim 13 (depends on 9)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 13)

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.

### Claim 16 (depends on 9)

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.

### Claim 17 (depends on 9)

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

### Claim 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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 18)

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