Methods for synchronizing storage system data

• US 8,671,255 B2
• Filed: 03/26/2012
• Issued: 03/11/2014
• Est. Priority Date: 08/01/2003
• Status: Active Grant

• Current Assignee: FalconStor, Inc (Hale Capital Management LP)
• Original Assignee: FalconStor, Inc (Hale Capital Management LP)
• Inventors: Lam, Wai, Niles, Ronald S., Li, Xiaowei
• Primary Examiner(s): THAI, TUAN V
• Application Number:
  US13/429,958
• Publication Number:
  US 20120278570A1
• Time in Patent Office: 715 Days
• Field of Search: 711/100, 711/154, 711/161, 711/162
• US Class Current: 711/161
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 21/78 to assure secure storage of data address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00
• CPC Class Codes: G06F 21/80 in storage media based on magnetic or optical technology, e.g. disks with sectors preventing unauthorised reproduction or copying of disc-type recordable media G11B20/00
• CPC Class Codes: G06F 2221/2103 Challenge-response
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

In accordance with one example, a method for comparing data units is disclosed comprising generating a first digest representing a first data unit stored in a first memory. A first encoded value is generated based, at least in part, on the first digest and a predetermined value. A second digest representing a second data unit stored in a second memory different from the first memory, is generated. A second encoded value is derived based, at least in part, on the second digest and the predetermined value. It is determined whether the first data unit and the second data unit are the same based, at least in part, on the first digest, the first predetermined value, the first encoded value, and the second digest, by first processor. If the second data unit is not the same as the first data unit, the first data unit is stored in the second memory.

Claims

1. A method for comparing data units, the method comprising:

generating a first digest representing a first data unit stored in a first memory, by a first control device associated with the first memory;

deriving a first encoded value based, at least in part, on the first digest and a predetermined value, by the first control device;

generating a second digest representing a second data unit stored in a second memory different from the first memory, by a second control device different from the first control device, the second control device being associated with the second memory;

deriving a second encoded value based, at least in part, on the second digest and the predetermined value, by the second control device;

determining whether the first data unit and the second data unit are the same; and

if the second data unit is not the same as the first data unit, storing the first data unit in the second memory, by the second control device.

2. The method of claim 1, comprising:

determining whether the first data unit and the second data unit are the same by comparing the first encoded value to the second encoded value.

3. The method of claim 1, comprising:

determining whether the first data unit and the second data unit are the same by the first control device.

4. The method of claim 1, further comprising:

transmitting the predetermined value to the second control device, via a network; and

transmitting the second encoded value to the first control device, via the network.

5. The method of claim 1, comprising:

randomly-generating the predetermined value.

6. A method for synchronizing a first unit of data stored in a first storage system and a second unit of data stored in a second storage system, comprising:

generating a first digest representing the first unit of data stored by the first storage system, by a first control device in the first storage system;

generating an initial value associated with the first unit of data, by the first control device;

deriving an encoded value using the first digest and the initial value, by the first control device;

transmitting the encoded value from the first storage system to the second storage system, by the first control device;

receiving a decoded value from the second storage system, the decoded value being derived by using a second digest of a second unit of data stored by the second storage system, to decode the encoded value;

determining whether the first unit of data and the second unit of data are duplicates of one another by comparing the decoded value and the initial value, by the first control device; and

sending a copy of the first unit of data from the first storage system to the second storage system, by the first control device, if the first unit of data is determined to be different from the second unit of data, for storage.

7. The method of claim 6, wherein the first control device comprises analog control circuitry.

8. The method of claim 6, wherein the first control device comprises digital control circuitry.

9. The method of claim 6, further comprising:

sending the encoded value from the first control device to a second control device of the second storage system; and

sending the second encoded value to the first control device, by the second control device.

10. The method of claim 9, wherein the first control device generates the first digest and the second control device generates the second digest by performing a same hash function on the first data unit and the second data unit, respectively.

11. The method of claim 9, wherein:

the first memory and the first control device define, at least in part, a first storage device; and

a second memory and the second control device define, at least in part, a second storage device different than the first storage device, the method further comprising;

sending a copy of the first data unit to the second storage device, if the second data unit is not the same as the first data unit; and

storing the first unit of data in the second memory.

12. The method of claim 11, wherein the first storage device and the second storage device are coupled to a network, the method comprising:

transmitting the encoded value from the first control device to the second control device, via the network;

transmitting the second encoded value from the second control device to the first control device, via the network; and

sending a copy of the first data unit to the second storage device, via the network.

13. The method claim 12, wherein the network comprises an intranet, a local area network, a wide area network, a storage area network, an Ethernet, and/or the Internet.

14. The method of claim 12, comprising transmitting the encoded value from the first control device to the second control device in a command to encode the initial value using the second digest.

15. The method of claim 14, comprising sending the command in accordance with SCSI protocols.

16. The method of claim 11, wherein the first storage system and/or the second storage system comprise a block-level storage system.

17. The method of claim 6, further comprising:

