Constraint-based conflict handling for synchronization

• US 20060242444A1
• Filed: 04/26/2005
• Published: 10/26/2006
• Est. Priority Date: 04/26/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev, Zhou, Shaoyu, Jhaveri, Vivek Jawahir, Sivapragasam, Muhunthan
• Granted Patent: US 7,778,963 B2
• Time in Patent Office: Days
• US Class Current: 713/400
• 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 data synchronization system comprising:

a synchronization component that synchronizes two or more replicas;

a conflict component that detects constraint-based conflicts during synchronization; and

a handler component that resolves the detected conflict.

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

3. The system of claim 2, the handler component includes a merge component that specifies a single identifier for referencing one or more conflicting entities.

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

5. The system of claim 4, 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.

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

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

8. The system of claim 2, the conflict component includes a cycle detection component that identifies temporary conflicts caused by cyclic renames.

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

10. A synchronization system comprising:

means for synchronizing one or more data stores;

means for detecting name collisions during synchronization; and

means for merging unique identifiers for colliding data units into a single identifier.

11. A computer implemented method of synchronizing data comprising:

detecting a constraint-based conflict during a synchronization process; and

resolving the conflict in accordance with a resolution policy.

12. The method of claim 11, 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.

13. The method of claim 12, resolving the conflict comprises renaming one of the data entities.

14. The method of claim 12, resolving the conflict comprises merging the entities in conflict into a singe entity identified by a single identifier.

15. The method of claim 14, merging the entities comprises specifying a merge history property of the single identifier that includes the identifiers that were merged into the single identifier.

16. The method of claim 15, the conflict policy specifies one of local wins, remote wins and most recent wins.

17. The method of claim 16, detecting a constraint-based conflict comprises identifying a temporary name collision conflict that corresponds to a cyclic rename.

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

19. The method of claim 17, resolving the conflict comprises applying at least one change to a temporary name.

20. A computer readable medium having stored thereon computer executable instructions for carrying out the method of claim 11.