Data consistency within a federation infrastructure

• US 8,090,880 B2
• Filed: 11/07/2007
• Issued: 01/03/2012
• Est. Priority Date: 11/09/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hasha, Richard L., Xun, Lu, Kakivaya, Gopala Krishna R., Malkhi, Dahlia
• Primary Examiner(s): TODD, GREGORY G
• Application Number:
  US11/936,556
• Publication Number:
  US 20080288646A1
• Time in Patent Office: 1,518 Days
• Field of Search: 709220-222, 709/230, 709/236, 709/237, 709/251, 709224-226, 709/205, 709217-219, 714/1, 714/4.11, 714/47.2, 707/627, 707/633, 707/634, 707/636, 707/637, 707/657
• US Class Current: 709/251
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

In some embodiments, it is determined that a primary node has been elected from among a plurality of nodes in a replica set of nodes. The primary node accepts and processes client data access requests. The replica set includes the primary node and other secondary nodes. The primary node receives client data access requests. The primary node assigns a data sequence number to each client data access request that mutates state in the order the client data access requests are received. The data sequence numbers include a linearized processing order that is to be followed by each of the nodes in the replica set. The primary node sends the mutating client data access requests including any corresponding data sequence numbers to the secondary nodes. The primary node receives, from a threshold number of secondary nodes, an acknowledgement indicating reception of the client data access request. The primary node commits the data mutating access request.

Claims

1. In a federation infrastructure of a ring of nodes configured for bi-directional routing, a method for performing a data access transaction within a replica set maintained within a federation infrastructure, the method comprising:

an act of determining that a primary node has been elected from among a plurality of nodes in a replica set of nodes, the primary node being configured to accept and process client data access requests, the replica set comprising the primary node and one or more secondary nodes;

an act of determining that the replica set includes a minimum number of secondary nodes as members based on a maximum number of tolerable simultaneous failures of secondary nodes of the replica set, the act further comprising;

determining that the minimum number of secondary nodes is at least a write quorum defining a minimum number of secondary nodes necessary to perform a request to write data and to provide complete fault tolerance for the maximum number of tolerable simultaneous failures; and

determining that the minimum number of secondary nodes is at least a read quorum defining a minimum number of secondary nodes necessary to provide complete fault tolerance for the maximum number of tolerable simultaneous failures;

an act of the primary node receiving one or more client data access requests, each data access request indicating at least a portion of data that is to be accessed on at least the primary node in the replica set, each data access request comprising one of a request to write data to at least a write quorum of nodes in the replica set or a request to read data from at least one of the nodes in the replica set;

an act of the primary node assigning a data sequence number (DSN) to each of the client data access requests that mutate state in the order the client data access requests are received, the data sequence numbers comprising a linearized processing order that is to be followed by each of the nodes in the replica set;

an act of the primary node sending at least one of the client data access requests including any corresponding data sequence numbers to at least one of the secondary nodes, the sending including the primary node sending the data access request to at least the write quorum of nodes when the request is a request to write data, and the primary node sending the data access request to at least one of the secondary nodes when the request is a request to read data;

an act of the primary node receiving, from at least a threshold number of secondary nodes, an acknowledgement indicating reception of the client data access request; and

an act of the primary node committing the data access request, the committing including, when the data access request is a write request, verifying that the threshold number of secondary nodes acknowledging reception of the client data access request meets the write quorum of nodes and subsequently writing the data locally at the primary node according to the client data access request, and when the data access request is a read request, reading the data from the at least one of the secondary nodes.

2. The method of claim 1, wherein the primary node commits the data access request in a single phase.

3. The method of claim 2, wherein the primary node committing the data access request in a single phase comprises a non-blocking transaction.

4. The method of claim 1, further comprising an act of electing a primary node from among a plurality of nodes in the replica set of nodes.

5. The method of claim 1, wherein the number of secondary nodes to be members of the replica set corresponds to the number of members in the primary node'"'"'s neighborhood.

6. The method of claim 1, wherein the acknowledgement indicates at least one of acceptance or rejection of the client data access request.

7. The method of claim 1, further comprising an act of a would-be primary node sending a request to the read quorum or the write quorum of secondary nodes to determine any transactions that the would-be primary node is unaware of.

8. The method of claim 1, further comprising receiving from each member of the write quorum an indication that each member of the quorum has at least inserted the client data access request into each member'"'"'s data access queue ordered by last used sequence number (LSN).

9. The method of claim 1, wherein the portion of data includes a set of control information about the replica set itself including at least one of a last used sequence number (LSN), a configuration sequence number (CSN), a DSN, a primary node identity or secondary node identities.

