Data processing service

• US 8,996,456 B2
• Filed: 11/14/2012
• Issued: 03/31/2015
• Est. Priority Date: 11/14/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Naidu, Siddartha, Agarwal, Amit, Sheldon, Michael, Kadatch, Andrew, Tigani, Jordan, Condit, Jeremy P. C.
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US13/677,069
• Publication Number:
  US 20130124467A1
• Time in Patent Office: 867 Days
• Field of Search: 707/610, 707/614, 707/770, 707/769, 707/812, 707/782
• US Class Current: 707/610
• 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 computerized system, comprising:

a first data center of multiple data centers, the multiple data centers configured to replicate a logical collection of data among the multiple data centers,

wherein the logical collection of data comprises multiple logical partitions of data that are distinct from each other and that as a whole comprise the logical collection of data, wherein the multiple logical partitions of data comprise a first logical partition of data, a second logical partition of data, and a third logical partition of data,

wherein each of the multiple data centers includes multiple computers that each include at least one processor and computer-readable memory;

a second data center of the multiple data centers;

a third data center of the multiple data centers;

a first writing subsystem, executable by at least some of the computers at the first data center, that is designated to write updates to a copy of the first logical partition of data that is stored by the first data center;

a second writing subsystem, executable by at least some of the computers at the second data center, that is designated to write updates to a copy of the second logical partition of data that is stored by the second data center;

a third writing subsystem, executable by at least some of the computers at the third data center, that is designated to write updates to a copy of the third logical partition of data that is stored by the third data center;

a first replicating subsystem, executable by at least some of the computers at the first data center, to replicate the updates to the first logical partition of data from the first data center to the second data center and the third data center;

a second replicating subsystem, executable by at least some of the computers at the second data center, to replicate the updates to the second logical partition of data from the second data center to the first data center and the third data center;

a third replicating subsystem, executable by at least some of the computers at the third data center, to replicate the updates to the third logical partition of data from the third data center to the first data center and the second data center;

a writing query distributor, executable by one or more computers, that is configured to receive, over a period of time, multiple queries from multiple client computing devices that are geographically remote from the multiple data centers and the one or more computers on which the writing query distributor is executable, and to;

(i) distribute, to the first writing subsystem at the first data center, those of the multiple queries that have been identified as being structured to write to the first logical partition of data,

(ii) distribute, to the second writing subsystem at the second data center, those of the multiple queries that have been identified as being structured to write to the second logical partition of data, and

(iii) distribute, to the third writing subsystem at the third data center, those of the multiple queries that have been identified as being structured to write to the third logical partition of data.

2. The computerized system of claim 1, wherein:

those of the multiple queries that have been identified as being structured to write to the first logical partition of data are all of the multiple queries that have been identified as being structured to write to the first logical partition of data;

those of the multiple queries that have been identified as being structured to write to the second logical partition of data are all of the multiple queries that have been identified as being structured to write to the second logical partition of data; and

those of the multiple queries that have been identified as being structured to write to the third logical partition of data are all of the multiple queries that have been identified as being structured to write to the third logical partition of data.

3. The computerized system of claim 1, wherein:

the period of time is at least an hour;

those of the multiple queries that have been identified as being structured to write to the first logical partition of data include at least a hundred queries;

those of the multiple queries that have been identified as being structured to write to the second logical partition of data include at least a hundred queries; and

those of the multiple queries that have been identified as being structured to write to the third logical partition of data include at least a hundred queries.

4. The computerized system of claim 1, further comprising:

a first querying subsystem, executable by at least some of the computers at the first data center, to receive queries and, in response, to query copies of the first logical partition of data, second logical partition of data, and third logical partition of data that are stored by the first data center;

a second querying subsystem, executable by at least some of the computers at the second data center, to receive queries and, in response, to query copies of the first logical partition of data, second logical partition of data, and third logical partition of data that are stored by the second data center; and

a third querying subsystem, executable by at least some of the computers at the third data center, to receive queries and, in response, to query copies of the first logical partition of data, second logical partition of data, and third logical partition of data that are stored by the third data center.

5. The computerized system of claim 1, wherein:

the first data center comprises at least fifty computer processors;

the second data center comprises at least fifty computer processors; and

the third data center comprises at least fifty computer processors.

6. The computerized system of claim 1, further comprising:

