Read, write, and recovery operations for replicated data

• US 7,761,421 B2
• Filed: 05/16/2003
• Issued: 07/20/2010
• 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: Spence, Susan, Frolund, Svend, Saito, Yasusuhi, Merchant, Arif, Veitch, Alistair
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Pyo; Monica M
• Application Number:
  US10/440,548
• Publication Number:
  US 20040230624A1
• Time in Patent Office: 2,622 Days
• Field of Search: 707/202, 707/204, 707/637, 711/162, 714/6
• US Class Current: 707/637
• 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 replicated data from a requestor;

issuing a message to each of a plurality of distributed 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, wherein the timestamp maintained by each storage device is for a range of data blocks;

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

when at least a majority of the storage devices but not necessarily all of the storage devices have 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 when the timestamp from the message 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 message is 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 to the requestor.

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. A method of reading replicated data comprising:

receiving a request to read replicated data from a requestor;

issuing a message to each of a plurality of distributed 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, wherein the timestamp maintained by each storage device is for a range of data blocks;

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

when at least a majority of the storage devices but not necessarily all of the storage devices have returned an affirmative response, providing the data to the requestor of the data; and

a coordinator device initiating a data recovery operation when less than a majority of the storage devices have returned an affirmative response.

14. A method of writing replicated data comprising:

receiving a request to write replicated data;

issuing a message to each of a plurality of distributed 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, wherein each storage device also stores indicia of any pending update operation to the data, wherein the indicia of any pending update operation includes a timestamp that indicates a time associated with the pending update operation, and wherein each timestamp maintained by each storage device is for a range of data blocks;

comparing the timestamp from the message to the timestamp at each storage device and, if the comparison indicates the storage device has an earlier version of the data and the timestamp associated with the pending update is not higher than the timestamp of the message, returning an affirmative response, wherein an affirmative response is not returned when the timestamp associated with the pending update operation is higher than the timestamp of the message; and

when at least a majority of the storage devices but not necessarily all of the storage devices have returned an affirmative response, providing the data to at least the majority of the storage devices.

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

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

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

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

19. A method of writing replicated data comprising:

receiving a request to write replicated data;

issuing a message to each of a plurality of distributed 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, wherein the timestamp maintained by each storage device is for a range of data blocks;

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

when at least a majority of the storage devices but not necessarily all of the storage devices have returned an affirmative response, providing the data to at least the majority of the storage devices; and

aborting a write associated with the write request when less than a majority of the storage devices return an affirmative response.

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

21. A system for redundant storage of data comprising a plurality of distributed storage devices and a communication medium for interconnecting the storage devices, wherein at least two of the storage devices are designated storage devices for storing a block of replicated data and wherein each designated storage 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 that has not yet been committed, wherein the first timestamp at each designated storage device is maintained for a range of data blocks, wherein in response to a request to read the block of data, one of the storage devices is configured to issue a message to each of the designated storage devices, wherein the message includes a timestamp and wherein each of the designated storage devices is configured to compare the timestamp from the message to its first and second timestamps, wherein when the comparison indicates the designated storage device has an earlier version of the block of data and a later update is not pending, the designated storage device is configured to return an affirmative response and, otherwise, the designated storage device is configured to return a negative response, wherein when at least a majority of the designated storage devices but not necessarily all of the designated storage devices have returned an affirmative response, the block of data at one of the designated storage devices is provided to a requestor of the data.

22. The system according to claim 21, 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 storage devices.

23. The system according to claim 22, wherein the system includes at least three of the designated storage devices.

24. The system according to claim 21, wherein in response to a request to write to the block of data, one of the storage devices is configured to issue a second message to each of the designated storage devices, wherein the second message includes a timestamp and wherein each of the designated storage devices compares the timestamp from the second message to its first and second timestamps.

25. The system according to claim 24, wherein when the comparison indicates the designated storage device has an earlier version of the data block and a later update is not pending, the designated storage device is configured to return an affirmative response and, otherwise, the designated storage device is configured to return a negative response.

26. The system according to claim 25, wherein when at least a majority of the designated storage devices but not necessarily all of the designated storage devices have returned an affirmative response to the second message, the block of data to be written is provided to at least the majority of the designated storage devices.

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

28. A system for redundant storage of data comprising a plurality of distributed storage devices and a communication medium for interconnecting the storage devices wherein at least two of the storage devices are designated storage devices for storing a block of replicated data and wherein each designated storage 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 that has not yet been committed, wherein the first timestamp at each designated storage device is maintained for a range of data blocks,

wherein in response to a message indicating that the block of data is to be recovered, the designated storage devices are configured to forward their first timestamps, and the system is configured to make a determination as to which version of the block of data is most-current based on the forwarded first timestamps.

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

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

31. The method according to claim 30, wherein each storage device that successfully updates its version of the block of data is configured to return an affirmative response.

32. The method according to claim 31, wherein in response to the message, each designated device is configured to use the second timestamp to determine whether any pending update operation is pending.