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

• US 9,141,481 B1
• Filed: 09/22/2010
• Issued: 09/22/2015
• Est. Priority Date: 08/06/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Open Invention Network LLC
• Inventors: Havemose, Allan
• Primary Examiner(s): Anya, Charles E
• Application Number:
  US12/887,598
• Time in Patent Office: 1,826 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/1683 at instruction level
• CPC Class Codes: G06F 11/2041 with more than one 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
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/825 the problem or solution involving locking
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

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 for providing reliable non-blocking messaging, the system comprising:

a primary application and one or more backup applications;

one or more system memory locations configured to store said primary application;

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

one or more interceptors configured to intercept calls to the host operating system and libraries and configured to generate replication messages based on said intercepted calls;

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

one or more backup hosts each comprised of;

one or more system memory locations configured to store the one or more backup applications, one or more central processing units operatively connected to computer system memory and configured to execute the one or more backups applications on a host operating system;

one or more additional interceptors configured to intercept calls to said one or more backup host operating systems and libraries; and

an additional messaging layer for each of the one or more backup applications configured to receive said replication messages,

wherein each replication message is comprised of a message sequence number, and one or more of a method identifier, a process identifier, a thread identifier, and a data-block containing data related to the intercepted call generating the replication message;

wherein an Input/Output (I/O) operation on the primary includes the result of the I/O operation and application state-changes in the corresponding replication message'"'"'s data-block; and

the one or more backup applications suppress the I/O operation and use said data-block to adjusts internal state based on internal state received from the primary application and to return the result generated by the primary application; and

wherein a process or thread operation on the primary includes the process and thread identifiers in the replication message; and

the one or more backup applications repeat the process and the thread operations corresponding to the replication message, and maintain mappings between process identifiers and thread identifiers for the primary application and the one or more backup applications.

2. The system according to claim 1, wherein said host operating system is one of Linux®

, UNIX®

or Microsoft Windows®

.

3. The system according to claim 1, wherein the messaging layer is configured to transmit said messages over one of User Datagram Protocol (UDP), Transmission Control Protocol (TCP), UDP using multicast, and UDP using broadcast.

4. The system according to claim 1, wherein a pending acknowledgement data structure on the primary host is configured to store a copy of each message sent for each of the one or more backup applications.

5. The system according to claim 4, wherein said pending acknowledgement data structure is one of a queue, list, and hashmap with one entry for each message-backup pair.

6. The system according to claim 4, wherein acknowledgment of receipt of a message is performed by removal of a copy of a sent message corresponding to a particular backup operation after said backup operation is performed.

7. The system according to claim 4, wherein copies of messages are created before the messages are transmitted to the one or more backup applications.

8. The system according to claim 4, wherein message acknowledgements are processed in the same order that said messages are sent.

9. The system according to claim 4, wherein message acknowledgements are processed in the order they arrive independently of the order in which the messages were sent.

10. The system according to claim 4, wherein a copy of a sent message corresponding to a particular backup application is retransmitted when the backup applications requests a retransmit of the sent message.

11. The system according to claim 4, wherein said pending acknowledgement data structure contains a copy of the message for each of the one or more backup applications.

12. The system according to claim 11, wherein said pending acknowledgement data structure comprises a pending acknowledgement data structure for each of the one or more backup applications.

13. The system according to claim 1, wherein the message is sent on a calling thread and all acknowledgements and retransmit requests are processed on a separate thread.

14. The system according to claim 13, wherein the calling thread stores one copy for each backup copy of said message in a pending acknowledgement data structure, and an acknowledgement and retransmit thread retrieves the message from the pending acknowledgement data structure, wherein access to said pending acknowledgement data structure is protected by a lock.

15. The system according to claim 1, wherein messages are sent concurrently with processing acknowledgement and retransmit requests.

16. The system according to claim 1, wherein the messaging layer transmits messages over Transmission Control Protocol (TCP) and each message is sent once to each backup application.

17. The system according to claim 16, wherein Transmission Control Protocol (TCP) is used to provide ordered delivery of messages.

18. The system according to claim 16, wherein the messages are sent over a wide area network (WAN).

19. The system according to claim 1, wherein the messaging layer transmits message over User Datagram Protocol (UDP) and said messaging layer for the primary application does not wait for receipt of message acknowledgement (ACK).

20. The system according to claim 1, wherein the messaging layer transmits messages using User Datagram Protocol (UDP) multi-cast and said messaging layer transmits each message one or more times, and duplicates are removed at the one or more backup applications.