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

• US 7,730,026 B2
• Filed: 07/01/2004
• Issued: 06/01/2010
• Est. Priority Date: 07/01/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Serlet, Bertrand
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Pham; Michael
• Application Number:
  US10/883,541
• Publication Number:
  US 20060069809A1
• Time in Patent Office: 2,161 Days
• Field of Search: 707/10, 707/200, 707/203, 707/204, 709/248
• 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 of maintaining meta data regarding user activity for synchronization of related data items based on reusable state descriptions, the reusable state descriptions comprising indications of state transitions of one or more data items based on user actions affecting versions of the one or more data items and user action history reflecting user actions affecting versions of the one or more data items, the method comprising the steps of:

making a first meta data activity association between a first reusable state description and a related first version of a first data item stored on a first device, wherein the first reusable state description reflects a first state transition of the first version of the first data item, based on a user action affecting the first version of the first data item and comprises user action history reflecting the user action affecting the first version of the first data item;

storing an indication of the first meta data activity association on the first device;

making a second meta data activity association between the first reusable state description and a second data item stored on the first device, after the second data item has undergone the first state transition based on the user action affecting the second data item;

storing an indication of the second meta data activity association on the first device;

storing a second reusable state description on the first device, the second reusable state description being distinct from the first reusable state description and reflecting a state transition of a third data item and comprises user action history reflecting user action affecting the third data item;

storing a third reusable state description on the first device, the third reusable state description being distinct from the first reusable state description and distinct from the second reusable state description, the third reusable state description reflecting a state transition of a fourth data item and comprises user action history reflecting user action affecting the fourth data item;

using the first reusable state description, the second reusable state description, and the third reusable state description to facilitate synchronizing a synchronization data item stored on the first device;

determining synchronization of the synchronization data item to be in conflict, and in the situation of conflict, determining whether one version of the synchronization data item is an ancestor of another version of the synchronization data item, wherein determining whether one version is an ancestor of another comprises;

determining if the reusable state descriptions are the same for a local version of a synchronization first data item and a remote version of the synchronization data item,

if the reusable state descriptions are the same then update is not required between the local version of the synchronization data item and the remote version of the synchronization data item;

else determining from the reusable state descriptions if the local version of the synchronization data item is an ancestor of the remote version of the synchronization data item or if the remote version of the synchronization data item is an ancestor of the local version of the synchronization data item,

if the local version of the synchronization data item is an ancestor of the remote version of the synchronization data item then determining that update between the local version of the synchronization data item and the remote version of the synchronization data item is required, and

if the remote version of the synchronization data item is an ancestor of the local version of the synchronization data item then determining that update between the local version of the synchronization data item and the remote version of the synchronization data item is not required.

2. The method of 1 wherein the user action is selected from the group consisting of:

creation of data;

editing of data;

deleting data; and

synchronizing data.

3. The method of 1 wherein the stored indication of the first meta data activity association on a first device comprises the identity of the device where user action occurred.

4. A system for maintaining meta data regarding user activity for synchronization of related data items based on reusable state descriptions, the reusable state descriptions comprising indications of state transitions of one or more data items based on user actions affecting versions of the one or more data items and user action history reflecting user actions affecting versions of the one or more data items, the system comprising:

one or more processors and memory wherein the one or more processors are configured to execute one or more functions to;

make a first meta data activity association between a first reusable state description and a related first version of a first data item stored on a first device, wherein the first reusable state description reflects a first state transition of the first version of the first data item, based on a user action affecting the first version of the first data item and comprises user action history reflecting the user action affecting the first version of the first data item;

store an indication of the first meta data activity association on the first device;

make a second meta data activity association between the first reusable state description and a second data item stored on the first device, after the second data item has undergone the first state transition based on the user action affecting the second data item;

store an indication of the second meta data activity association on the first device;

store a second reusable state description on the first device, the second reusable state description being distinct from the first reusable state description and reflecting a state transition of a third data item and comprises user action history reflecting user action affecting the third data item;

store a third reusable state description on the first device, the third reusable state description being distinct from the first reusable state description and distinct from the second reusable state description, the third reusable state description reflecting a state transition of a fourth data item and comprises user action history reflecting user action affecting the fourth data item;

use the first reusable state description, the second reusable state description, and the third reusable state description to facilitate synchronizing a synchronization data item stored on the first device;

determine synchronization of the synchronization data item to be in conflict, and in the situation of conflict, determining whether one version of the synchronization data item is an ancestor of another version of the synchronization data item, wherein determining whether one version is an ancestor of another comprises;

determining if the reusable state descriptions are the same for a local version of a synchronization data item and a remote version of the synchronization data item,

if the reusable state descriptions are the same then update is not required between the local version of the synchronization data item and the remote version of the synchronization data item;

else determining from the reusable state descriptions if the local version of the synchronization data item is an ancestor of the remote version of the synchronization data item or if the remote version of the synchronization data item is an ancestor of the local version of the synchronization data item,

if the local version of the synchronization data item is an ancestor of the remote version of the synchronization data item then determining that update between the local version of the synchronization data item and the remote version of the synchronization data item is required, and

if the remote version of the synchronization data item is an ancestor of the local version of the synchronization data item then determining that update between the local version of the synchronization data item and the remote version of the synchronization data item is not required.

5. The system of claim 4 wherein the user action is selected from the group consisting of:

creation of data;

editing of data;

deleting data; and

synchronizing data.

6. The system of 4 wherein the stored indication of the first meta data activity association on a first device comprises the identity of the device where user action occurred.