Locality based quorum eligibility

Patent metadata

Field	Value
Publication number	US-9710344-B1
Application number	US-96602510-A
Country	US
Kind code	B1
Filing date	Dec 13, 2010
Priority date	Dec 13, 2010
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

Abstract

Disclosed are various embodiments for distributing data items. A plurality of nodes forms a distributed data store. A new master candidate is determined through an election among the plurality of nodes. Before performing a failover from a failed master to the new master candidate, a consensus is reached among a locality-based failover quorum of the nodes. The quorum excludes any of the nodes that are in a failover quorum ineligibility mode.

First claim

Therefore, the following is claimed:

1. A non-transitory computer-readable medium embodying a program executable in a computing device, the program, when executed, causing the computing device to at least:
transition a respective one of a plurality of slave nodes to a failover quorum non-eligibility mode responsive to receiving a first transition event;
cease to acknowledge, upon transition to the failover quorum non-eligibility mode, any replication requests received from a master node, the master node and the plurality of slave nodes forming a distributed data store;
perform, after ceasing to acknowledge the replication requests, a first notification to notify the master node and at least one of a remainder of the plurality of slave nodes in the distributed data store that the failover quorum non-eligibility mode has been entered by the respective one of the plurality of slave nodes, the remainder of the plurality of slave nodes excluding the respective one of the plurality of slave nodes;
transition from the failover quorum non-eligibility mode to a failover quorum eligibility mode responsive to receiving a second transition event;
perform, upon transition to the failover quorum eligibility mode, a second notification to notify the at least one of the remainder of the plurality of slave nodes in the distributed data store that the failover quorum eligibility mode has been entered by the respective one of the plurality of slave nodes;
wait, after the second notification that the failover quorum eligibility mode has been entered by the respective one of the plurality of slave nodes, for acknowledgment of the second notification from a locality-based durability super quorum which excludes the respective one of the plurality of slave nodes entering the failover quorum eligibility mode;
resume, after waiting for the acknowledgment of the second notification, acknowledgement of the replication requests received from the master node;
wherein individual ones of the plurality of slave nodes in the distributed data store reside at a respective data center within a plurality of data centers, the locality-based durability super quorum being made of at least one of the plurality of slave nodes residing in respective ones of the plurality data centers but excluding the respective one of the plurality of slave nodes entering the failover quorum eligibility mode.

2. The non-transitory computer-readable medium of claim 1 , wherein the first transition event is a message received as part of a graceful shutdown.

3. The non-transitory computer-readable medium of claim 1 , wherein the first transition event is a message originating from a system operator.

4. A method of distributing data items, comprising:
determining a new master candidate through an election among a plurality of slave nodes forming a distributed data store;
waiting to perform a failover from a failed master to the new master candidate until a consensus is reached among a locality-based failover quorum of the plurality of slave nodes that excludes any of the plurality of slave nodes that are in a failover quorum non-eligibility mode;
wherein individual ones of the plurality of slave nodes in the distributed data store reside at a respective data center within a plurality of data centers, a locality-based durability super quorum being made of at least one of the plurality of slave nodes residing in respective ones of the plurality of data centers but excluding a respective one of the plurality of slave nodes entering the failover quorum eligibility mode;
entering the respective one of the plurality of slave nodes into the failover quorum non-eligibility mode by first ceasing to acknowledge any replication requests received from a master node and then performing a first notification to notify at least one of a remainder of the plurality of slave nodes in the distributed data store of entry into the failover quorum non-eligibility mode, the remainder of the plurality of slave nodes excluding the respective one of the plurality of slave nodes; and
entering the respective one of the plurality of slave nodes into a failover quorum eligibility mode by first performing a second notification to notify the at least one of the remainder of the plurality of slave nodes in the distributed data store of entry into the failover quorum eligibility mode, then waiting for acknowledgment of the second notification from the locality-based durability super quorum, and then resuming acknowledgement of the replication requests received from the master node.

5. The method of claim 4 , wherein the locality-based failover quorum includes N-K+1 of the plurality of data centers but excludes any of the plurality of slave nodes that are in the failover quorum non-eligibility mode, wherein N is a size of the plurality of data centers and K is a durability requirement.

6. The method of claim 4 , wherein the first notification, second notification, and acknowledging all utilize a context-ordered group delivery message service.

7. The method of claim 4 , wherein the first notification, second notification, and acknowledging all utilize a context-ordered group message delivery service in which the message delivery is described by a directed acyclical graph.

8. The method of claim 4 , further comprising:
while in the failover quorum non-eligibility mode, processing the replication requests from the master node; and
transitioning from the failover quorum non-eligibility mode to the failover quorum eligibility mode when the processed replication requests have caught up with the master node and the plurality of slave nodes in the distributed data store.

9. The method of claim 4 , further comprising sending a message, on behalf of another respective one of the plurality of slave nodes in the distributed data store, indicating that the other respective one of the plurality of slave nodes has entered the failover quorum non-eligibility mode.

10. The method of claim 4 , wherein ceasing to acknowledge any replication requests received from the master node is responsive to receiving a first transition event.

11. The method of claim 4 , wherein transitioning from the failover quorum non-eligibility mode to the failover quorum eligibility mode occurs responsive to a message received from a system operator.

12. A system for distributing data items, comprising:
at least one computing device configured to at least:
cease to acknowledge any replication requests received from a master node, the master node and a plurality of slave nodes forming a distributed data store;
perform, after ceasing to acknowledge the replication requests, a first notification to notify the master node and at least one of a remainder of the plurality of slave nodes in the distributed data store that a failover quorum non-eligibility mode has been entered by a respective one of the plurality of slave nodes, the remainder of the plurality of slave nodes excluding the respective one of the plurality of slave nodes;
perform, upon a transition from the failover quorum non-eligibility mode to a failover quorum eligibility mode, a second notification to notify the master node and the at least one of the remainder of the plurality of slave nodes in the distributed data store that the failover quorum eligibility mode has been entered by the respective one of the plurality of slave nodes;
wait, after the second notification that the failover quorum eligibility mode has been entered, for acknowledgment of the second notification from a locality-based durability super quorum;
resume, after waiting for the acknowledgment of the second notification, acknowledgment of the replication requests received from

Assignees

• Helmick Michael T
• Kulesza Jakub
• Stefani Stefano
• Lutz David A
• Amazon Tech Inc

Inventors

• Helmick Michael T
• Kulesza Jakub
• Stefani Stefano
• Lutz David A

Classifications

• G06F11/1425 Primary

  by reconfiguration of node membership · CPC title

• G06F11/2097

  maintaining the standby controller/processing unit updated (initialisation or re-synchronisation thereof G06F11/1658 and subgroups) · CPC title

• G06F11/2028 Primary

  eliminating a faulty processor or activating a spare · CPC title

• G06F16/275

  Synchronous replication · CPC title

• G06F16/273

  Asynchronous replication or reconciliation · CPC title