Hybrid quorum policies for durable consensus in distributed systems

• US 9,723,064 B1
• Filed: 09/02/2014
• Issued: 08/01/2017
• Est. Priority Date: 09/02/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Corey, James McClellan, Leshinsky, Yan Valerie, Gupta, Anurag Windlass, McKelvie, Samuel James, Madhavarapu, Pradeep Jnana
• Primary Examiner(s): Gillis, Brian J
• Assistant Examiner(s): Lin, Steve
• Application Number:
  US14/475,200
• Time in Patent Office: 1,064 Days
• Field of Search: 709203
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Hybrid quorum policies may be implemented for access requests to state maintained in a distributed system. An update to state maintained in a distributed system may be sent to multiple nodes in the distributed system maintain the state in order to satisfy a hybrid quorum policy for updating the state in the distributed system. The hybrid quorum policy may include individual quorum policies for multiple quorum sets including nodes of the distributed system. Acknowledgments received from nodes in the distributed system indicating that the update is performed may be evaluated according to the individual quorum policies to determine whether the hybrid quorum policy is satisfied. If the hybrid quorum policy is satisfied, then the update to the state may be considered durable.

Claims

1. A system, comprising:

at least one processor;

a memory comprising program instructions, wherein the program instructions when executed by the at least one processor, cause the at least one processor to;

receive an indication of an update to a state maintained in a distributed system for a client, wherein the distributed system comprises a plurality of nodes that maintain the state for the client;

in response to the receipt of the indication, send a request to update the state according to the indicated update to different ones of the plurality of nodes in order to satisfy a hybrid quorum policy for updating the state maintained in the distributed system, wherein the hybrid quorum policy comprises individual quorum policies for a plurality of different quorum sets, wherein each quorum set includes one or more nodes of the plurality of nodes such that a given node of the plurality of nodes is included in at least one quorum set of the plurality of quorum sets;

receive a plurality of acknowledgments from at least some of the different nodes sent the request indicating that the update to the state is performed;

in response to the receipt of the plurality of acknowledgments, determine that the plurality of acknowledgements satisfy the hybrid quorum policy for updating the state maintained in the distributed system, wherein the determination evaluates the plurality of acknowledgments with respect to the individual quorum policies for the plurality of different quorum sets and with respect to an indication in the hybrid quorum policy of which individual quorum policies are to be satisfied; and

in response to the determination that the plurality of acknowledgments satisfy the hybrid quorum policy, provide an indication that the update to the state is durably performed for the client.

2. The system of claim 1, wherein the program instructions further cause the at least one processor to:

receive an indication of a request to read at least a portion of the state maintained in the distributed system for the client;

in response to the receipt of the indication to read the portion of the state, send a read request for the portion of the state to at least some of the plurality of nodes in order to satisfy a hybrid quorum policy for reading the state maintained in the distributed system, wherein the hybrid quorum policy for reading the state comprises individual read quorum policies for the plurality of different quorum sets;

receive a plurality of responses from different ones of the at least some nodes sent the read request, wherein the responses respectively comprise a version of the requested portion of the state;

in response to the receipt of the plurality of responses, determine that the plurality of plurality of responses satisfy the hybrid quorum policy for reading the state maintained in the distributed system, wherein the determination evaluates the plurality of responses with respect to the individual read quorum policies for the plurality of different quorum sets; and

in response to the determination that the plurality of responses satisfy the hybrid quorum policy for reading the state, identify a consistent version of the portion of the state to provide as the requested portion of the state based, at least in part, on the respective versions of the requested portion of the state.

3. The system of claim 1, wherein the one or more nodes included in at least one of the plurality of different quorum sets are subject to a correlated failure characteristic, wherein the update to the state is performed across the quorum sets such that the hybrid quorum policy for updating the state is not satisfied without updating more than the one or more nodes subject to the correlated failure characteristic.

4. The system of claim 1, wherein the program instructions further cause the at least one processor to:

detect a modification to the hybrid quorum policy;

obtain the modified hybrid quorum policy; and

in response to receipt of an indication for another request to update the state in the distributed system, perform the send, the receive, the determination, and the provision for the other request according to the modified hybrid quorum policy.

5. A method, comprising:

performing, by one or more computing devices;

sending a request to update a state maintained in a distributed system to different ones of a plurality of nodes that comprise the distributed system in order to satisfy a hybrid quorum policy for updating the state maintained in the distributed system, wherein the hybrid quorum policy comprises individual quorum policies for a plurality of different quorum sets, wherein each quorum set includes one or more nodes of the plurality of nodes such that a given node of the plurality of nodes is included in at least one quorum set of the plurality of quorum sets;

receive a plurality of acknowledgments from at least some of the different nodes sent the request indicating that the update to the state is performed;

determining that the plurality of acknowledgements satisfy the hybrid quorum policy for updating the state maintained in the distributed system, wherein said determining comprises;

evaluating the plurality of acknowledgments with respect to the individual quorum policies for the plurality of different quorum sets and with respect to an indication in the hybrid quorum policy of which individual quorum policies are to be satisfied; and

in response to determining that the plurality of acknowledgments satisfy the hybrid quorum policy, identifying the update to the state as durably performed.

6. The method of claim 5, wherein the one or more nodes included in at least two of the plurality of different quorum sets are subject to a different common performance characteristic such that a read request for the state of the distributed system is serviced according to a faster one of the two different quorum sets.

