Locality based quorums
First Claim
1. A non-transitory computer-readable medium embodying a program executable in a computing device, the program comprising:
- code that replicates a write request from a master node to a plurality of slave nodes, the master node and the plurality of slave nodes each residing in a respective data center within a plurality of data centers;
code that applies a locality-based durability requirement which determines that the replicated write request has been acknowledged by at least one node residing in each of K data centers out of N data centers, wherein N is a size of the plurality of data centers;
code that confirms the replicated write request to a client responsive to the determination that the replicated write request has been acknowledged, the client having originated the write request;
code that detects that the master node has failed;
code that determines a new master candidate through an election among the slave nodes in response to the detection that the master node has failed;
code that waits to recover data from all of the nodes that reside within N−
K+1 of the data centers, wherein N is a size of the plurality of data centers and K is a durability requirement; and
code that transitions the new master candidate, after the wait, to become a new master that is ready to process another write request.
1 Assignment
0 Petitions
Accused Products
Abstract
Disclosed are various embodiments for distributing data items within a plurality of nodes. A data item update request is replicated from a master node in a plurality of nodes to a plurality of slave nodes within the plurality of nodes. The replicated data item update request is determined to be locality-based durable. Responsive to the determination that the replicated data item update request is locality-based durable, the data item update request is confirmed to a client, wherein the client had originated the data item update request. Upon failover of the master node to another node within the plurality of nodes, a fault-tolerant failover quorum ensures that all previously confirmed updates are found and recognized by the new master node.
70 Citations
20 Claims
-
1. A non-transitory computer-readable medium embodying a program executable in a computing device, the program comprising:
-
code that replicates a write request from a master node to a plurality of slave nodes, the master node and the plurality of slave nodes each residing in a respective data center within a plurality of data centers; code that applies a locality-based durability requirement which determines that the replicated write request has been acknowledged by at least one node residing in each of K data centers out of N data centers, wherein N is a size of the plurality of data centers; code that confirms the replicated write request to a client responsive to the determination that the replicated write request has been acknowledged, the client having originated the write request; code that detects that the master node has failed; code that determines a new master candidate through an election among the slave nodes in response to the detection that the master node has failed; code that waits to recover data from all of the nodes that reside within N−
K+1 of the data centers, wherein N is a size of the plurality of data centers and K is a durability requirement; andcode that transitions the new master candidate, after the wait, to become a new master that is ready to process another write request. - View Dependent Claims (2, 3)
-
-
4. A system for distributing data items within a plurality of nodes, comprising:
-
at least one computing device; and a data store management application in the at least one computing device, the data store management application comprising; logic that detects failure of a master node in the plurality of nodes; logic that, in response to the detection that the master node has failed, determines a new master candidate through an election among a plurality of slave nodes within the plurality of nodes; logic that waits for a consensus among a locality-based failover quorum of the slave nodes; logic that verifies that data discovered during the consensus is locality-based durable; and logic that, responsive to the verification, transitions the new master candidate to become a new master that is ready to process another data item update request. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method of distributing data items within a plurality of nodes, comprising the steps of:
-
replicating a data item update request from a master node in the plurality of nodes to a plurality of slave nodes within the plurality of nodes, wherein each of the nodes resides at a respective data center within a plurality of availability zones; determining that the replicated data item update request is locality-based durable based on a location of the nodes that have acknowledged receipt of the replicated data item update request; and responsive to the determination that the replicated data item update request is locality-based durable, confirming the data item update request to a client, the client having originated the data item update request. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification