State based synchronization

• US 20060069809A1
• Filed: 07/01/2004
• Published: 03/30/2006
• Est. Priority Date: 07/01/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Serlet, Bertrand
• Granted Patent: US 7,730,026 B2
• Time in Patent Office: Days
• US Class Current: 709/248
• 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 the steps of:

creating first data on a first device and associating a first state with said first data;

creating a first history statement to reflect metadata regarding the creation of said first data;

associating said first history statement with said first state; and

creating second data on said first device and associating said first state with said second data.

2. The method of claim 1 wherein said first data is a data set such as a record.

3. The method of claim 1 wherein said first data is a data item.

4. The method of claim 1 wherein said first data represents a photo.

5. The method of claim 1 wherein said first data represents sound.

6. The method of claim 1 wherein said first history statement comprises information regarding the identity of said first device and the nature by which said first data was created.

7. The method of claim 1 further comprising the steps of:

editing said first data on said first device;

associating a second state with said first data;

creating a second history statement to reflect metadata regarding said editing;

associating said second state with said second history statement.

71. A computer-readable medium having computer executable instructions for performing the method recited in any one of claims 1, 20, 42, 50, 62 or 67.

8. A device for maintaining data to be synchronized, said device comprising:

a user input for creating a first data and a second data;

a processor and software for creating a first history statement to reflect metadata regarding the creation of said first data and the creation of said second data, and for associating said first data, said second data and said first history statement with a first state;

a first memory for storing a first data structure, said first data structure for maintaining both said association between said first data and said first state, and said association between said second data and said first state;

a second memory for storing a second data structure, said second data structure for maintaining said association between said first history statement and said first state.

9. The device of claim 8 wherein said first data is a data item.

10. The device of claim 8 wherein said first data represents sound.

11. The device of claim 8 wherein said first data represents a photo.

12. The device of claim 8 wherein said first history statement comprises information regarding the identity of said first device and the nature by which said first data was created.

13. The device of claim 8 wherein said first memory is magnetic.

14. The device of claim 8 wherein said first memory is dynamic memory.

15. The device of claim 8 wherein said first memory is static memory.

16. The device of claim 8 wherein said first memory and said second memory or the same.

17. The device of claim 8 wherein said first data structure and said second data structure are incorporated into a single soup data structure.

18. The device of claim 8 wherein said first data structure and said second data structure are incorporated into a single flat data structure.

19. The device of claim 8 wherein said first data structure and said second data structure are separate objects.

20. A method of synchronizing databases, the method comprising the steps of:

in a first data structure, associating a first state identification with one or more data sets;

in a second data structure, associating said first state identification with information regarding said one or more data sets associated with said state identification;

making a change to a first one of said one or more data sets;

in said first data structure, associating a second state with said first one of said one or more data sets;

in said second data structure, associating said second state with information regarding said change if said information regarding said change is not already associated with said second state in said second data structure.

21. The method of claim 20 wherein said first data structure is a soup database.

22. The method of claim 20 wherein said first data structure is a flat file.

23. The method of claim 20 wherein said first data structure comprises two or more sub data structures.

24. The method of claim 20 wherein said second data structure is a soup database.

25. The method of claim 20 wherein said second data structure is a flat file.

26. The method of claim 20 wherein said second data structure comprises two or more sub data structures

27. The method of claim 20 wherein a third data structure comprises both said first and said second data structures.

28. The method of claim 20 wherein a data set is a record.

29. The method of claim 20 wherein a data set is a data item.

30. The method of claim 20 wherein said change is an edit.

31. The method of claim 20 where said change is a deletion.

41. The device of claim 20 wherein said change is an edit.

32. A device for synchronizing information comprising:

a first memory for storing a first data structure, said first data structure for associating a first state identification with one or more data sets;

a second memory for storing a second data structure, said second data structure for associating said first state identification with information regarding said one or more data sets associated with said state identification;

a user input for making a change to a first one of said one or more data sets;

a processor and software for

associating a second state with said first one of said one or more data sets, in said first data structure; and

for

associating said second state with information regarding said change in said second data structure, if said information regarding said change is not already associated with said second state in said second data structure.

