System and method for dynamic transparent consistent application-replication of multi-process multi-threaded applications

• US 8,584,145 B1
• Filed: 09/21/2010
• Issued: 11/12/2013
• Est. Priority Date: 08/06/2010
• Status: Expired due to Fees

• 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,144
• Time in Patent Office: 1,148 Days
• Field of Search: 707/610, 711/162, 714/6.3, 719/319
• US Class Current: 719/319
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• 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 13/00 Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units interface circuits for specific input/output devices G06F3/00 ; multiprogram control therefor G06F9/46; multiprocessor systems G06F15/16
• 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 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A system, method, and computer readable medium for consistent and transparent replication of multi process multi threaded applications. 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. Replica consistency between primary application and its replicas is provided by imposing the execution ordering of the primary on all its replicas. The execution ordering on a primary is captured by intercepting calls to the operating system and libraries, sending replication messages to its replicas, and using interception on the replicas to enforce said captured primary execution order. Replication consistency is provided without requiring modifications to the application, operating system or libraries.

Claims

1. A system for providing replica consistency between a primary application and one or more backup applications, the system comprising:

computer system memory comprising one or more memory locations configured to store the primary application;

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

an interception layer on the primary application configured to intercept calls to the host operating system and configured to intercept calls to shared libraries, and configured to generate replication messages based on said intercepted calls;

a messaging engine, for said primary application, that is configured to send said replication messages to the one or more backup applications;

one or more backup hosts each with a host operating system and each comprising;

computer system memory comprising one or more memory locations configured to store one or more backup applications, and one or more Central Processing Units (CPUs) operatively connected to said computer system memory and configured to execute said one or more backup applications;

at least one additional messaging engine, for each backup application, that is configured to receive said replication messages from said primary application; and

backup interception layers, corresponding to each backup application, which are configured to intercept calls to the host operating system and shared libraries, wherein ordering information is retrieved from the additional messaging engine for each backup application, and

wherein each replication message contains at least a process identifier, a thread identifier and a sequence number, and wherein said calls do not create or destroy processes and do not create or destroy threads, and replica consistency is provided by imposing a same call ordering on the backup applications as on the primary applications; and

wherein said primary application'"'"'s call ordering is imposed for said each backup application by sorting incoming replication messages by sequence number, and only delivering the replication messages with matching process and thread identifiers and with a sequence number exactly one larger than the sequence number of the most recently delivered message.

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 said call ordering is encoded by increasing the sequence number by one on said primary application for each new replication message.

4. The system according to claim 1, further comprising:

a pending thread callback queue memory where requests for replication messages without matching process identifier and thread identifier are placed, until the oldest received replication message matches said process identifier and thread identifier.

5. The system according to claim 1, wherein the interception layer for the primary application first calls the host operating system or shared library, and then creates and sends the corresponding replication message, and then returns a resource call to a calling application.

6. The system according to claim 1, wherein an interceptor for each of said backup applications requests a replication message from the additional messaging engine, and then calls the host operating system or shared library, and returns to a calling application.

7. The system according to claim 1, wherein the sequence numbers are generated as globally unique identifiers for at least one of the primary applications and the backup applications.

8. The system according to claim 1, where replication messages are sent from the primary application to said each backup application over one of Transmission Control Protocol (TCP/IP) or User Datagram Protocol (UDP).

9. The system according to claim 1, wherein the primary application and said each backup application are connected with one of a local area network, wide area network, Internet and a wireless network.

10. The system according to claim 1, wherein the interception layer and backup interception layer and the additional messaging engine are implemented without the need to modify one or more of the primary application, the host operating system or the shared libraries.

11. The system according to claim 1, wherein said intercepted call to the host operating system or shared library is a write operation, which is configured to perform encoding of a result of said write operation and encoding of data structures of all parameters within a DATA block and including said DATA block in the replication messages.

12. The system according to claim 11, wherein actual data written is not included in the replication messages.

13. The system according to claim 11, wherein each of said backup applications suppresses said write operation and uses the DATA block from the primary application to update a return value and data structures of all parameters to match the primary application.

14. The system according to claim 11, wherein said write operation writes data to at least one of storage, system memory, network storage, a network connection, and an external device, and wherein the system is connected to one or more of a local area network, wide area network, Internet and a wireless network.

15. The system according to claim 11, wherein said encoding uses one of Extensible Markup Language (XML) or custom coding.

16. The system according to claim 11, wherein storage is mounted as shared storage for both the primary application and one or more of each of the backup applications.

17. The system according to claim 1, wherein said intercepted call to the host operating system or shared library is a read operation that encodes the results of said read operation, the data structures of all parameters, and the data read within a DATA block and including said DATA block in the replication messages.

18. The system according to claim 17, wherein each of said backup applications suppress said read operation and uses the DATA block from the primary application to update a return value, data structures and read data to match the primary application.

19. The system according to claim 17, wherein said read operation reads data from at least one of storage, a system memory, a network storage, a network connection and an external device.