Method and system for establishing a quorum for a geographically distributed cluster of computers

One embodiment of the present invention provides a system that facilitates establishing a quorum for a cluster of computers that are geographically distributed. The system operates by detecting a change in membership of the cluster. Upon detecting the change, the system forms a potential new cluster by attempting to communicate with all other computers within the cluster. The system accumulates votes for each computer successfully contacted. The system also attempts to gain control of a quorum server located at a site separate from all computers within the cluster. If successful at gaining control, the system accumulates the quorum server's votes as well. If the total of accumulated votes is a majority of the available votes, the system forms a new cluster from the potential new cluster.

BACKGROUND

1. Field of the Invention

The present invention relates to computer clusters. More specifically, the present invention relates to a method and system for establishing a quorum for a geographically distributed computer cluster.

2. Related Art

Corporate intranets and the Internet are coupling more and more computers together to provide computer users with an ever-widening array of services. Many of these services are provided through the client-server model in which a client communicates with a server to have the server perform an action for the client or provide data to the client. A server may have to provide these services to many clients simultaneously and, therefore, must be fast and reliable.

In an effort to provide speed and reliability within servers, designers have developed clustering systems for the servers. Clustering systems couple multiple computers—also called computing nodes or simply nodes—together to function as a single unit. It is desirable for a cluster to continue to function correctly even when a node has failed or the communication links between the nodes have failed.

In order to accomplish this, nodes of a cluster typically send “heartbeat” messages to each other regularly over private communication links. Failure to receive a heartbeat message from a node for a period of time indicates that either the node has failed or the communication links to the node have failed.

In the event of a failure, the remaining nodes can perform a recovery procedure to allow operations to continue without the failed node. By continuing operations without the failed node, the cluster provides higher availability. Note that when a failure of a node is detected, the surviving nodes must come to an agreement on the cluster membership.

Failures of communication links can cause two problems: “split-brain” and “amnesia,” which can be viewed as partitions in space and partitions in time, respectively. The split-brain problem occurs if a communication failure partitions the cluster into two (or more) functioning sub-groups. Each sub-group will not be able to receive heartbeat messages from the nodes in other sub-groups. Potentially, each sub-group could decide that the nodes in the other sub-group have failed, take control of devices normally belonging to the other sub-group, and restart any applications that were running on the other sub-group. The result is that two different sub-groups are trying to control the same devices and run the same applications. This can cause data corruption if one sub-group overwrites data belonging to the other sub-group and application-level corruption because the applications in each sub-group are unaware that another copy of the application is running.

The amnesia problem occurs if one sub-group makes data modifications while the nodes in another sub-group have failed. If the cluster is then restarted with the failed sub-group running and the formerly operational sub-group not running, the data modifications can potentially disappear.

A standard solution to the split-brain problem is to provide a quorum mechanism. Each node in a cluster is assigned a number of votes. All of the operational nodes within a sub-group pool their votes and if the sub-group has a majority of votes it is permitted to form a new cluster and continue operation. For example, in a three-node cluster, each node can be given one vote. If the cluster is partitioned by a network failure into a two-node sub-group and a one-node sub-group, the two-node sub-group has two votes and the one-node sub-group has one vote. Only the two-node sub-group will be permitted to form a new cluster, while the one-node sub-group will cease operation.

With a two-node cluster, it is desired that either node can continue operation if the other node fails. However, the quorum mechanism described above does not permit either node to function alone. If each node has one vote, neither node running alone can achieve a quorum majority. Majority can be attained if, for example, one node gets two votes and the other gets one. This solution allows only the former node to run alone, but will prevent the latter from running alone.

A solution to the two-node quorum problem is to introduce a quorum device, which can be viewed as a vote “tie-breaker.” For example, a disk drive, which supports small computer system interface (SCSI) reservations, can be used for a quorum device. The SCSI reservation mechanism allows one node to reserve the disk drive. The other node can then detect that the disk drive has been reserved. In operation, the quorum device is assigned an additional vote. If a network failure partitions the cluster, both nodes will attempt to reserve the SCSI disk. The node that succeeds will obtain the additional vote of the quorum device and will have two out of three votes and will become the surviving cluster member. The other node will have only one vote and thus will not become a cluster member.

Note that the link from a node to the quorum device must be independent of the link between nodes. Otherwise, a single link failure could cause failure of both inter-node communication and communication with the quorum device. In this case, neither node would be able to get two votes and the cluster, as a whole, would fail.

