Method and system for consistent cluster operational data in a server cluster using a quorum of replicas

• US 6,938,084 B2
• Filed: 07/02/2001
• Issued: 08/30/2005
• Est. Priority Date: 03/26/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gamache, Rod, Lomet, David B., Massa, Michael T., Shrivastava, Sunita, Nishanov, Gor V., Jain, Rohit, Bernstein, Philip A.
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US09/895,810
• Publication Number:
  US 20020161889A1
• Time in Patent Office: 1,520 Days
• Field of Search: 709/219, 709/226, 709/220, 709/223, 709/201, 709/246, 707/10, 707/204, 707/200, 714/13, 714/4
• US Class Current: 709/226
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/181 Eliminating the failing redundant component
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• CPC Class Codes: G06F 11/2023 Failover techniques
• CPC Class Codes: G06F 11/2035 without idle spare hardware

Abstract

A method and system for increasing server cluster availability by requiring at a minimum only one node and a quorum replica set of replica members to form and operate a cluster. Replica members, independent from the nodes, maintain cluster operational data. A cluster operates when one node possesses a majority of replica members, which ensures that any new or surviving cluster includes consistent cluster operational data via at least one replica member from the immediately prior cluster. Arbitration provides exclusive ownership by one node of the replica members, including at cluster formation, and when the owning node fails. Arbitration uses a fast mutual exclusion algorithm and a reservation mechanism to challenge for and defend the exclusive reservation of each member. A quorum replica set algorithm brings members online and offline with data consistency, including updating unreconciled replica members, and ensures consistent read and update operations.

Claims

1. A system for providing consistent operational data of a previous server cluster to a new server duster, comprising, a plurality of nodes, a plurality of replica members, each of the replica members maintaining an epoch number indicative of a state of the cluster operational data, at least one replica member having updated cluster operational data stored thereon by a first node including information indicative of a quorum requirement of a number of replica members needed to form a cluster, and a duster service on a second node configured to 1) obtain control of a replica set of a number of replica members, 2) compare the number of replica members in the replica set with the quorum requirement, 3) form the new server cluster if the quorum requirement is met by the number of replica members in the replica set, and 4) determine which of the replica members of the replica set has data that is most updated.

2. The system of claim 1 wherein the cluster service determines which available replica member of the replica set has the most updated data based on a comparison of the epoch numbers in the available replica members.

3. The system of claim 1 wherein the cluster service determines which available replica member of the replica set has the most updated data based on a comparison of the epoch numbers in the available replica members, and if a determination cannot be made by the comparison, by comparing a sequence number of a record maintained on each of at least two replica members.

4. The system of claim 1 wherein the cluster service prevents updates to the cluster operational data if the number of available replica members falls below the quorum requirement.

5. The system of claim 1 wherein the cluster service terminates the cluster if the number of operational replica members falls below the quorum requirement.

6. The system of claim 1 wherein the second node obtains control of the replica set by arbitrating with at least one other node for control of each replica member.

7. The system of claim 1 wherein each replica member is independent of any node of the server cluster.

8. The system of claim 1 wherein each replica member is independent of any node of the server cluster, and wherein the second node obtains control of the replica set by arbitrating with at least one other node for control of each replica member.

9. A computer-implemented method, comprising:

maintaining cluster operational date on a replica set comprising a plurality of replica members that are each independent of any node of a server cluster;

representing the cluster at a node if the number of replica members controlled by the node comprises at least a majority of the total number of replica members configured to operate in the cluster; and

determining which of the replica members of the replica set has operational data that is most updated, including maintaining an epoch number in association with each replica member, and replicating at least some of that operational data to the other replica members of the replica set.

10. The method of claim 9 wherein the size of each epoch number indicates a relative state of the cluster operational data on its respective replica member, and wherein determining which of the replica members of the replica set has operational data that is most updated includes determining which of the epoch numbers from each member is the largest.

11. The method of claim 10 at least two members have epoch numbers equal the largest epoch number, end wherein determining which of the replica members of the replica set has the most updated operational data includes, maintaining a sequence number in association with the cluster operational data, and determining the largest sequence number from the replica members that have epoch numbers that equal the largest.

12. A computer-implemented method, comprising:

maintaining cluster operational data on a replica set comprising a plurality of replica members that are each independent of any node of a server cluster;

representing the cluster at a node if the number of replica members controlled by the node comprises at least a majority of the total number of replica members configured to operate in the cluster;

determining which of the replica members of the replica set has operational data that is most updated, and replicating at least some of that operational data to the other replica members of the replica set; and

evaluating a last record logged on a replica member to which data is being replicated, against at least one record of the replicated data, to determine whether to discard the last record.

13. The method of claim 12 comprising, evaluating a second-to-last record logged on the replica member to which data is being replicated, against at least one record of the replicated data, to determine whether to discard the second-to-last record.

14. A computer-implemented method, comprising:

maintaining cluster operational data on a replica set comprising a plurality of replica members that are each independent of any node of a server cluster;

representing the cluster at a node if the number of replica members controlled by the node comprises at least a majority of the total number of replica members configured to operate in the cluster;

determining which of the replica members of the replica set has operational data that is most updated, and replicating at least some of that operational data to the other replica members of the replica set; and

