Data consistency within a federation infrastructure

• US 8,990,434 B2
• Filed: 08/30/2011
• Issued: 03/24/2015
• Est. Priority Date: 11/09/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hasha, Richard L., Xun, Lu, Kakivaya, Gopala Krishna R., Malkhi, Dahlia
• Primary Examiner(s): TODD, GREGORY G
• Application Number:
  US13/221,635
• Publication Number:
  US 20120036237A1
• Time in Patent Office: 1,302 Days
• Field of Search: 709/224, 709/226, 709/251, 714/4.11, 707/627, 707/636, 707/637, 707/634
• 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

Embodiments include establishing and maintaining a consistent replica set within the federation infrastructure. A replica set, including a primary node and secondary nodes, is established from among nodes in a ring of nodes. An occurrence of a replica set configuration event affecting at least one of the replica set members is indicated. Based on the indication and based on a type of the replica set configuration event, it is determined that the replica set is to be reconfigured. The replica set is reconfigured according to a reconfiguration appropriate for the type of the replica set configuration event.

Claims

1. 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 the 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 replica set members an existing primary node and one or more secondary nodes, each replica set member storing at least;

a configuration sequence number (CSN) that points to a latest configuration change in the replica set,

a last used sequence number (LSN) that is incremented by each node with each write and reconfiguration operation, and

data stored in the replica set;

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

based on the received indication and based on a type of the replica set configuration event, an act of determining that the replica set is to be reconfigured, reconfiguration including;

when the type of the replica set configuration event is a failure of an existing secondary node, removing the existing secondary node from the replica set,

when the type of the replica set configuration event is a node joining the replica set, adding a new secondary node to the replica set,

when the type of the replica set configuration event is a failure of the existing primary node, abruptly transitioning from the existing primary node to a new primary node through the new primary node performing the abrupt transition without orchestrating the abrupt transition with the existing primary node, including the new primary node bringing each of the one or more secondary nodes current with respect to the latest replica data and the new primary node removing the existing primary node from the replica set, and

when the type of the replica set configuration event is a departure of the existing primary node, smoothly transitioning from the existing primary node to the new primary node through the new primary node orchestrating the smooth transition with the existing primary node, including;

the new primary node contacting one or more of the secondary nodes, to instruct each contacted secondary node to transfer replica data to the new primary node;

simultaneous to contacting the one or more of the secondary nodes, the new primary node instructing the existing primary node to forward new operations to the new primary node; and

after completing the transfer of replica data from each contacted secondary node, the new primary node instructing the existing primary node to initiate a configuration change to make the new primary node the current primary of the replica set; and

an act of reconfiguring the replica set according to a reconfiguration appropriate for the type of the replica set configuration event, including reconfiguring the replica set based on a comparison of the stored CSN and the stored LSN of at least one replica set member.

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

3. The method of claim 1, further comprising:

an act of the existing 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 the replica set members;

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

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

4. The method of claim 1, further comprising:

an act of detecting, based on configuration state information, that one or more replica set reconfigurations are in progress.

5. The method of claim 1, wherein the reconfiguration appropriate for the type of to the replica set configuration event is determined based on a user-defined configuration.

6. The method of claim 1, wherein abruptly transitioning from the existing primary node to the new primary node includes:

an act of electing the new primary node according to a leader election algorithm;

an act of the new primary node contacting each of the secondary nodes to determine which of the secondary nodes have latest replica data, including identifying a corresponding CSN and LSN for each secondary node and using the corresponding CSN and LSN to determine which secondary nodes have the latest replica data;

an act of the new primary node building a new replica configuration; and

an act of the new primary node communicating the new replica configuration to each of the secondary nodes.

7. The method of claim 1, wherein smoothly transitioning from the existing primary node to the new primary node includes:

an act of electing the new primary node according to a leader election algorithm;

prior to the secondary nodes reporting to the new primary node that they have transferred the replica data to the new primary node, an act of the new primary node forwarding any client operations to the existing primary node; and

wherein the new primary node instructs the existing primary node to initiate a configuration change to make the new primary node the current primary of the replica set subsequent to the secondary nodes reporting to the new primary node that they have transferred the replica data to the new primary node.

8. The method of claim 1, wherein removing the existing secondary node from the replica set includes:

an act of the existing primary node blocking incoming client operations; and

an act of the existing primary node installing a new replica configuration locally by removing the existing secondary node from the replica set and assigning the new replica configuration a CSN, including atomically incrementing a LSN associated with the new replica configuration; and

an act of the existing primary node communicating the new replica configuration to all of the secondary nodes.

9. The method of claim 1, wherein adding a new secondary node to the replica set includes:

an act of a new secondary node simultaneously instructing each secondary node to transfer replica data to the new secondary node and instructing the existing primary node to forward new operations to the new secondary node; and

subsequent to one or more of the secondary nodes reporting to the new secondary node that they have transferred the replica data to the new secondary node, the new secondary node contacting the existing primary node to request that the existing primary node add the new secondary node to the replica set.

10. The method of claim 1, wherein each replica set member also stores an identity of the replica set and an identity of each replica set member.

11. One or more computer storage devices having stored thereon computer-executable instructions that, when executed, cause one or more processors of a computer system to implement a method for establishing and maintaining a consistent replica set within a federation infrastructure, including the following:

establishing a replica set from among a plurality of nodes in a ring of nodes, the replica set comprising as replica set members an existing primary node and one or more secondary nodes, each replica set member storing at least;

