Change tracking for multiphase deduplication

A non-transitory computer-readable medium storing a program that causes a processor to execute a method of tracking changes to a source storage of a source system for multiphase deduplication, the method comprising:

• a change tracking phase that includes performing the following steps for only allocated blocks in the source storage that are changed between the taking of a prior snapshot at a prior point in time and the taking of a subsequent snapshot at a 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 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 to determine if the corresponding changed block in the source storage is duplicated in the vault storage;
• and
• associating a location of the corresponding changed block in the source storage with a location of the corresponding duplicated block stored in the vault storage if the corresponding changed block is duplicated in the vault storage;
• and
• a backup phase that is performed after completion of the analysis phase and that includes performing the following steps for all unique nonduplicate runs of changed blocks stored in the source storage in order to create an incremental backup of the source storage, each unique nonduplicate run including one 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;
• associating the blocks in the runs with their corresponding hash values in a vault database;
• and
• associating a location of each run stored in the source storage with a corresponding location of the run stored in the vault storage.

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

• a change tracking phase that includes performing the following steps for only allocated block in the source storage that are 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:
• 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 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 to determine if the corresponding changed block in the source storage is duplicated in the vault storage;
• and
• associating a location of the corresponding changed block in the source storage with a location of the corresponding duplicated block stored in the vault storage if the corresponding changed block is duplicated in the vault storage;
• and
• a backup phase that is performed after completion of the analysis phase and that includes performing the following steps for all unique nonduplicate runs of changed blocks stored in the source storage in order to create an incremental backup of the source storage, each unique nonduplicate run including one 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;
• associating the blocks in the runs with their corresponding hash values in a vault database;
• and
• associating a location of each run stored in the source storage with a corresponding location of the run stored in the vault storage.