Linked value replication

• US 20020099728A1
• Filed: 01/19/2001
• Published: 07/25/2002
• 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,162,499 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, the attribute comprised of individual values, the individual values having conflict-resolution data;

a second computer configured to maintain a replica object, the replica object being replicated from the object; and

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

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 value of the attribute in the object and the conflict-resolution data associated with the 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 value of the attribute in the object and the version number associated with the value of the attribute in the replica object to resolve the replication conflict; and

update the value of the attribute in the replica object if the value has a lower version number than the 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 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 value is updated, and wherein the second computer is further configured to:

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

update the value of the attribute in the replica object if the value has an earlier update timestamp than the 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 value of the attribute in the object and the creation timestamp associated with the value of the attribute in the replica object to resolve the replication conflict; and

update the value of the attribute in the replica object if the value has an earlier creation timestamp than the 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 value of the attribute in the object and the conflict-resolution data associated with the value of the attribute in the replica object; and

resolve the replication conflict in favor of the 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 value of the attribute in the object and the conflict-resolution data associated with the value of the attribute in the replica object to resolve the replication conflict;

update the value of the attribute in the replica object if the value has a lower version number than the value of the attribute in the object; and

if the version number associated with the value of the attribute in the replica object is equivalent to the version number associated with the value of the attribute in the object, update the value of the attribute in the replica object if the value has an earlier update timestamp than the 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 value of the attribute in the object and the conflict-resolution data associated with the value of the attribute in the replica object; and

resolve the replication conflict in favor of the 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 value of the attribute in the object and the conflict-resolution data associated with the value of the attribute in the replica object to resolve the replication conflict;

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

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

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

15. A network system as recited in claim 1, wherein the individual values have an associated deletion indicator that is a null identifier to indicate the existence of a value of the attribute in the object.

16. A network system as recited in claim 1, wherein the individual values have an associated deletion indicator that corresponds to when an individual value is marked for deletion from the attribute in the object.

17. A network system as recited in claim 1, wherein the individual values have an associated deletion timestamp that corresponds to when an individual value is marked for deletion from the attribute in the object, and wherein the second computer is further configured to delete a value from the attribute in the object if the value has a deletion timestamp that indicates the value is marked for deletion.

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.

21. A state-based replication system as recited in claim 18, wherein the indicators comprise an update indicator that corresponds to when a value is changed.

22. A state-based replication system as recited in claim 18, wherein the indicators comprise a creation indicator that corresponds to when a value is created.

23. A state-based replication system as recited in claim 18, wherein the indicators comprise a version number that corresponds to a version of a value and an update timestamp that corresponds to when the value is changed.

24. A state-based replication system as recited in claim 18, wherein the indicators comprise a creation timestamp that corresponds to when a value is created, a version number that corresponds to a version of the value, and an update timestamp that corresponds to when the value is changed.

25. A state-based replication system as recited in claim 18, wherein the indicators comprise a deletion indicator that has a null identifier to indicate the existence of a value of the attribute.

26. A state-based replication system as recited in claim 18, wherein the indicators comprise a deletion timestamp that corresponds to when a value is marked for deletion from the attribute.

28. A state-based replication system as recited in claim 27, wherein the first and second computers are further configured to:

compare the conflict-resolution information associated with the value of the attribute in the first data structure with the conflict-resolution information associated with the value of the attribute in the second data structure;

identify a replication conflict; and

resolve the replication conflict with the conflict-resolution information associated with the values.

29. A state-based replication system as recited in claim 27, wherein the conflict-resolution information comprises a version indicator that corresponds to a version of an individual linked value.

30. A state-based replication system as recited in claim 27, wherein:

the conflict-resolution information comprises a version number that corresponds to a version of an individual linked value;

the first and second computers are further configured to compare the version number associated with the linked value of the attribute in the first data structure with the version number associated with the linked value of the attribute in the second data structure;

the first computer is further configured to update the linked value of the attribute in the first data structure if the linked value has a lower version number than the linked value of the attribute in the second data structure; and

