Method and system using reusable state information for synchronization and maintenance of data

• US 8,868,493 B2
• Filed: 11/19/2012
• Issued: 10/21/2014
• Est. Priority Date: 07/01/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Serlet, Bertrand
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Pham, Michael
• Application Number:
  US13/680,467
• Publication Number:
  US 20130218839A1
• Time in Patent Office: 701 Days
• Field of Search: None
• US Class Current: 707/610
• 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/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• 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

A system for synchronization whereby metadata repository maintains information regarding the history and status of data items in a data repository. Data items are associated with states and such states changes (e.g. increment) in response to changes to the data items. History statements associated with the same states describe the changes in a generic enough fashion that multiple data items may be associated with a single state (e.g. if multiple data items share a common history such as that they were all edited by a user on the same device). The history repository is synchronized with other history repositories so as to reflect the states of data items on multiple devices. The synchronized history stores are used during synchronization to identify and resolve data conflicts through ancestry of data item history.

Claims

1. A method for maintaining data and metadata for synchronization, the method comprising:

altering a first data item of a first object on a first device, the first object comprising a first state of the first data item on the first device and a log, the first state having a first value of an ordered set values, the log comprising one or more portions, and each of the portions identifying a type of change performed by a user to the first data item;

in response to altering the first data item, changing the first value to a second value, the second value being the next value after the first value in the ordered set of values, and updating the log according to the type of change performed by the user to the first data item;

obtaining a second state of the first data item from a communicatively coupled second device, the second state having a third value of the ordered set of values;

comparing the third value of the second state to the second value of the first state; and

determining whether synchronization of the first data item is required between the first device and the second device based on the comparison.

2. The method of claim 1, wherein the ordered set of values are integer values.

3. The method of claim 2, wherein changing the first value to a second value includes increasing the integer value of the first state by one on the first device.

4. The method of claim 2, further comprising:

transmitting, from the first device to the second device, the first data item when the integer value of the second state is less than the integer value of the first state.

5. The method of claim 2, further comprising:

when the integer value of the second state is greater than the integer value of the first state, altering the first data item on the first device to be the same as on the second device.

6. The method of claim 1, further comprising:

transmitting, from the first device to the second device, the first data item when the third value of the second state is before the second value of the first state in the ordered set of values.

7. The method of claim 1, further comprising:

when the third value of the second state is after the second value of the first state, altering the first data item on the first device to be the same as on the second device.

8. The method of claim 1, further comprising:

altering a second data item of a second object on the first device such that a third state of the second data item has the second value of the ordered set values,

wherein the first state of the first data item and the third state of the second data share the second value of the ordered set values for a time period.

9. The method of claim 1, wherein altering the first data item comprises editing the first data item.

10. The method of claim 1, wherein altering the first data item comprises deleting the first data item.

11. The method of claim 1, further comprising:

synchronizing a plurality of remote history statements from a remote history store for data objects on the second device to a local store on the first device, each one of the plurality of remote history statements associated with respective remote state having a different value of the ordered set of values.

12. The method of claim 11, wherein a remote history statement includes:

a new state, a command, a device identifier, and an old state.

13. The method of claim 11, wherein synchronizing the plurality of remote history statements from the remote history store to the local store on the first device includes:

creating new local states to correspond to the remote states;

translating each of the remote history statements into a local history statement and storing in the local store; and

eliminating local history statements associated with a state having a duplicate value as another local history statement.

14. The method of claim 11, wherein synchronizing the plurality of history statements from the remote history store to the local store on the first device includes:

comparing the values of the states of the remote history statements to the values of the states of one or more local history statements on the first device; and

creating new local history statements with states having values that are not in the existing one or more location history statement.

15. The method of claim 11, wherein synchronizing the plurality of remote history statements from the remote history store to the local store on the first device includes:

identifying one or more remote history statements that have a same value as a local history statement on the first device; and

translating editing commands from the remote history statements to the local history statements having the same value.

16. The method of claim 15, wherein translating editing commands includes adding an external command to a first local history statement when an existing command for the first local history statement is different than a command for the remote history statement having the same value.

17. The method of claim 11, wherein synchronizing the plurality of remote history statements from the remote history store to the local store on the first device includes:

identifying a first remote history statement that has one or more editing commands that correspond to a first local history statement on the first device, where the first remote history statement and first local history statement have different values for the respective states; and

translating the editing commands of the first remote history statement to the first local history statement.

18. A non-transitory computer readable medium with instructions embodied thereon to configure a processor to:

alter a first data item of a first object on a first device, the first object comprising a first state of the first data item on the first device and a log, the first state having a first value of an ordered set values, the log comprising one or more portions, and each of the portions identifying a type of change performed by a user to the first data item;

change the first value to a second value in response to altering the first data item, the second value being the next value after the first value in the ordered set of values, and updating the log according to the type of change performed by the user to the first data item;

obtain a second state of the first data item from a communicatively coupled second device, the second state having a third value of the ordered set of values;

compare the third value of the second state to the second value of the first state; and

determine whether synchronization of the first data item is required between the first device and the second device based on the comparison.

19. The computer readable medium of claim 18, further comprising:

transmitting, from the first device to the second device, the first data item when the third value of the second state is before the second value of the first state in the ordered set of values.

20. The computer readable medium of claim 18, further comprising:

when the third value of the second state is after the second value of the first state, altering the first data item on the first device to be the same as on the second device.

21. The computer readable medium of claim 18, further comprising:

altering a second data item of a second object on the first device such that a third state of the second data item has the second value of the ordered set values,

wherein the first state of the first data item and the third state of the second data share the second value of the ordered set values for a time period.

22. A device for maintaining data to be synchronized, the device comprising:

one or more memories communicatively coupled to a processor;

a display communicatively coupled to the processor and to a user input mechanism, the user input mechanism for creating, editing or deleting a data item,

wherein the processor is programmed to;

alter a first data item of a first object on a first device, the first object comprising a first state of the first data item on the first device and a log, the first state having a first value of an ordered set values, the log comprising one or more portions, and each of the portions identifying a type of change performed by a user to the first data item;

change the first value to a second value in response to altering the first data item, the second value being the next value after the first value in the ordered set of values, and updating the log according to the type of change performed by the user to the first data item;

obtain a second state of the first data item from a communicatively coupled second device, the second state having a third value of the ordered set of values;

compare the third value of the second state to the second value of the first state; and

determine whether synchronization of the first data item is required between the first device and the second device based on the comparison.

23. The device of claim 22, further comprising:

transmitting, from the first device to the second device, the first data item when the third value of the second state is before the second value of the first state in the ordered set of values.

24. The device of claim 22, further comprising:

when the third value of the second state is after the second value of the first state, altering the first data item on the first device to be the same as on the second device.

25. The device of claim 22, further comprising:

altering a second data item of a second object on the first device such that a third state of the second data item has the second value of the ordered set values,

wherein the first state of the first data item and the third state of the second data share the second value of the ordered set values for a time period.