Consistent cluster operational data in a server cluster using a quorum of replicas

• US 7,774,469 B2
• Filed: 09/12/2005
• Issued: 08/10/2010
• Est. Priority Date: 03/26/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dion, David A., Bernstein, Philip A., Shrivastava, Sunita V., Lomet, David B., Massa, Michael T., Das, Rajsekhar, Gamache, Rod N., Nishanov, Gor V., Jain, Rohit, Doshi, Rushabh
• Primary Examiner(s): Avellino; Joseph E
• Assistant Examiner(s): Thiaw; Catherine
• Application Number:
  US11/225,222
• Publication Number:
  US 20060090095A1
• Time in Patent Office: 1,793 Days
• Field of Search: 709220-229, 714 1- 9, 707 1- 9
• 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 computer-implemented method, comprising:

maintaining operational data of a cluster on a replica set comprising a plurality of replica members that includes at least one independent replica member that is a device that is not integral to any node of the cluster and wherein the at least one independent replica member is configured to be online in the replica set regardless of how many of the any nodes are operable in the cluster and wherein each of the replica members can be controlled by only one of the any nodes at a time and wherein each of the replica members is a device configured to maintain a replica of the operational data of the cluster;

maintaining an epoch number in association with each replica member, wherein a value of each epoch number indicates a relative state of the cluster operational data on its respective replica member, and wherein at least two replica members have epoch numbers that equal a largest epoch number;

maintaining a sequence number in association with each replica member;

representing the cluster if a number of replica members exclusively owned and controlled by the only one of the any nodes comprises at least a majority of a total number of replica members of the replica set;

determining which of the replica members has operational data that is most updated, wherein the determining includes determining that the at least two replica members have epoch numbers that equal the largest epoch number and determining which of the at least two replica members have a sequence number that equals a largest sequence number; and

replicating at least some of that operational data by the only one of the any nodes to the other replica members of the replica set wherein others of the any nodes access the operational data of the cluster only through the only one of the any nodes.

2. The method of claim 1 further comprising, 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.

3. The method of claim 2 further 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.

4. The method of claim 1 further comprising,

detecting availability of a new replica member that is configured to operate in the cluster;

and

reconciling the cluster operational data of the new replica member.

5. The method of claim 1 further comprising,

detecting the unavailability of a replica member that was operational;

and

determining whether the majority of replica members are operational and, if not, halting updates to the cluster configuration data and executing a recovery process to attempt to obtain control of a majority of replica members.

6. The method of claim 1 wherein, maintaining the cluster operational data includes storing information indicative of a total number of replica members configured in the cluster and/or storing state of at least one other storage device of the cluster.

7. The method of claim 1 wherein, the replica set comprising a plurality of replica members includes at least one local replica member and at least one independent replica member.

8. A clustering system comprised of:

a first node of a plurality of nodes, the first node including a first local replica member of a replica set;

a second node of the plurality of nodes, the second node including a second local replica member of the replica set;

an independent replica member of the replica set wherein the independent replica member is a device that is not integral to any node of the plurality of nodes of the clustering system and wherein the independent replica member is configured to be online in the replica set regardless of the how many of the nodes of the plurality of nodes are operable in the clustering system and wherein the independent replica member can be controlled by only one node of the plurality of nodes at a time, and wherein each of the replica members of the replica set is a device configured to maintain a replica of operational data of the clustering system;

the first node and the second node and the independent replica member coupled together forming the clustering system; and

the first local replica member and the second local replica member and the independent replica member exclusively owned and controlled by the only one node of the plurality of nodes and forming a quorum replica set wherein others of the plurality of nodes access the operational data of the clustering system only through the only one node.

9. The clustering system of claim 8 wherein, the quorum replica set is comprised of the first local replica member and the second local replica member in the event that the independent replica member fails to operate.

10. The clustering system of claim 8 wherein, the quorum replica set is comprised of the independent replica member and the first local replica member in the event that the second local replica member fails to operate.