Fault tolerance and failover using active copy-cat

• US 9,244,771 B2
• Filed: 05/16/2013
• Issued: 01/26/2016
• Est. Priority Date: 08/11/2006
• Status: Active Grant

• Current Assignee: Chicago Mercantile Exchange, Inc. (CME Group Incorporated)
• Original Assignee: Chicago Mercantile Exchange, Inc. (CME Group Incorporated)
• Inventors: Callaway, Paul J., Hagemann, Robert C. III, Shethwala, Zuber, Reece, Troy, Bauerschmidt, Paul Andrew, Ferrari, Enrico
• Primary Examiner(s): SCHELL, JOSEPH O
• Application Number:
  US13/896,093
• Publication Number:
  US 20130297970A1
• Time in Patent Office: 985 Days
• Field of Search: 714/11, 714/12, 714/15, 714/16, 714/17, 714/55, 714/18, 714/20
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• CPC Class Codes: G06F 11/1641 where the comparison is not performed by the redundant processing components
• CPC Class Codes: G06F 11/1687 at event level, e.g. by interrupt or result of polling
• CPC Class Codes: G06F 11/1695 which are operating with time diversity
• 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/2046 where the redundant components share persistent storage G06F11/2043 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups

Abstract

Fault tolerant operation is disclosed for a primary instance, such as a process, thread, application, processor, etc., using an active copy-cat instance, a.k.a. backup instance, that mirrors operations in the primary instance, but only after those operations have successfully completed in the primary instance. Fault tolerant logic monitors inputs and outputs of the primary instance and gates those inputs to the backup instance once a given input has been processed. The outputs of the backup instance are then compared with the outputs of the primary instance to ensure correct operation. The disclosed embodiments further relate to fault tolerant failover mechanism allowing the backup instance to take over for the primary instance in a fault situation wherein the primary and backup instances are loosely coupled, i.e. they need not be aware that they are operating in a fault tolerant environment.

Claims

1. A computer-implemented method of providing fault tolerant operation to a primary instance, the method comprising:

providing a backup instance to which a copy of a first transaction transmitted to the primary instance is forwarded, the backup instance operative to process the copy of the first transaction and generate a first backup result based thereon, the first backup result being transmitted as a response to the first transaction when it has been determined, subsequent to the transmission of the first transaction to the primary instance, that the primary instance is unlikely to transmit a first primary result based on the first transaction, and, based thereon, the primary instance has been prevented from completing an external operation upon which the transmission of the first primary result by the primary instance is dependent; and

sending data indicative of a constraint violation to the primary instance in response to an attempt by the primary instance to complete the first transaction, the constraint violation forcing the primary instance into a failure state.

2. The computer-implemented method of claim 1 further comprising:

forwarding, to the backup instance subsequent to the copy of the first transaction, a copy of a second transaction transmitted to the primary instance, when it has been determined that the primary instance has transmitted both the first primary result and a second primary result based on the second transaction.

3. The computer-implemented method of claim 2 further comprising:

comparing the first primary result with the first backup result and indicating a failure of the backup instance, the primary instance, or a combination thereof, when the first primary result is at least partially different from the first backup result.

4. The computer-implemented method of claim 1 wherein the determination that the primary instance is unlikely to transmit the first primary result comprises waiting for a defined period of time to elapse and determining that the first primary result has not been transmitted before the defined period of time has elapsed.

5. The computer-implemented method of claim 1 further comprising causing the primary instance to self terminate.

6. The computer-implemented method of claim 1 wherein the primary instance comprises an instance of a financial exchange.

7. The computer-implemented method of claim 1 wherein the primary instance comprises a software application, a processor, or a combination thereof.

8. The computer-implemented method of claim 1 wherein the first transaction comprises an incoming trader order, an order cancellation, or a combination thereof.

9. The computer-implemented method of claim 1 wherein the first primary result comprises an order cancellation confirmation, an order confirmation, a trade execution confirmation, an order elimination, an order rejection, or a combination thereof.

10. The computer-implemented method of claim 1 wherein the backup instance is further operative to accept the copy of the first transaction and match the copy of the first transaction with a counter transaction to execute a trade, the first backup result being generated based thereon.

11. A system for providing fault tolerance to a primary instance, the system comprising:

a backup instance comprising a first processor operative to duplicate operation of the primary instance and to which a copy of a first transaction, transmitted to the primary instance, is forwarded, the first processor further operative to process the copy of the first transaction and generate a first backup result based thereon and transmit the first backup result as a response to the first transaction and further in response to an indication by a fault detector coupled therewith that, subsequent to the transmission of the first transaction to the primary instance, that the primary instance is unlikely to transmit a first primary result based on the first transaction, and, based thereon, the primary instance has been prevented from completing an external operation upon which the transmission of the first primary result by the primary instance is dependent; and

a second processor coupled with the primary instance, wherein the second processor is operative to send data indicative of a constraint violation to the primary instance in response to an attempt by the primary instance to complete the first transaction, the constraint violation forcing the primary instance into a failure state.

12. The system of claim 11 wherein the first processor is further operative to be responsive to a copy of a second transaction transmitted to the primary instance, the copy of the second transaction being forwarded to the backup instance subsequent to the copy of the first transaction in response to the fault detector having determined that the primary instance has transmitted both the first primary result and a second primary result based on the second transaction.

13. The system of claim 12 wherein the fault detector is further operative to compare the first primary result with the first backup result and indicate a failure of the backup instance, the primary instance or a combination thereof, when the first primary result is at least partially different from the first backup result.

14. The system of claim 11 wherein the fault detector is further operative to wait for a defined period of time to elapse and determine that the first primary result has not been received before the defined period of time has elapsed.

15. The system of claim 11 wherein the fault detector is further operative to cause the primary instance to self terminate.

16. The system of claim 11 where in the primary instance comprises an instance of a financial exchange.

17. The system of claim 11 wherein the primary instance comprises a software application, a processor or a combination thereof.

18. The system of claim 11 wherein the first transaction comprises an incoming trade order, an order cancellation or a combination thereof.

19. The system of claim 11 wherein the first primary result comprises an order cancellation confirmation, an order confirmation, a trade execution confirmation, an order elimination, an order rejection, or a combination thereof.

20. The system of claim 11 wherein the first transaction is related to a first trade order, the backup instance being further operative to accept the first trade order and match the first trade order with another order to execute a trade, the first backup result being based thereon.

21. A system for providing fault tolerance to a primary instance, the system comprising:

a backup instance comprising;

a first processor; and

a first non-transitory memory coupled to the first processor;

wherein the first processor is operative to duplicate at least some operation of the primary instance and to which a copy of a first transaction transmitted to a primary instance is forwarded as a result of execution of first logic stored in the non-transitory memory by the first processor, the backup instance operative to process the copy of the first transaction and generate a first backup result based thereon and transmit the first backup result as a response to the first transaction and further in response to an indication provided as a result of execution of second logic stored in the non-transitory memory and executable by the first processor to determine that, subsequent to the transmission of the first transaction to the primary instance, that the primary instance is unlikely to transmit a first primary result based on the first transaction, and, based thereon, the primary instance has been prevented from completing an external operation upon which the transmission of the first primary result by the primary instance is dependent; and

a second processor coupled with the primary instance, wherein the second processor is operative to send data indicative of a constraint violation to the primary instance in response to an attempt by the primary instance to complete the first transaction, the constraint violation forcing the primary instance into a failure state.