Processing mutations for a remote database

• US 10,545,948 B2
• Filed: 10/30/2015
• Issued: 01/28/2020
• Est. Priority Date: 06/24/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Chen, Jianjun, Fuller, Alfred R. K., Tsai, Steve
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Nafziger, David M
• Application Number:
  US14/928,011
• Publication Number:
  US 20160048554A1
• Time in Patent Office: 1,551 Days
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• 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

Abstract

Methods, systems, and apparatus are described for processing mutations for a remote database. In one aspect, a method includes receiving a log of database mutations from a client device, the log of database mutations indicating changes previously made to a client version of a database stored on the client device, and each database mutation specifying: an entity included in the database; an operation for the entity; and a client version number for the entity; identifying, in the log of database mutations, two or more database mutations that each specify a same client version number for a same entity; determining, based on a conflict resolution policy, that the two or more database mutations are eligible for collapsing; and collapsing the two or more database mutations into a single database mutation.

Claims

1. A method implemented by one or more data processing apparatus, the method comprising:

accessing a log of database mutations stored on a client device, the log of database mutations indicating changes previously made to a client version of a database stored on the client device, and each database mutation specifying;

an entity included in the database;

an operation for the entity; and

a client version number for the entity;

identifying, in the log of database mutations, two or more database mutations that each specify a same client version number for a same entity, where a first database mutation of the two or more database mutations occurred before a second database mutation of the two or more database mutations;

determining, based on a conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device; and

in response to determining, based on the conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device, collapsing the two or more database mutations into a single database mutation.

2. The method of claim 1, wherein determining, based on a conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device comprises determining that an outcome of the operations specified by the two or more database mutations is independent from values stored for corresponding database entities on a remote version of the database.

3. The method of claim 1, wherein collapsing the two or more database mutations into a single database mutation comprises collapsing, into the single database mutation, a most recent database mutation from the two or more database mutations that are eligible for collapsing.

4. The method of claim 1, wherein each of the two or more database mutations eligible for collapsing specify the conflict resolution policy.

5. The method of claim 1, wherein the conflict resolution policy is a default conflict resolution policy associated with the remote version of the database.

6. The method of claim 1, further comprising:

providing a collapsed log of database mutations to a database server, the collapsed log of database mutations including each mutation in the log of database mutations that was not collapsed and the single database mutation.

7. A system comprising:

one or more data processing apparatus; and

a data store storing instructions that, when executed by the one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising;

accessing a log of database mutations stored on a client device, the log of database mutations indicating changes previously made to a client version of a database stored on the client device, and each database mutation specifying;

an entity included in the database;

an operation for the entity; and

a client version number for the entity;

identifying, in the log of database mutations, two or more database mutations that each specify a same client version number for a same entity, where a first database mutation of the two or more database mutations occurred after a second database mutation of the two or more database mutations;

determining, based on a conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device; and

in response to determining, based on the conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device, collapsing the two or more database mutations into a single database mutation.

8. The system of claim 7, wherein determining, based on a conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device comprises determining that an outcome of the operations specified by the two or more database mutations is independent from values stored for corresponding database entities on a remote version of the database.

9. The system of claim 7, wherein collapsing the two or more database mutations into a single database mutation comprises collapsing, into the single database mutation, a most recent database mutation from the two or more database mutations that are eligible for collapsing.

10. The system of claim 7, wherein each of the two or more database mutations eligible for collapsing specify the conflict resolution policy.

11. The system of claim 7, wherein the conflict resolution policy is a default conflict resolution policy associated with the remote version of the database.

12. The system of claim 7, wherein the operations further comprise:

providing a collapsed log of database mutations to a database server, the collapsed log of database mutations including each mutation in the log of database mutations that was not collapsed and the single database mutation.

13. A non-transitory computer readable medium storing instructions that, when executed by one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising,

accessing a log of database mutations stored on a client device, the log of database mutations indicating changes previously made to a client version of a database stored on the client device, and each database mutation specifying:

an entity included in the database;

an operation for the entity; and

a client version number for the entity;

identifying, in the log of database mutations, two or more database mutations that each specify a same client version number for a same entity, where a first database mutation of the two or more database mutations occurred before a second database mutation of the two or more database mutations;

determining, based on a conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device; and

in response to determining, based on the conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device, collapsing the two or more database mutations into a single database mutation.

14. The computer readable medium of claim 13, wherein determining, based on a conflict resolution policy and the operations specified by the first database mutation and the second database mutation, that the first database mutation of the two or more database mutations would not resolve in favor of the client device while the second database mutation of the two or more database mutations resolve in favor of the server over the client device comprises determining that an outcome of the operations specified by the two or more database mutations is independent from values stored for corresponding database entities on a remote version of the database.

15. The computer readable medium of claim 13, wherein collapsing the two or more database mutations into a single database mutation comprises collapsing, into the single database mutation, a most recent database mutation from the two or more database mutations that are eligible for collapsing.

16. The computer readable medium of claim 13, wherein each of the two or more database mutations eligible for collapsing specify the conflict resolution policy.

17. The computer readable medium of claim 13, wherein the conflict resolution policy is a default conflict resolution policy associated with the remote version of the database.

18. The computer readable medium of claim 13, wherein the operations further comprise:

providing a collapsed log of database mutations to a database server, the collapsed log of database mutations including each mutation in the log of database mutations that was not collapsed and the single database mutation.