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

• US 9,135,127 B1
• Filed: 09/21/2010
• Issued: 09/15/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): Sough, H S
• Assistant Examiner(s): JORDAN, KIMBERLY L
• Application Number:
  US12/887,208
• Time in Patent Office: 1,820 Days
• US Class Current: 1/1
• 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/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/2048 where the redundant components share neither address space nor persistent storage
• 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/10 File systems; File servers
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• 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
• 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 primary host with a host operating system;

an interception layer on the primary application configured to intercept access to processes and threads and generate replication messages based on said interception, wherein said intercepted access includes one or more of creating threads, destroying threads, managing threads, creating processes, destroying processes, and managing processes;

a messaging engine on the primary application 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;

an additional messaging engine for each backup application configured to receive said replication messages from the primary application; and

backup interception layers corresponding to each backup application, said backup interception layers configured to intercept access to processes and threads, wherein ordering information is retrieved from the additional messaging engines for each backup application;

wherein each instance of creating and destroying threads and processes are assigned a unique Method ID, and each replication message contains at least the Method ID, a process ID, a thread ID and a sequence number;

wherein interceptors for said each instance of creating and destroying threads and processes send unique replication messages with said unique Method IDs to the one or more backups;

wherein said unique replication messages are used on the one or more backup applications to maintain mappings between a primary process ID and thread ID pair and a corresponding process ID and thread ID pair on the one or more backup applications; and

wherein replica consistency is provided by imposing the same event ordering on each backup application as on the primary application.

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

3. The system according to claim 1, wherein 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, wherein the ordering of the primary application'"'"'s creation and destruction of processes and threads is imposed on the one or more backup applications by sorting incoming replication messages by sequence number, and only delivering replication messages with matching Method ID and with a sequence number exactly one larger than the most recently delivered message.

5. The system according to claim 4, wherein requests for replication messages without matching Method ID are placed in a pending thread callback queue until an oldest replication message matches said Method ID.

6. The system according to claim 1, wherein said unique replication messages is a replication message with Method ID of PROCESS_INIT sent prior to the application'"'"'s main( ) method being called.

7. The system according to claim 1, wherein said unique replication message is a replication message with Method ID of PROCESS_CREATE sent after creation of a new process, or a replication message with Method ID of THREAD_CREATE sent after creation of a new thread.

8. The system according to claim 1, wherein said unique replication message is a replication message with Method ID of PROCESS_EXIT sent after termination of a process, or a replication message with Method ID of THREAD_EXIT sent after termination of a thread.

9. The system according to claim 1, wherein a replication message for creating a process further contains a process ID of a parent process.

10. The system according to claim 1, wherein a replication message for creating a thread further contains a process ID of a parent process.

11. The system according to claim 1, wherein sequence numbers are generated as a globally unique identifier for the application.

12. The system according to claim 1, wherein said replication messages are sent from the primary application to the one or more backup application over one of TCP/IP or UDP.

13. The system according to claim 1, wherein said interception layer on the primary application first calls a process or thread, then creates and sends a corresponding replication message, and then returns the call to the calling application.

14. The system according to claim 1, wherein the interceptor on the backup application first requests a replication message from the messaging engine, then calls the corresponding process or thread method, and then returns to the calling application.

15. The system according to claim 1, wherein the primary application and the one or more backup applications are connected over one of a local area network, wide area network, Internet or wireless network.

16. The system according to claim 1, wherein encoding is performed using one of XML or custom encoding, and wherein the interception layer and messaging engine are implemented without the need to modify one of the application, operating system or system libraries.

17. 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 primary host with a host operating system;

an interception layer on the primary application configured to intercept access to processes and threads and generate replication messages based on said interception, wherein said intercepted access includes one or more of creating threads, destroying threads, managing threads, creating processes, destroying processes, and managing processes;

a messaging engine on the primary application 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;

an additional messaging engine for each backup application configured to receive said replication messages from the primary application; and

backup interception layers corresponding to each backup application, said backup interception layers configured to intercept access to processes and threads, wherein ordering information is retrieved from the additional messaging engines for each backup application;

wherein each instance of creating and destroying threads and processes are assigned a unique Method ID, and each replication message contains at least the Method ID, a process ID, a thread ID and a sequence number, and replica consistency is provided by imposing the same event ordering on each backup application as on the primary application;

wherein an interceptor of the primary application sends a PROCESS_INIT replication message prior to the application'"'"'s main( ) method is executed; and

wherein said PROCESS_INIT replication message is used on the one or more backup applications to build an initial mapping between a primary application'"'"'s initial process ID and thread ID pair and the corresponding process ID and thread ID pair on the one or more backup applications.

18. The system according to claim 17, wherein the initial mapping between the primary application process and thread ID pair and one or more backup processes and thread ID pair is implemented using one of a hash table or a database.

19. 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 primary host with a host operating system;

an interception layer on the primary application configured to intercept access to processes and threads and generate replication messages based on said interception, wherein said intercepted access includes one or more of creating threads, destroying threads, managing threads, creating processes, destroying processes, and managing processes;

a messaging engine on the primary application 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;

an additional messaging engine for each backup application configured to receive said replication messages from the primary application; and

backup interception layers corresponding to each backup application, said backup interception layers configured to intercept access to processes and threads, wherein ordering information is retrieved from the additional messaging engines for each backup application;

wherein each instance of creating and destroying threads and processes are assigned a unique Method ID, and each replication message contains at least the Method ID, a process ID, a thread ID and a sequence number, and replica consistency is provided by imposing the same event ordering on each backup application as on the primary application;

wherein the primary application'"'"'s interceptor sends a PROCESS_CREATE replication message after creation of a new process, and a THREAD_CREATE replication message is sent after creation of a new thread; and

wherein said PROCESS_CREATE and THREAD_CREATE replication messages are used on the one or more backup applications to build a mapping between a primary process ID and thread ID pair and a corresponding process ID and thread ID pair on the one or more backup applications.

20. 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 primary host with a host operating system;

an interception layer on the primary application configured to intercept access to processes and threads and generate replication messages based on said interception, wherein said intercepted access includes one or more of creating threads, destroying threads, managing threads, creating processes, destroying processes, and managing processes;

a messaging engine on the primary application 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;

an additional messaging engine for each backup application configured to receive said replication messages from the primary application; and

backup interception layers corresponding to each backup application, said backup interception layers configured to intercept access to processes and threads, wherein ordering information is retrieved from the additional messaging engines for each backup application;

wherein each instance of creating and destroying threads and processes are assigned a unique Method ID, and each replication message contains at least the Method ID, a process ID, a thread ID and a sequence number, and replica consistency is provided by imposing the same event ordering on each backup application as on the primary application;

wherein the primary application'"'"'s interceptor is configured to send a PROCESS_EXIT replication message after termination of a process and a THREAD_EXIT replication message after termination of a thread; and

wherein said PROCESS_EXIT and THREAD_EXIT replication messages are used on the one or more backup applications to remove a mapping between a primary process ID and thread ID pair and a corresponding process ID and thread ID pair on the one or more backup applications.