Method of writing data

Patent metadata

Field	Value
Publication number	US-9047306-B1
Application number	US-25233505-A
Country	US
Kind code	B1
Filing date	Oct 17, 2005
Priority date	Oct 17, 2005
Publication date	Jun 2, 2015
Grant date	Jun 2, 2015

Abstract

An embodiment of a method of writing data begins with a first step of generating a timestamp. A second step issues a query that includes the timestamp to each of a plurality of primary storage devices. The method continues with a third step of receiving a query reply from at least a quorum of the primary storage devices. The query replies indicate that the timestamp is later than an existing timestamp for the data. In a fourth step, the data is mirrored to secondary storage after receiving the query reply from at least the quorum of the primary storage devices. Upon receiving a mirror completion message from the secondary storage, a fifth step issues a write message that includes at least a portion of the data and the timestamp to each of the primary storage devices.

First claim

What is claimed is:

1. A method of writing data comprising the steps of:
generating a timestamp related to writing the data;
issuing, by a processor, a query that includes the timestamp to each of a plurality of primary storage devices;
receiving, by the processor, a query reply from at least a quorum of the primary storage devices indicating that the timestamp is later than an existing timestamp for the data;
after receiving the query reply from at least the quorum of the primary storage devices, initiating, by the processor, mirroring of the data to secondary storage; and
upon receiving a mirror completion message from the secondary storage, issuing, by the processor, a write message that includes at least a portion of the data to each of the primary storage devices.

2. The method of claim 1 wherein the write message issued to each of the primary storage devices further includes the timestamp.

3. The method of claim 1 wherein the write message issued to each of the primary storage devices further includes another timestamp generated after the timestamp.

4. The method of claim 1 wherein a coordinator that includes the processor performs the steps of generating the timestamp, issuing the query to the primary storage devices, receiving the query reply form at least the quorum of the primary storage devices, and issuing the write message to each of the primary storage devices.

5. The method of claim 4 wherein the timestamp includes a time and an identifier of the coordinator.

6. The method of claim 4 wherein the coordinator is one of the primary storage devices.

7. The method of claim 1 wherein each of the primary storage devices comprises a processor, non-volatile memory, and storage.

8. The method of claim 7 wherein the storage includes disk storage.

9. The method of claim 1 wherein a particular one of the primary storage devices receives the query, determines that an order timestamp exists, confirms that the generated timestamp is later than the order timestamp and a value timestamp, saves the generated timestamp as the order timestamp, and sends a particular query reply responsive to the query to the processor.

10. The method of claim 1 wherein a particular one of the primary storage devices receives the query, determines that an order timestamp does not exist, confirms that the generated timestamp is later than a value timestamp, saves the generated timestamp as the order timestamp, and sends a particular query reply responsive to the query to the processor.

11. The method of claim 1 wherein initiating the mirroring of the data to the secondary storage comprises sending the timestamp and the data to a secondary-storage coordinator to cause the secondary-storage coordinator to mirror the data to the secondary storage.

12. The method of claim 11 further comprising the secondary-storage coordinator:
sending a secondary-storage query that includes the timestamp to each of a plurality of secondary storage devices that are part of the secondary storage;
receiving a secondary-storage query reply from at least a second quorum of the secondary storage devices indicating that the timestamp is later than a previously stored timestamp; and
in response to receiving the secondary-storage query reply from at least the second quorum of the secondary storage devices, sending a secondary-storage write message that includes at least a portion of the data and the timestamp to each of the secondary storage devices.

13. The method of claim 1 wherein the primary storage devices employ replication to store the data.

14. The method of claim 13 wherein the secondary storage employs replication to store the data.

15. The method of claim 13 wherein the secondary storage employs erasure coding to store the data.

16. The method of claim 1 wherein the primary storage devices employ erasure coding to store the data.

17. The method of claim 16 wherein the secondary storage employs replication to store the data.

18. The method of claim 16 wherein the secondary storage employs erasure coding to store the data.

19. A method of writing data comprising the steps of:
generating a timestamp related to writing the data;
issuing, by a processor, a query that includes the timestamp to each of a plurality of primary storage devices, each of the plurality of primary storage devices storing a replica of a previously written version of the data;
receiving, by the processor, a query reply from at least a quorum of the primary storage devices indicating that the timestamp is later than an existing timestamp;
in response to receiving the query reply from at least the quorum of the primary storage devices, initiating, by the processor, mirroring of the data to secondary storage; and
upon receiving a mirror completion message for the mirroring of the data from the secondary storage, issuing a write message that includes the data to each of the primary storage devices.

20. The method of claim 19 wherein the plurality of primary storage devices store replicated data.

21. The method of claim 20 wherein the quorum is a majority of the primary storage devices.

22. The method of claim 20 further comprising receiving a write confirmation message from each of at least a second quorum of the primary storage devices indicating successful storage of the data in non-volatile memory or storage.

23. The method of claim 22 wherein the second quorum is a majority of the primary storage devices.

24. The method of claim 20 further comprising reading the data and a value timestamp from one of the primary storage devices and confirming that the value timestamp for the data exists on a majority of the primary storage devices.

25. The method of claim 20 further comprising reading the data and a value timestamp from one of the primary storage devices and determining that an order timestamp or another value timestamp on at least one of the primary storage devices is later than the value timestamp.

26. The method of claim 25 further comprising performing a recover procedure.

27. The method of claim 26 wherein the recover procedure includes checking the secondary storage for a most recent value of the data.

28. A method of writing data comprising the steps of:
generating a timestamp related to writing the data;
issuing, by a processor, a query that includes the timestamp to each of a plurality of primary storage devices, the plurality of primary storage devices storing a stripe of erasure coded data that comprises m data blocks and p parity blocks, each primary storage device storing a data block or a parity block;
receiving, by the processor, a query reply from each of at least a quorum of the primary storage devices indicating that the timestamp is later than an existing timestamp;
after receiving the query reply from each of at least the quorum of the primary storage devices, initiating, by the processor, mirroring of the data to secondary storage; and
upon receiving a mirror completion message from the secondary storage, issuing a write message that includes a data block or a parity block to each of the primary storage devices.

29. The method of claim 28 wherein the quorum is a number of the primary storage devices that is at least m plus one half p.

30. The method of claim 28 further comprising receiving a write confirmation message from each

Assignees

• Frolund Svend
• Merchant Arif
• Veitch Alistair
• Hewlett Packard Development Co

Inventors

• Frolund Svend
• Merchant Arif
• Veitch Alistair

Classifications

• G06F11/2076 Primary

  Synchronous techniques · CPC title

• G06F17/30174 Primary

  Physics · mapped topic

• G06F16/178 Primary

  Techniques for file synchronisation in file systems · CPC title

• G06F2201/835

  Timestamp · CPC title

• G06F11/2064

  while ensuring consistency · CPC title