Automatic reconnection of partner software processes in a fault-tolerant computer system

[0002] 1. Field of the Invention

[0003] The present invention relates to the field of fault-tolerant computer systems. More specifically, the present invention relates to the problem reconnecting partner software processes that share an interface when any of these software processes may independently fail over to a redundant backup copy of the software process. The present invention solves this problem in a manner that is independent of the capabilities of the hardware and operating system used and ensures that the partner software processes do not have to be aware of the redundancy scheme used by their partners.

[0004] 2. Description of Prior Art

[0005] Fault-tolerant computer systems use a variety of techniques to provide highly-available systems for use in safety-critical or mission-critical environments. Many different approaches have been taken by different organizations to achieve fault-tolerance.

[0006] One approach to fault-tolerance is to use specialized hardware and operating systems to mirror all inputs to a number of redundant processing units. Outputs from the system are taken from just one processing unit, called the primary, until it is determined to have failed and another processing unit is selected as the primary. Another approach is to take a majority vote for the correct output, and disabling any processing unit which disagrees with this output on the assumption that it has failed. For further details of this approach to fault-tolerance, see the following U.S. Pat. Nos. 5,271,013, Gleeson; 5,363,503, Gleeson; 5,560,033, Doherty et al.; and 5,802,265, Bressoud et al.

[0007] An alternative approach is to provide fault-tolerance in the software process layer, which avoids the need for specialized hardware or operating system support. This approach is also more easily deployed on a cluster of heterogeneous processing units with different hardware characteristics, since it does not rely on specific attributes of the hardware. Software fault-tolerance, as this approach is commonly called, typically uses a combination of redundant backup software processes and replication of internal state between the primary and backup copies of each software process to speed recovery from any software or hardware faults. However, many practical fault-tolerant systems combine both hardware and software fault tolerance techniques. For further details of the general techniques used to achieve software fault-tolerance, see the following U.S. Pat. Nos. 5,129,080, Smith; and 5,748,882, Huang. See also the following publications: Hardware and Software Architectures for Fault Tolerance, Chapter 3, ed. Banatre et al., Springer-Verlag 1994; Fault Tolerance in Distributed Systems, Chapter 5, Jalote, Prentice Hall 1994; and Fault-Tolerant Computer System Design, Chapter 7, Pradhan, Prentice Hall 1996.

[0008] A common problem in software fault tolerance is the need to reconnect partner software processes quickly and efficiently after one or more of the partners has failed over to a redundant backup copy. In many systems, this is achieved by using special hardware or operating system facilities to allow such reconnection. However such mechanisms are difficult to implement in heterogeneous distributed systems.

[0009] The present invention, known as a “join”, is a means of connecting two partner processes and automatically reconnecting them after one or both of the partner processes fails over to a redundant backup copy. This is achieved by use of a join manager component that allows the partner processes to register the joins between them and manages the reconnection after a fail over.

[0010] The present invention has the following advantages over prior art:

[0011] The present invention is independent of the system hardware architecture or operating system, and can be used in heterogeneous distributed systems.

[0012] The partner processes associated with a join do not need to know whether the other processes associated with a join employ a redundancy scheme or what that redundancy scheme may be, yet can be reconnected successfully even if the more than one partner to a join fails simultaneously.

[0013] The join manager actively controls reconnection, so no polling mechanism is required in the partner processes to achieve the reconnection. This saves on processor and communications resources by avoiding repeated unsuccessful attempts to poll a failed partner to see if it has recovered.

[0014] FIG. 1 shows the use of replicated handles on an interface between two software processes, each with a primary and backup copy running on separate processing units.

[0015] 100: A processing unit or CPU within a distributed computing system.

[0016] 101: A processing unit or CPU within a distributed computing system.

[0017] 102: A processing unit or CPU within a distributed computing system.

[0018] 103: A processing unit or CPU within a distributed computing system.

[0019] 104: A processing unit or CPU within a distributed computing system.

[0020] 110: The join manager software process running on CPU 100.

[0021] 121: The copy of Process A running on CPU 101. This copy is currently the primary copy of A.

[0022] 122: The copy of Process A running on CPU 102. This copy is currently the backup copy of A.

[0023] 131: The copy of Process B running on CPU 103. This copy is currently the primary copy of B.

