Data synchronization

• US 9,294,566 B2
• Filed: 10/20/2014
• Issued: 03/22/2016
• Est. Priority Date: 01/14/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Giampaolo, Dominic B., Morard, Jean-Gabriel
• Primary Examiner(s): Chau, Dung K
• Application Number:
  US14/518,938
• Publication Number:
  US 20150106330A1
• Time in Patent Office: 519 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• 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
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for data synchronization. In general, one aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving a knowledge vector from a first device of the pair of devices, the knowledge vector identifying data items and latest changes to the data items known to the peer device; comparing, at a second device of the pair of devices, the received knowledge vector with a local knowledge vector for changes unknown to the first device; and sending a list of changes to the first device.

Claims

1. A method comprising:

identifying a first version of a data item to synchronize from a first device using a first change identifier associated with the data item;

identifying a second version of the data item to synchronize from a second device using a second change identifier associated with the data item;

upon determining that the first version and the second version occurred within a specified threshold, determining that there is a conflict between the first version of the data item and the second version of the data item; and

upon determining that there is a conflict, resolving the conflict, including;

determining, from the first change identifier, a first device identifier identifying the first device;

determining, from the second change identifier, a second device identifier identifying the second device;

selecting, from the first version of the data item and the second version of the data item, a conflict winner by comparing the first device identifier and the second device identifier and designating a version of the data item as stored on a device identified by a lowest device identifier or highest device identifier as the conflict winner;

designating the version not selected as the conflict winner as a conflict loser; and

storing a copy of the conflict loser.

2. The method of claim 1, comprising retrieving the stored conflict loser upon request.

3. The method of claim 1, wherein the first device and second device are devices among a plurality of devices logically arranged into a ring, the first device and second device being logically adjacent to each other in the ring.

4. The method of claim 3, wherein each device in the ring is associated with a device identifier, logically adjacent devices having device identifiers adjacent in value, wherein a device having a lowest device identifier is logically adjacent to a device having a highest device identifier, and wherein data synchronization is performed between logically adjacent devices.

5. The method of claim 4, wherein the data item is not directly synchronized between devices in the ring that are not logically adjacent to one another.

6. The method of claim 1, wherein the first device is designated as a server performing actions of resolving the conflict, the second device being designated as a client, and, after resolving the conflict, the second device is designated as a server, the first device being designated as a client.

7. A non-transitory storage device storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

identifying a first version of a data item to synchronize from a first device using a first change identifier associated with the data item;

identifying a second version of the data item to synchronize from a second device using a second change identifier associated with the data item;

upon determining that the first version and the second version occurred within a specified threshold, determining that there is a conflict between the first version of the data item and the second version of the data item; and

upon determining that there is a conflict, resolving the conflict, including;

determining, from the first change identifier, a first device identifier identifying the first device;

determining, from the second change identifier, a second device identifier identifying the second device;

selecting, from the first version of the data item and the second version of the data item, a conflict winner by comparing the first device identifier and the second device identifier and designating a version of the data item as stored on a device identified by a lowest device identifier or highest device identifier as the conflict winner;

designating the version not selected as the conflict winner as a conflict loser; and

storing a copy of the conflict loser.

8. The non-transitory storage device of claim 7, the operations comprising retrieving the stored conflict loser upon request.

9. The non-transitory storage device of claim 7, wherein the first device and second device are devices among a plurality of devices logically arranged into a ring, the first device and second device being logically adjacent to each other in the ring.

10. The non-transitory storage device of claim 9, wherein each device in the ring is associated with a device identifier, logically adjacent devices having device identifiers adjacent in value, wherein a device having a lowest device identifier is logically adjacent to a device having a highest device identifier, and wherein data synchronization is performed between logically adjacent devices.

11. The non-transitory storage device of claim 10, wherein the data item is not directly synchronized between devices in the ring that are not logically adjacent to one another.

12. The non-transitory storage device of claim 7, wherein the first device is designated as a server performing actions of resolving the conflict, the second device being designated as a client, and, after resolving the conflict, the second device is designated as a server, the first device being designated as a client.

13. A system comprising:

a first device; and

a second device connected to a the first device, the second device being configured to perform operations comprising;

identifying a first version of a data item to synchronize from a first device using a first change identifier associated with the data item;

identifying a second version of the data item to synchronize from a second device using a second change identifier associated with the data item;

upon determining that the first version and the second version occurred within a specified threshold, determining that there is a conflict between the first version of the data item and the second version of the data item; and

upon determining that there is a conflict, resolving the conflict, including;

determining, from the first change identifier, a first device identifier identifying the first device;

determining, from the second change identifier, a second device identifier identifying the second device;

selecting, from the first version of the data item and the second version of the data item, a conflict winner by comparing the first device identifier and the second device identifier and designating a version of the data item as stored on a device identified by a lowest device identifier or highest device identifier as the conflict winner;

designating the version not selected as the conflict winner as a conflict loser; and

storing a copy of the conflict loser.

14. The system of claim 13, the operations comprising retrieving the stored conflict loser upon request.

15. The system of claim 13, wherein the first device and second device are devices among a plurality of devices logically arranged into a ring, the first device and second device being logically adjacent to each other in the ring.

16. The system of claim 15, wherein each device in the ring is associated with a device identifier, logically adjacent devices having device identifiers adjacent in value, wherein a device having a lowest device identifier is logically adjacent to a device having a highest device identifier, and wherein data synchronization is performed between logically adjacent devices.

17. The system of claim 16, wherein the data item is not directly synchronized between devices in the ring that are not logically adjacent to one another.

18. The system of claim 13, wherein the second device is designated as a server, the first device being designated as a client, and, after resolving the conflict, the first device is designated as a server, the second device being designated as a client.