the second computer is further configured to update the linked value of the attribute in the second data structure if the linked value has a lower version number than the linked value of the attribute in the first data structure.

31. A state-based replication system as recited in claim 27, wherein the conflict-resolution information comprises an update indicator that corresponds to when an individual linked value is changed.

32. A state-based replication system as recited in claim 27, wherein:

the conflict-resolution information comprises an update timestamp that corresponds to when an individual linked value is changed;

the first and second computers are further configured to compare the update timestamp associated with the linked value of the attribute in the first data structure with the update timestamp associated with the linked value of the attribute in the second data structure;

the first computer is further configured to update the linked value of the attribute in the first data structure if the linked value has an earlier update timestamp than the linked value of the attribute in the second data structure; and

the second computer is further configured to update the linked value of the attribute in the second data structure if the linked value has an earlier update timestamp than the linked value of the attribute in the first data structure.

33. A state-based replication system as recited in claim 27, wherein the conflict-resolution information comprises a creation indicator that corresponds to when an individual linked value is created.

34. A state-based replication system as recited in claim 27, wherein:

the conflict-resolution information comprises a creation timestamp that corresponds to when an individual linked value is created;

the first and second computers are further configured to compare the creation timestamp associated with the linked value of the attribute in the first data structure with the creation timestamp associated with the linked value of the attribute in the second data structure;

the first computer is further configured to update the linked value of the attribute in the first data structure if the linked value has an earlier creation timestamp than the linked value of the attribute in the second data structure; and

the second computer is further configured to update the linked value of the attribute in the second data structure if the linked value has an earlier creation timestamp than the linked value of the attribute in the first data structure.

35. A state-based replication system as recited in claim 27, wherein the conflict-resolution information comprises a version indicator that corresponds to a version of an individual linked value and an update indicator that corresponds to when the individual linked value is changed.

36. A state-based replication system as recited in claim 27, wherein the conflict-resolution information comprises a creation indicator that corresponds to when an individual linked value is created, a version indicator that corresponds to a version of the individual linked value, and an update indicator that corresponds to when the individual linked value is changed.

37. A state-based replication system as recited in claim 27, wherein the individual linked values have an associated deletion indicator that is a null identifier to indicate the existence of a linked value of the multi-valued attribute.

38. A state-based replication system as recited in claim 27, wherein the individual linked values have an associated deletion indicator that corresponds to when an individual linked value is marked for deletion from the multi-valued attribute.

40. A computer-readable medium as recited in claim 39, wherein the data structure further comprises a fifth data field containing a creation indicator corresponding to when the value contained in the second data field is created.

41. A computer-readable medium as recited in claim 39, wherein the data structure further comprises a sixth data field containing a deletion indicator corresponding to the value contained in the second data field and configured to indicate when the value is marked for deletion from the data structure.

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.

27. A state-based replication system, comprising:

a first computer configured to maintain a first data structure, the first data structure having a multi-valued attribute comprised of linked values, individual linked values having conflict-resolution information to indicate a change to a value of the attribute;

a second computer configured to maintain a second data structure having the multi-valued attribute comprised of the linked values; and

the first and second data structures configured to be replicated and to have a replication conflict between a value of the attribute in the first data structure and a value of the attribute in the second data structure resolved with the conflict-resolution information associated with the values.

39. A computer-readable medium having stored thereon a data structure, comprising:

a first data field containing an attribute;

a second data field containing a value of the attribute contained in the first data field;

a third data field containing a version indicator corresponding to a version of the value contained in the second data field; and

a fourth data field containing an update indicator corresponding to when the version indicator contained in the third data field is changed.

42. A network system, comprising:

a first computer configured to replicate objects at an attribute level, and further configured to maintain an object having a multi-valued attribute, the multi-valued attribute comprised of individual values;

a second computer configured to replicate objects at an attribute value level, and further configured to maintain a second object, the second object having a multi-valued attribute comprised of individual values, the individual values configured to have conflict-resolution data;