10. The method of claim 1, wherein the portion of data includes application state information.

11. The method of claim 1, wherein committing the data access request in a single phase comprises accessing the data without sending and receiving commit queries with any of the secondary nodes.

12. The method of claim 1, further comprising an act of sending the client data access request to a second replica set, the second replica set being in a neighborhood different than the neighborhood of the primary node.

13. The method of claim 12, wherein the primary node'"'"'s neighborhood includes the same nodes as those in the replica set.

14. The method of claim 12, wherein the replica set is requested to handle a first portion of the client data access request and the second replica set is requested to handle a second different portion of the data access request.

15. The method of claim 14, further comprising:

an act of receiving a reply from the replica set corresponding to the first portion of the client data access request;

an act of receiving a reply from the second replica set corresponding the second different portion of the data access request;

an act of combining the replies; and

an act of generating, based on the combined replies, an up-to-date data access response.

16. The method of claim 1, further comprising the primary node receiving a second data access request comprising a read request, and wherein the method further comprises:

an act of the primary node sending the second data access request to the read quorum of nodes;

an act of determining that the primary node failed to contact the read quorum of nodes; and

an act of taking at least one step to perform disaster recovery.

17. The method of claim 1, further comprising the primary node receiving a second data access request comprising a write request, and wherein the method further comprises:

an act of the primary node sending the second data access request to the write quorum of nodes;

an act of determining that the primary node failed to contact the write quorum of nodes; and

an act of initiating a reconfiguration operation to eliminate any failed secondary nodes.

18. The method of claim 1, further comprising the primary node determining that writing the data locally failed, and wherein the method further comprises an act of the primary node initiating a reconfiguration operation to transition to a new primary.

19. The method of claim 1, wherein the act of the primary node sending at least one of the client data access requests including any corresponding data sequence numbers to at least one of the secondary nodes further comprises:

sending a configuration sequence number (CSN) that points to a latest configuration change in the replica set and that is used by the at least one of the secondary nodes to determine at least a failure condition.

20. The method of claim 1, wherein each node in the replica set includes a last used sequence number (LSN) that is used by the primary node to determine a value of the DSN, and that is used by the at least one of the secondary nodes to determine whether to ignore, buffer or accept the at least one of the client data access requests.

21. The method of claim 1, wherein the write quorum defines a different number of secondary nodes than the read quorum.

22. A computer program product comprising one or more computer-readable storage device having thereon computer executable instructions that, when executed by one or more processors of a computing system, cause the computing system to perform a method for participating in a data access transaction within a replica set maintained within a federation infrastructure, the method comprising:

determining that the computing system is a primary node elected from among a plurality of nodes in a replica set of nodes, the primary node being configured to accept and process client data access requests, the replica set comprising the primary node and one or more secondary nodes;

determining that the replica set includes a minimum number of secondary nodes as members based on a maximum number of tolerable simultaneous failures of secondary nodes of the replica set, the act further comprising;

determining that the minimum number of secondary nodes is at least a write quorum defining a minimum number of secondary nodes necessary to perform a request to write data and to provide complete fault tolerance for the maximum number of tolerable simultaneous failures; and

determining that the minimum number of secondary nodes is at least a read quorum defining a minimum number of secondary nodes necessary to provide complete fault tolerance for the maximum number of tolerable simultaneous failures;

receiving one or more client data access requests, each data access request indicating at least a portion of data that is to be accessed on at least the primary node in the replica set, each data access request comprising one of a request to write data to at least a write quorum of nodes in the replica set or a request to read data from at least one of the nodes in the replica set;

assigning a data sequence number (DSN) to each of the client data access requests that mutate state in the order the client data access requests are received, the data sequence numbers comprising a linearized processing order that is to be followed by each of the nodes in the replica set;

sending at least one of the client data access requests including any corresponding data sequence numbers to at least one of the secondary nodes, the sending including sending the data access request to at least the write quorum of nodes when the request is a request to write data, and sending the data access request to at least one of the secondary nodes when the request a request to read data;

receiving, from at least a threshold number of secondary nodes, an acknowledgement indicating reception of the client data access request; and

committing the data access request, the committing including, when the data access request is a write request, verifying that the threshold number of secondary nodes acknowledging reception of the client data access request meets the write quorum of nodes and subsequently writing the data locally at the primary node according to the client data access request, and when the data access request is a read request, reading the data from the at least one of the secondary nodes.

23. The computer program product [storage device] of claim 22, wherein the storage device comprises the computing system having the one or more processors.