Data synchronization with eventual consistency

• US 8,775,682 B1
• Filed: 05/08/2012
• Issued: 07/08/2014
• Est. Priority Date: 05/08/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mathias, Razvan, Korn, Jeffrey L., Sherman, Alexander, Liu, Xiaoyong, Bachand, Albert, Carter, Nicholas Bennett
• Primary Examiner(s): Barry, Lance L
• Application Number:
  US13/467,005
• Time in Patent Office: 791 Days
• Field of Search: 709/248, 707/625
• US Class Current: 709/248
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Computer-implemented methods for synchronizing data between a server and a client are provided. In one aspect, a method includes receiving a request from a client to synchronize data. The request includes a synchronization token that includes client recent synchronization signatures, each client recent synchronization signature representing a state of data synchronization on the client for a certain time period. The method also includes comparing each client recent synchronization signature with a corresponding server recent synchronization signature representing data on a server for the same time period. When the comparison indicates that the data on the client for the time period represented by the client recent synchronization signature is not synchronized with corresponding data on the server for the time period, then the method includes sending the data on the server for the time period to the client. Systems and machine-readable media are also provided.

Claims

1. A computer-implemented method for synchronizing data between a server and a client, the method comprising:

receiving a request from a client to synchronize data, the request comprising a synchronization token, wherein the synchronization token comprises client recent synchronization signatures, each client recent synchronization signature representing a state of data synchronization on the client for a certain time period;

comparing each client recent synchronization signature with a corresponding server recent synchronization signature representing data on a server for the same time period;

when a comparison of a client recent synchronization signature with a corresponding server recent synchronization signature indicates that the data on the client for the time period represented by the client recent synchronization signature is not synchronized with corresponding data on the server for the time period, sending the data on the server for the time period to the client; and

sending an updated synchronization token to the client when the data is sent to the client, wherein the updated synchronization token comprises updated client recent synchronization signatures.

2. The computer-implemented method of claim 1, wherein comparing the client recent synchronization signatures with the server recent synchronization signatures comprises comparing a hash value determined from each client recent synchronization signature with a hash value determined from each corresponding server recent synchronization signature.

3. The computer-implemented method of claim 2, wherein if a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature, the method further comprises:

providing a timestamp value associated with the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for comparison with a timestamp value associated with the data on the client for the time period represented by the client recent synchronization signature; and

wherein sending the data on the server for the time period to the client comprises sending the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for overwriting the data on the client for the time period represented by the client recent synchronization signature when the timestamp value associated with the data on the server is different than the timestamp value associated with the data on the client.

4. The computer-implemented method of claim 2, wherein if a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature, the method further comprises:

providing a timestamp value associated with the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for comparison with a timestamp value associated with queued update data on the client for the time period represented by the client recent synchronization signature; and

wherein sending the data on the server for the time period to the client comprises sending the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for overwriting the queued update data on the client for the time period represented by the client recent synchronization signature when the timestamp value associated with the data on the server is different than the timestamp value associated with the queued update data on the client.

5. The computer-implemented method of claim 2, wherein sending the data on the server for the time period to the client comprises sending the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for merging with the data on the client for the time period represented by the client recent synchronization signature when a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature.

6. The computer-implemented method of claim 5, wherein the merging of the data on the server for the time period represented by the corresponding server recent synchronization signature with the data on the client for the time period represented by the client recent synchronization signature comprises creating a union of differing properties between the data on the server for the time period represented by the corresponding server recent synchronization signature and the data on the client for the time period represented by the client recent synchronization signature.

7. The computer-implemented method of claim 1, wherein sending the data on the server for the time period to the client comprises sending the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for storage when a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature.

8. The computer-implemented method of claim 1, wherein the number of client recent synchronization signatures is determined based on a frequency of data synchronization.

9. The computer-implemented method of claim 8, the number of client recent synchronization signatures is decreased when the frequency of data synchronization is decreased.

10. The computer-implemented method of claim 9, wherein a size of the synchronization token increases as the frequency of data synchronization is increased.

11. The computer-implemented method of claim 1, wherein the data to be synchronized comprises at least one of web browser data, audio data, and electronic mail data.

12. The computer-implemented method of claim 1, wherein the synchronization token comprises a first portion comprising the client recent synchronization signatures and a second portion comprising a replicated synchronization signature for the client, the client replicated synchronization signature representing a state of data synchronization on the client for a time period older than the time periods associated with the client recent synchronization signatures, and the method further comprises:

comparing the client replicated synchronization signature with a corresponding replicated synchronization signature for the server representing data on the server for the same time period; and

when a comparison of the client replicated synchronization signature for the client with the server replicated synchronization signature indicates that the data on the client for the time period represented by the client replicated synchronization signature is not synchronized with corresponding data on the server, sending the data on the server for the time period represented by the client replicated synchronization signature to the client.