33. The device of claim 32 wherein said first memory and said second memory are the same.

34. The device of claim 32 wherein said first data structure is a soup database.

35. The device of claim 32 wherein said first data structure is a flat file.

36. The device of claim 32 wherein said first data structure comprises two or more sub data structures.

37. The device of claim 32 wherein a data set is a record.

38. The device of claim 32 wherein said data set is a data item.

39. The device of claim 38 wherein said data item represents sound.

40. The device of claim 38 wherein said data item represents a photo.

42. A method of synchronizing first data maintained in a first data structure with second data maintained in a second data structure, the method comprising the steps of:

associating each data item of first data with a first state identification in said first data structure;

associating each first state identification with a history statement in a third data structure;

associating each data item of second data with a second state identification in said second data structure;

associating each second state identification with a history statement in a fourth data structure;

synchronizing history statements from said third data structure into said fourth data structure to create a synchronized fourth data structure;

synchronizing data from said first data structure into said second data structure by using information from said synchronized fourth data structure.

43. The method of claim 42 wherein said first and third data structures are the same.

44. The method of claim 42 wherein said first and third data structures reside on one device and said second and fourth data structures reside on another device.

45. The method of claim 42 wherein one or more of said history statements in each of the third and fourth data structures comprises correlation between a first state identification and a second state identification.

46. The method of claim 42 wherein first data comprises N data items, and such N data items are associated with M states, and M<

N.

47. A local device for synchronization with a remote device, said local device comprising:

a first local data store for storing local data items and associated local data states, a plurality of said local data items correlating with remote data items stored on said remote device, said remote data items associated with remote states;

a second local data store for storing history statements, said history statements comprising statements associating local data states with remote data states and statements regarding the editing of one or more local data items and one or more remote data items.

48. The device of claim 47 wherein editing is creating.

49. The device of claim 47 wherein editing is deleting.

50. The device of claim 47 wherein editing is truncating.

51. The device of claim 47 wherein there are N local data items, and such N local data items are associated with M local states, and M<

N.

52. A method of tracking changes to data, wherein data comprises a plurality of data items, said method comprising the steps of:

Associating a first state with a first plurality of data items, all of said first plurality of data items having a first common history;

Associating said first state with a first history statement describing said first common history.

53. The method of claim 52 wherein said first common history is the creation of said data items.

54. The method of claim 53 wherein said first history statement indicates that data was created and how data was created.

55. The method of claim 53 wherein said first history statement indicates that data was created and what device was used to create data.

56. The method of claim 53 wherein said first history statement indicates that data was created and a synchronization client associated with said data creation.

57. The method of claim 52 wherein said first common history is the editing of data, said editing associated with a certain synchronization client.

58. The method of claim 52 wherein said first plurality of items comprises an address and a phone number.

59. The method of claim 52 wherein said first plurality of items comprises two addresses.

60. The method of claim 52 further comprising the steps of:

making a first change to a first subset of data items, said first subset of data items comprising one or more of said first plurality of data items;

associating a second state with said first subset of data items; and

associating a second history statement with said first change.

61. The method of claim 60 wherein the step of associating a second history statement with said first change comprising creating a said second history statement.

62. The method of claim 60 wherein said first change is deleting said first subset of data items.

63. The method of claim 60 wherein said first change is independently editing each of said data items of said first subset of data items.

64. The method of claim 60 wherein said plurality of data items and all associated history statements are maintained in a first common data structure.

65. The method of claim 64, further comprising the step of synchronizing history statements from a second common data structure into said first common data structure.

66. The method of claim 65 wherein said first common data structure resides on a first device and said second common data structure resides on a second device.

67. The method of claim 64 further comprising the step of reducing unnecessary history statements from the synchronized first common data structure.

68. The method of claim 67 wherein said step of reducing comprises keeping history statements have a subject state that is a descendant of a state in use.

69. The method of claim 66 further comprising the step of reducing unnecessary history statements from the synchronized first common data structure.

70. The method of claim 69 wherein said step of reducing comprises keeping history statements have a subject state that is a descendant of a state in use on said first device or said second device.