Processing mutations for a remote database

• US 10,521,417 B2
• Filed: 06/24/2015
• Issued: 12/31/2019
• 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., Tsai, Steve
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Nafziger, David M
• Application Number:
  US14/748,642
• Publication Number:
  US 20150370844A1
• Time in Patent Office: 1,651 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:

receiving, by a server, a log of database mutations from a single client device, the log of database mutations indicating changes previously made to a client version of a database stored on the single client device, and each database mutation specifying;

an entity included in the database, where the entity includes a row or record in the database;

an operation for the entity; and

a client version number for the entity;

identifying, in the log of database mutations and by the server, two or more database mutations that each specify a same client version number for a same entity and specify a different operation that was performed on the single client device for the same entity;

determining, by the server and based on a conflict resolution policy that describes a policy for resolving a conflict in the entity between the single client device and the server, that a conflict between the single client device and the server for a first database mutation of the two or more database mutations resolves in favor of the client device over the server; and

in response to determining the conflict between the single client device and the server for the first database mutation of the two or more database mutations resolves in favor of the client device over the server, collapsing the first database mutation and a second database mutation of the two or more database mutations, that specifies setting a value of the entity to a different value than the first database mutation specifies, into a single database mutation that specifies a single operation that sets the value of the entity to the different value,

wherein a conflict between the second database mutation and the server resolves in favor of the client device because both the first database mutation occurred before the second database mutation and the conflict between first database mutation and the server resolves in favor of the client device.

2. The method of claim 1, wherein determining, by the server and based on a conflict resolution policy that describes a policy for resolving a conflict in the entity between the single client device and the server, that a conflict between the single client device and the server for a first database mutation of the two or more database mutations resolves in favor of the client device over the server comprises:

identifying a first database mutations of the two or more database mutations that, based on the conflict resolution policy, would be applied to a remote database.

3. The method of claim 2, wherein collapsing the first database mutation and the second database mutation comprises:

collapsing the first database mutation and each other database mutation of the two or more database mutations that occurs subsequent to the first database mutation into the single database mutation.

4. The method of claim 3, wherein collapsing the first database mutation and each other database mutation into the single database mutation that specifies the single operation comprises collapsing, into the single database mutation, a most recent database mutation from the two or more database mutations.

5. The method of claim 1, wherein each of the two or more database mutations specify the conflict resolution policy.

6. The method of claim 1, further comprising:

for the single database mutation and for each other database mutation included in the log;

querying a remote version of the database to identify a base version number for the entity specified by the mutation;

determining whether the client version number for the entity matches the base version number for the entity;

in response to determining that the client version number matches the base version number;

performing, for the remote version of the database, the operation specified by the mutation;

generating response data for the single client device, the response data including an updated base version number for the entity; and

in response to determining that the client version number does not match the base version number;

determining, based on a conflict resolution policy, whether the operation specified by the mutation will be performed;

performing, for the remote version of the database, the operation specified by the mutation only if it is determined that the operation specified by the mutation will be performed; and

generating conflict response data for the single client device, the conflict response data specifying whether the operation specified by the mutation was performed.

7. The method of claim 6, wherein the conflict response data for the single client device includes, for the entity specified by the mutation, a current version for the entity stored in the remote version of the database.

8. 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;

receiving, by a server, a log of database mutations from a single client device, the log of database mutations indicating changes previously made to a client version of a database stored on the single client device, and each database mutation specifying;

an entity included in the database, where the entity includes a row or record in the database;

an operation for the entity; and

a client version number for the entity;

identifying, in the log of database mutations and by the server, two or more database mutations that each specify a same client version number for a same entity and specify a different operation that was performed on the single client device for the same entity;

determining, by the server and based on a conflict resolution policy that describes a policy for resolving a conflict in the entity between the single client device and the server, that a conflict between the single client device and the server for a first database mutation of the two or more database mutations resolves in favor of the client device over the server; and

in response to determining the conflict between the single client device and the server for the first database mutation of the two or more database mutations resolves in favor of the client device over the server, collapsing the first database mutation and a second database mutation of the two or more database mutations, that specifies setting a value of the entity to a different value than the first database mutation specifies, into a single database mutation that specifies a single operation that sets the value of the entity to the different value,