a configuration sequence number (CSN) that points to a latest configuration change in the replica set,

a last used sequence number (LSN) that is incremented by each node with each write and reconfiguration operation, and

data stored in the replica set;

determining that the replica set is to be reconfigured based at least in part on a replica set configuration event occurrence affecting at least one of the replica set members, reconfiguration including;

when the type of the replica set configuration event is a failure of an existing secondary node, removing the existing secondary node from the replica set,

when the type of the replica set configuration event is a node joining the replica set, adding a new secondary node to the replica set,

when the type of the replica set configuration event is a failure of the existing primary node, abruptly transitioning from the existing primary node to a new primary node through the new primary node performing the abrupt transition without orchestrating the abrupt transition with the existing primary node, including the new primary node bringing each of the one or more secondary nodes current with respect to the latest replica data and the new primary node removing the existing primary node from the replica set, and

when the type of the replica set configuration event is a departure of the existing primary node, smoothly transitioning from the existing primary node to the new primary node through the new primary node orchestrating the smooth transition with the existing primary node, including;

the new primary node contacting one or more of the secondary nodes, to instruct each contacted secondary node to transfer replica data to the new primary node;

simultaneous to contacting the one or more of the secondary nodes, the new primary node instructing the existing primary node to forward new operations to the new primary node; and

after completing the transfer of replica data from each contacted secondary node, the new primary node instructing the existing primary node to initiate a configuration change to make the new primary node the current primary of the replica set; and

reconfiguring the replica set according to a reconfiguration appropriate for the type of the replica set configuration event, including reconfiguring the replica set based on a comparison of the stored CSN and the stored LSN of at least one replica set member.

12. The one or more computer storage devices of claim 11, further comprising:

receiving, at the existing primary node, 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 the replica set members;

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

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

13. The one or more computer storage devices of claim 11, wherein abruptly transitioning from the existing primary node to the new primary node includes:

electing the new primary node according to a leader election algorithm;

the new primary node contacting each of the secondary nodes to determine which of the secondary nodes have latest replica data, including identifying a corresponding CSN and LSN for each secondary node and using the corresponding CSN and LSN to determine which secondary nodes have the latest replica data;

the new primary node building a new replica configuration; and

the new primary node communicating the new replica configuration to each of the secondary nodes.

14. The one or more computer storage devices of claim 11, wherein smoothly transitioning from the existing primary node to the new primary node includes:

electing the new primary node according to a leader election algorithm;

prior to the secondary nodes reporting to the new primary node that they have transferred the replica data to the new primary node, the new primary node forwarding any client operations to the existing primary node; and

wherein the new primary node instructs the existing primary node to initiate a configuration change to make the new primary node the current primary of the replica set subsequent to the secondary nodes reporting to the new primary node that they have transferred the replica data to the new primary node.

15. The one or more computer storage devices of claim 11, wherein removing the existing secondary node from the replica set includes:

the existing primary node blocking incoming client operations; and

the existing primary node installing a new replica configuration locally by removing the existing secondary node from the replica set and assigning the new replica configuration a CSN by atomically incrementing the new replica configuration a LSN; and

the existing primary node communicating the new replica configuration to all of the secondary nodes.

16. A computer system, comprising:

one or more processors; and

one or more computer storage media having stored thereon computer-executable instructions that, when executed, cause the one or more processors of to implement a method for establishing and maintaining a consistent replica set within a federation infrastructure, including the following;

establishing a replica set from among a plurality of nodes in a ring of nodes, the replica set comprising as replica set members an existing primary node and one or more secondary nodes, each replica set member storing at least;

a configuration sequence number (CSN) that points to a latest configuration change in the replica set,

a last used sequence number (LSN) that is incremented by each node with each write and reconfiguration operation, and

data stored in the replica set;

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

based on the received indication and based on a type of the replica set configuration event, determining that the replica set is to be reconfigured, reconfiguration including;

when the type of the replica set configuration event is a failure of an existing secondary node, removing the existing secondary node from the replica set,

when the type of the replica set configuration event is a node joining the replica set, adding a new secondary node to the replica set,

when the type of the replica set configuration event is a failure of the existing primary node, abruptly transitioning from the existing primary node to a new primary node through the new primary node performing the abrupt transition without orchestrating the abrupt transition with the existing primary node, including the new primary node bringing each of the one or more secondary nodes current with respect to the latest replica data and the new primary node removing the existing primary node from the replica set, and

when the type of the replica set configuration event is a departure of the existing primary node, smoothly transitioning from the existing primary node to the new primary node through the new primary node orchestrating the smooth transition with the existing primary node, including;

the new primary node contacting one or more of the secondary nodes, to instruct each contacted secondary node to transfer replica data to the new primary node;

simultaneous to contacting the one or more of the secondary nodes, the new primary node instructing the existing primary node to forward new operations to the new primary node; and

after completing the transfer of replica data from each contacted secondary node, the new primary node instructing the existing primary node to initiate a configuration change to make the new primary node the current primary of the replica set,

the computer-executable instructions being configured for performing a plurality of reconfigurations, including the removing of the existing secondary node from the replica set, adding the new secondary node to the replica set, abruptly transitioning to the new primary node, as well as smoothly transitioning to the new primary node; and

reconfiguring the replica set according to a reconfiguration that corresponds to the type of the replica set configuration event, including reconfiguring the replica set based on a comparison of the stored CSN and the stored LSN of at least one replica set member.