To prevent amnesia, each node keeps a copy of state data. When nodes join a cluster, they get up-to-date state data from the other nodes in the cluster. By requiring a majority of votes, the new cluster will have at least one node that was in the previous cluster, therefore ensuring up-to-date state data within the new cluster.

The previous discussion has assumed that the nodes of the cluster are located physically near each other, so that the nodes can be coupled to each other and to the quorum device through separate links. However, in many cases users wish to have a two-node cluster with nodes that are widely separated, by potentially thousands of miles, in order to provide reliability in the event of a local disaster. This separation poses problems for the quorum configuration. If the quorum device is located with either node, a disaster at that site could destroy both the node and the quorum device, effectively preventing the other node from taking control. In addition, connecting a quorum device such as a SCSI disk over these long distances can be extremely expensive or impossible.

What is needed is a method and system that establishes a quorum for a geographically distributed cluster of computers that eliminates the problems presented above.

SUMMARY

One embodiment of the present invention provides a system that facilitates establishing a quorum for a cluster of computers that are geographically distributed. The system operates by detecting a change in membership of the cluster. Upon detecting the change, the system forms a potential new cluster by attempting to communicate with all other computers within the cluster. The system accumulates votes for each computer successfully contacted. The system also attempts to gain control of a quorum server located at a site separate from all computers within the cluster. If successful at gaining control, the system accumulates the quorum server's votes as well. If the total of accumulated votes is a majority of the available votes, the system forms a new cluster from the potential new cluster.

In one embodiment of the present invention, the system exchanges heartbeat messages with all other computers that are part of the cluster. Upon discovering an absence of heartbeat messages from any computer in the cluster, the system initiates a cluster membership protocol.

In one embodiment of the present invention, detecting the change in cluster membership includes detecting that the cluster has not been formed.

In one embodiment of the present invention, attempting to gain control of the quorum server involves communicating with the quorum server using cryptographic techniques.

In one embodiment of the present invention, the system exchanges a status message with each member of the new cluster. The system updates the local status of the computer to the most recent status available within the status messages.

One embodiment of the present invention provides a system that facilitates establishing a quorum for a cluster of computers that are geographically distributed. The system provides a quorum server at a site separate from a location of any computer within the cluster. The system assigns at least one vote to each computer within the cluster. The system also assigns at least one vote to the quorum server. In operation, the system attempts to establish communications between each pair of computers within the cluster. A count of votes is accumulated at each computer for each computer that responds. The system also attempts to establish control over the quorum server from each computer within the cluster. If control is established over the quorum server, the quorum server's votes are accumulated in the count of votes. The system establishes a quorum when a majority of available votes has been accumulated in the count of votes.

In one embodiment of the present invention, the quorum server grants control to only a first computer attempting to establish control.

In one embodiment of the present invention, the quorum server grants control to only one computer of all computers attempting to establish control based on a pre-established priority list.

In one embodiment of the present invention, votes are assigned so that the quorum includes at least one computer that was in an immediately previous cluster, to ensure that a cluster formed from the quorum has current data.

In one embodiment of the present invention, attempting to establish control over the quorum server involves establishing communications with the quorum server.

In one embodiment of the present invention, establishing communications with the quorum server involves using cryptographic techniques to deter attacks.

DETAILED DESCRIPTION

Computer Cluster

FIG. 1illustrates a geographically distributed cluster of computers coupled together in accordance with an embodiment of the present invention. Computers102and104form a cluster of computers that operate in concert to provide services and data to users. Two or more computers are formed into a cluster to provide speed and reliability for the users. Computers102and104are located in geographic areas120and122respectively. Geographic areas120and122are widely separated, possibly by thousands of miles, in order to provide survivability for the cluster in case of a local disaster at geographic area120or122. For example, geographic area120may be located in California, while geographic area122may be located in New York.

Computers102and104can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance.

Computers102and104communicate across private network108. Private network108may include at least two independent links of communication between computers102and104to provide redundancy to allow uninterrupted communications in case one of the links fails. Private network108can generally include any type of wire or wireless communication channel capable of coupling together computing nodes. This includes, but is not limited to, a local area network, a wide area network, or a combination of networks.

Computers102and104are also coupled to public network110to allow communication with users. Public network110can generally include any type of wire or wireless communication channel capable of coupling together computing nodes. This includes, but is not limited to, a local area network, a wide area network, or a combination of networks. In one embodiment of the present invention, public network110includes the Internet.

