Data processing service

• US 10,176,225 B2
• Filed: 03/23/2015
• Issued: 01/08/2019
• Est. Priority Date: 11/14/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Naidu, Siddartha, Agarwal, Amit, Sheldon, Michael, Kadatch, Andrew, Tigani, Jordan, Condit, Jeremy P. C.
• Primary Examiner(s): Beausoliel, Jr., Robert W
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US14/665,026
• Publication Number:
  US 20150193504A1
• Time in Patent Office: 1,387 Days
• Field of Search: 707610, 707611, 707612, 707613, 707619, 707690
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/248 Presentation of query results
• 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 16/275 Synchronous replication
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06F 8/453 Data distribution

Abstract

In general, the subject matter described in this disclosure can be embodied in methods, systems, and program products. A system includes a first data center, a second data center, and a third data center. The multiple data centers are configured to replicate a logical collection of data that comprises multiple logical partitions of data. The system comprises a first writing subsystem that is designated to write updates to a copy of a first logical partition of data that is stored by the first data center. The system comprises a second writing subsystem that is designated to write updates to a copy of a second logical partition of data that is stored by the second data center. The system comprises a third writing subsystem that is designated to write updates to a copy of a third logical partition of data that is stored by the third data center.

Claims

1. A computer-implemented method, comprising:

receiving, by a computing system and from a remote computing device, a first query that is structured to cause a querying system to select first data;

identifying, by the computing system, that the first data is stored within a first logical portion of data that is designated for replication among multiple data centers;

identifying, by the computing system, that the first logical portion of data has been fully replicated among none of the multiple data centers;

in response to identifying that the first logical portion of data has been fully replicated among none of the multiple data centers, identifying, by the computing system, a most-recent data center of the multiple data centers that most-recently updated the first logical portion of data;

sending, by the computing system, the first query to the identified most-recent data center, so as to cause the identified most-recent data center to select the first data and send the first data to the remote computing device, in accordance with the first query, from a copy of the first logical portion of data that is stored by the identified most-recent data center;

receiving, by the computing system and from the remote computing device, a second query that is structured to cause the querying system to select second data;

identifying, by the computing system, that the second data is stored within a second logical portion of data that is designated for replication among the multiple data centers, with a first data center of the multiple data centers being designated to always be an initial data center to update its copy of the second logical portion of data before other data centers of the multiple data centers update their respective copies of the second logical portion of data;

identifying, that the second logical portion of data has been fully replicated to both the first data center and a second data center of the multiple data centers, based on comparing a write timestamp for a copy of the second logical portion of data that is stored by the second data center to a write timestamp for a copy of the second logical portion of data that is stored by the first data center that is designated to always be the initial data center to update its copy of the second logical portion of data, and determining based on determining that the write timestamp for the copy of the second logical portion of data that is stored by the second data center is more recent than the write timestamp for the copy of the second logical portion of data that is stored by the first data center;

in response to identifying that the second logical portion of data has been fully replicated among the first data center and the second data center, selecting one of the first data center and the second data center to handle the second query based at least in part on criterion that includes;

(1) identifying which of the first data center and the second data center is geographically closest to the remote computing device that transmitted the second query to the computing system;

(2) identifying which of the first data center and the second data center is associated with a shortest trip time for a message transmitted between (a) the remote computing device that transmitted the second query to the computing system, and (b) each of the first data center and the second data center, and

(3) identifying which of the first data center and the second data center has been determined to have most available computing capacity from among the first data center and the second data center; and

sending, by the computing system, the second query to the selected one data center for execution of the second query, so as to cause the selected one data center to send a copy of the second data to the remote computing device.

2. The computer-implemented method of claim 1, wherein the computing system is adapted to not select certain of the multiple data centers as having fully replicated the second logical portion of data as a result of identifying that copies of the second logical portion of data stored by the certain data centers have write timestamps for the copies of the second logical portion of data that are less recent than the write timestamp for the copy of the second logical portion of data that is stored by the first data center.

3. The computer-implemented method of claim 1, further comprising:

receiving, by the computing system and from the remote computing device, a third query that is structured to select third data;

