Fault-tolerant processing method

• US 6,023,772 A
• Filed: 09/25/1997
• Issued: 02/08/2000
• Est. Priority Date: 01/26/1996
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Fleming, Roger Alan
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US08/913,933
• Time in Patent Office: 866 Days
• Field of Search: 714/13, 714/11, 714/12, 714/15, 714/16, 714/20, 714/38, 714/39, 714/41, 714/2, 709/300, 709/400
• US Class Current: 714/13
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2038 with a single idle spare processing component
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups

Abstract

A recovery unit in a software fault-tolerant system has primary and secondary processing units (I, II) running replicate application processes (24). Input messages sent to the recovery unit are received at the primary unit (I) and in due course processed by the primary process (24) to produce application messages; however, these application messages produced by the primary process (24) are not normally output from the primary unit I as the recovery-unit output messages. Instead, these application messages are logged from the primary unit (I) to the secondary unit (II) together with state update information. The secondary process (24) run by secondary unit (II) uses this update information to updates its own state so as to track the state of the primary process. The secondary unit (II) outputs the application messages logged to it from the primary unit (I) as the recovery-unit output messages. Should the primary unit (I) fail, the secondary unit (II) takes over the role of the primary. Furthermore, in the absence of an operative secondary unit (II) (due either to its failure or to its promotion to the primary unit), the primary unit becomes responsible for outputting its own application messages as the recovery-unit output messages. Configurations with multiple secondaries are also possible.

Claims

1. A method of operating a fault-tolerant recovery unit for receiving and processing input messages to produce output messages, the method comprising the steps of:

(a) providing at least two processing entities running respective replicate application processes capable of processing said input messages to progress through a succession of states and produce application messages, one said processing entity serving as a primary processing entity and each other said processing entity serving as a secondary processing entity with one said secondary processing entity acting as a sender processing entity;

(b) receiving said input messages at said primary processing entity and causing said replicate application process run by the latter, herein the primary process, to process these input messages to produce application messages;

(c) logging to each said secondary processing entity said application messages produced by the primary process together with update information for enabling the replicate application process run by each secondary processing entity, herein a secondary process, to update its state to track the state of the primary process;

(d) causing each secondary process to use said update information logged to the secondary processing entity running the secondary process, in order to track the state of the primary process; and

(e) outputting from said sender processing entity as said recovery-unit recovery messages, the application messages logged to the sender entity from the primary processing entity in step (c), the application messages so output being restricted to those produced by the primary process during processing for which update information has been received by said sender processing entity;

said method comprising the further steps of;

(f) upon failure of the primary processing entity, causing a said secondary processing entity to take over the role of the primary processing entity, and

(g) upon failure of the sender processing entity or upon the sender processing entity taking over the role of the primary processing entity in step (f), causing another of said secondary processing entities, where present, to become the sender processing entity, and otherwise, causing the primary processing entity to output the application messages produced thereby as said output messages, this step (g) being effected without loss of recovery-unit output messages.

2. A method according to claim 1, wherein said update information comprises the changes in state experienced by the primary process in processing each input message, each secondary process directly using this state-change information to update its own state in step (d).

3. A method according to claim 1, wherein said update information comprises said input messages together with any non-deterministic choices made by the primary process in processing these input messages, each secondary process updating, its state in step (d) by processing said input messages but instead of itself making any non-deterministic choices required by this processing, using the choices logged to it as part of said update information.

4. A method according to claim 1, wherein each said application message output in step (e) is only output after the state of the secondary process of the sender processing entity has been updated to take account of the processing effected by the primary process in producing that application message.

5. A method according to claim 1, wherein each said application message output in step (e) is output following receipt by the sender entity of the update information necessary to update the state of the secondary process of the sender entity to take account of the processing effected by the primary process in producing that application message, but without waiting for such updating to be effected.

6. A method according to claim 1, wherein at least two said secondary processing entities are provided, step (c) being effected in a pass-along manner with the primary processing entity effecting said logging to one said secondary processing entity and this entity in turn effecting logging to another said secondary processing entity and so on as required, the said sender processing entity being the final entity in this logging chain.

7. A method according to claim 6, including the steps of:

maintaining at least one resend queue of items logged in step (c), and

upon failure of an intermediate said secondary processing entity in said logging chain, resending at least certain of said items from said resend queue to the secondary processing entity following the failed said secondary processing entity in the logging chain.

8. A method according to claim 7, wherein a respective said resend queue is maintained by at least each said processing entity other than the last two in said logging chain, the items in each such queue being those sent out by the corresponding processing entity.

