System and method for reliable non-blocking messaging for multi-process application replication

• US 9,128,904 B1
• Filed: 10/01/2012
• Issued: 09/08/2015
• Est. Priority Date: 08/06/2010
• Status: Expired due to Fees

• Current Assignee: Open Invention Network LLC
• Original Assignee: Open Invention Network LLC
• Inventors: Havemose, Allan
• Primary Examiner(s): Manoskey, Joseph D
• Application Number:
  US13/632,951
• Time in Patent Office: 1,072 Days
• Field of Search: 714/4.11, 714/10, 714/11, 714/12, 714/13, 714/15, 714/18, 719/313, 719/314
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• 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
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

A system, method, and computer readable medium for reliable messaging between two or more servers. The computer readable medium includes computer-executable instructions for execution by a processing system. Primary applications runs on primary hosts and one or more replicated instances of each primary application run on one or more backup hosts. The reliable messaging ensures consistent ordered delivery of messages in the event that messages are lost; arrive out of order, or in duplicate. The messaging layer operates over TCP or UDP with our without multi-cast and broad-cast and requires no modification to applications, operating system or libraries.

Claims

1. A system, comprising:

a primary host computer with computer system memory configured to store a primary application which is configured to be executed on said primary host computer with an operating system, wherein said primary application is comprised of one or more processes and each process is comprised of one or more threads;

one or more central processing units (CPUs) for said primary host computer operatively connected to said computer system memory and configured to execute said primary application;

one or more interceptors configured to intercept calls to the operating system and configured to generate replication messages based on said intercepted calls, wherein said intercepted calls include at least one of process calls, thread calls, resource calls including calls to Input/Output resources, lock calls including calls to mutexes, semaphores, futexes, critical sections and monitors;

a messaging layer for said primary application configured to transmit said replication messages to one or more backup applications;

one or more backup host computers each with computer system memory configured to store the one or more backup applications that execute on said one or more backup hosts each with a corresponding operating system;

one or more CPUs for each one or more backup hosts operatively connected to said computer system memory for each backup host and configured to execute said one or more backup applications;

one or more additional interceptors that intercept calls to said one or more backup operating systems; and

an additional messaging layer for each one or more of the backup applications which are configured to receive said replication messages; and

wherein each replication message generated for the primary application contains a unique replication sequence number which is one larger than the replication sequence number for the previously sent replication message; and

wherein said replication messages received are sorted by replication sequence number and an order of replication messages by sorted sequence number is used to impose a same order of events on the one or more backup application as on the primary application.

2. The computer system according to claim 1, wherein said operating system is one of Linux, UNIX or Windows.

3. The computer system according to claim 1, wherein the messaging layer and the additional messaging layer transmits said replication messages over one of User Datagram Protocol (UDP), Transmission Control Protocol (TCP), UDP using multicast, or UDP using broadcast.

4. The computer system according to claim 1, wherein a variable is sent to the backup application containing a sequence number of a replication message most recently sent to the backup application.

5. The computer system according to claim 4, wherein any received messages with a sequence number less than said variable is ignored.

6. The computer system according to claim 4, wherein a received message with a sequence number one larger than said variable is delivered to said one or more backup applications and said variable is updated.

7. The computer system according to claim 4, wherein a message is stored in one of a queue, list, hashmap, and database if said message has a sequence number more than 2 larger than said variable and if said message is not already in the list.

8. The computer system according to claim 7, wherein an acknowledgement (ACK) is sent if said message was not found in one of the queue, list, hashmap and database.

9. The computer system according to claim 7, wherein said message is ignored if it was found in one of the queue, list, hashmap and database.

10. The computer system according to claim 7, wherein retransmit requests (REQ) are sent for all messages with sequence numbers between and including the sequence number of said message minus one and said variable plus one.

11. The system according to claim 7, wherein the message is delivered with the lowest sequence number contained in said one of the queue, list, hashmap and database if said lowest sequence number is one larger than said variable.

12. The computer system according to claim 1, wherein the messaging layer is configured to transmit messages over TCP, and deliver said messages directly to said one or more backup applications on said backup hosts.

13. The computer system according to claim 12, wherein all acknowledgement messages are suppressed.

14. The computer system according to claim 12, wherein all retransmit request messages are suppressed.

15. The computer system according to claim 12, wherein incoming messages are processed in the order in which they arrive.

16. The computer system according to claim 1, wherein the messaging layer transmits messages over one of UDP and UDP multicast, and a messaging processing unit (MPU) for said one or more backup applications process messages in the order they arrive.

17. The computer system according to claim 1, wherein said additional messaging layer for said one or more backup applications processes replication messages independently and generates acknowledgements (ACK) and requests for re-transmission (REQ) independently.

18. The computer system according to claim 1, wherein said one or more backup applications execute independently, and the corresponding additional messaging layers receive and process replication messages independently.

19. The computer system according to claim 1, wherein the additional messaging layers for a portion of the one or more of the backup applications generate an acknowledgement (ACK) message for a particular replication message if the message was received, and the additional messaging layers for the remaining backup applications generate requests for re-transmission (REQ).

20. The computer system according to claim 19, wherein a retransmitted message is rejected by the one or more backup applications where the message already has been acknowledged (ACK).