CONSISTENT CLUSTER OPERATIONAL DATA IN A SERVER CLUSTER USING A QUORUM OF REPLICAS

• US 20110238842A1
• Filed: 06/08/2011
• Published: 09/29/2011
• Est. Priority Date: 03/26/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nishanov, Gor N., Gamache, Rod N., Jain, Rohit, Doshi, Rushabh A., Bernstein, Philip A., Lomet, David B., Dion, David A., Massa, Michael T., Das, Rajsekhar, Shrivastava, Sunita
• Granted Patent: US 8,850,018 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• 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
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency

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 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 method comprising replicating, by a computer, cluster operational data from a replica of a cluster that has a highest sequence number of sequence numbers of various replicas of the cluster, each of the various replicas of the cluster having an equally highest epoch number of epoch numbers of available replicas of the cluster, the available replicas comprising the various replicas and the replica.

2. The method of claim 1 further comprising initializing, prior to the replicating, a log from each of the available replicas of the cluster.

3. The method of claim 2 further comprising determining, in response to the initializing, the equally highest epoch number of the epoch numbers of available replicas of the cluster.

4. The method of claim 3 further comprising:

establishing, based on the determining, a current replica number based on the equally highest epoch number; and

updating the log of each of the available replicas of the cluster with the current replica number.

5. The method of claim 4 further comprising selecting, in response to the determining, the replica as a leader replica based on the replica having the equally highest epoch number and the highest sequence number.

6. The method of claim 5 wherein the replicating includes the leader replica propagating the cluster operational data to each of the available replicas that do not already have the cluster operational data.

7. The method of claim 6 further comprising generating, in response to the replicating, a commit notification that indicates that the available replicas are consistent with the leader replica.

8. At least one computer-readable media storing computer-executable instruction that, when executed by a computer, cause the computer to perform a method comprising replicating cluster operational data from a replica of a cluster that has a highest sequence number of sequence numbers of various replicas of the cluster, each of the various replicas of the cluster having an equally highest epoch number of epoch numbers of available replicas of the cluster, the available replicas comprising the various replicas and the replica.

9. The at least one computer-readable media of claim 8, the method further comprising initializing, prior to the replicating, a log from each of the available replicas of the cluster.

10. The at least one computer-readable media of claim 9, the method further comprising determining, in response to the initializing, the equally highest epoch number of the epoch numbers of available replicas of the cluster.

11. The at least one computer-readable media of claim 10, the method further comprising:

establishing, based on the determining, a current replica number based on the equally highest epoch number; and

updating the log of each of the available replicas of the cluster with the current replica number.

12. The at least one computer-readable media of claim 11, the method further comprising selecting, in response to the determining, the replica as a leader replica based on the replica having the equally highest epoch number and the highest sequence number.

13. The at least one computer-readable media of claim 12 wherein the replicating includes the leader replica propagating the cluster operational data to each of the available replicas that do not already have the cluster operational data.

14. The at least one computer-readable media of claim 13, the method further comprising generating, in response to the replicating, a commit notification that indicates that the available replicas are consistent with the leader replica.

15. A system comprising a computer configured for replicating cluster operational data from a replica of a cluster that has a highest sequence number of sequence numbers of various replicas of the cluster, each of the various replicas of the cluster having an equally highest epoch number of epoch numbers of available replicas of the cluster, the available replicas comprising the various replicas and the replica.

16. The system of claim 15, the computer configured for comprising initializing, prior to the replicating, a log from each of the available replicas of the cluster.

17. The system of claim 16, the computer configured for determining, in response to the initializing, the equally highest epoch number of the epoch numbers of available replicas of the cluster.

18. The system of claim 17, the computer configured for establishing, based on the determining, a current replica number based on the equally highest epoch number and for updating the log of each of the available replicas of the cluster with the current replica number.

19. The system of claim 18, the computer configured for selecting, in response to the determining, the replica as a leader replica based on the replica having the equally highest epoch number and the highest sequence number and for generating, in response to the replicating, a commit notification that indicates that the available replicas are consistent with the leader replica.

20. The system of claim 19 wherein the replicating includes the leader replica propagating the cluster operational data to each of the available replicas that do not already have the cluster operational data.