9. A method according to claim 7, including causing the last said processing entity in said logging chain to output an indicator upon receipt of a said item logged to it, and using said indicator to initiate removal of said item from the or each said resend queue.

10. A method according to claim 1, wherein at least two said secondary processing entities are provided, step (c) being effected in a one-to-many manner with the primary processing entity effecting said logging to all said secondary processing entities.

11. A method according to claim 10, including the further steps of:

maintaining for each secondary processing entity a resend queue of items logged to that entity in step (c), and

upon a said secondary processing entity being promoted in step (f) to become the primary processing entity, using said resend queues to ensure that all remaining processing entities have received the same logged items whereby to enable such entities to be advanced to the same states.

12. A method according to claim 11, wherein step (f) involves determining which of said secondary processing entities has its application process most advanced, promoting that processing entity to be the primary processing entity, and sending to the remaining secondary processing entities at least certain items from the said resend queue of the new primary processing entity.

13. A method according to claim 11, wherein step (f) involves forwarding to the new primary processing entity from said resend queues of the remaining secondary processing entities, any said items that are present in the latter queues but not in the resend queue of the new primary processing entity, and using these forwarded items to advance the primary processing entity.

14. A method according to claim 10, including causing each secondary processing entity to output an indication upon receipt of a said item logged to it, and initiating removal of said item from said resend queues when all said secondary processing entities have produced a said indication in respect of a particular said item.

15. A method according to claim 1, wherein only one said secondary processing entity is provided.

16. A method according to claim 1, comprising the additional step, following failure of a said processing entity, of bringing up a new secondary processing entity running a new said secondary process and transferring to this new secondary process state information on a said replicate application process running on a non-failed said processing entity of the recovery unit.

17. A method according to claim 16, wherein only one said secondary processing entity is normally provided, said additional step further comprising, upon the state-information transfer being complete, of causing the new secondary processing entity to serve as said sender processing entity.

18. A method according to claim 1, wherein said input messages contain information as to their source and, at least implicitly, their sequencing, and wherein step (b) further involves temporarily storing input messages received out of sequence from said source while awaiting receipt of missing earlier-in-sequence messages, and submitting the input messages received from said source for processing by said primary process in their correct sequencing.

19. A method according to claim 1, including the further steps of:

logging in a resend queueing arrangement the said application messages available at that one of said processing entities which according to step (g) is to output application messages as said output messages in the event of failure of the sender processing entity; and

resending from said resend queueing arrangment at least some of the application messages held therein upon failure of the sender processing entity.

20. A method according to claim 1, including the further steps of:

logging in a resend queueing arrangement the said application messages logged to the sender processing entity; and

resending from said resend queueing arrangment at least some of those output messages destined for a particular further said recovery unit on failover of the latter.

21. A method according to claim 1, including the further steps of:

logging in a respective resend queueing arrangement the said application messages generated by each said replicate application process;

following failure of a said processing entity;

bringing up a new secondary processing entity running a new said secondary process,

providing said new secondary process with an associated said resend queueing arrangement, and

transferring to said new secondary process state information, but not logged application messages, associated with a said replicate application process running on a non-failed said processing entity of the recovery unit; and

upon failover of a particular further said recovery unit, resending from said resend queueing arrangement associated with the secondary process run by the sender processing entity, at least some of the messages logged therein that are addressed to said particular further said recovery unit;

this latter step involving, when said sender processing entity is formed by said new secondary processing entity, causing said non-failed processing entity to send to said particular further recovery unit application messages in its resend queueing arrangement that are addressed to said particular further recovery unit and are associated with states of said non-failed processing entity entered prior to the said transferring of state information to said new secondary processing entity.

22. A method according to claim 19, including the further step of receiving input acknowledgements acknowledging the receipt of said output messages, and removing from said resend queue those output messages the receipt of which has been acknowledged.

23. A method according to claim 1, including the further step of outputting from the sender processing entity an acknowledgement of each said input message received by the primary processing entity, said acknowledgement being output following receipt by the sender processing entity of said update information that takes account of the processing effected by the primary process in processing the input message concerned.

24. A method according to claim 1, wherein each said processing entity comprises a respective processor running the corresponding said replicate application process.

25. A method according to claim 1, wherein said processing entities share a common processor on which said replicate application processes are run.

26. A method according to claim 1, comprising the additional steps, following failure of a secondary processing entity, of

bringing up a new secondary processing entity running a new said secondary process, transferring to said new secondary processing entity responsibility for sending output messages, and

causing said new secondary processing entity to request from said primary processing entity only those output messages required by other said recovery units.