Comparing mass storage devices through digests that are representative of stored data in order to minimize data transfer

• US 6,085,298 A
• Filed: 10/01/1998
• Issued: 07/04/2000
• Est. Priority Date: 10/13/1994
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: Vinca Corp. (Dell Technologies Inc.)
• Inventors: Ohran, Richard
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US09/165,180
• Time in Patent Office: 642 Days
• Field of Search: 711/162, 711/154, 711/161, 711/167, 395/182.04, 395/182.03, 395/182.05, 714/118, 714/13
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1466 to make the backup process non-disruptive
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

A system and method for comparing mass storage devices. Generally, a mass storage device is subdivided into data blocks representing physical storage locations of some particular size. For each one (or group) of data block(s), a digest is calculated, wherein the digest is an alternate representation of the data stored within the data block(s). A digest is highly dependent on the data it represents such that different data is extremely likely to result in different digests. This high dependence allows for comparing digests rather than directly comparing the data stored at each data block. Furthermore, by calculating a digest that requires fewer bits than the data block(s) it represents, the amount of data that must be transferred between mass storage devices during comparison is minimized.

Claims

1. In a computing environment including a primary system having a primary mass storage device that stores a plurality of primary data blocks and a backup system having a backup mass storage device that stores a plurality of backup data blocks, a method for comparing the primary mass storage device to the backup mass storage device, comprising the steps of:

calculating, by the backup system, a first digest based on a selected backup data block, the selected backup data block corresponding to a physical location within the backup mass storage device, wherein the first digest is smaller than the selected backup data block;

calculating, by the primary system, a second digest based on a selected primary data block, the selected primary data block corresponding to the selected backup data block and also corresponding to a physical location within the primary mass storage device, wherein the second digest is smaller than the selected primary data block, and

comparing the second digest with the first digest to determine whether the second digest and the first digest indicate that the selected backup data block and the selected primary data block contain the same data.

2. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1 wherein the first and second digests represent data of the respective selected primary and backup data blocks, the digests having a high probability of uniquely correlating to the data.

3. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1, further comprising, prior to the step of calculating the second digest, the step of transmitting the first digest from the backup system to the primary system.

4. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 3, wherein the step of comparing is conducted at the primary system.

5. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1, wherein the step of comparing is conducted at the backup system.

6. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1 wherein the step of comparing the second digest with the first digest comprises the step of determining whether the second digest and the first digest are the same.

7. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1, further comprising the steps of:

establishing a connection between the primary system and backup system; and

terminating the connection between the primary system and backup system after the step of comparing has been completed.

8. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1, further comprising the step of storing, at the primary system, the results of the comparing step.

9. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1, further comprising repeating the steps of retrieving a selected backup data block, calculating a first digest, transmitting the first digest, retrieving a selected primary data block, calculating a second digest, and comparing the second digest with the first digest until all of the plurality of primary data blocks have been compared to corresponding backup data blocks.

10. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1 wherein the step of comparing comprises the step of determining that the selected backup data block and the selected primary data block do not contain the same data, and wherein the method further comprises the step of updating the selected backup data block so that it contains the same data as the selected primary data block.

12. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 1, further comprising the step of updating the selected backup data block so that it contains the same data as the selected primary data block when the step of comparing the second digest and the first digest indicates the data blocks contain different data.

11. In a computing environment including a primary system having a primary mass storage device that stores a plurality of primary data blocks and a backup system having a backup mass storage device that stores a plurality of backup data blocks, a method for comparing the primary mass storage device to the backup mass storage device, comprising repeating, until all primary data blocks have been compared to corresponding backup data blocks, the steps of:

calculating, by the backup system, a first digest based on a selected backup data block, the selected backup data block corresponding to a physical location within the backup mass storage device, wherein the first digest is smaller than the selected backup data block;

transmitting the first digest from the backup system to the primary system;

calculating, by the primary system, a second digest based on a selected primary data block, the selected primary data block corresponding to the selected backup data block and also corresponding to a physical location within the primary mass storage device, wherein the second digest is smaller than the selected primary data block; and

comparing the second digest with the first digest to determine whether the second digest and the first digest indicate that the selected backup data block and the selected primary data block contain the same data.

13. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 11 wherein the method is initiated by the primary system.

14. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 11 wherein the method is initiated by the backup system.

15. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 11 wherein the backup system is remotely located from the primary system.

16. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 11 wherein the first and second digests represent multiple data blocks.

17. A method for comparing the primary mass storage device to the backup mass storage device as recited in claim 11 wherein calculating the first digest is computationally faster than transmitting the first digest.

18. In a computing environment including a mass storage device having a plurality of data blocks, a method for comparing data blocks, comprising the steps of:

selecting a first data block;