a reading query router, executable by at least one computer, to receive a reading query that is structured to select data from a table that is stored within the logical collection of data, and to route the reading query to one of the first data center, the second data center, or the third data center that is geographically closest to the at least one computer, without regard for whether the table is logically stored within the first logical partition of data, the second logical partition of data, or the third logical partition of data.

7. The computerized system of claim 6, wherein:

the reading query is structured to select data from the second logical partition of data; and

the reading query router is configured to route the reading query to the first data center during the period of time as a result of determining that the first data center is geographically closest to the at least one computer.

8. The computerized system of claim 1, wherein the one or more computers through which the writing query distributor is executable are one or more computers of the first data center, the second data center, or the third data center.

9. A computer-implemented method, comprising:

receiving, by a computing system, a query that is structured to cause a querying system to select data from a database table;

identifying, by the computing system, that the data that is to be selected from the database table is stored within one or more logical portions of data;

identifying, by the computing system, multiple data centers among which the one or more logical portions of data are designated for replication;

identifying, by the computing system, that the one or more logical portions of data have been fully replicated among none of the multiple data centers;

in response to identifying that the one or more logical portions of data have 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 one or more logical portions of data, wherein identifying the most-recent data center includes identifying that a write timestamp for a copy of the one or more logical portions of data stored by the most-recent data center is more recent than write timestamps for copies of the one or more logical portions of data stored by other of the multiple data centers that do not include the most-recent data center; and

sending, by the computing system, the query to the identified most-recent data center, so as to cause the identified most-recent data center to select data, in accordance with the query, from a copy of the database table that is stored by the most-recent data center.

10. The computer-implemented method of claim 9, further comprising:

receiving, by the computing system, a second query that is structured so as to cause the querying system to select second data from a second database table;

identifying, by the computing system, that the second data that is to be selected from the second database table is stored by one or more second logical portions of data;

identifying, by the computing system, that the one or more second logical portions of data are designated for replication among the multiple data centers;

identifying, by the computing system, that one or more of the second logical portions of data have been fully replicated among at least two of the multiple data centers;

in response to identifying that the one or more of the second logical portions of data have been fully replicated among at least two of the multiple data centers, identifying, by the computing system, one of the at least two data centers to handle the second query based at least in part on a first criterion; and

sending, by the computing system, the second query to the identified one data center for execution of the second query.

11. The computer-implemented method of claim 10, wherein identifying that the one or more of the second logical portions have been fully replicated among at least two of the multiple data centers includes:

identifying, by the computing system, a first data center of the multiple data centers as being one of the at least two of the multiple data centers among which the one or more second logical portions of data have been fully replicated, based on identifying that the first data center is designated as a data center that initially updates a local copy of the one or more second logical portions of data before other of the multiple data centers update respective local copies of the one or more second logical portions of data; and

identifying, by the computing system, a second data center of the multiple data centers as being another of the at least two of the multiple data centers among which the one or more second logical portions of data have been fully replicated, based on identifying that a copy of the one or more second logical portions of data that is stored by the second data center has a write timestamp that is more recent than a write timestamp for a copy of the one or more second logical portions of data that is stored by the first data center.

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

13. The computer-implemented method of claim 11, further comprising:

receiving, by the computing system, a third query that is structured so as to select data from a third database table;

identifying, by the computing system, that the third data that is to be selected from the database table is stored by the one or more third logical portions of data;

identifying, by the computing system, that the one or more third logical portions of data are 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 logical data; and

in response to identifying that a single one of the multiple data centers has fully replicated the logical data, sending, by the computing system, the third query to the single one of the multiple data centers.

14. The computer-implemented method of claim 10, wherein identifying one of the at least two data centers to handle the second query based at least in part on the first criterion includes identifying which of the at least two data centers is geographically closest to a remote computing device that transmitted the second query to the computing system.

15. The computer-implemented method of claim 10, wherein identifying one of the at least two data centers to handle the second query based at least in part on the first criterion includes identifying which of the at least two data centers is associated with a shortest trip time for a message transmitted between (i) a remote computing device that transmitted the second query to the computing system, and (ii) each of the at least two data centers.

16. The computer-implemented method of claim 10, wherein identifying one of the at least two data centers to handle the second query based at least in part on the first criterion includes identifying which of the at least two data centers has been determined to have a most available computing capacity from among the at least two data centers.