Quorum server106provides quorum services to computers102and104. Additionally, quorum server106can provide quorum services to other clusters of computers independent of computers102and104. Quorum server106is located in geographic area124, which is separate from geographic areas120and122. For example, geographic area124may be located in Illinois.

Quorum server106can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, a computational engine within an appliance, and a cluster of computers. There may also be multiple quorum servers at different sites.

Computers102and104communicate with quorum server106across communication links116and118respectively. Communication links116and118can be low bandwidth communication links such as dial-up modem connections. Communication links116and118are typically used only during configuration or re-configuration of the cluster. These links may also be the same network as public network110, e.g., the Internet.

Cluster Failures

FIG. 2is a flowchart illustrating the process of detecting and processing a failure within a cluster in accordance with an embodiment of the present invention. The system starts when a computer, say computer102, exchanges a heartbeat message with every other node in the cluster (step202). Next, computer102checks for a failure to receive heartbeats via one of the links on private network108(step204). If there are no link failures, the process returns to202to repeat exchanging heartbeat messages.

If computer102detects a failure in the links to another node on private network108, computer102determines if all links to the other node have failed to provide heartbeats (step206). If all links to the other node have not failed, the process returns to202to repeat exchanging heartbeat messages. Otherwise, either all links have failed, or the other node has failed.

If computer102detects that all links to the other node have failed to provide heartbeats, computer102attempts to exchange messages with other communicating nodes to initiate a cluster membership protocol (step208). The surviving nodes then co-operate to determine membership for a new cluster (step210). Details of determining membership for the new cluster are described below in conjunction withFIG. 3.

After determining cluster membership, computer102determines if computer102was excluded from membership (step212). If computer102was excluded from membership, computer102shuts down (step214). Otherwise, computer102reconfigures (step216). Details of how computer102reconfigures are described below in conjunction withFIG. 5. The reconfiguration algorithm ensures that each computer reaches consistent membership decisions, therefore, each computer will either be part of the new cluster or will shut down.

Determining Cluster Membership

FIG. 3is a flowchart illustrating the process of determining cluster membership in accordance with an embodiment of the present invention. The system starts when a computer, for example computer102, attempts to take control of quorum server106(step302). Whether successful or not, computer102accumulates votes from all other computers contacted plus, if computer102successfully took control of quorum server106, the votes of quorum server106(step304).

Next computer102informs all other nodes how many votes have been attained (step306). Computer102then determines if the group has captured the majority of votes (step308). If the majority of votes have not been captured, computer102determines if it was part of the previous cluster (step310). If computer102was part of the previous cluster, the process returns to step304and continues to accumulate votes, otherwise, computer102shuts down (step312).

If a majority of votes have been captured at308, computer102determines a fully connected set of the responding computers (step314). Computer102uses well-known graphing techniques to determine a fully connected set of responding computers, therefore this process will not be discussed further.

After a fully connected set of computers has been determined, computer102informs the other nodes of the membership of the new cluster (step316). Note that the above steps are being accomplished by all computers in the system simultaneously.

Controlling Quorum Server

FIG. 4is a flowchart illustrating the process of granting control of quorum server106in accordance with an embodiment of the present invention. The system starts when quorum server106receives a request for control from a node in the proposed new cluster (step402). Next, quorum server106determines if the requesting node was on the list of nodes for the previous cluster (step404). If the requesting node was not on the list of nodes for the previous cluster, quorum server106determines if the list of nodes for the previous cluster is empty (step406). Note that an empty list indicates that a cluster had never been formed and this request is part of initializing a cluster for the first time. If the cluster list is not empty at406, quorum server106denies the request to control quorum server106(step408).

If the node was on the previous cluster list at404or if the cluster list is empty at406, quorum server106sets the cluster list to contain only the requesting node (step410). Note that it will be obvious to a person of ordinary skill in the art that there are other ways to reset the list, including receiving a list of nodes from the requesting node to include in the list or receiving a list of nodes from the requesting node to exclude from the list. Finally, quorum server106affirms the request to control quorum server106and grants its votes to the requesting node (step412).

Reconfiguring a Computer

FIG. 5is a flowchart illustrating the process of reconfiguring a computer within a cluster in accordance with an embodiment of the present invention. The system starts when a computer, say computer102, receives status data from other nodes in the new cluster (step502). Next, computer102determines which set of status data is the most recent (step504).

Computer102updates its own internal status to conform with the most recent status data available (step506). Finally, computer102informs quorum server106which nodes to include in the new cluster list (step508).