7. The method of claim 5, wherein the one or more nodes included in at least one of the plurality of different quorum sets are located in a correlated failure zone such that recovery operation of the state may be performed in the event of a failure of the one or more nodes in the correlated failure zone.

8. The method of claim 5, further comprising:

sending a request to read at least a portion of the state maintained in the distributed system to at least some of the plurality of nodes that comprise the distributed system in order to satisfy a hybrid quorum policy for reading the state maintained in the distributed system, wherein the hybrid quorum policy for reading the state comprises individual read quorum policies for the plurality of different quorum sets;

receiving a plurality of responses from different ones of the at least some nodes sent the read request, wherein the plurality of responses comprise respective versions of the portion of the state;

determining that the plurality of responses satisfy the hybrid quorum policy for reading the state maintained in the distributed system, wherein said determining comprises;

evaluating the plurality of responses with respect to the individual read quorum policies for the plurality of different quorum sets; and

in response to determining that the plurality of responses satisfy the hybrid quorum policy for reading the state, identifying a consistent version of the portion of the state to provide as the requested portion of the state based, at least in part, on the respective versions of the requested portion of the state.

9. The method of claim 5, further comprising:

detecting a modification event for the hybrid quorum policy;

in response to detecting the modification event;

modifying the hybrid quorum policy according to the modification event; and

storing a new hybrid policy version identifier corresponding to the modified hybrid quorum policy at a number of nodes including the one or more nodes such that an access request directed to a possible read quorum or a possible update quorum includes at least one of the number of nodes.

10. The method of claim 9, wherein modifying the hybrid quorum policy according to the modification event comprises removing the individual quorum policy for one or more of the plurality of different quorum sets from the hybrid quorum policy.

11. The method of claim 9, wherein modifying the hybrid quorum policy according to the modification event comprises adding an individual quorum policy for one or more of additional quorum sets.

12. The method of claim 5, wherein the plurality of different quorum sets comprise an original quorum set and a new quorum set, and wherein the update request is performed during a transition between the original quorum set and the new quorum set.

13. The method of claim 5, wherein the state maintained in the distributed system is a data, and wherein the distributed system is a distributed storage system.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

sending a request to update a state maintained in a distributed system to different ones of a plurality of nodes that comprise the distributed system in order to satisfy a hybrid quorum policy for updating the state maintained in the distributed system, wherein the hybrid quorum policy comprises individual quorum policies for a plurality of different quorum sets, wherein each quorum set includes one or more nodes of the plurality of nodes such that a given node of the plurality of nodes is included in at least one quorum set of the plurality of quorum sets;

receiving a plurality of acknowledgments from at least some of the different nodes sent the request indicating that the update to the state is performed;

determining that the plurality of acknowledgements satisfy the hybrid quorum policy for updating the state maintained in the distributed system, wherein said determining comprises;

evaluating the plurality of acknowledgments with respect to the individual quorum policies for the plurality of different quorum sets and with respect to an indication in the hybrid quorum policy of which individual quorum policies are to be satisfied; and

in response to determining that the plurality of acknowledgments satisfy the hybrid quorum policy, identifying the update to the state as durably performed.

15. The non-transitory, computer-readable storage medium of claim 14, wherein the one or more nodes included in at least one of the plurality of different quorum sets are located in a correlated failure zone.

16. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions further cause the one or more computing devices to implement:

sending a request to read at least a portion of the state maintained in the distributed system to at least some of the plurality of nodes that comprise the distributed system in order to satisfy a hybrid quorum policy for reading the state maintained in the distributed system, wherein the hybrid quorum policy for reading the state comprises individual read quorum policies for the plurality of different quorum sets;

receiving a plurality of responses from different ones of the at least some nodes sent the read request, wherein the plurality of responses comprise respective versions of the portion of the state;

determining that the plurality of responses satisfy the hybrid quorum policy for reading the state maintained in the distributed system, wherein said determining comprises;

evaluating the plurality of responses with respect to the individual read quorum policies for the plurality of different quorum sets; and

in response to determining that the plurality of responses satisfy the hybrid quorum policy for reading the state, identifying a consistent version of the portion of the state to provide as the requested portion of the state based, at least in part, on the respective versions of the requested portion of the state.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

prior to sending the request to update the state maintained in the distributed system;

sending the request to update the state to one or more nodes of the plurality nodes, wherein the request includes a hybrid quorum policy version identifier for a particular hybrid quorum policy for updating the state;

receiving an error response from at least one of the one or more nodes indicating a new hybrid quorum policy version identifier; and

obtaining a new hybrid quorum policy corresponding to the new hybrid quorum policy version identifier;

wherein the new hybrid quorum policy is the hybrid quorum policy for updating the state maintained in the distributed system.

18. The non-transitory, computer-readable storage medium of claim 17, wherein the program instructions further cause the one or more computing devices to implement:

detecting a modification event for the hybrid quorum policy;

in response to detecting the modification event;

modifying the hybrid quorum policy according to the modification event; and

storing the new hybrid policy version identifier at a number of nodes including the one or more nodes such that a possible read quorum or a possible update quorum includes at least one of the number of nodes.

19. The non-transitory, computer-readable storage medium of claim 18, wherein in modifying the hybrid quorum policy according to the modification event, the program instructions cause the one or more computing devices to implement:

adding an individual quorum policy for one or more of additional quorum sets;

or

removing the individual quorum policy for one or more of the plurality of different quorum sets from the hybrid quorum policy.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the distributed system is a distributed storage system, wherein the one or more computing devices together implement a client of the distributed storage system, and wherein the state is a data volume maintained for the client.