[0024] 132: The copy of Process B running on CPU 104. This copy is currently the backup copy of B.

[0025] 140: Interface between join manager and 121 for creation, reconnection and release of joins.

[0026] 141: Interface between join manager and 131 for creation, reconnection and release of joins.

[0027] 142: Interface between join manager and 122 for creation, reconnection and release of joins.

[0028] 143: Interface between join manager and 132 for creation, reconnection and release of joins.

[0029] 150: Replication of internal state information between primary and backup copies of process A.

[0030] 151: Replication of internal state information between primary and backup copies of process B.

[0031] 160: The interface between processes A and B.

[0032] This description covers a method for automatically reconnecting partner software processes after one or both of the partner processes fails over to a redundant backup copy. In the description, there are set forth, for purposes of explanation, many specific details, to provide the reader with a thorough understanding of the invention. It will be obvious to one skilled in the art that the invention may be practiced without these details. Furthermore, certain devices and orders of processing are given in the diagrams and the description, to make understanding the invention easier. It will, again, be apparent to one skilled in the art that the specific devices and sequences are merely illustrative and may be varied whilst remaining within the spirit and scope of the present invention.

[0033] What follows is a description of the preferred embodiment of the present invention. Other possible embodiments will be discussed later.

[0034] With reference to FIG. 1, the preferred embodiment of a system that supports joins comprises the following components:

[0035] A plurality of processing units, shown as CPU 100 through CPU 104, each of which may execute one or a plurality of software processes. FIG. 1 shows each software processes executing on a separate processing unit. Alternative embodiments of the present invention may have more than one software process executing on each processing unit.

[0036] A join manager software process, 110, that executes on CPU 100. This process is responsible for controlling creation, reconnection and release of joins in response to requests from the partner processes.

[0037] Two partner processes, process A and process B, each of which employs primary and backup redundancy. Process A Primary, 121, executes on CPU 101. Process A Backup, 122, executes on CPU 102. Process B Primary, 131, executes on CPU 103. Process B Backup, 132, executes on CPU 104.

[0038] The join manager and partner processes communicate via a synchronous message passing interfaces, which require the sender of a message to know only the process identifier for the intended recipient in order to be able to send a message to that recipient. In the preferred embodiment of the present invention, join manager is responsible for creating the copies of each partner process in the system and is therefore able to learn the process identifier for each partner process copy such as 121, 122, 131 and 132.

[0039] Join manager communicates with each of the partner processes to control the primary and backup status of each partner process copy and the joins between partner processes. This is shown as JM-Process Interface 140 through JM-Process Interface 143.

[0040] Process A Primary replicates state information to Process A Backup via the A—A replication interface, 150.

[0041] Process B primary replicates state information to Process B Backup via the B—B replication interface, 151.

[0042] Process A and Process B primary copies communicate via A-B interface 160.

[0043] With reference to FIG. 1, the join between Process A and Process B is created as follows.

[0044] For each join, such as that between Process A and Process B corresponding to 160, one partner process registers the need for the join with the join manager. This partner to the join is known as the master side of the join. In FIG. 1 Process A is the master, so Process A primary, 121, requests, via 140, that join manager create the join. Join manager accepts the join request and informs 121 that it will be notified when the partner process is available.

[0045] Using information passed on the join request,join manager identifies the partner process for the join to be Process B, and sends a message, via 141, to Process B Primary, 131, requesting it to accept the join. The identifier passed on the join request is a combination of the name of the software process that Process A Primary, 121, wishes to join to plus an instance identifier that specifies, for example, the physical port which an instance of a communications protocol is associated with. Each process registers its name and instance identifier with join manager on startup.

[0046] Process B Primary, 131, replies to join manager, via 141, saying whether it can accept the join. If 131 accepts the join, join manager informs Process A primary, 121, via 140 that the partner process is now available and is 131.

[0047] The join manager may identify the partner process for the join by means of static or dynamic configuration information, or by means of a logical identifier registered by Process B Primary, 131, via 141 when 131 initializes and passed from Process A Primary, 121, via 140 when 121 requests the creation of the join.

[0048] With reference to FIG. 1, consider the case when 121 fails. Join manager is able to automatically reconnect the join between Process A and Process B as follows.

[0049] Join manager detects the failure of processes 121. In the preferred embodiment, join manager uses operating system services to request notification from the operating system of the failure of any process that system manger controls.

