Hash value comparison during crash-tolerant incremental change tracking between backups of a source storage

1. A method of crash-tolerant incremental change tracking between backups of a source storage, the method comprising:

assigning each block in a source storage into one of multiple zones, each of the zones including multiple of the blocks;

creating, in a nonvolatile storage, a nonvolatile zone map that represents each of the zones;

tracking, in the nonvolatile zone map, each of the zones that is changed between a first point in time and a second point in time, each of the zones being marked as changed in the nonvolatile zone map upon the first receipt of a request to write to any of the blocks of the zone and prior to execution of the write request;

identifying, as potentially changed zone blocks, the blocks in the source storage assigned to any zone marked as changed in the nonvolatile zone map;

identifying, as potentially outdated backup blocks, the most recently backed-up blocks in one or more prior backups of the source storage that correspond to the potentially changed zone blocks, the one or more prior backups representing the source storage at the first point in time;

calculating source hash values of the potentially changed zone blocks;

calculating backup hash values of the potentially outdated backup blocks; and

subsequent to the second point in time, comparing the source hash values to the backup hash values to determine which blocks in the source storage actually changed between the first point in time and the second point in time,

wherein at least some of the source hash values and/or at least some of the backup hash values are calculated subsequent to a crash of an operating system associated with the source storage.

2. The method as recited in claim 1 , wherein at least some of the source hash values and/or at least some of the backup hash values are preemptively calculated prior to the second point in time.

3. The method as recited in claim 2 , wherein the calculating of the backup hash values of the potentially outdated backup blocks is performed during the backing-up of the potentially outdated backup blocks.

4. The method as recited in claim 1 , wherein at least some of the source hash values and/or at least some of the backup hash values are calculated subsequent to the first point in time and subsequent to a crash of an operating system associated with the source storage.

5. The method as recited in claim 1 , wherein at least some of the source hash values and/or at least some of the backup hash values are calculated subsequent to the first point in time, subsequent to a crash of an operating system associated with the source storage, and prior to the second point in time.

6. The method as recited in claim 1 , wherein at least some of the source hash values and/or at least some of the backup hash values are calculated subsequent to the second point in time.

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

the source storage is locally accessible to a source system;

the one or more prior backups are stored on a destination storage that is locally accessible to a destination system; and

the source system is only configured to communicate with the destination system over a Wide Area Network (WAN).

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 crash-tolerant incremental change tracking between backups of a source storage, the method comprising:

creating, in a volatile memory, a volatile block map that represents each block in a source storage;

assigning each of the blocks in the source storage into one of multiple zones, each of the zones including multiple of the blocks;

creating, in the source storage, a nonvolatile zone map that represents each of the zones;

tracking, in the volatile block map, each of the blocks that is changed between a first point in time and a second point in time;

tracking, in the nonvolatile zone map, each of the zones that is changed between the first point in time and the second point in time, each of the zones being marked as changed in the nonvolatile zone map upon the first receipt of a request to write to any of the blocks of the zone and prior to execution of the write request; and

subsequent to a crash of an operating system associated with the source storage:

discontinuing the tracking in the volatile block map;

continuing the tracking in the nonvolatile zone map;

identifying, as potentially changed zone blocks, the blocks in the source storage assigned to any zone marked as changed in the nonvolatile zone map;

identifying, as potentially outdated backup blocks, the most recently backed-up blocks in one or more prior backups of the source storage that correspond to the potentially changed zone blocks, the one or more prior backups representing the source storage at the first point in time;

calculating source hash values of the potentially changed zone blocks;

calculating backup hash values of the potentially outdated backup blocks; and

subsequent to the second point in time, comparing the source hash values to the backup hash values to determine which blocks in the source storage actually changed between the first point in time and the second point in time.

10. The method as recited in claim 9 , wherein at least some of the source hash values and/or at least some of the backup hash values are preemptively calculated prior to the second point in time.

11. The method as recited in claim 9 , wherein at least some of the source hash values and/or at least some of the backup hash values are calculated subsequent to the second point in time.

12. The method as recited in claim 9 , wherein none of the source hash values and the backup hash values are calculated prior to the crash of the operating system associated with the source storage.

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

the source storage is locally accessible to a source system;

the one or more prior backups are stored on a destination storage that is locally accessible to a destination system; and

the source system is only configured to communicate with the destination system over a Wide Area Network (WAN).

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

15. A method of crash-tolerant incremental change tracking between backups of a source storage, the method comprising:

creating, in a volatile memory, a volatile block map that represents each block in a source storage;

assigning each of the blocks in the source storage into one of multiple zones, each of the zones including multiple of the blocks;

creating, in the source storage, a nonvolatile zone map that represents each of the zones;

creating, in the volatile memory, a volatile zone map that represents each of the zones;

tracking, in the volatile block map, each of the blocks that is changed between a first point in time and a second point in time;

tracking, in the volatile and nonvolatile zone maps, each of the zones that is changed between the first point in time and the second point in time, each of the zones being marked as changed in the volatile and nonvolatile zone maps upon the first receipt of a request to write to any of the blocks of the zone and prior to execution of the write request; and

subsequent to a crash of an operating system associated with the source storage:

identifying, as potentially changed zone blocks, at least the blocks in the source storage assigned to any zone that was marked as changed in the nonvolatile zone map prior to the crash of the operating system associated with the source storage;

identifying, as potentially outdated backup blocks, the most recently backed-up blocks in one or more prior backups of the source storage that correspond to the potentially changed zone blocks, the one or more prior backups representing the source storage at the first point in time;

calculating source hash values of the potentially changed zone blocks;

calculating backup hash values of the potentially outdated backup blocks; and

subsequent to the second point in time, comparing the source hash values to the backup hash values to determine which blocks in the source storage actually changed between the first point in time and the second point in time.

16. The method as recited in claim 15 , wherein at least some of the source hash values and/or at least some of the backup hash values are preemptively calculated prior to the second point in time.

17. The method as recited in claim 15 , wherein at least some of the source hash values and/or at least some of the backup hash values are calculated subsequent to the second point in time.

18. The method as recited in claim 15 , wherein none of the source hash values and the backup hash values are calculated prior to the crash of the operating system associated with the source storage.

19. The method as recited in claim 15 , wherein:

the source storage is locally accessible to a source system;

the one or more prior backups are stored on a destination storage that is locally accessible to a destination system; and

the source system is only configured to communicate with the destination system over a Wide Area Network (WAN).

20. 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 15 .