wherein a conflict between the second database mutation and the server resolves in favor of the client device because both the first database mutation occurred before the second database mutation and the conflict between first database mutation and the server resolves in favor of the client device.

9. The system of claim 8, wherein determining, by the server and based on a conflict resolution policy that describes a policy for resolving a conflict in the entity between the single client device and the server, that a conflict between the single client device and the server for a first database mutation of the two or more database mutations resolves in favor of the client device over the server comprises:

identifying a first database mutations of the two or more database mutations that, based on the conflict resolution policy, would be applied to a remote database.

10. The system of claim 9, wherein collapsing the first database mutation and the second database mutation comprises:

collapsing the first database mutation and each other database mutation of the two or more database mutations that occurs subsequent to the first database mutation into the single database mutation.

11. The system of claim 10, wherein collapsing the first database mutation and each other database mutation into the single database mutation that specifies the single operation comprises collapsing, into the single database mutation, a most recent database mutation from the two or more database mutations.

12. The system of claim 8, wherein each of the two or more database mutations specify the conflict resolution policy.

13. The system of claim 8, wherein the operations further comprise:

for the single database mutation and for each other database mutation included in the log;

querying a remote version of the database to identify a base version number for the entity specified by the mutation;

determining whether the client version number for the entity matches the base version number for the entity;

in response to determining that the client version number matches the base version number;

performing, for the remote version of the database, the operation specified by the mutation;

generating response data for the single client device, the response data including an updated base version number for the entity; and

in response to determining that the client version number does not match the base version number;

determining, based on a conflict resolution policy, whether the operation specified by the mutation will be performed;

performing, for the remote version of the database, the operation specified by the mutation only if it is determined that the operation specified by the mutation will be performed; and

generating conflict response data for the single client device, the conflict response data specifying whether the operation specified by the mutation was performed.

14. The system of claim 13, wherein the conflict response data for the single client device includes, for the entity specified by the mutation, a current version for the entity stored in the remote version of the database.

15. 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:

receiving, by a server, a log of database mutations from a single client device, the log of database mutations indicating changes previously made to a client version of a database stored on the single client device, and each database mutation specifying;

an entity included in the database, where the entity includes a row or record in the database;

an operation for the entity; and

a client version number for the entity;

identifying, in the log of database mutations and by the server, two or more database mutations that each specify a same client version number for a same entity and specify a different operation that was performed on the single client device for the same entity;

determining, by the server and based on a conflict resolution policy that describes a policy for resolving a conflict in the entity between the single client device and the server, that a conflict between the single client device and the server for a first database mutation of the two or more database mutations resolves in favor of the client device over the server; and

in response to determining the conflict between the single client device and the server for the first database mutation of the two or more database mutations resolves in favor of the client device over the server, collapsing the first database mutation and a second database mutation of the two or more database mutations, that specifies setting a value of the entity to a different value than the first database mutation specifies, into a single database mutation that specifies a single operation that sets the value of the entity to the different value,

wherein a conflict between the second database mutation and the server resolves in favor of the client device because both the first database mutation occurred before the second database mutation and the conflict between first database mutation and the server resolves in favor of the client device.

16. The computer readable medium of claim 15, wherein determining, by the server and based on a conflict resolution policy that describes a policy for resolving a conflict in the entity between the client device and the server, that a conflict between the single client device and the server for a first database mutation of the two or more database mutations resolves in favor of the client device over the server comprises:

identifying a first database mutations of the two or more database mutations that, based on the conflict resolution policy, would be applied to a remote database.

17. The computer readable medium of claim 16, wherein collapsing the first database mutation and the second database mutation comprises:

collapsing the first database mutation and each other database mutation of the two or more database mutations that occurs subsequent to the first database mutation into the single database mutation.

18. The computer readable medium of claim 17, wherein collapsing the first database mutation and each other database mutation into the single database mutation that specifies the single operation comprises collapsing, into the single database mutation, a most recent database mutation from the two or more database mutations.