[0050] Join manager notifies 131, via 141, that the partner process for the join has failed and that it will be notified when a new partner process is available.

[0051] Join manager notifies 122, via 142, that it should become the Process A Primary.

[0052] While 122 activates as the new Process A Primary, it detects from the replicated state or configuration information that it needs the join with Process B and requests, via 142, that join manager reconnect the join. Join manager informs 122, via 142, that it will be notified when the partner process is available.

[0053] Join manager identifies the partner process for that join is 131 and sends a message via 141 to Process B Primary, 131, requesting it to accept reconnection of the join to 122. Process B Primary, 131, replies to join manager, via 141, saying whether it can accept the reconnection. If 131 accepts the reconnected join, join manager informs the new Process A Primary, 122, via 142 that the partner process is now available and is 131.

[0054] When 122 has requested reconnection of all the joins it is aware of, it informs join manager, via 142, that activation of the new Process A Primary, 122, is complete. Join manager can then perform any garbage collection needed to release resources used by unwanted joins (see the section entitled “Release of Joins” below).

[0055] With reference to FIG. 1, consider the case when both 121 and 131 fail simultaneously after the join between process A and Process B has been established. At this point, the software processes know the following information:

[0056] Join manager is aware of the process identifiers for both of the backup processes, 122 and 132, and the need to reconnect the join between process A and process B once a new primary has been restored to service.

[0057] Process A Backup, 122, is aware from the state information replicated via 150 that it should be joined to Process B, but it does not know the process identifier of 132. If 122 was aware of the process identifier for 132, this would imply that the partner processes are aware of the redundancy strategy employed by its partner processes, which complicates the implementation of each process and increases the volume of data it must maintain about each partner process. The present invention avoids this by use of the join manager, as described below.

[0058] Similarly, Process A Backup, 132, is aware from the state information replicated via 151 that it should be joined to Process A, but it does not know the process identifier of 122.

[0059] Join manager is able to automatically reconnect the join between Process A and Process B without the need for either process to be aware of the redundancy strategy employed by its partner. With reference to FIG.1, join manager achieves reconnection of the join between Process A and Process B as follows.

[0060] Join manager detects the failure of processes 121 and 131.

[0061] Join manager notifies 122, via 142, that it should become the Process A Primary.

[0062] Similarly, join manager notifies 132 , via 143, that it should become the Process B Primary.

[0063] While 122 is activating as the new Process A Primary, it detects from the replicated state information that it needs the join with Process B and requests, via 142, that the join manager reconnect the join. Join manager informs 122, via 142, that the partner has failed and it will be notified when the partner process is available.

[0064] 132 completes activating as the new Process B primary and informs join manager, via 143, that it is ready.

[0065] Both sides of the join are now available, so join manager sends a message, via 143, to the new Process B Primary, 132 , requesting i t to accept reconnection of the join to 122. 132, replies to join manager, via 143, saying whether it can accept the reconnection. If 132 accepts the reconnected join, join manager informs the new Process A Primary, 122, via 142 that the partner process is now available and is 132.

[0066] Joins are released in the following circumstances

[0067] If the master side of a join requests that the join be destroyed, join manager informs the other partners to the join that the join has been destroyed then releases any resources it holds relating to the join.

[0068] If the master side of a join fails and does not request the join to be reconnected during activation of the backup process as the new primary process, join manager assumes that the join is not longer required and manager informs the other partners to the join that the join has been destroyed then releases any resources it holds relating to the join. This garbage collection prevents any faults or inconsistencies in the replication of state between primary and backup copies of the master side of the join consuming unwanted resources in join manager or partner processes.

[0069] Similarly, if the master side of a join fails with no active backup copy available to be activated as the primary, join manager garbage collects the join and informs the other partners to the join that the join has been destroyed.

[0070] What follows is a description of some alternative embodiments of the present invention. One skilled in the art will easily be able to envisage other alternative embodiments of the invention.

[0071] It should be noted that the section titled “Detailed Description of the Invention” is simply a description of the preferred and some additional embodiments of the invention; the full scope of the invention is determined by the claims. A systems engineer skilled in the art of developing fault-tolerant distributed computing systems, based on the claims and the detailed description, should be able to implement a wide variety of systems for automatic reconnection of partner software processes significantly advanced compared with the current state of the art.