13. A system for synchronizing data between a server and a client, the system comprising:

a memory for storing instructions;

a processor configured to execute the instructions to;

receive a request from a client to synchronize data, the request comprising a synchronization token, wherein the synchronization token comprises client recent synchronization signatures, each client recent synchronization signature representing a state of data synchronization on the client for a certain time period;

compare each client recent synchronization signature with a corresponding server recent synchronization signature representing data on a server for the same time period;

when a comparison of a client recent synchronization signature with a corresponding server recent synchronization signature indicates that the data on the client for the time period represented by the client recent synchronization signature is not synchronized with corresponding data on the server for the time period, send the data on the server for the time period to the client; and

send an updated synchronization token to the client when the data is sent to the client, wherein the updated synchronization token comprises updated client recent synchronization signatures.

14. The system of claim 13, wherein the processor being configured to execute the instructions to compare the client recent synchronization signatures with the server recent synchronization signatures comprises the processor being configured to execute the instructions to compare a hash value determined from each client recent synchronization signature with a hash value determined from each corresponding server recent synchronization signature.

15. The system of claim 14, wherein if a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature, then the processor is configured to execute the instructions to:

provide a timestamp value associated with the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for comparison with a timestamp value associated with the data on the client for the time period represented by the client recent synchronization signature; and

wherein the processor being configured to execute the instructions to send the data on the server for the time period to the client comprises the processor being configured to execute the instructions to send the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for overwriting the data on the client for the time period represented by the client recent synchronization signature when the timestamp value associated with the data on the server is different than the timestamp value associated with the data on the client.

16. The system of claim 14, wherein if a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature, the processor is configured to execute the instructions to:

provide a timestamp value associated with the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for comparison with a timestamp value associated with queued update data on the client for the time period represented by the client recent synchronization signature; and

wherein the processor being configured to execute the instructions to send the data on the server for the time period to the client comprises the processor being configured to execute the instructions to send the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for overwriting the queued update data on the client for the time period represented by the client recent synchronization signature when the timestamp value associated with the data on the server is different than the timestamp value associated with the queued update data on the client.

17. The system of claim 14, wherein the processor being configured to execute the instructions to send the data on the server for the time period to the client comprises the processor being configured to execute the instructions to send the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for merging with the data on the client for the time period represented by the client recent synchronization signature when a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature.

18. The system of claim 17, wherein the merging of the data on the server for the time period represented by the corresponding server recent synchronization signature with the data on the client for the time period represented by the client recent synchronization signature comprises creating a union of differing properties between the data on the server for the time period represented by the corresponding server recent synchronization signature and the data on the client for the time period represented by the client recent synchronization signature.

19. The system of claim 13, wherein the processor being configured to execute the instructions to send the data on the server for the time period to the client comprises the processor being configured to execute the instructions to send the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for storage when a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature.

20. The system of claim 13, wherein the number of client recent synchronization signatures is determined based on a frequency of data synchronization.

21. The system of claim 20, the number of client recent synchronization signatures is decreased when the frequency of data synchronization is decreased.

22. The system of claim 21, wherein a size of the synchronization token increases as the frequency of data synchronization is increased.

23. The system of claim 13, wherein the data to be synchronized comprises at least one of web browser data, audio data, and electronic mail data.

24. The system of claim 13, wherein the synchronization token comprises a first portion comprising the client recent synchronization signatures and a second portion comprising a replicated synchronization signature for the client, the client replicated synchronization signature representing a state of data synchronization on the client for a time period older than the time periods associated with the client recent synchronization signatures, and the processor is further configured to execute the instructions to:

compare the client replicated synchronization signature with a corresponding replicated synchronization signature for the server representing data on the server for the same time period; and

when a comparison of the client replicated synchronization signature for the client with the server replicated synchronization signature indicates that the data on the client for the time period represented by the client replicated synchronization signature is not synchronized with corresponding data on the server, send the data on the server for the time period represented by the client replicated synchronization signature to the client.

25. A non-transitory machine-readable storage medium comprising machine-readable instructions for causing a processor to execute a method for synchronizing data between a server and a client, the method comprising:

receiving a request from a client to synchronize data, the request comprising a synchronization token, wherein the synchronization token comprises client recent synchronization signatures, each client recent synchronization signature representing a state of data synchronization on the client for a certain time period;

comparing a hash value determined from each client recent synchronization signature with a hash value determined from each corresponding server recent synchronization signature;

when a hash value determined from a client recent synchronization signature differs from a hash value determined from a corresponding server recent synchronization signature, sending the data on the server for the time period represented by the corresponding server recent synchronization signature to the client for overwriting the data on the client for the time period represented by the client recent synchronization signature; and

sending an updated synchronization token to the client when the data is sent to the client, wherein the updated synchronization token comprises updated client recent synchronization signatures.