identifying, by the computing system, that the third data is stored within a third logical portion of data that is designated for replication among the multiple data centers;

identifying, by the computing system, that a single one of the multiple data centers has fully replicated the third logical portion of data; and

in response to identifying that a single one of the multiple data centers has fully replicated the third logical portion of data, sending, by the computing system, the third query to the single one of the multiple data centers, so as to cause the single one of the multiple data centers to send the third to the remote computing device.

4. The computer-implemented method of claim 1, wherein the computing system identifies that the first logical portion of data has been fully replicated among none of the multiple data centers as a result of the computing system having transitioned data stored by one of the multiple data centers to another data center during a process of transferring responsibility for storing the first logical portion of data from the one of the multiple data centers to the another data center.

5. One or more computer-readable devices including instructions that, when executed by one or more processors, cause performance of operations that comprise:

receiving, by a computing system and from a remote computing device, a first query that is structured to cause a querying system to select first data;

identifying, by the computing system, that the first data is stored within a first logical portion of data that is designated for replication among multiple data centers;

identifying, by the computing system, that the first logical portion of data has been fully replicated among none of the multiple data centers;

in response to identifying that the first logical portion of data has been fully replicated among none of the multiple data centers, identifying, by the computing system, a most-recent data center of the multiple data centers that most-recently updated the first logical portion of data;

sending, by the computing system, the first query to the identified most-recent data center, so as to cause the identified most-recent data center to select the first data and send the first data to the remote computing device, in accordance with the first query, from a copy of the first logical portion of data that is stored by the identified most-recent data center;

receiving, by the computing system and from the remote computing device, a second query that is structured to cause the querying system to select second data;

identifying, by the computing system, that the second data is stored within a second logical portion of data that is designated for replication among the multiple data centers, with a first data center of the multiple data centers being designated to always be an initial data center to update its copy of the second logical portion of data before other data centers of the multiple data centers update their respective copies of the second logical portion of data;

identifying, that the second logical portion of data has been fully replicated to both the first data center and a second data center of the multiple data centers, based on comparing a write timestamp for a copy of the second logical portion of data that is stored by the second data center to a write timestamp for a copy of the second logical portion of data that is stored by the first data center that is designated to always be the initial data center to update its copy of the second logical portion of data, and determining based on determining that the write timestamp for the copy of the second logical portion of data that is stored by the second data center is more recent than the write timestamp for the copy of the second logical portion of data that is stored by the first data center;

in response to identifying that the second logical portion of data has been fully replicated among the first data center and the second data center, selecting one of the first data center and the second data center to handle the second query based at least in part on criterion that includes;

(1) identifying which of the first data center and the second data center is geographically closest to the remote computing device that transmitted the second query to the computing system;

(2) identifying which of the first data center and the second data center is associated with a shortest trip time for a message transmitted between (a) the remote computing device that transmitted the second query to the computing system, and (b) each of the first data center and the second data center, and

(3) identifying which of the first data center and the second data center has been determined to have most available computing capacity from among the first data center and the second data center; and

sending, by the computing system, the second query to the selected one data center for execution of the second query, so as to cause the selected one data center to send a copy of the second data to the remote computing device.

6. The one or more computer-readable devices of claim 5, wherein the computing system is adapted to not select certain of the multiple data centers as having fully replicated the second logical portion of data as a result of identifying that copies of the second logical portion of data stored by the certain data centers have write timestamps for the copies of the second logical portion of data that are less recent than the write timestamp for the copy of the second logical portion of data that is stored by the first data center.

7. The one or more computer-readable devices of claim 5, wherein the operations further comprise:

receiving, by the computing system and from the remote computing device, a third query that is structured to select third data;

identifying, by the computing system, that the third data is stored within a third logical portion of data that is designated for replication among the multiple data centers;

identifying, by the computing system, that a single one of the multiple data centers has fully replicated the third logical portion of data; and

in response to identifying that a single one of the multiple data centers has fully replicated the third logical portion of data, sending, by the computing system, the third query to the single one of the multiple data centers, so as to cause the single one of the multiple data centers to send the third to the remote computing device.