Multi-level replication and conflict resolution

• US 7,526,513 B2
• Filed: 04/24/2006
• Issued: 04/28/2009
• Est. Priority Date: 06/21/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hacherl, Donald J., Lees, William B., Parham, Jeffrey B., Brown, Mark R.
• Primary Examiner(s): Pham; Khanh B
• Application Number:
  US11/379,996
• Publication Number:
  US 20060184589A1
• Time in Patent Office: 1,100 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control
• 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
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/961 Associative
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A network computer maintains a directory of objects having multi-valued attributes. The attributes are comprised of individual linked values having conflict-resolution data that indicates a change to an object at an attribute-value level. A second network computer stores a replica of the directory in which a replica of the objects is maintained. The computers replicate the objects in the directories and update the individual linked values of the attributes. Replication conflicts are identified and resolved with the conflict-resolution data at the attribute-value level of the objects.

Claims

1. A network system, comprising:

a first computer configured to maintain an object having a first attribute and a second attribute, wherein the first attribute has attribute level data for attribute level replication and conflict resolution, and wherein the second attribute has attribute level data and attribute value level data for replication and conflict resolution at either the attribute level or the attribute value level, and wherein the attribute value level data comprises a plurality of individual linked values, wherein each linked value has non-null conflict-resolution data;

a second computer configured to replicate the object to generate a replica object of the object maintained by the first computer and maintain the replica object having the first attribute and the second attribute, wherein the first attribute has attribute level data for attribute level replication and conflict resolution, and wherein the second attribute has attribute level data and attribute value level data for replication and conflict resolution at either the attribute level or the attribute value level, and wherein the attribute value level data comprises a plurality of individual linked values, wherein each linked value has non-null conflict-resolution data;

when a change is made to the first attribute of the object maintained by the first computer, the second computer is configured to replicate the first attribute from the first computer at the attribute level and resolve conflicts at the attribute level;

when a change is made to the second attribute of the object maintained by the first computer, the second computer is configured to replicate the second attribute from the first computer at the attribute value level and resolve conflicts at the attribute value level, the replication and conflict resolution being accomplished with the conflict-resolution data associated with the individual linked values, wherein the second computer is further configured to compare the conflict-resolution data associated with the linked value of the attribute in the object and the conflict-resolution data associated with the linked value of the attribute in the replica object to resolve each replication conflict;

wherein the conflict-resolution data for each linked value comprises a version indicator that corresponds to a version of an individual value, an update timestamp that corresponds to then an individual linked value is updated, and a deletion timestamp; and

wherein the deletion timestamp has a zero value if the linked value is present and a non-zero value if the linked value has been identified to be deleted.

2. A network system as recited in claim 1, wherein a third computer is configured to generate a replica object of the object maintained by the first computer and maintain the replica object having the first attribute and the second attribute, wherein the first attribute has attribute level data for attribute level replication and conflict resolution, and wherein the second attribute has attribute level data and attribute value level data for replication and conflict resolution at either the attribute level or the attribute value level, and wherein the attribute value level data comprises a plurality of individual linked values, wherein each linked value has null conflict-resolution data;

and

wherein the third computer promotes itself to implement attribute value level replication when it identifies that the first computer or the second computer is implementing attribute value level replication.

3. A network system as recited in claim 2, wherein no new changes are occurring and wherein the first, second and third computers converge to the same set of values for the attribute level data and the attribute value level data by replicating one from the other.

4. A network system as recited in claim 1, wherein the second computer is further configured to:

compare the version indicator associated with the linked value of the attribute in the object and the version indicator associated with the linked value of the attribute in the replica object to resolve the replication conflict; and

update the linked value of the attribute in the replica object if the linked value has a lower version indicator than the linked value of the attribute in the object.

5. A network system as recited in claim 1, wherein the conflict-resolution data comprises an update indicator that corresponds to an occurrence of when an individual value is updated.

6. A network system as recited in claim 1, wherein the second computer is further configured to:

compare the update timestamp associated with the linked value of the attribute in the object and the update timestamp associated with the linked value of the attribute in the replica object to resolve the replication conflict; and

update the linked value of the attribute in the replica object if the linked value has an earlier update timestamp than the linked value of the attribute in the object.

7. A network system as recited in claim 1, wherein the conflict-resolution data comprises a creation indicator that corresponds to when an individual value is created.

8. A network system as recited in claim 1, wherein the conflict-resolution data comprises a creation timestamp that corresponds to when an individual value is created, and wherein the second computer is further configured to:

compare the creation timestamp associated with the linked value of the attribute in the object and the creation timestamp associated with the linked value of the attribute in the replica object to resolve the replication conflict; and

update the linked value of the attribute in the replica object if the linked value has an earlier creation timestamp than the linked value of the attribute in the object.

9. A network system as recited in claim 1, wherein the conflict-resolution data comprises a version number that corresponds to a version of an individual value, and wherein the second computer is further configured to:

compare the conflict-resolution data associated with the linked value of the attribute in the object and the conflict-resolution data associated with the linked value of the attribute in the replica object; and

resolve the replication conflict in favor of the linked value that first has a higher version number, and second has a later update timestamp.

10. A network system as recited in claim 1, wherein the conflict-resolution data comprises a version number that corresponds to a version of an individual value, and wherein:

