MULTIPHASE DEDUPLICATION

6 . The method as recited in claim 1 , further comprising an incremental phase that includes performing at a second point in time, after completion of the backup phase, a subsequent analysis phase and a subsequent backup phase for only those allocated blocks in the source storage that changed between the point in time and the second point in time.

7 . The method as recited in claim 1 , wherein the vault storage is connected to the source storage over the internet.

8 . A non-transitory computer-readable medium storing a program that causes a processor to execute the method as recited in claim 1 .

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

an analysis phase that includes performing the following steps for each of multiple allocated blocks stored in a source storage at a point in time:

reading the block from the source storage;

determining whether the block is duplicated in a vault storage; and

associating a location of the block stored in the source storage with a location of the corresponding duplicated block stored in the vault storage if the block is duplicated in the vault storage; and

a backup phase that includes performing, after completion of the analysis phase, the following steps for each unique nonduplicate block stored in the source storage:

reading the block from the source storage;

storing the block in the vault storage; and

associating a location of the block stored in the source storage with a location of the corresponding block stored in the vault storage.

10 . The method as recited in claim 9 , further comprising a restore phase that includes performing, after completion of the backup phase, the following steps for each of the multiple allocated blocks that was stored in the source storage at the point in time:

reading the block from the vault storage; and

storing the block in a restore storage in the same position as stored in the source storage at the point in time.

11 . The method as recited in claim 9 , wherein the step of storing the block in the vault storage includes storing, in the vault storage, at least some runs of unique nonduplicate blocks in the same sequence as stored in the source storage at the point in time.

12 . The method as recited in claim 9 , further comprising an incremental phase that includes performing at a second point in time, after completion of the backup phase, a subsequent analysis phase and a subsequent backup phase for only those allocated blocks in the source storage that changed between the point in time and the second point in time.

13 . A non-transitory computer-readable medium storing a program that causes a processor to execute the method as recited in claim 9 .

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

an analysis phase that includes performing the following steps for each of multiple allocated blocks stored in a source storage at a point in time:

reading the block from the source storage;

determining whether the block is duplicated in a vault storage; and

associating a location of the block stored in the source storage with a location of the corresponding duplicated block stored in the vault storage if the block is stored in the vault storage; and

a backup phase that includes performing, after completion of the analysis phase, the following steps for all unique nonduplicate runs in the source storage:

reading the runs from the source storage;

storing the runs in the vault storage in the same sequence as stored in the source storage at the point in time; and

associating a location of each run stored in the source storage with a corresponding location of the run stored in the vault storage.

15 . The method as recited in claim 14 , wherein the step of determining whether the block is duplicated in the vault storage includes performing a cryptographic hash function on the block to calculate a cryptographic hash value corresponding to the block and comparing the cryptographic hash value against all other cryptographic hash values corresponding to the blocks that are stored in the vault storage.

16 . The method as recited in claim 15 , wherein the backup phase further includes performing a step of adding the cryptographic hash value corresponding to each unique nonduplicate block to a data structure of cryptographic hash values corresponding to the blocks that are stored in the vault storage.

17 . The method as recited in claim 14 , wherein the locations associated during the associating steps are stored in a vault data structure.

18 . The method as recited in claim 17 , further comprising a restore phase that includes performing, after completion of the backup phase, the following steps for each of the runs that was stored in the source storage at the point in time:

accessing the vault data structure to determine the location of the run stored in the vault storage;

reading the run from the determined location in the vault storage; and

storing the run in a restore storage in the same position as stored in the source storage at the point in time.

19 . The method as recited in claim 14 , further comprising an incremental phase that includes performing at a second point in time, after completion of the backup phase, a subsequent analysis phase and a subsequent backup phase for only those allocated blocks in the source storage that changed between the point in time and the second point in time.

20 . A non-transitory computer-readable medium storing a program that causes a processor to execute the method as recited in claim 14 .