Scalable, highly available cluster membership architecture

• US 20060291459A1
• Filed: 03/07/2005
• Published: 12/28/2006
• Est. Priority Date: 03/10/2004
• Status: Active Grant

• Current Assignee: William L. Bain
• Original Assignee: William L. Bain
• Inventors: Bain, William L.
• Granted Patent: US 7,738,364 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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 network comprising:

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

b) a second chain of heartbeat links between said multiple hosts such that each host is connected by a heartbeat link to the host adjoining said adjoining neighbor host.

2. The system of claim 1 wherein a failure of one of said multiple hosts causes:

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

b) the failed host'"'"'s first adjoining neighbor host to connect by heartbeat link to said failed host'"'"'s second adjoining neighbor host'"'"'s adjoining neighbor host; and

c) causes said failed host'"'"'s second adjoining neighbor host to connect by heartbeat to said failed host'"'"'s first adjoining neighbor host'"'"'s second adjoining neighbor;

d) thereby establishing the links necessary to maintain the cohesiveness of the original network.

3. The system of claim 1 wherein the second chain of heartbeat links between said multiple hosts connects hosts with at least two intervening hosts between two heartbeat linked hosts.

4. The system of claim 3 wherein a failure of one of said multiple hosts causes:

a) the failed host'"'"'s first adjoining neighbor host to connect by heartbeat link to said failed host'"'"'s second adjoining neighbor host;

b) the failed host'"'"'s first adjoining neighbor host to connect by heartbeat link to said failed host'"'"'s at least second adjoining neighbor host'"'"'s adjoining neighbor host;

c) said failed host'"'"'s at least second adjoining neighbor host to connect by heartbeat to said failed host'"'"'s first adjoining neighbor host'"'"'s at least second adjoining neighbor;

d) thereby establishing the links necessary to maintain the cohesiveness of the original network.

5. A method for connecting multiple hosts in a networked cluster of computers comprising:

.

a) establishing a first chain of links between said multiple hosts such that each host is connected by a heartbeat to its adjoining neighbor host; and

b) establishing a second chain of links between said multiple hosts such that each host is connected by a heartbeat link to the host adjoining said adjoining neighbor host.

6. The method of claim 5 wherein a failure of one of said multiple hosts causes:

a) connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host;

b) connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host'"'"'s adjoining neighbor host; and

c) connecting said failed host'"'"'s second adjoining neighbor host by heartbeat link to said failed host'"'"'s first adjoining neighbor host'"'"'s adjoining neighbor host.

7. The method of claim 5 for connecting multiple hosts in a networked cluster of computers wherein said second chain of heartbeat links is connected to a host with at least two intervening hosts between two heartbeat linked hosts.

8. The method of claim 5 wherein a failure of one of said multiple hosts causes:

a) connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host;

b) connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host'"'"'s adjoining neighbor host; and

c) connecting said failed host'"'"'s second adjoining neighbor host by heartbeat link to said failed host'"'"'s first adjoining neighbor host'"'"'s adjoining neighbor host.

9. The method of claim 7 wherein a failure of one of said multiple hosts causes:

a) connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host;

b) connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host'"'"'s at least adjoining neighbor host; and

c) connecting said failed host'"'"'s second adjoining neighbor host by heartbeat link to said failed host'"'"'s first adjoining neighbor host'"'"'s at least adjoining neighbor host.

10. A means for maintaining the coherency of connection of multiple hosts in a networked cluster of computers, while using a minimum of bandwidth, comprising:

a) means for establishing a first chain of links between said multiple hosts such that each host is connected by a heartbeat link to its adjoining neighbor host; and

b) means for establishing a second chain of heartbeat links between said multiple hosts such that each host is connected by a heartbeat link to the host adjoining said adjoining neighbor host.

11. The means of claim 10 wherein coherency of the network is maintained during failure of one of said multiple hosts, said coherency capability comprised of:

a) means for connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host;

b) means for connecting the failed host'"'"'s first adjoining neighbor host by heartbeat link to said failed host'"'"'s second adjoining neighbor host'"'"'s adjoining neighbor host;

c) means for connecting said failed host'"'"'s second adjoining neighbor host by heartbeat link to said failed host'"'"'s first adjoining neighbor host'"'"'s adjoining neighbor host;

d) whereby the interconnection of the remaining networked hosts is maintained.