Read, write, and recovery operations for replicated data

• US 20040230624A1
• Filed: 05/16/2003
• Published: 11/18/2004
• Est. Priority Date: 05/16/2003
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company), Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Merchant, Arif, Veitch, Alistair, Spence, Susan, Frolund, Svend, Saito, Yasusuhi
• Granted Patent: US 7,761,421 B2
• Time in Patent Office: Days
• US Class Current: 707/204
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• CPC Class Codes: G06F 2201/835 Timestamp

Abstract

Read, write and recovery operations for replicated data are provided. In one aspect, a system for redundant storage of data included a plurality of storage devices and a communication medium for interconnecting the storage devices. At least two of the storage devices are designated devices for storing a block of data. Each designated device has a version of the data and a first timestamp that is indicative of when the version of data was last updated and a second timestamp that is indicative of any pending update to the block of data. The read, write and recovery operations are performed to the data using the first and second timestamps to coordinate the operations among the designated devices.

Claims

1. A method of reading replicated data comprising:

receiving a request to read data from a requester;

issuing a message to each of a plurality of storage devices wherein the message includes a timestamp and wherein each storage device has a version of the data and a timestamp that indicates when the version of data was last updated;

comparing the timestamp from the request to the timestamp at each storage device and, if the comparison indicates the device has the same version of the data block returning an affirmative response; and

when at least a majority of the storage devices has returned an affirmative response, providing the data to the requestor of the data.

2. The method according to claim 1, wherein the comparison indicates the storage device has the same version of the data block when the timestamp from the request and the timestamp at the storage device are equal.

3. The method according to claim 1, wherein each storage device also stores indicia of any pending update operation to the data and wherein an affirmative response is not returned if an update operation is pending.

4. The method according to claim 3, wherein the indicia of the pending update operation is a timestamp that indicates a time associated with the pending update operation.

5. The method according to claim 1, wherein the messages are issued by a coordinator device and wherein the coordinator device is designated for storing a version of the data.

6. The method according to claim 5, wherein the data provided to the requestor is obtained from the coordinator device.

7. The method according to claim 5, wherein the data provided to the requestor is obtained from other than the coordinator device.

8. The method according to claim 1, wherein the message is issued by a coordinator device and wherein the coordinator device is not designated for storing a version of the data.

9. The method according to claim 8, wherein the data provided to the requestor is obtained from one of the storage devices other than the coordinator device.

10. The method according to claim 9, wherein the storage device from which the data is obtained is selected by the coordinator device for load balancing.

11. The method according to claim 8, wherein one of the storage devices other than the coordinator device is appointed for providing the data.

12. The method according to claim 11, wherein the coordinator device initiates a data recovery operation when the appointed device does not return an affirmative response.

13. The method according to claim 1, wherein the coordinator device initiates a data recovery operation when less than a majority of the storage devices has returned an affirmative response.

15. The method according to claim 13, wherein if the comparison indicates that the device has a later version of the data block, the device does not return an affirmative response.

14. A method of writing replicated data comprising:

receiving a request to write data;

issuing a message to each of a plurality of storage devices wherein the message includes a timestamp and wherein each storage device has a version of the data and a timestamp that indicates when the version of data was last updated;

comparing the timestamp from the request to the timestamp at each storage device and, if the comparison indicates the device has an earlier version of the data block returning an affirmative response; and

when at least a majority of the storage devices has returned an affirmative response, providing the data to at least the majority of the storage devices.

16. The method according to claim 14, wherein each storage device also stores indicia of any pending update operation to the data.

17. The method according to claim 16, wherein the indicia of any pending update operation includes a timestamp that indicates a time associated with the pending update operation and wherein an affirmative response is not returned when the timestamp associated with the pending update operation is higher than the timestamp of the message.

18. The method according to claim 14, further comprising aborting the write operation when less than a majority of the storage devices return an affirmative response.

19. The method according to claim 18, further comprising retrying the write operation.

20. The method according to claim 14, further comprising updating versions of the data at the storage devices in response to said providing the data to at least the majority of the storage devices.

21. The method according to claim 20, wherein each device that successfully updates its version of the data returns an affirmative response.

