Quorum based reliable low latency storage

Patent metadata

Field	Value
Publication number	US-10229015-B2
Application number	US-201615289825-A
Country	US
Kind code	B2
Filing date	Oct 10, 2016
Priority date	Aug 30, 2016
Publication date	Mar 12, 2019
Grant date	Mar 12, 2019

Abstract

Representative embodiments disclose a consistent, low latency, reliable storage system that uses quorum logic. An odd number of storage nodes are selected to store data for a client application. The odd number allows a quorum to be determined. When data is written to the storage nodes, success is identified if the data is successfully written to a majority of the storage nodes. Similarly, when a read is performed, success is identified if the majority of the storage nodes return the same value written in the same write operation. This is determined by matching a value and a version number for each node. Additional data is written to the storage nodes along with the values to allow the system to identify and repair inconsistencies in the data. In some embodiments, both the current data and prior data are stored to aid in repairing inconsistent data.

First claim

What is claimed is:

1. A method performed by a storage manager connected to a plurality of data storage nodes, the method comprising:
receiving, from a client application, a key associated with data to be read;
sending the key to each of a plurality of data storage nodes;
responsive to the sending, receiving a number of responses from the plurality of data storage nodes;
determining whether the received number of responses represents a quorum of the plurality of data storage nodes having a matching version of stored data;
responsive to determining the received number of responses represents the quorum, returning the matching version of the stored data to the client application.

2. The method of claim 1 , further comprising:
responsive to determining the received number of responses does not represent a quorum, returning either failure or unknown result to the client application.

3. The method of claim 1 , wherein determining whether the received number of responses represents the quorum comprises:
for each of the received number of responses:
identifying a version number and a value for stored data;
identifying a match between two received responses if the version number in the two received responses match;

counting a number of matches in the received responses; and
determining that a quorum exists when the number of matches equals or exceeds a majority of the plurality of storage nodes.

4. The method of claim 1 wherein sending the key to each of the plurality of data storage nodes comprises creating a read message comprising a storage node unique key derived from the key and sending the read message to the plurality of data storage nodes.

5. The method of claim 1 , further comprising:
responsive to determining the received number of responses does not represent a quorum, returning an indication of unknown result when no response is received from a majority of the plurality of data storage nodes.

6. The method of claim 1 , further comprising waiting a designated time period for responses and wherein the received number of responses is the number of those responses received during the designated time period.

7. The method of claim 1 , further comprising:
determining whether repair is needed; and
responsive to determining that repair is needed:
overwriting data in each storage node not storing a last consistent value of the data.

8. The method of claim 1 , further comprising:
determining whether repair is needed; and
responsive to determining that repair is needed:
overwriting data stored in each node not storing a value of the data stored by a majority of the plurality of storage nodes.

9. The method of claim 1 , wherein each response received from a storage node comprises a version number and a value.

10. A method comprising:
receiving, from a client application, data to be stored;
sending a storage request comprising a key and the data to be stored to each of a plurality of data storage nodes;
responsive to the sending, waiting for occurrence of a first occurring return event from among a set of plurality of return events, the set of plurality of return events comprising:
expiration of a wait period;
identification of a quorum of the plurality of data storage nodes indicating successful storage of the data; and
identification that the quorum of the plurality of data storage nodes indicating successful storage of the data cannot be achieved;

responsive the first occurring return event comprising identification of a quorum of the plurality of data storage nodes indicating successful storage of the data, returning an indication of success to the client application.

11. The method of claim 10 , further comprising:
receiving the key from the client application.

12. The method of claim 10 , wherein identification of a quorum of the plurality of storage nodes indicating successful storage of the data comprises:
receiving a response from a plurality of data storage nodes;
for each received response:
identifying a version number for the stored data;
identifying a match between two received responses if the version number in the two received responses match;

counting a number of matches in the received responses; and
determining that a quorum exists when the number of matches equals or exceeds a majority of the plurality of storage nodes.

13. The method of claim 10 , further comprising:
responsive to the first occurring return event comprising expiration of a wait period or identification that the quorum of the plurality of data storage nodes indicating successful storage of the data cannot be achieved, returning to the client application an indication of result unknown when no response is received from a majority of the plurality of data storage nodes.

14. The method of claim 10 , further comprising:
responsive to the first occurring return event comprising expiration of a wait period or identification that the quorum of the plurality of data storage nodes indicating successful storage of the data cannot be achieved, returning to the client application an indication of failure when responses received from a majority of the plurality of data storage nodes do not indicate a successful write of the data.

15. The method of claim 10 , further comprising:
identifying a version number for each of the plurality of storage nodes;
modifying the version number; and
sending the modified version number to the plurality of storage nodes.

16. The method of claim 10 , wherein each response received from a storage node comprises a version number and a value.

17. A computing system comprising:
a processor and executable instructions accessible on a machine-readable medium that, when executed, cause the system to perform operations comprising:
perform a write data operation comprising:
receiving, from a client application, data to be stored;
sending a key to each of a plurality of data storage nodes along with the data to be stored;
responsive to the sending, receiving a number of responses from the plurality of data storage nodes;
determining whether the received number of responses represents a quorum of the plurality of data storage nodes having successfully stored the data;
responsive to determining the received number of responses represents the quorum, returning an indication of success to the client application;

perform a read data operation comprising:
receiving, from the client application, the key associated with data to be read;
sending the key to each of the plurality of data storage nodes;
responsive to the sending, receiving a second number of responses from the plurality of data storage nodes;
determining whether the received second number of responses represents a quorum of the plurality of data storage nodes having a matching version of stored data;
responsive to determining the received number of responses represents the quorum, returning the matching version of the stored data to the client application.

18. The system of claim 17 , further comprising determining whether repair is needed and, responsive to determining that repair is needed performing at least one of:
overwriting data in each storage node not storing a last consistent version of the data; or
overwriting data stored in each node not storing a version of the data stored by a majority of the plurality of storage nodes.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Talbert Nathan Christopher
• West Joel David
• Pinto Edmund Samuel Victor

Classifications

• G06F11/186

  Passive fault masking when reading multiple copies of the same data · CPC title

• G06F11/183 Primary

  by voting, the voting not being performed by the redundant components · CPC title

• G06F2201/805

  Real-time · CPC title

• G06F2201/82

  Solving problems relating to consistency · CPC title

• G06F2201/81

  Threshold · CPC title