DATABASE REPLICATION

• US 20100121817A1
• Filed: 01/20/2010
• Published: 05/13/2010
• Est. Priority Date: 03/15/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Giannandrea, John, MEYER, Scott, Degener, Jutta, Michener, Barak
• Granted Patent: US 8,204,856 B2
• Time in Patent Office: Days
• 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 computer implemented method for providing a graph database which contains another graph database, comprising the steps of:

providing a master database;

providing at least one replica database core comprising an identity of said master database;

providing a concentric replica database to said replica database core to store any relatively long-lived data which relates to said replica database core;

for each transaction in a replica stream, producing an equivalent set of writes and applying them to said concentric replica database;

wherein said concentric replica database comprises a superset of said master database.

2. A database replication method, comprising the steps of:

providing a master database against which all writes occur;

providing a processor configured for assigning sequential IDs to each primitive in said database;

providing a plurality of replica machines, each replica machine establishing a connection with said master database;

said master database sending every primitive that is written to it to each of said replicas; and

providing a plurality of middle tier machines, each middle tier machine having one connection to a replica;

wherein when a middle tier machine sends a write to a corresponding replica, said replica uses a second connection to forward said write to said master database;

said master database performing said write and returning a result to said middle tier machine via a corresponding replica.

3. The method of claim 2, further comprising the step of:

providing a plurality of master databases for at least one replica.

4. The method of claim 2, further comprising the step of:

configuring at least two replicas as respective branches of a tree structure.

5. A parallel processing method for a database, comprising the steps of:

providing a database against which all writes occur;

providing a plurality of processors, each processor establishing a connection with said database; and

each processor writing every primitive it processes to said database.

6. A computer implemented method for identifying poison queries and preventing connections to a database from trying to execute them, comprising the steps of:

a processor configured for identifying poison queries by storing a hash of a currently executing query into a shared memory;

when a parent process determines that a child has crashed, said parent process reading said hash identifying a query that was running at the time of said crash;

providing a dictionary which maps a hash version of a query to a death-count and date, where said death-count is a number of crashes associated with a query represented by said hash and said date is the date of a most recent crash;

adjusting said death-count and date as poison queries arrive; and

when an entry'"'"'s death count exceeds a threshold broadcasting antidote messages to all connections, wherein new connections receive antidote messages for all poison queries immediately after connecting.