PROCESSING MUTATIONS FOR A REMOTE DATABASE

• US 20150370844A1
• Filed: 06/24/2015
• Published: 12/24/2015
• Est. Priority Date: 06/24/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chen, Jianjun, Fuller, Alfred R., Tsai, Steve
• Granted Patent: US 10,521,417 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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.

2. The method of claim 1, wherein determining, based on a conflict resolution policy, that the two or more database mutations are eligible for collapsing comprises:

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

3. The method of claim 2, wherein collapsing the two or more database mutations 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 a single database mutation.

4. The method of claim 3, wherein collapsing the first database mutation and each other database mutation 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.

5. The method of claim 1, wherein each of the two or more database mutations eligible for collapsing 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 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 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 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 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.

9. The system of claim 8, wherein determining, based on a conflict resolution policy, that the two or more database mutations are eligible for collapsing comprises:

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

10. The system of claim 9, wherein collapsing the two or more database mutations 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 a single database mutation.

11. The system of claim 10, wherein collapsing the first database mutation and each other database mutation 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.

12. The system of claim 8, wherein each of the two or more database mutations eligible for collapsing 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 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 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 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 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 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.

16. The computer readable medium of claim 15, wherein determining, based on a conflict resolution policy, that the two or more database mutations are eligible for collapsing comprises:

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

17. The computer readable medium of claim 16, wherein collapsing the two or more database mutations 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 a single database mutation.

18. The computer readable medium of claim 17, wherein collapsing the first database mutation and each other database mutation 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.

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

20. The computer readable medium of claim 15, 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 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 client device, the conflict response data specifying whether the operation specified by the mutation was performed.