Scalable, highly available cluster membership architecture

• US 7,738,364 B2
• Filed: 03/07/2005
• Issued: 06/15/2010
• Est. Priority Date: 03/10/2004
• Status: Active Grant

• Current Assignee: William L. Bain
• Original Assignee: William L. Bain
• Inventors: Bain, William L
• Primary Examiner(s): Juntima; Nittaya
• Application Number:
  US11/074,164
• Publication Number:
  US 20060291459A1
• Time in Patent Office: 1,926 Days
• Field of Search: None
• US Class Current: 370/228
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

The invention comprises a software-based communications architecture and associated software methods for establishing and maintaining a common membership among a cluster of multiple, cooperating computers (called hosts). The invention incorporates the use of nearest neighbor and overlapping heartbeat connections between clustered computers that are logically organized in a linear or multi-dimensional array. This arrangement of heartbeat connections has two principal advantages. First it keeps the cluster membership highly available after host failures because hosts can quickly detect and recover from another host'"'"'s failure without partitioning the membership. Second, it enables the cluster membership to scale to large numbers (e.g., hundreds) of computers because the computational and message passing overhead per host to maintain the specified heartbeat connections is fixed and the underlying physical network is allowed to scale. This membership architecture is well suited to distributed applications (such as a partitioned database) in which changes to the workload are made and propagated cluster-wide by neighboring hosts for purposes of load-balancing.

Claims

1. A system connecting multiple hosts in a computing network by at least one heartbeat link to each host comprising:

a) a first set of heartbeat links between said multiple hosts such that each host is connected by the heartbeat link to a first adjoining neighbor host and a second adjoining neighbor host; and

b) a second set of heartbeat links between said multiple hosts such that each host is connected by a heartbeat link to the first adjoining neighbor host'"'"'s adjoining neighbor host and to the second adjoining neighbor host'"'"'s adjoining neighbor host; and

c) wherein a failure of one of said multiple hosts comprises a resulting action of;

d) the failed host'"'"'s first adjoining neighbor host remaining connected by a heartbeat link to said failed host'"'"'s second adjoining neighbor host; and

e) the failed host'"'"'s second adjoining neighbor host remaining connected by a heart beat link to said failed host'"'"'s second adjoining neighbor host'"'"'s second adjoining neighbor; and

f) the failed host'"'"'s first adjoining neighbor host, using said remaining connected heartbeat link from said first adjoining neighbor host to failed host'"'"'s second adjoining neighbor host, and said remaining connected heartbeat link from said second adjoining neighbor host to said second adjoining neighbor host'"'"'s adjoining neighbor host, to connect a new heartbeat link to said failed host'"'"'s second adjoining neighbor host'"'"'s adjoining neighbor host; and

g) the failed host'"'"'s first adjoining neighbor host remaining connected by a heartbeat to said failed host'"'"'s first adjoining neighbor host'"'"'s first adjoining neighbor; and

h) the failed host'"'"'s second adjoining neighbor host connecting a new heartbeat link to said failed host'"'"'s first adjoining neighbor host'"'"'s first adjoining neighbor host by using said remaining connected heartbeat link from failed host'"'"'s first adjoining neighbor host to the failed host'"'"'s second adjoining neighbor host and said remaining heartbeat link from the first adjoining neighbor host to the first adjoining neighbor'"'"'s first adjoining neighbor host;

i) thereby establishing a heartbeat linking structure similar to a heartbeat linking structure prior to the failure of the failed host, with an exception that the failed host is no longer in the structure.

2. The system of claim 1 further comprising a third set of heartbeat links between said multiple hosts connecting hosts with at least two intervening hosts between two heartbeat linked hosts.

3. The system of claim 2 wherein when two adjoining hosts, of said multiple hosts, fail, comprising an ability to use the remaining heartbeat links to re-establish links between adjacent hosts, links between hosts separated by an intervening host, and links between hosts separated by two intervening hosts.

4. A method for connecting heartbeat links between multiple hosts in a networked cluster of hosts comprising:

a. connecting a first set of heartbeat links between said multiple hosts such that each host is connected by said heartbeat link to said host'"'"'s adjoining neighbor host; and

b. connecting a second set of heartbeat links between said multiple hosts such that each host is connected to said host'"'"'s adjoining host'"'"'s adjoining host; and

c. whereupon the failure of a single host in said networked cluster of hosts leaves a set of surviving hosts and surviving heartbeat links, the surviving hosts using the surviving heartbeat links to re-establish a set of heartbeat links to each adjoining host and to re-establish a set of heartbeat links to each adjoining host'"'"'s adjoining host;

d. thereby returning the networked cluster of hosts to said networked cluster of host'"'"'s original state of heartbeat links minus the failed host.