DATA CONSISTENCY WITHIN A FEDERATION INFRASTRUCTURE

• US 20080288646A1
• Filed: 11/07/2007
• Published: 11/20/2008
• Est. Priority Date: 11/09/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malkhi, Dahlia, Hasha, Richard L., Kakivaya, Gopala Krishna R., Xun, Lu
• Granted Patent: US 8,090,880 B2
• Time in Patent Office: Days
• US Class Current: 709/228
• 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 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;

an act of the primary node assigning a data sequence number 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;

as 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 accessing the data according to the client data access request.

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 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, further comprising an act of determining the number of secondary nodes to be members of the replica set based on a maximum number of tolerable simultaneous failures.

6. The method of claim 5, 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.

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

8. The method of claim 1, wherein the threshold number of secondary nodes represents a quorum.

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

10. The method of claim 8, further comprising receiving from each member of the 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 LSN.

11. 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 LSN, CSN, DSN, primary node identity and secondary node identities.

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

13. 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.

14. 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.

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

16. The method of claim 14, 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.

17. The method of claim 16, 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.

18. In a federation infrastructure of a ring of nodes configured for bi-directional routing, a system for accessing data from a replica set within a federation infrastructure, the system comprising:

a neighborhood establishing module configured to establish a neighborhood of a plurality of nodes on the ring, the neighborhood including at least an immediately adjacent predecessor node and an immediately adjacent successor node;

an intent determining module configured to determine that a joining node outside the established neighborhood has indicated an intent to join the established neighborhood in the ring of nodes;

a consistency maintaining module configured to maintain consistency within the established neighborhood such that each node in the plurality of nodes takes id-space ownership for a portion of id-space in the neighborhood;

an election determining module configured to determine that one of the nodes in the plurality of nodes has been elected to be a primary node with responsibility over a replica set of nodes configured to respond to client data access requests as directed by the primary node;

a request receiving module configured to receive 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 one of the nodes in the replica set; and

a data accessing module configured to access the data indicated in the client data access request.

19. The system of claim 18, wherein the data accessing module is configured to write data according to a client data write request.

20. The system of claim 19, wherein the primary node instructs a secondary node to write the data indicated in the client data write request to a data store managed by the secondary node.

21. The system of claim 19, wherein the primary node replicates the write request to one or more secondary nodes in two phases.

22. The system of claim 18, wherein the data accessing module is configured to read data according to a client data read request.

23. The system of claim 22, wherein the client data read request is directly handled by a secondary node.

24. The system of claim 18, wherein the data that is to be accessed comprises the state backing a service.

25. The system of claim 18, wherein the established neighborhood of a primary is the set of secondary nodes of a replica set of that primary.

26. The system of claim 18, wherein the service is a lock manager.

27. The system of claim 18, wherein the service is a producer-consumer queue.

28. The system of claim 18, wherein the system maintains ACID properties for all data in the replica set.

29. In a federation infrastructure of a ring of nodes configured for bi-directional routing, a method for establishing and maintaining a consistent replica set within a federation infrastructure, the method comprising:

an act of establishing a replica set from among a plurality of nodes in a ring of nodes, the replica set comprising as members a primary node and one or more secondary nodes;

an act of receiving an indication indicating a replica set configuration event occurrence affecting at least one of the replica set members;

based on the received indication, an act of determining that the replica set is to be reconfigured, the reconfiguration including at least one of removing an existing secondary node from the replica set, adding a new secondary node to the replica set, abruptly transitioning to a new primary and smoothly transitioning to a new primary, based on the replica set configuration event occurrence;

an act of reconfiguring the replica set according to the reconfiguration corresponding to the replica set configuration event.

30. The method of claim 29, wherein the replica set configuration comprises at least one of a node failure within the replica set, a node departure from the replica set, and a node joining the replica set.

31. The method of claim 30, wherein the configuration event occurs during a client data access request.

32. The method of claim 29, further comprising an act of maintaining a portion of data storage controlled by one or more of the replica set nodes.

33. The method of claim 32, further comprising:

an act of the primary node receiving a client data access request, the client data access request including an indication of information that is to be accessed on at least one node within a replica set of nodes;

an act of detecting that the primary node failed to access at least a portion of information indicated in the received client data access request;

an act of the primary node removing itself from the replica set such that information stored on the primary node is prevented from being accessed in response to the client data access request.

34. The method of claim 29, further comprising an act of detecting, based on the configuration state information, one or more replica set reconfigurations in progress.

35. The method of claim 29, further comprising an act of electing a new primary node for the replica set.