Database replication

• US 8,204,856 B2
• Filed: 01/20/2010
• Issued: 06/19/2012
• Est. Priority Date: 03/15/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Meyer, Scott, Degener, Jutta, Michener, Barak, Giannandrea, John
• Primary Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US12/690,696
• Publication Number:
  US 20100121817A1
• Time in Patent Office: 881 Days
• Field of Search: None
• US Class Current: 707/623
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation

Abstract

A new database design is implemented in which everything in the database is modeled with primitives, including the links and nodes for a graph tuple store. A query syntax provides a nested tree of constraints with a single global schema. Various optimization techniques for queries and replication techniques are also described.

Claims

1. A method performed by a system of one or more computers, the method comprising:

receiving a transaction representing an update to a master graph database, the transaction including a new primitive and a first unique identifier for the new primitive in the master graph database;

updating a concentric graph database with the new primitive, wherein the concentric graph database includes a first plurality of primitives and a second plurality of primitives, wherein each of the first plurality of primitives is also included in the master graph database and none of the second plurality of primitives are included in the master graph database, and wherein updating the concentric graph database with the new primitive comprises assigning a different, second unique identifier to the new primitive in the concentric graph database; and

storing a mapping from the second unique identifier to the first unique identifier in the concentric graph database.

2. The method of claim 1, further comprising:

monitoring a replica stream, wherein, for each primitive added to the master graph database, the master graph database publishes a transaction over the replica stream, the transaction including the primitive added to the master graph database.

3. The method of claim 1, wherein, for each of the first plurality of primitives, the concentric graph database includes a respective mapping from a second unique identifier for the primitive to a first unique identifier associated with the primitive.

4. The method of claim 3, wherein, for each primitive of the first plurality of primitives added to the concentric graph database before any of the second plurality of primitives, the respective second unique identifier associated with the primitive is equivalent to the respective first unique identifier associated with the primitive.

5. The method of claim 4, wherein, for each primitive of the first plurality of primitives added to the concentric graph database after an earliest primitive in the second plurality of primitives, the respective second unique identifier for the first primitive is different from the respective first unique identifier for the first primitive.

6. The method of claim 1, wherein the new primitive includes a particular first identifier of a particular primitive in the first plurality of primitives that the new primitive is modifying, and wherein updating the concentric database with the new primitive comprises:

identifying a particular second identifier for the particular primitive; and

replacing, in the new primitive in the concentric graph database, the particular first identifier with the particular second identifier.

7. The method of claim 1, further comprising:

storing the mapping as a link primitive in the concentric graph database, wherein the link primitive includes the first unique identifier, the second unique identifier, and data indicating that the link primitive defines an identifier for the new primitive in the concentric database that is equivalent to the second identifier for the new primitive.

8. A system comprising one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

receiving a transaction representing an update to a master graph database, the transaction including a new primitive and a first unique identifier for the new primitive in the master graph database;

updating a concentric graph database with the new primitive, wherein the concentric graph database includes a first plurality of primitives and a second plurality of primitives, wherein each of the first plurality of primitives is also included in the master graph database and none of the second plurality of primitives are included in the master graph database, and wherein updating the concentric graph database with the new primitive comprises assigning a different, second unique identifier to the new primitive in the concentric graph database; and

storing a mapping from the second unique identifier to the first unique identifier in the concentric graph database.

9. The system of claim 8, the operations further comprising:

monitoring a replica stream, wherein, for each primitive added to the master graph database, the master graph database publishes a transaction over the replica stream, the transaction including the primitive added to the master graph database.

10. The system of claim 8, wherein, for each of the first plurality of primitives, the concentric graph database includes a respective mapping from a second unique identifier for the primitive to a first unique identifier associated with the primitive.

11. The system of claim 10, wherein, for each primitive of the first plurality of primitives added to the concentric graph database before any of the second plurality of primitives, the respective second unique identifier associated with the primitive is equivalent to the respective first unique identifier associated with the primitive.

12. The system of claim 11, wherein, for each primitive of the first plurality of primitives added to the concentric graph database after an earliest primitive in the second plurality of primitives, the respective second unique identifier for the first primitive is different from the respective first unique identifier for the first primitive.

13. The system of claim 8, wherein the new primitive includes a particular first identifier of a particular primitive in the first plurality of primitives that the new primitive is modifying, and wherein updating the concentric database with the new primitive comprises:

identifying a particular second identifier for the particular primitive; and

replacing, in the new primitive in the concentric graph database, the particular first identifier with the particular second identifier.

14. The system of claim 8, the operations further comprising:

storing the mapping as a link primitive in the concentric graph database, wherein the link primitive includes the first unique identifier, the second unique identifier, and data indicating that the link primitive defines an identifier for the new primitive in the concentric database that is equivalent to the second identifier for the new primitive.