if the version number associated with the linked value of the attribute in the replica object is equivalent to the version number associated with the linked value of the attribute in the object, update the linked value of the attribute in the replica object if the linked value has an earlier update timestamp than the linked value of the attribute in the object.

11. A network system as recited in claim 1, wherein the conflict-resolution data comprises a creation timestamp that corresponds to when an individual value is created, a version number that corresponds to a version of the individual value, and an update timestamp that corresponds to when the individual value is updated, and wherein the second computer is further configured to:

compare the conflict-resolution data associated with the linked value of the attribute in the object and the conflict-resolution data associated with the linked value of the attribute in the replica object; and

resolve the replication conflict in favor of the linked value that first has a later creation timestamp, second has a higher version number, and third has a later update timestamp.

12. A network system as recited in claim 1, wherein the conflict-resolution data comprises a creation timestamp that corresponds to when an individual value is created, a version number that corresponds to a version of the individual value, and an update timestamp that corresponds to when the individual value is updated, and wherein the second computer is further configured to:

compare the conflict-resolution data associated with the linked value of the attribute in the object and the conflict-resolution data associated with the linked value of the attribute in the replica object to resolve the replication conflict;

update the linked value of the attribute in the replica object if the linked value has an earlier creation timestamp than the linked value of the attribute in the object;

if the creation timestamp associated with the linked value of the attribute in the replica object is equivalent to the creation timestamp associated with the linked value of the attribute in the object, update the linked value of the attribute in the replica object if the linked value has a lower version number than the linked value of the attribute in the object; and

if the version number associated with the linked value of the attribute in the replica object is equivalent to the version number associated with the linked value of the attribute in the object, update the linked value of the attribute in the replica object if the linked value has an earlier update timestamp than the linked value of the attribute in the object.

13. A network system as recited in claim 1, wherein the linked value of the attribute in the object is associated with a first deletion timestamp corresponding to when the linked value of the attribute in the object is marked for deletion from the attribute in the object, and the linked value of the attribute in the replica object is associated with a second deletion timestamp corresponding to when the linked value of the attribute in the replica object is marked for deletion from the attribute in the replica object.

14. A network system as recited in claim 1, wherein the linked value of the attribute in the object is associated with a first deletion timestamp that corresponds to when the linked value of the attribute in the object is marked for deletion from the attribute in the object, wherein the linked value of the attribute in the replica object is associated with a second deletion timestamp that corresponds to when linked value of the attribute in the replica object is marked for deletion from the attribute in the replica object, and wherein the second computer is further configured to delete a linked value from the attribute in the object if the linked value has a deletion timestamp that indicates the linked value is marked for deletion.

15. A method for implementing attribute value level replication, comprising:

maintaining a first computer having an object having a first attribute and a second attribute, wherein the first attribute has attribute level data for attribute level replication and conflict resolution, and wherein the second attribute has attribute level data and attribute value level data for replication and conflict resolution at either the attribute level or the attribute value level, and wherein the attribute value level data comprises a plurality of individual linked values, wherein each linked value has non-null conflict-resolution data;

maintaining a second computer generating a replica object of the object maintained by the first computer and maintaining the replica object having the first attribute and the second attribute, wherein the first attribute has attribute level data for attribute level replication and conflict resolution, and wherein the second attribute has attribute level data and attribute value level data for replication and conflict resolution at either the attribute level or the attribute value level, and wherein the attribute value level data comprises a plurality of individual linked values, wherein each linked value has non-null conflict-resolution data;

when a change is made to the first attribute of the object maintained by the first computer, the second computer replicating the first attribute from the first computer at the attribute level and resolving conflicts at the attribute level;

when a change is made to the second attribute of the object maintained by the first computer, the second computer replicating the second attribute from the first computer at the attribute value level and resolving conflicts at the attribute value level, the replication and conflict resolution being accomplished with the conflict-resolution data associated with the individual linked values, wherein the second computer is further configured to compare the conflict-resolution data associated with the linked value of the attribute in the object and the conflict-resolution data associated with the linked value of the attribute in the replica object to resolve each replication conflict;

wherein the conflict-resolution data for each linked value comprises a version indicator that corresponds to a version of an individual value, an update timestamp that corresponds to when an individual linked value is updated, and a deletion timestamp; and

wherein the deletion timestamp has a zero value if the linked value is present and a non-zero value if the linked value has been identified to be deleted.

16. The method as recited in claim 15, further comprising:

maintaining a third computer configured to generate a replica object of the object maintained by the first computer and maintaining the replica object having the first attribute and the second attribute, wherein the first attribute has attribute level data for attribute level replication and conflict resolution, and wherein the second attribute has attribute level data and attribute value level data for replication and conflict resolution at either the attribute level or the attribute value level, and wherein the attribute value level data comprises a plurality of individual linked values, wherein each linked value has null conflict-resolution data; and

wherein the third computer promotes itself to implement attribute value level replication when it identifies that the first computer or the second computer is implementing attribute value level replication.

17. The method as recited in claim 15, further comprising:

comparing the version indicator associated with the linked value of the attribute in the object and the version indicator associated with the linked value of the attribute in the replica object to resolve the replication conflict; and

updating the linked value of the attribute in the replica object if the linked value has a lower version indicator than the linked value of the attribute in the object.