deriving a decoded value using the second digest to decode the encoded value, by the second control device.

18. The method of claim 6, further comprising generating the initial value by the first control device by generating a random value.

19. A system for comparing data units comprising:

a first storage system comprising;

first memory;

a first control device configured to;

generate a first digest that represents the first unit of data stored in the first memory;

generate an initial value associated with the first unit of data; and

derive an encoded value using the first digest and the initial value; and

a first interface configured to;

transmit the encoded value from the first storage system to the second storage system;

the second storage system comprising;

second memory;

a second controller configured to;

generate a second digest that represents the second unit of data stored in the second memory; and

derive a decoded value using the second digest to decode the encoded value; and

a second interface configured to;

transmit the decoded value from the second storage system to the first storage system;

wherein the first control device is further configured to;

determine whether the first unit of data and the second unit of data are duplicates of one another by comparing the decoded value and the initial value; and

send a copy of the first unit of data from the first storage system to the second storage system for storage in the second memory, if the first unit of data is determined to be different from the second unit of data.

20. The system of claim 19, wherein the first control device and the second control device are each configured to generate the first digest and the second digest, respectively, using a hash function.

21. The system of claim 20, wherein the hash function comprises a message digest 5 algorithm or a secure hash algorithm.

22. The system of claim 19, wherein the first control device and the second control device are each configured to generate the first digest and the second digest, respectively, using a cyclic redundancy check.

23. The system of claim 19, wherein the first storage system and the second storage system are configured to communicate with each other via a network.

24. The system of claim 23, wherein the network comprises an intranet, a local area network, a wide area network, a storage area network, an Ethernet, and/or the Internet.

25. The system of claim 19, wherein the first interface is further configured to:

transmit the encoded value in a command to decode the encoded value using the second digest.

26. The system of claim 25, wherein the command is transmitted in accordance with SCSI protocols.

27. The system of claim 26, wherein the command comprises instructions contained in a SCSI command descriptor block.

28. The system of claim 19, wherein the initial value comprises a randomly-generated number.

29. The system of claim 19, wherein:

the first storage system comprises a primary storage system and the second storage system comprises a back-up storage system to back-up the primary storage system.

30. A system for comparing data units comprising:

a first storage system comprising;

first memory;

a first control device configured to;

generate a first digest representing the first unit of data; and

generate an initial value associated with the first unit of data; and

derive an encoded value using the first digest and the initial value; and

a first interface configured to;

transmit the initial value from the first storage system to a second storage system;

the second storage system comprising;

second memory;

a second control device configured to;

generate a second digest representing the second unit of data; and

derive a first encoded value using the second digest and the initial value; and

a second interface configured to;

transmit the encoded value from the second storage system to the first storage system;

wherein the first control device is further configured to;

determine whether the first unit of data and the second unit of data are duplicates of one another by comparing the first encoded value and the second encoded value;

send a copy of the first unit of data from the first storage system to the second storage system for storage in a memory in the second storage system, if the first unit of data is determined to be different from the second unit of data.

31. The system of claim 30, wherein the first and second control devices are configured to generate the first digest and the second digest, respectively, by using a hash function.

32. The system of claim 31, wherein the hash function comprises a message digest 5 algorithm or a secure hash algorithm.

33. The system of claim 30, wherein the first control device and the second control device are configured to generate the first and second digests, respectively, by using a cyclic redundancy check.

34. The system of claim 30, wherein the first storage system and the second storage system are configured to communicate over a network.

35. The system of claim 34, wherein the network comprises an intranet, a local area network, a wide area network, a storage area network, an Ethernet, and/or the Internet.

36. The system of claim 30, wherein the first interface is further configured to:

transmit the encoded value in a command to decode the encoded value using the second digest that represents the second unit of data.

37. The system of claim 36, wherein the command is transmitted in accordance with SCSI protocols.

38. The system of claim 37, wherein the command comprises instructions contained in a SCSI command descriptor block.

39. The system of claim 30, wherein the initial value comprises a randomly-generated number.

40. The system of claim 30, wherein:

the first storage system comprises a primary storage system; and

the second storage system comprises a backup storage system to backup the primary storage system.

41. A method for comparing data units, the method comprising:

generating a first digest representing a first data unit stored in a first memory, by a first control device associated with the first memory;

deriving a first encoded value based, at least in part, on the first digest and a predetermined value, by the first control device;

generating a second digest representing a second data unit stored in a second memory different from the first memory, by a second control device different from the first control device, the second control device being associated with the second memory;

deriving a decoded value based, at least in part, on the second digest and the encoded value, by the second control device;

determining whether the first data unit and the second data unit are the same; and

if the second data unit is not the same as the first data unit, storing the first data unit in the second memory, by the second control device.

42. The method of claim 41, comprising:

determining that the first and second data units are the same by comparing the decoded valve to the predetermined number.

43. The method of claim 42, comprising:

determining whether the first data unit and the second data unit are the same by the first control device.