[0072] The components of the preferred embodiment of the present invention can be instantiated in different forms according to the requirements and capabilities of the hardware and operating system. Some alternative embodiments include the following variations:

[0073] Software processes that use joins may communicate with the join manager or between partner processes by means of function calls or message exchanges. The communication method chosen for this interaction may be different for different partner processes.

[0074] All components of the system may be instantiated on a single processing unit or any subset of the processing units that make up a distributed system. In particular, each partner process may be instantiated on a different set of processing units, though said sets of processing units may overlap for different partner processes. All processing units may be of a single type, or each processing unit may be one of a plurality of different types.

[0075] The preferred embodiment of the present invention enables join manager to learn of the existence and identity of each partner process copy in the system because join manager is responsible for starting each process copy. Some alternative embodiments may move this responsibility for partner process creation to one or a plurality of other components in the system. In such cases,join manager needs to be notified of, or be able to monitor for, new partner process copies created by any system component.

[0076] The means of creating a new copy of a process may be different for each partner process.

[0077] The preferred embodiment of the present invention uses underlying operating system facilities to allow join manager to learn of the failure of any partner process copy in the system. Some alternative embodiments may achieve this by other means, such as requiring a watchdog message sent from each partner process copy to join manager via the JM-process interface on a timed basis, or monitoring the health of the processing unit on which a partner process copy is executing using specialized hardware support. In such cases, join manager needs to be notified of, or be able to monitor for, failure of partner process copies however this failure is detected.

[0078] The means of process copy failure detection may be different for each partner process or for each processing unit on which partner process copies are executing.

[0079] Some alternative embodiments of the present invention may move the decision point for control of the primary or backup status of each partner process copy from join manager to one or a plurality of other components in the system, such as the underlying operating system if it has suitable facilities. In such cases, join manager needs to be notified of, or be able to monitor for, changes to the state of each partner process copy.

[0080] The means of control of the primary and backup partner process copy state may be different for each partner process.

[0081] The preferred embodiment of the present invention uses 1:1 redundancy for the partner processes with one primary and one backup copy of each process. Alternative embodiments may employ different redundancy strategies for the partner processes, including the following possible strategies:

[0082] A partner process may use no redundancy and rely on a new copy being started after failure. This may be combined with separate persistent storage of the internal state of the partner process in order to enable the new copy to recover quickly to the point at which the previous copy of the process failed.

[0083] A partner process may employ more than one backup copy to give improved failure protection.

[0084] A group of n similar partner processes, such as the copies of a communications protocol stack running on each of a set of n line cards, may employ m (usually m<n) backup copies, each of which may be activated to replace any failed process from the group. This is known as m:n redundancy.

[0085] The redundancy strategy used may be different for each partner process

[0086] Some alternative embodiments of the present invention may make use of redundant copies of the join manager with replication of internal state between the join manager copies in order to make the management of joins resilient to join manager software process failure.

[0087] Some alternative embodiments of the present invention may provide additional information to the partner processes to a join to enable the partner processes to determine whether a join is reconnected fast enough to satisfy the real-time requirements of the partner processes. This may be particularly important for the use of joins in communications protocols.

[0088] Some possible alternative embodiments that enable such determination include the following:

[0089] The join manager can indicate on the notification to a partner process that the other side of a join has failed whether a backup copy of the partner process is in the process of being activated as the new primary. If no backup process is immediately available, the surviving partner process may choose to release resources associated with the join immediately.

[0090] When notifying a partner process of the reconnection of a join, the join manager may specify the time when the failure of the join was detected, or it may specify the time interval since the failure was detected. The partner process can use this information to determine whether the join has been reconnected fast enough to meet its needs before replying to the join manager to indicate whether it accepts the reconnection. If the reconnection is not accepted, the partner processes and join manager must release any resources associated with the join.

[0091] Some alternative embodiments of the present invention may allow a software process to declare that it is unable to continue to provide service to partner processes, for example because it has received a configuration request that disables this function. The join manager treats such revocation of service as a temporary failure of the joins that this process participates in and notifies all partners to this process that the process in unavailable. When the software process declares that it is able to restore service, the join manager automatically reconnects the joins in the same way as it would if the primary copy of this software process had failed and a backup had been activated in its place, though the primary copy has not actually changed.