Change tracking for multiphase deduplication

1. A non-transitory computer-readable medium storing a program that causes a processor to execute a method of multiphase deduplication, the method comprising:

a change tracking phase that includes performing the following steps for each allocated block in a source storage that is changed between the taking of a prior snapshot at a prior point in time and upon which a prior base or incremental backup is based and the taking of a subsequent snapshot at a subsequent point in time and upon which a subsequent incremental backup is based, without performing the following steps on any allocated block in the source storage that is not changed between the prior point in time and the subsequent point in time:

temporarily storing a copy of the changed block in a volatile memory of the source system prior to writing the changed block to the source storage;

performing a hash function only once on the copy of the changed block, while the copy is temporarily stored in a volatile memory of the source system, to calculate a hash value corresponding to the changed block;

writing the changed block to the source storage; and

tracking, in a change log, a location in the source storage of the changed block and the corresponding cryptographic hash value;

an analysis phase that is performed after completion of the change tracking phase and that includes performing the following steps for each unique hash value stored in the change log:

comparing the hash value with hash values of blocks that are stored in a vault storage, without reading the corresponding unique changed block from the source storage, to determine if the corresponding unique changed block in the source storage is duplicated in the vault storage; and

associating a location of the corresponding unique changed block in the source storage with a location of the corresponding duplicated block stored in the vault storage if the corresponding unique changed block is duplicated 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 of changed blocks stored in the source storage, where each unique nonduplicate run of changed blocks includes two or more nonduplicate changed blocks that are stored sequentially 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 subsequent 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.

2. The non-transitory computer-readable medium as recited in claim 1 , wherein:

the hash function comprises a cryptographic hash function and the hash value comprises a cryptographic hash value; or

the hash function comprises a computable check sum function and the hash value comprises a computable check sum value.

3. The non-transitory computer-readable medium as recited in claim 1 , wherein the change log comprises an unordered list of data structures each corresponding to a run of changed blocks.

4. The non-transitory computer-readable medium as recited in claim 1 , wherein the method further comprises a restore phase that is performed after completion of the backup phase and that includes reading, from the vault storage, and storing, in a restore storage, each changed block that was stored in the source storage at the subsequent point in time in the same position as stored in the source storage at the subsequent point in time.

5. The non-transitory computer-readable medium as recited in claim 1 , wherein the method further comprises a restore phase that is performed after completion of the backup phase and that includes performing, after completion of the backup phase, the following steps for each changed block that was stored in the source storage at the subsequent 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 subsequent point in time.

6. The non-transitory computer-readable medium as recited in claim 1 , wherein the method further comprises a restore phase that is performed after completion of the backup phase and that includes performing, after completion of the backup phase, the following steps for all runs of changed blocks stored in the source storage at the subsequent point in time:

reading the runs from the vault storage; and

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

7. The non-transitory computer-readable medium as recited in claim 1 , wherein the step of performing the hash function only once on the copy of the changed block includes performing the hash function only once on the copy of the changed block just prior to, simultaneously with, or just subsequent to writing the changed block to the source storage.

8. The non-transitory computer-readable medium as recited in claim 1 , wherein the vault storage is configured to only store, during the backup phase, a single copy of each unique changed block from the source storage to prevent having any duplicate blocks in the vault storage.