Constraint-based conflict handling for synchronization

• US 7,778,963 B2
• Filed: 04/26/2005
• Issued: 08/17/2010
• Est. Priority Date: 04/26/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev, Zhou, Shaoyu, Jhaveri, Vivek Jawahir, Sivapragasam, Muhunthan
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): BUCKINGHAM, KELLYE DEE
• Application Number:
  US11/114,519
• Publication Number:
  US 20060242444A1
• Time in Patent Office: 1,939 Days
• Field of Search: None
• US Class Current: 707/610
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems

Abstract

The subject invention pertains to data synchronization across replicas. Disclosed are systems and methods of detecting and handling constraint-based conflicts that occur during a synchronization session. In accordance with one particular aspect of the invention, name-constraint violations can be detected. These violations can be resolved by generating a single merged identity that can be utilized to refer to data units, for example on different replicas that had the same name. A property of the merged identity can be merge history, which specifies the identifiers subsumed by the merge.

Claims

1. A computer-based data synchronization system comprising:

a processor communicatively coupled to a memory having stored thereon data related to at least one replica involved in a synchronization event;

a synchronization component that synchronizes between data stores two or more replicas;

a conflict component that detects constraint-based conflicts, including naming conflicts between data entities stored on the data stores, during synchronization, the conflict component includes a cycle detection component that identifies temporary conflicts associated with name collisions caused by cyclic renames by at least in part receiving knowledge associated with the data entity in question transmitted from one or more synchronization partners to facilitate determining if the conflict is temporary or permanent; and

a handler component that automatically resolves the detected conflict such that when a temporary cyclic rename conflict is detected, a change or update to a named data entity participating in the synchronization is at least in part facilitated by applying said change or update to a data entity with a temporary name that is unique in the related namespace and at a later time resolving the temporary name to the named data entity, wherein the handler component comprises a merge component that specifies a single identifier for referencing one or more conflicting entities based on a merge history.

2. The system of claim 1, the conflict component detects a name constraint violation.

3. The system of claim 1, the merge component comprising a selection component facilitating selecting an identifier based on a merge policy.

4. The system of claim 3, the merge component comprising a history component that determines all the identifiers subsumed by the single identifier and stores such information as a metadata property of the single identifier.

5. The system of claim 2, the handler component including a component that renames one or more of data entities to ensure unique names are associated with entities.

6. The system of claim 2, the handler component includes a component that logs constraint conflicts to facilitate resolution at a later time.

7. The system of claim 2, the handler component including a policy component that provides rules that govern how detected conflicts should be processed.

8. A computer implemented method of synchronizing data comprising:

detecting a constraint-based conflict, including a naming conflict between data entities, during a synchronization process, the synchronization process synchronizing one or more data stores, the detecting comprising identifying a temporary name collision conflict that corresponds to a cyclic rename, wherein the temporary name collision is identified by reviewing a synchronization partner'"'"'s knowledge to determine if it is aware of a data entity name change, wherein the partner'"'"'s knowledge comprises versions of the data;

determining that a temporary violation has occurred based on the partner'"'"'s knowledge of the data versions, wherein the partner'"'"'s knowledge identifies which versions of data entities a partner is aware;

resolving the conflict automatically in accordance with a resolution policy, at least in part including applying a change or update to a data entity having a temporary namespace name that is unique, wherein resolving the conflict comprises merging the entities in conflict into a single entity identified by a single identifier, the merging including specifying a merge history property of the single identifier that includes identifiers that were merged into the single identifier, wherein the conflict policy specifies one of local wins, remote wins and most recent wins.

9. The method of claim 8, detecting a constraint-based conflict comprises identifying name constraint violations in which a two or more data entities have the same namespace name and dependencies.

10. The method of claim 9, resolving the conflict comprises renaming one of the data entities.

11. The method of claim 8, a temporary name collision is identified by reviewing a synchronization partner'"'"'s knowledge to determine if it is aware of a name change.

12. A data synchronization system comprising:

a processor communicatively coupled to a memory having stored thereon computer-executable instructions configured to implement the data synchronization system including;

a synchronization component that facilitates automatic synchronization of two or more replicas each comprising one or more data entities wherein the synchronization component detects changes between the two or more replicas;

a conflict detection component that detects constraint-based conflicts, including naming conflicts between data entities, during synchronization, the conflict component including a detection component that (i) facilitates identifying temporary conflicts caused by cyclic renames based at least in part on additional information returned by a knowledge retrieval component that facilitates information retrieval related to a data entity in question from the relevant synchronization partner, such information indicating that a naming conflict is of a temporary scope, and (ii) facilitates identifying permanent conflicts caused by data entities with the same name or type that will conflict regardless of the order in which changes are applied to the data entities participating in the synchronization;

a conflict handler component that automatically resolves the detected naming conflict, wherein the handler component includes a merge component that applies a unique identifier to each of the one or more data entities participating in a synchronization to ensure unique identifiers are associated with each participating data entity despite any continuing naming conflict and applying a change to a temporary data entity that is later resolved; and

a merge policy component that facilitates automatically determining and applying a merging order for the one or more uniquely identified data entities based at least in part on the data entities name such that the merged data entities reflect at least in part the merging order in metadata comprising at least in part the unique identifier of each merged data entity.

13. A computer program product for implementing a method of synchronizing data, the computer program product comprising one or more computer storage media having stored thereon computer-executable instructions that, when executed by a processor, perform the following:

detect a constraint-based conflict, including a naming conflict between data entities, during a synchronization process, the synchronization process synchronizing one or more data stores, the detecting comprising identifying a temporary name collision conflict that corresponds to a cyclic rename the temporary name collision is identified by reviewing a synchronization partner'"'"'s knowledge to determine if it is aware of a data entity name change, wherein the partner'"'"'s knowledge comprises versions of the data;

determining that a temporary violation has occurred based on the partner'"'"'s knowledge of the data versions, wherein the partner'"'"'s knowledge identifies which versions of data entities a partner is aware;

resolve the conflict automatically in accordance with a resolution policy, at least in part including applying a change or update to a data entity having a temporary namespace name that is unique, wherein resolving the conflict comprises merging the entities in conflict into a single entity identified by a single identifier, the merging including specifying a merge history property of the single identifier that includes identifiers that were merged into the single identifier, wherein the conflict policy specifies one of local wins, remote wins and most recent wins.