Method and system for detecting object inconsistency in a loosely consistent replicated directory service

• US 6,751,634 B1
• Filed: 08/26/1999
• Issued: 06/15/2004
• Est. Priority Date: 08/26/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Judd, Steven G.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): DODDS, HAROLD E
• Application Number:
  US09/383,445
• Time in Patent Office: 1,755 Days
• Field of Search: 707/1, 707/2, 707/100, 707/103, 707/200, 707/201, 707/203, 707/103-R-1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• 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: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The invention describes a system for detecting partial changes to data-structures of interest. If an inter-related set of data items are to be used then it is of value to know that the data items are undergoing changes, and thus may not be self consistent, and/or have been tampered with and/or are not the most recent update. The invention uses GUIDS to track updates by assigning a GUID to a selected set of nodes or items belonging to an identified set, preferably arranged in a tree structure. A new GUID is generated whenever an update takes place. Methods are defined to test that the interrelated data items are valid, i.e., replicated in toto, by testing for changes in the GUID by traversing the interrelated data items and comparing GUIDs at each node. Similarly, methods are provided for generating a new GUID in course of inititiating an update, or in order to invalidate an intererlated data item set, and additional methods are envisaged for catering to particular applications such as assuring integrity of the data by using encryption and certificates.

Claims

1. A method for creating an object-set in a database to aid in detecting object inconsistency in the object-set, wherein the object-set includes a plurality of objects, each object having a plurality of attributes, and the plurality of objects in the object-set corresponding to nodes in a tree, the tree having a root node, the method comprising:

associating each node in the tree with a consistency-identifier that identifies the nodes in the tree, and a consistency-count that represents information about a number of children nodes of the node;

setting an arbitrary number as the consistency-count for at least one of the nodes;

generating a new identifier; and

traversing the tree to visit every node in the tree;

where furthermore, at a particular node in the tree, while traversing the tree;

determining the number of children nodes of the particular node in the tree;

assigning the new identifier to the consistency-identifier associated with the particular node in the tree; and

assigning a number associated with the number of children nodes of the particular node to the consistency-count associated with the particular node.

2. The method of claim 1 further including determining the number of children of the particular node in the tree by counting the children of the particular while traversing the tree.

3. The method of claim 1 wherein a depth-first strategy is used in traversing the tree.

4. A method for creating an object-set in a database to facilitate detection of a partial-update of the object-set wherein the object-set includes a plurality of objects, each object having a plurality of attributes, and the plurality of objects in the object-set corresponding to nodes in a tree, the tree having a root node, the method comprising:

associating a consistency-identifier with each node in the tree;

associating a consistency-count with each node in the tree;

setting an arbitrary number as the consistency-count for at least one of the nodes;

generating a new identifier;

determining a number of children of a particular node in the tree by traversing the tree; and

assigning the new identifier to the consistency-identifier of a particular node in the tree, and assigning a number associated with the number of children of the particular node to the consistency-count associated with the particular node.

5. The method of claim 4 wherein the tree traversal follows a depth-first strategy.

6. The method of claim 4 further including the step of assigning the new identifier to a consistency-identifier corresponding to a node in the tree, the node being encountered while conducting a tree traversal of the tree.

7. The method of claim 6 wherein the tree traversal follows a depth-first strategy.

8. A computer-readable medium having stored thereon a database comprising a plurality of objects, each of the plurality of objects having a plurality of attributes, the database comprising an object set, and the object set comprising:

a set of objects selected from the plurality of objects and being organized in a tree structure with an object corresponding to a node of the tree structure, and each of the objects in the object-set having at least two attributes, a first of the two attributes being a consistency-count, the consistency-count not being equal to the number of the children of the node if the object-set is not consistent, in the tree structure corresponding to the object; and

a second of the two attributes being a consistency-identifier, the consistency-identifier being equal to the consistency-identifier of every other object in the object-set if the object-set is consistent.

9. The object-set of claim 8 further comprising an object having a digital signature for authenticating a plurality of attributes of the object in the object-set.

10. The object-set of claim 8 wherein the consistency-count of an object in the object-set is equal to the number of children of a node corresponding to the object if and only if the object-set is consistent.

11. The object-set of claim 8 wherein the consistency-identifier of an object in the object-set is equal to the consistency-identifier of an object in the object-set corresponding to a root node of the tree structure if and only if the object-set is consistent.

12. A method of modifying an object-set in a database, the object-set comprising a plurality of objects, each of the objects of the plurality of objects corresponding to a distinct node of a tree, where, furthermore, each object in the plurality of objects having a consistency-identifier and a consistency-count, the method comprising:

invalidating the object-set by assigning a new identifier to a consistency-identifier of a root node of the tree and setting a consistency-count of the root node of the tree to an arbitrary number, the arbitrary number not being equal to the number of children of a node corresponding to the object;

making the modification to the objects-set;

assigning the new identifier to the consistency-identifiers of the remaining objects in the object-set; and

setting the consistency-count of each object in the object-set, including the root node, to a value associated with a number of children of a node corresponding to the object.

13. The method of claim 12 wherein assigning the new identifier to the consistency-identifiers of the objects in the object-set includes traversing the tree.

14. The method of claim 13 wherein the tree traversal follows a depth-first strategy.

15. The method of claim 12 wherein the number of children of the node in the tree is determined by traversing the tree using a depth-first strategy.

16. A computer readable medium, having computer-executable instructions for performing, in a database, the database including an object-set, the object-set comprising a plurality of objects, each of the plurality of objects corresponding to a distinct node in a tree, the computer-executable instructions comprising:

creating an object-set,

validating the object-set, and

invalidating the object-set by setting a consistency-count corresponding the root node of the tree to an arbitrary number.

17. The computer-readable medium of claim 16 wherein creating the object-set includes assigning an identifier to a consistency-identifier corresponding to a node in the tree while traversing the tree;

counting the number of children for the node while traversing the tree; and

, assigning a number associated with the number of children for the node in the tree to a consistency-count corresponding to the node.

18. The computer readable medium of claim 16 wherein creating an object-set is preceded by setting a consistency-flag, which is checked by a client prior to accessing the object-set, followed by making changes to the object-set, followed by resetting the consistency-flag.

19. The computer-readable medium of claim 16 wherein invalidating the object-set includes assigning a new identifier to a consistency-identifier corresponding to a root node of the tree;

and setting a consistency-count corresponding the root node of the tree to one.

20. The computer readable medium of claim 16 wherein invalidating the object-set includes setting a consistency-flag, which is checked by a client prior to accessing the object-set.

21. The computer-readable medium of claim 16 wherein validating the object-set includes counting the number of children of a root node of the tree, each of said children with a consistency-identifier equal to a consistency-identifier of the root node of the tree, while traversing the tree;

and declaring the objects set to be valid if the number of children of the root node of the tree is the same as a consistency-count of the root node of the tree.

22. The computer readable medium of claim 16 wherein validating an object-set includes checking a consistency-flag, where the object-set is invalid if the consistency-flag is set.

23. The computer-readable medium of claim 16 having, furthermore, computer-executable instructions for authenticating a user accessing the object-set.

24. The computer-readable medium of claim 16 having, furthermore, computer-executable instructions for generating a digital certificate corresponding to a plurality of attributes associated with an object in the object-set.