the first computer further configured to;

replicate the second object from the second computer;

resolve a replication conflict between the object and the second object at the attribute level; and

resolve a replication conflict between the object and the second object at the attribute value level with the conflict-resolution data.

43. A network system as recited in claim 42, wherein the first computer first resolves the replication conflict between the object and the second object at the attribute level, and second resolves the replication conflict between the object and the second object at the attribute value level.

44. A network system as recited in claim 42, wherein the first computer does not replicate a value from the second object if the value does not have conflict-resolution data.

45. A network system as recited in claim 42, wherein the first computer does not replicate a value from the second object if the value has null conflict-resolution data.

46. A network system as recited in claim 42, wherein the first computer resolves the replication conflict between the object and the second object at the attribute value level in favor of a value that has conflict-resolution data.

47. A network system as recited in claim 42, wherein the first computer resolves the replication conflict between the object and the second object at the attribute value level in favor of a value that has non-null conflict-resolution data.

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

replicate the object from the first computer;

resolve a replication conflict between the object and the second object at the attribute level; and

resolve a replication conflict between the object and the second object at the attribute value level with the conflict-resolution data.

49. A network system as recited in claim 48, wherein the second computer first resolves the replication conflict between the object and the second object at the attribute level, and second resolves the replication conflict between the object and the second object at the attribute value level.

50. A network system as recited in claim 48, wherein the second computer does not replicate a value from the object if the value does not have conflict-resolution data.

51. A network system as recited in claim 48, wherein the second computer does not replicate a value from the object if the value has null conflict-resolution data.

52. A network system as recited in claim 48, wherein the second computer resolves the replication conflict between the object and the second object at the attribute value level in favor of a value that has conflict-resolution data.

53. A network system as recited in claim 48, wherein the second computer resolves the replication conflict between the object and the second object at the attribute value level in favor of a value that has non-null conflict-resolution data.

54. A network system as recited in claim 48, wherein the second computer is further configured to delete a value from the second object if the value does not have conflict resolution data, and if the value is not replicated from the object.

55. A method, comprising:

replicating an object stored in a first directory with a replica object stored in a second directory, the object and the replica object having an attribute comprised of individual values, the individual values having conflict-resolution data;

comparing a value of the attribute in the object with a value of the attribute in the replica object to identify a replication conflict; and

resolving the replication conflict with the conflict-resolution data.

56. A method as recited in claim 55, wherein the conflict-resolution data comprises a version number that corresponds to a version of an individual value, and wherein said comparing comprises determining if a value version number has been changed

57. A method as recited in claim 55, wherein the conflict-resolution data comprises a version number that corresponds to a version of an individual value, said comparing comprises determining if a value version number has been changed, and the method further comprises updating the value of the attribute that has a lower version number with the value of the attribute that has a higher version number.

58. A method as recited in claim 55, wherein the conflict-resolution data comprises an update timestamp that corresponds to when an individual value is changed, and wherein said comparing comprises determining if a value update timestamp has been changed.

59. A method as recited in claim 55, wherein the conflict-resolution data comprises an update timestamp that corresponds to when an individual value is changed, said comparing comprises determining if a value update timestamp has been changed, and the method further comprises updating the value of the attribute that has an earlier update timestamp with the value of the attribute that has a later update timestamp.

60. A method as recited in claim 55, wherein the conflict-resolution data comprises a creation timestamp that corresponds to when an individual value is created, and wherein said comparing comprises determining if a creation timestamp has been changed.

61. A method as recited in claim 55, wherein the conflict-resolution data comprises a creation timestamp that corresponds to when an individual value is created, said comparing comprises determining if a creation timestamp has been changed, and the method further comprises updating the value of the attribute that has an earlier creation timestamp with the value of the attribute that has a later creation timestamp.

62. A method as recited in claim 55, 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 changed, and wherein said comparing comprises determining if a value version number has been changed and if the value update timestamp has been changed.

63. A method as recited in claim 55, 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 changed, and the method further comprises updating the value of the attribute that first has a lower version number, and second has an earlier update timestamp.

64. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 63.

65. A method as recited in claim 55, 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 changed, and wherein said comparing comprises determining if a value creation timestamp has been changed, if the value version number has been changed, and if the value update timestamp has been changed.

66. A method as recited in claim 55, 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 changed, and the method further comprises updating the value of the attribute that first has an earlier creation timestamp, second has a lower version number, and third has an earlier update timestamp.

67. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 66.

68. A method as recited in claim 55, wherein the individual values have a deletion timestamp that is a null identifier to indicate the existence of a value of the attribute.

69. A method as recited in claim 55, wherein the individual values have a deletion timestamp that corresponds to when an individual value is marked for deletion from the attribute.

70. A method as recited in claim 55, wherein the individual values have a deletion timestamp that corresponds to when an individual value is marked for deletion from the attribute, and the method further comprises deleting a value from the attribute if the value has a deletion timestamp that indicates the value is marked for deletion.

71. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 70.

72. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 55.

73. A method for replicating a linked value of a multi-valued attribute contained in an object, the linked value having conflict-resolution information and replicated from a replica object having the multi-valued attribute and the linked value, the method comprising:

comparing the conflict-resolution information associated with the linked value in the object with the conflict-resolution information associated with the linked value in the replica object;

identifying a replication conflict with the conflict-resolution information; and

resolving the replication conflict with the conflict-resolution information.

74. A method as recited in claim 73, wherein the conflict-resolution information comprises a version number that corresponds to a version of the linked value, and the method further comprising:

determining if the linked value version number has been changed; and

updating the linked value of the attribute that has a lower version number with the linked value of the attribute that has a higher version number.

75. A method as recited in claim 73, wherein the conflict-resolution information comprises an update timestamp that corresponds to when the linked value is changed, and the method further comprising:

determining if the linked value update timestamp has been changed; and

updating the linked value of the attribute that has an earlier update timestamp with the linked value of the attribute that has a later update timestamp.

76. A method as recited in claim 73, wherein the conflict-resolution information comprises a creation timestamp that corresponds to when the linked value is created, and the method further comprising:

determining if the linked value creation timestamp has been changed; and

updating the linked value of the attribute that has an earlier creation timestamp with the linked value of the attribute that has a later creation timestamp.

77. A method as recited in claim 73, wherein the conflict-resolution information comprises a creation timestamp that corresponds to when the linked value is created, a version number that corresponds to a version of the linked value, and an update timestamp that corresponds to when the linked value is changed.

78. A method as recited in claim 73, wherein the conflict-resolution information comprises a creation timestamp that corresponds to when the linked value is created, a version number that corresponds to a version of the linked value, and an update timestamp that corresponds to when the linked value is changed, and the method further comprises updating the linked value of the attribute if the linked value first has an earlier creation timestamp, second has a lower version number, and third has an earlier update timestamp.

79. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 78.

80. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 73.

81. A method, comprising:

replicating a first object with a second object, the first object having an attribute comprised of individual values, the second object having an attribute comprised of individual values configured to have associated conflict-resolution data;

resolving first a replication conflict between the first object and the second object at an attribute level; and

resolving second, with the conflict-resolution data, a replication conflict between the first object and the second object at an attribute value level.

82. A method as recited in claim 81, further comprising determining whether a value corresponding to the second object has conflict-resolution data and said replicating the value if said determining that the value has conflict-resolution data.

83. A method as recited in claim 81, further comprising determining whether a value corresponding to the second object has non-null conflict-resolution data and said replicating the value if said determining that the value has non-null conflict-resolution data.

84. A method as recited in claim 81, said resolving the replication conflict between the first object and the second object at the attribute value level in favor of a value that has conflict-resolution data.

85. A method as recited in claim 81, further comprising deleting a value corresponding to the second object if the value does not have conflict-resolution data and if the value is not replicated.

86. A computer-readable medium comprising computer executable instructions that, when executed, direct a computing system to perform the method of claim 81.