Database replication

• US 9,361,348 B1
• Filed: 07/28/2014
• Issued: 06/07/2016
• Est. Priority Date: 10/05/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ashcraft, Kenneth M., Kasera, Vishal, Leon, Jean-Michel, Agarwal, Amit
• Primary Examiner(s): Le, Debbie
• Application Number:
  US14/444,220
• Time in Patent Office: 680 Days
• Field of Search: 707/637
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• 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: H04L 49/9005 using dynamic buffer space allocation
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]

Abstract

A database server receives a request from a client application for performing a data transaction on persistent data storage. The request is sent to a set of replication servers. An acknowledgement for the request is received from each replication server, including a start sequence number and an end sequence number for data that is stored in local cache of the replication server, and a latest committed sequence number for data that was written to the persistent data storage by the replication server. A maximum value of latest committed sequence numbers received from the set of replication servers is determined. For each replication server, it is examined whether there is a gap between the start sequence number for data stored in local cache and the maximum value of the latest committed sequence numbers. Based on the examining, it is determined whether there is an occurrence of loss of data.

Claims

1. A method comprising:

receiving, at a database server, a read request from a client application for reading data from persistent data storage;

determining, by the database server, whether one or more replication servers associated with the database server have a complete cache window corresponding to data of the client application, wherein a complete cache window indicates an entire amount of uncommitted data for the client application is stored in a local cache of a replication server and the uncommitted data is contiguous with committed data associated with the client application, wherein committed data is data that has been written to persistent data storage and uncommitted data is data that has not been written to persistent data storage but is in local cache of the replication servers;

based on determining that one or more replication servers associated with the database server have a complete cache window, selecting a replication server from the one or more replication servers; and

sending the read request to the selected replication server;

wherein sequence numbers are associated with the data, and wherein a replication server has a cache start sequence number and a cache end sequence number for uncommitted data for the client application present in the local cache of the replication server, the cache start sequence number associated with least recent uncommitted data for the client application present in the local cache and the cache end sequence number associated with most recent uncommitted data for the client application present in the local cache.

2. The method of claim 1, wherein the one or more replication servers are geographically distributed.

3. The method of claim 1, wherein a replication server is configured to perform read and write operations directly on the persistent data storage.

4. The method of claim 1, wherein a difference between the cache start sequence number and the cache end sequence number for the uncommitted data in the local cache of the replication server indicates a cache window for the client application at the replication server.

5. The method of claim 4, wherein the cache window includes the complete cache window for the client application if the local cache includes data with a sequence number that is greater by one than a highest sequence number of committed data for the client application, and the cache end sequence number corresponds to a highest sequence number of the uncommitted data for the client application received from the database server by the one or more replication servers.

6. The method of claim 1, wherein determining whether one or more replication servers associated with the database server have a complete cache window corresponding to data of the client application comprises:

receiving, at the database server and from each replication server, a cache start sequence number and a cache end sequence number associated with the respective replication server, along with information indicating a highest sequence number of the data committed by the replication server for the client application;

determining an overall highest sequence number of the committed data for the client application based on the information received from the replication servers;

selecting a subset of the replication servers that each have data with a sequence number that is greater than the overall highest sequence number by one;

determining a replication server in the selected subset of the replication servers with a highest value of the cache end sequence number; and

selecting the determined replication server as having a complete cache window.

7. The method of claim 1, wherein selecting a replication server from the one or more replication servers comprises:

selecting the replication server from the one or more replication servers based on a random selection mechanism.

8. The method of claim 1, wherein selecting a replication server from the one or more replication servers comprises:

determining a level of processing activity at each of the one or more replication servers; and

selecting a replication server with a level of processing activity that is lower than the level of processing activity associated with all other replication servers in the one or more replication servers.

9. A computer program product, suitably embodied in a non-transitory machine-readable medium and including instructions executable by a processor, the instructions configured to cause the processor to perform operations comprising:

receiving, at a database server, a read request from a client application for reading data from persistent data storage;

determining, by the database server, whether one or more replication servers associated with the database server have a complete cache window corresponding to data of the client application, wherein a complete cache window indicates an entire amount of uncommitted data for the client application is stored in a local cache of a replication server and the uncommitted data is contiguous with committed data associated with the client application, wherein committed data is data that has been written to persistent data storage and uncommitted data is data that has not been written to persistent data storage but is in local cache of the replication servers;

based on determining that one or more replication servers associated with the database server have a complete cache window, selecting a replication server from the one or more replication servers; and

sending the read request to the selected replication server,

wherein sequence numbers are associated with the data, and wherein a replication server has a cache start sequence number and a cache end sequence number for uncommitted data for the client application present in the local cache of the replication server, the cache start sequence number associated with least recent uncommitted data for the client application present in the local cache and the cache end sequence number associated with most recent uncommitted data for the client application present in the local cache.

10. The computer program product of claim 9, wherein the one or more replication servers are geographically distributed.

11. The computer program product of claim 9, wherein a replication server is configured to perform read and write operations directly on the persistent data storage.

12. The computer program product of claim 10, wherein a difference between the cache start sequence number and the cache end sequence number for the uncommitted data in the local cache of the replication server indicates a cache window for the client application at the replication server.

13. The computer program product of claim 12, wherein the cache window includes the complete cache window for the client application if the local cache includes data with a sequence number that is greater by one than a highest sequence number of committed data for the client application, and the cache end sequence number corresponds to a highest sequence number of the uncommitted data for the client application received from the database server by the one or more replication servers.

14. The computer program product of claim 10, wherein the instructions that are configured to cause the processor to perform operations comprising determining whether one or more replication servers associated with the database server have a complete cache window corresponding to data of the client application includes instructions that are configured to cause the processor to perform operations comprising:

receiving, at the database server and from each replication server, a cache start sequence number and a cache end sequence number associated with the respective replication server, along with information indicating a highest sequence number of the data committed by the replication server for the client application;

determining an overall highest sequence number of the committed data for the client application based on the information received from the replication servers;

selecting a subset of the replication servers that each have data with a sequence number that is greater than the overall highest sequence number by one;

determining a replication server in the selected subset of the replication servers with a highest value of the cache end sequence number; and

selecting the determined replication server as having a complete cache window.

15. The computer program product of claim 9, wherein the instructions that are configured to cause the processor to perform operations comprising selecting a replication server from the one or more replication servers includes instructions that are configured to cause the processor to perform operations comprising:

selecting the replication server from the one or more replication servers based on a random selection mechanism.

16. The computer program product of claim 9, wherein the instructions that are configured to cause the processor to perform operations comprising selecting a replication server from the one or more replication servers includes instructions that are configured to cause the processor to perform operations comprising:

determining a level of processing activity at each of the one or more replication servers; and

selecting a replication server with a level of processing activity that is lower than the level of processing activity associated with all other replication servers in the one or more replication servers.