22. The method according to claim 21, further comprising returning a reply message to a requestor for indicating successful completion of the request to write the data when at least a majority of the devices returns an affirmative response after successfully updating its version of the data.

23. A method of recovering replicated data comprising:

issuing a message to each of a plurality of storage devices indicating that data is to be recovered, wherein each storage device has a version of the data and a timestamp that indicates when the version of data was last updated;

receiving the timestamp from at least a majority of the storage devices and determining which version of the data is most-current based on the received timestamps; and

providing the most-current version of the data to at least a majority of the storage devices.

24. The method according to claim 23, wherein the message also includes a timestamp associated with the recovery and wherein each storage device compares its timestamp to the timestamp of the message and if the comparison indicates that the device has a later version of the data block, the device returns a negative response.

25. The method according to claim 24, wherein each storage device also stores indicia of any pending update operation to the data.

26. The method according to claim 25, wherein the indicia of any pending update operation includes a timestamp that indicates a time associated with the pending update operation and wherein a negative response is returned when the timestamp associated with the pending update operation is higher than the timestamp of the message.

27. The method according to claim 26, further comprising aborting the write operation when less than a majority of the storage devices do not return an affirmative response.

28. The method according to claim 23, further comprising at least the majority of the storage devices updating their versions of the data in response to said providing the data to at least the majority of the storage devices.

29. The method according to claim 28, wherein each device that successfully updates its version of the data returns an affirmative response.

30. The method according to claim 23, wherein said issuing the message indicating that data is to be recovered is performed in response to a failed read operation.

31. The method according to claim 30, further comprising providing the recovered data to a requestor of the read operation.

32. A system for redundant storage of data comprising a plurality of storage devices and a communication medium for interconnecting the storage devices wherein at least two of the storage devices are designated devices for storing a block of data and wherein each designated device has a version of the block of data and a first timestamp that is indicative of when the version of the block of data was last updated and a second timestamp that is indicative of any pending update to the block of data.

33. The system according to claim 32, wherein read, write and recovery operations are performed to the block of data using the first and second timestamps to coordinate the operations among the designated devices.

34. The system according to claim 33, wherein the system includes at least three of the designated devices.

35. The system according to claim 32, wherein in response to a request to read the block of data, one of the storage devices issues a message to each of the designated storage devices wherein the message includes a timestamp and wherein each of the designated storage devices compares the timestamp from the request to its timestamps.

36. The system according to claim 35, wherein when the comparison indicates the device has an earlier version of the block of data and a later update is not pending, the device returns an affirmative response and, otherwise, the device returns a negative response.

37. The system according to claim 36, wherein when at least a majority of the storage devices has returned an affirmative response, the block of data at one of the designated devices is provided to a requestor of the data.

38. The system according to claim 32, wherein in response to a request to write to the block of data, one of the storage devices issues a message to each of the designated storage devices wherein the message includes a timestamp and wherein each of the designated storage devices compares the timestamp from the request to its timestamps.

39. The system according to claim 38, wherein when the comparison indicates the device has an earlier version of the data block and a later update is not pending, the device returns an affirmative response and, otherwise, the device returns a negative response.

40. The system according to claim 39, wherein when at least a majority of the storage devices has returned an affirmative response to the message, the block of data to be written is provided to at least a majority of the designated storage devices.

41. The system according to claim 40, wherein a reply message is returned to a requester for indicating successful completion of the request to write the block of data when at least a majority of the devices returns an affirmative response to the data after successfully updating its version of the data.

42. The system according to claim 32, wherein in response to message indicating that the block of data is to be recovered, the designated storage devices forward their first timestamp and a determination is made as to which version of the data is most-current based on the forwarded timestamps.

43. The system according to claim 42, wherein the determination is made by one of the storage devices.

44. The system according to claim 43, wherein the most-current version of the block of data is provided to at least a majority of the storage devices.

45. The method according to claim 44, wherein each device that successfully updates its version of the block of data returns an affirmative response.

46. The method according to claim 45, wherein in response to the message, each designated device uses the second timestamp to determine whether any pending update operation is pending.