Linked Value Replication

• US 20060184589A1
• Filed: 04/24/2006
• Published: 08/17/2006
• Est. Priority Date: 06/21/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lees, William B., Parham, Jeffrey B., Brown, Mark R., Hacherl, Donald J.
• Granted Patent: US 7,526,513 B2
• Time in Patent Office: Days
• 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 an attribute comprised of individual linked values, each linked value having conflict-resolution data;

a second computer configured to replicate the object to generate a replica object and maintain the replica object; and

the second computer further configured to resolve a replication conflict between a linked value of the attribute in the object and the linked value of the attribute in the replica object, the replication conflict being resolved with the conflict-resolution data associated with the linked values.

2. A network system as recited in claim 1, 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.

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

4. 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 version number associated with the linked value of the attribute in the object and the version number 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 number 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 conflict-resolution data comprises an update timestamp that corresponds to when an individual linked value is updated, and 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 indicator that corresponds to a version of an individual value and an update indicator that corresponds to when the individual value is updated.

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 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 higher version number, and second has a later update timestamp.

11. 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 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 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.

12. 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, a version indicator that corresponds to a version of the individual value, and an update indicator that corresponds to when the individual value is updated.

13. 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.

14. 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.

15. A network system as recited in claim 1, wherein the linked value of the attribute in the object is associated with a first deletion indicator that is a null identifier to indicate the existence of the liked value of the attribute in the object, and the linked value of the attribute in the replica object is associated with a second deletion indicator that is a null identifier to indicate the existence of a linked value of the attribute in the replica object.

16. A network system as recited in claim 1, wherein the linked value of the attribute in the object is associated with a first deletion indicator 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 indicator corresponding to when the linked value of the attribute in the replica object is marked for deletion from the attribute in the replica object.

17. 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 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.

18. A state-based replication system, comprising:

an object having an attribute comprised of values, individual values having indicators to indicate a change to a value of the attribute;

a computing device configured to replicate the object and, with the indicators, identify a change to a value of the attribute.

19. A state-based replication system as recited in claim 18, wherein the computing device is further configured to:

maintain a replica object, the replica object being replicated from the object; and

compare the object with the replica object to identify, with the indicators, a value replication conflict.

20. A state-based replication system as recited in claim 18, wherein the indicators comprise a version indicator that corresponds to a version of a value, an update indicator that corresponds to when a value is changed, an update timestamp that corresponds to when the value is changed, a creation indicator that corresponds to when a value is created, a creation timestamp that corresponds to when a value is created, a version number that corresponds to a version of a value, a deletion indicator that has a null identifier to indicate the existence of a value of the attribute, a deletion timestamp that corresponds to when a value is marked for deletion from the attribute.