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

• US 8,589,953 B1
• Filed: 08/06/2010
• Issued: 11/19/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/851,706
• Time in Patent Office: 1,201 Days
• Field of Search: 707/610, 711/162, 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/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 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
• 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 to shared libraries and configured to generate replication messages based on said intercepted calls;

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

one or more additional messaging engines for each backup application configured to receive said replication messages from the primary application; and

backup interception layers corresponding to each backup application configured to intercept calls to the operating system and shared libraries, wherein information to be ordered is retrieved from the one or more messaging engines for each backup application,

wherein each intercepted operating system or shared library call is assigned a unique method identifier, and each replication message contains at least the method identifier, process identifier, thread identifier and a sequence number, and replica consistency is provided based on the ordered information for each backup application as on the primary application; and

wherein a call order of the primary application is imposed for said each backup application when incoming replication messages are sorted by sequence number, and replication messages are delivered with matching method, process and thread identifiers with a sequence number exactly one larger than the most recent delivered message.

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

, UNIX®

or Microsoft Windows®

.

3. The system according to claim 1, wherein resource access ordering is encoded by increasing the sequence number by one on the 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 method identifier, process identifier, and thread identifier are placed until the oldest replication message matches said method identifier, process identifier, and thread identifier.

5. The system according to claim 1, wherein the interception layer for the primary application first calls the intercepted operating system or shared library, 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 the interceptor for said each backup application first requests a replication message from the messaging engine, then calls the intercepted operating system or shared library, and then returns to a calling application.

7. The system according to claim 1, wherein sequence numbers are generated as globally unique identifiers for the application.

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 interceptors and messaging engine are implemented without the need to modify one or more of the primary application, operating system or system libraries.

11. The system according to claim 1, wherein a resource access is a write operation, further comprising encoding the result of said write operation and the data structures of all parameters within a DATA block and including said DATA block in the replication message.

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

13. The system according to claim 11, wherein said each backup application 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, network connection, and an external device.

15. The system according to claim 14, wherein said network is connected to one of a local area network, wide area network, Internet and a wireless network or a combination of the networks.

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

17. The system according to claim 11, wherein storage is mounted as shared storage for both primary application and each backup application.

18. The system according to claim 1, wherein a resource access 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 message.

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

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