calculating a first digest, the first digest being generated from data contained within the first data block and being smaller than the first data block, the first data block corresponding to a physical location within the mass storage device;

selecting a second data block;

calculating a second digest, the second digest being generated from data contained within the second data block and being smaller than the second data block, the second data block corresponding to a physical location within the mass storage device, the first and second digests being calculated in a process wherein a change in the data blocks would have a high probability of changing the value of the corresponding digest; and

comparing the first digest with the second digest to determine whether the first digest and the second digest indicate that the first data block and the second data block contain the same data.

19. A system for comparing mass storage, comprising:

primary mass storage means attached to a primary system for storing a plurality of primary data blocks;

backup mass storage means attached to a backup system for storing a plurality of backup data blocks;

backup system processor means for performing the steps of;

retrieving a backup data block from the backup mass storage means, the backup data block corresponding to a physical location within the backup mass storage means;

calculating a first digest based on data stored in the backup data block, the first digest being smaller than and having a high probability of uniquely correlating to the backup data block it represents; and

repeating the above steps until all backup data blocks have been considered; and

primary system processor means for performing the steps of;

receiving the first digest from the backup system processor means;

retrieving a primary data block from the primary mass storage means, the primary data block corresponding to a physical location within the primary mass storage means and also corresponding to the backup data block associated with the first digest;

calculating a second digest based on data stored in the primary data block, the second digest being smaller than and having a high probability of uniquely correlating to the primary data block it represents;

comparing the first digest and the second digest;

interpreting any difference between the first and second digests to indicate a difference between the primary mass storage means and the backup mass storage means; and

repeating the above steps until all primary and backup data blocks have been considered.

20. A system for comparing mass storage as recited in claim 19 further comprising:

primary processor means for performing the steps of;

establishing a connection between the primary processor means and backup processor means;

storing the results of the comparing step; and

transmitting an update data block to the backup processor means, when the comparing step indicates that the primary data block and the backup data block contain different data; and

backup processor means for performing the steps of;

receiving the update data block from the primary processor means; and

updating the backup data block with the received update data block.

21. A system for comparing mass storage as recited in claim 19, wherein the backup system processor means is remotely located from the primary system processor means.

22. A system for comparing mass storage as recited in claim 19, wherein the first and second digests represent multiple data blocks.

23. A computer program product for implementing a method for use in a backup system including a backup mass storage device that stores a plurality of backup data blocks, the backup system being connected to a primary system including a primary mass storage device that stores a plurality of primary data blocks, the computer program product comprising:

a computer-readable medium carrying computer-executable instructions for implementing the method, wherein the computer-executable instructions comprise;

means for retrieving a backup data block from the backup mass storage device, the backup data block corresponding to a physical location within the backup mass storage device;

means for calculating a first digest based on data stored in the backup data block, the first digest being smaller than and having a high probability of uniquely correlating to the backup data block it represents; and

means for transmitting the first digest to the primary system;

wherein retrieving the backup data block, calculating the first digest, and transmitting the first digest are conducted until all of the plurality of backup data blocks have been considered.

24. A computer program product as recited in claim 23, wherein the computer-executable instructions further comprise backup means for receiving an update data block from the primary system for updating a corresponding backup data block when it has been determined that the corresponding backup data block and a corresponding primary data block at the primary mass storage device contain different data.

25. A computer program product as recited in claim 23, wherein the means for calculating a first digest calculates the first digest based on data stored in multiple backup data blocks.

26. A computer program product for implementing a method for use in a primary system including a primary mass storage device that stores a plurality of primary data blocks, the primary system connected to a backup system including a backup mass storage device that stores a plurality of backup data blocks, the computer program product comprising:

a computer-readable medium carrying computer-executable instructions for implementing the method, wherein the computer-executable instructions comprise;

means for receiving a first digest from the backup system;

means for retrieving a primary data block from the primary mass storage device that corresponds to the first digest, the primary data block corresponding to a physical location within the primary mass storage device;

means for calculating a second digest based on data stored in the primary data block, the second digest being smaller than and having a high probability of uniquely correlating to the primary data block it represents;

means for comparing the first digest and the second digest; and

means for interpreting any difference between the first and second digests to indicate a difference between the backup mass storage device and the primary mass storage device;

wherein receiving the first digest, retrieving the primary data block, calculating the second digest, comparing the first digest and the second digest, and interpreting any difference are conducted until all backup data blocks and all primary data blocks have been considered.

27. A computer program product as recited in claim 26, wherein the computer executable instructions further comprise means for transmitting an update data block to the backup system for updating the corresponding data block in the backup system, wherein a difference between the first and second digests has indicated a difference between the backup mass storage device and the primary mass storage device.

28. A computer program product as recited in claim 26, wherein the means for calculating a second digest calculates the second digest based on data stored in multiple primary data blocks.