detecting the unavailability of a replica member that was operational, determining whether the majority of replica members still exists, and if not, halting updates to the cluster configuration data.

15. The method of claim 14 further comprising, executing a recovery process to attempt to obtain control of a majority of replica members.

16. A computer-implemented method, comprising:

maintaining cluster operational data on a replica set comprising a plurality of replica members that are each independent of any node of a server cluster;

representing the cluster at a node if the number of replica members controlled by the node comprises at least a majority of the total number of replica members configured to operate in the cluster, wherein the node controls the majority of replica members by arbitrating for exclusive ownership of each member, including, issuing a reset command, delaying for a period of time, and issuing a reserve command; and

determining which of the replica members of the replica set has operational data that is most updated, and replicating at least some of that operational data to the other replica members of the replica set.

17. A computer-implemented method, comprising:

maintaining cluster operational data on a replica set comprising a plurality of replica members that are each independent of any node of a server cluster;

representing the cluster at a node if the number of replica members controlled by the node comprises at least a majority of the total number of replica members configured to operate in the cluster, wherein the node controls the majority of replica members by arbitrating for exclusive ownership of each member, including, issuing a reset command; and

determining which of the replica members of the replica set has operational data that is most updated, and replicating at least some of that operational data to the other replica members of the replica set.

18. A computer-implemented method of operating a server cluster of at least three nodes, comprising:

storing cluster operational data on a replica set of at least one replica member, each replica member being independent from any node;

at a first node, arbitrating with at least two other nodes for control of the replica set, the arbitration being performed for each replica member and comprising, attempting to obtain a right to exclusively reserve that replica member wherein attempting to obtain a right to exclusively reserve that replica member includes, attempting to write a unique identifier to a location on the replica member, delaying, and reading from the location to determine whether the unique identifier is unchanged, and if the attempt is successful, exclusively reserving that replica member; and

representing the cluster at the first node if the replica set is controlled thereby and has consistent cluster operational data with respect to a previous cluster.

19. A computer-implemented method of operating a server cluster of at least three nodes, comprising:

storing cluster operational data on a replica set of at least one replica member, each replica member being independent from any node;

at a first node, arbitrating with at least two other nodes for control of the replica set, the arbitration being performed for each replica member and comprising, attempting to obtain a right to exclusively reserve that replica member, and if the attempt is successful, exclusively reserving that replica member, wherein arbitrating for each replica member includes, issuing a reset command for the replica member, delaying for a period of time, and issuing a reserve command for the replica member; and

representing the cluster at the first node if the replica set is controlled thereby and has consistent cluster operational data with respect to a previous cluster.

20. A computer-readable medium having computer-executable instructions, comprising:

representing a cluster by obtaining exclusive control of a majority of replica members in an available set thereof;

detecting a status change of one replica member with respect to the available set; and

taking action in response to the changed status to ensure that the replica members are consistent with respect to any update logged thereto, wherein taking action in response to the changed status comprises running a recovery process to make the replica members consistent including increasing an epoch number maintained on each available replica member.

21. A computer-readable medium having computer-executable instructions, comprising:

representing a cluster by obtaining exclusive control of a majority of replica members in an available set thereof;

detecting a status change of one replica member with respect to the available set; and

taking action in response to the changed status to ensure that the replica members are consistent with respect to any update logged thereto, wherein taking action in response to the changed status comprises running a recovery process to make the replica members consistent including looking for a non-committed update that was not committed before a subsequent committed update on at least one available replica member, and discarding each such non-committed update found.

22. A computer-readable medium having computer-executable instructions, comprising:

representing a cluster by obtaining exclusive control of a majority of replica members in an available set thereof, wherein a majority of replica members does not still exist;

detecting a status change of one replica member with respect to the available set; and

taking action in response to the changed status to ensure that the replica members are consistent with respect to any update logged thereto, wherein taking action in response to the changed status further includes preventing updates from being written to replica members that remain available.

23. A computer-readable medium having computer-executable instructions, comprising:

representing a cluster by obtaining exclusive control of a majority of replica members in an available set thereof;

detecting a status change of one replica member with respect to the available set, wherein detecting a status change includes attempting to write an update to each available replica member, receiving success or failure information for each attempted write, and determining whether a majority of replica members still exists by evaluating a number of successful writes against a number required for a majority; and

taking action in response to the changed status to ensure that the replica members are consistent with respect to any update logged thereto.

24. A computer-readable medium having computer-executable instructions, comprising:

representing a cluster by obtaining exclusive control of a majority of replica members in an available set thereof;

detecting a status change of one replica member with respect to the available set, wherein detecting a status change includes attempting to write an update to each available replica member, receiving success or failure information for each attempted write, determining whether a majority of replica members still exists by evaluating a number of successful writes against a number required for a majority, and reporting that the update succeeded if the number of successful writes is greater than or equal to the number required for a majority; and

taking action in response to the changed status to ensure that the replica members are consistent with respect to any update logged thereto.

25. A computer-readable medium having computer-executable instructions, comprising:

representing a cluster by obtaining exclusive control of a majority of replica members in an available set thereof;

detecting a status change of one replica member with respect to the available set;

taking action in response to the changed status to ensure that the replica members are consistent with respect to any update logged thereto; and

preventing further updates unless the number of successful writes is greater than or equal to the number required for a majority.