Inherited information propagator for objects

• US 6,446,077 B2
• Filed: 09/21/1998
• Issued: 09/03/2002
• Est. Priority Date: 09/21/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Williams, Tim, Straube, Dave
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Pardo, Thuy
• Application Number:
  US09/157,728
• Publication Number:
  US 20020002557A1
• Time in Patent Office: 1,443 Days
• Field of Search: 707/102, 707/103, 707/8, 707/100, 707/201, 709/226, 714/7, 717/4, 717/7, 395/707, 345/329
• US Class Current: 1/1
• 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/275 Synchronous replication
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Dynamic inheritance for data in a replicated tree structured database which is dynamically inherited from parent objects is provided by only replicating original modifications, and then causing each system to propagate inherited information across it'"'"'s local tree of objects. When a change to a security descriptor or a reparenting of objects is received, a breadth first tree traversal is used to find all the affected objects. An ID list is incrementally deleted as each object is updated. A security descriptor propagator queue is used to track the progress of updates, and items are taken off the list only after they are committed to the database. A gate is used to ensure that that transactions which add new objects and the security descriptor propagation transactions which write new security descriptors are mutually exclusive. A new data structure for the propagation queue comprises a table having a unique, incrementing number representing an order, an identifier of the node to begin on, a flag indicting whether the item may be trimmed a client id, an order index used to find the next element in the queue and a trim index which tracks all trimmable nodes.

Claims

1. A method of modifying information inherited between objects when one of the objects is modified, the method comprising:

receiving a modification to an object;

writing indications of modified objects into a propagation queue;

searching a directory structure for related objects;

recalculating portions of the related objects which need to be modified as a result of the received modification based on the indications in the queue; and

modifying the related objects with the recalculated portions.

2. The method of claim 1 and further comprising creating an id list of the related objects.

3. The method of claim 1 and further comprising creating a list of received modifications.

4. The method of claim 3 wherein the received modifications are received from programs running on a single computer and are received from programs running on networked computers.

5. The method of claim 3 and further comprising trimming the propagation queue to remove modifications that would be redundant.

6. The method of claim 1 wherein the modifications comprise dynamically inherited security descriptors or parent lists.

7. The method of claim 1 wherein searching for related objects is stopped for an object if the portion recalculated did not change.

8. A machine readable medium having instructions stored thereon for causing a computer to perform a method of modifying information inherited between objects when one of the objects is modified, the method comprising:

receiving a modification to an object;

searching a directory database for related objects;

recalculating portions of the related objects which need to be modified as a result of the received modification; and

modifying the related objects with the recalculated portions.

9. The machine readable medium of claim 8 and further comprising instructions for creating a queue of received modifications.

10. The method of claim 9 wherein the received modifications are received from programs running on a single computer and are received from programs running on networked computers.

11. The machine readable medium of claim 9 and further comprising instructions for trimming the queue to remove modifications that would be redundant.

12. A machine readable medium having a data structure stored thereon for use in propagating changes to a replicated directory database comprising a plurality of directory objects, the data structure comprising:

an incrementing number data field to enable the data structure to function as a queue;

a start object data field to identify an object of the directory objects with which to begin propagating a change to the object and to a set of corresponding objects comprising information inherited from the object; and

an order index data field to identify a next object of the directory objects to continue propagating the change to the next object and to a set of corresponding objects comprising information inherited from the next object.

13. The data structure of claim 12 and further comprising:

a trim flag data field to indicate that an indication of a particular object of the directory objects can be removed from the data structure; and

a trim index data field to provide clients with an option to receive information about a state of replication underway.

14. The data structure of claim 13 wherein the trim index comprises a compound index over the trim flag and the start object.

15. In a distributed computing environment at a first computing device, a method for propagating changes across multiple copies of a distributed directory database, the method comprising:

modifying a parent object and one or more related objects in a first copy of the distributed directory database;

responsive to modifying the parent object, communicating a single replication message indicating the parent object to a second computing device in the distributed computing environment; and

whereupon receipt of the single replication message causes the second computing device to synchronize a second copy of the distributed database with the first copy such that there is a one-to-one correspondence between modifications made in the first copy and modifications made in the second copy.

16. A method as recited in claim 15, wherein modifying the parent object and the one or more related objects further comprises:

searching the first copy for the one or more related objects; and

for each related object;

(a) recalculating a portion of the related object based on a state of the parent and a set of characteristics of the related object; and

(b) modifying the related object based on the portion.

17. A method as recited in claim 16, wherein the distributed directory database comprises a plurality of objects organized as a hierarchal tree, and wherein searching the first copy further comprises searching the first copy for the one or more related objects with a breadth first search starting from the parent object.

18. A method as recited in claim 15, further comprising generating a propagation queue comprising indications of the parent object and the one or more related objects.

19. A method as recited in claim 18, further comprising trimming the propagation queue to remove information that would cause redundant modifications to be made to one or more directory objects in the distributed directory database.

20. A computer-readable medium comprising computer-executable instructions for propagating changes across multiple copies of a distributed directory database, the computer-executable instructions comprising instructions for:

modifying a parent object and one or more related objects in a first copy of the distributed directory database;

responsive to modifying the parent object, communicating a single replication message indicating the parent object to a second computing device in the distributed computing environment; and

whereupon receipt of the single replication message causes the second computing device to synchronize a second copy of the distributed database with the first copy such that there is a one-to-one correspondence between modifications made in the first copy and modifications made in the second copy.

21. A computer-readable medium as recited in claim 20, wherein the instructions for modifying the parent object and the one or more related objects further comprise instructions for:

searching the first copy for the one or more related objects; and

for each related object;

(a) recalculating a portion of the related object based on a state of the parent and a set of characteristics of the related object; and

(b) modifying the related object based on the portion.

22. A computer-readable medium as recited in claim 20, wherein the distributed directory database comprises a plurality of objects organized as a hierarchal tree, and wherein the instructions for searching the first copy further comprise instructions for searching the first copy for the one or more related objects with a breadth first search starting from the parent object.

23. A computer-readable medium as recited in claim 20, further comprising computer-executable instructions for generating a propagation queue comprising indications of the parent object and the one or more related objects.

24. A computer-readable medium as recited in claim 23, further comprising computer-executable instructions for trimming the propagation queue to remove information that would cause redundant modifications to be made to one or more directory objects in the distributed directory database.

25. A method for propagating multiple changes across various copies of a distributed directory database, the method comprising:

receiving, at a first device, a replication message indicating that a second device has modified a single object in a second copy of the distributed directory database; and

responsive to receiving the replication message, synchronizing, at the first device, a first copy of the distributed directory database to mirror the second copy such that at least one change to each of a plurality of objects in the second copy resulting from modification of the single object are replicated in the second copy.

26. A method as recited in claim 25, wherein synchronizing the first copy to mirror the second copy further comprises:

modifying an object in the first copy that corresponds to the single object based on the replication message; and

modifying one or more of other directory objects in the first copy that dynamically inherit information the object.

27. A method as recited in claim 25, wherein the second copy comprises a plurality of directory objects that are organized as a hierarchal tree, and wherein synchronizing the first copy to mirror the second copy further comprises:

identifying an object of the directory objects that corresponds to the single object; and

locating any other objects of the directory objects that are related to the object using a breadth first search that starts at object.

28. A method as recited in claim 25, wherein synchronizing the first copy to mirror the second copy further comprises:

generating a propagation queue comprising indications of each other object in the first copy that is related to the object; and

for each indication in the propagation queue, modifying a corresponding object based on a state of the object and one or more characteristics of the corresponding object.

29. A method as recited in claim 25, wherein synchronizing the first copy to mirror the second copy further comprises:

generating a propagation queue comprising indications of each other object in the first copy that is related to the object; and

for each indication;

(a) determining if one or more portions of a corresponding object need to be changed; and

(b) only modifying the corresponding object if one or more portions need to be changed.

30. A method as recited in claim 29, further comprising trimming the propagation queue to remove information that would cause redundant modifications to be made to one or more of the directory objects in the first copy.

31. A computer-readable medium comprising computer-executable instructions for propagating multiple changes across various copies of a distributed directory database, the computer-executable instructions comprising instructions for:

receiving, at a first device, a replication message indicating that a second device has modified a single object in a second copy of the distributed directory database; and

responsive to receiving the replication message, synchronizing, at the first device, a first copy of the distributed directory database to mirror the second copy such that at least one change to each of a plurality of objects in the second copy resulting from modification of the single object are replicated in the second copy.

32. A computer-readable medium as recited in claim 31, wherein the instructions for synchronizing the first copy to mirror the second copy further comprise instructions for:

modifying an object in the first copy that corresponds to the single object based on the replication message; and

modifying one or more of other directory objects in the first copy that dynamically inherit information the object.

33. A computer-readable medium as recited in claim 31, wherein the second copy comprises a plurality of directory objects that are organized as a hierarchal tree, and wherein the instructions for synchronizing the first copy to mirror the second copy further comprise instructions for:

identifying an object of the directory objects that corresponds to the single object; and

locating any other objects of the directory objects that are related to the object using a breadth first search that starts at object.

34. A computer-readable medium as recited in claim 31, wherein the instructions for synchronizing the first copy to mirror the second copy further comprise instructions for:

generating a propagation queue comprising indications of each other object in the first copy that is related to the object; and

for each indication in the propagation queue, modifying a corresponding object based on a state of the object and one or more characteristics of the corresponding object.

35. A computer-readable medium as recited in claim 31, wherein the instructions for synchronizing the first copy to mirror the second copy further comprise instructions for:

generating a propagation queue comprising indications of each other object in the first copy that is related to the object; and

for each indication;

(a) determining if one or more portions of a corresponding object need to be changed; and

(b) only modifying the corresponding object if one or more portions need to be changed.

36. A computer-readable medium as recited in claim 35, further comprising instructions for trimming the propagation queue to remove information that would cause redundant modifications to be made to one or more of the directory objects in the first copy.

37. In a distributed computing environment, a method for propagating a plurality of changes across multiple copies of a distributed directory database, the method comprising:

receiving a message indicating that a first object in a distributed directory database has been modified;

responsive to receiving the message;

identifying one or more other objects in the distributed directory database that correspond to the first object; and

for each other object in at least one subset of the one or more other objects, changing an attribute of the other object based on a state of the first object and characteristics of the other object.

38. A method as recited by claim 37, wherein the message is a single replication message that is communicated by a first computing device, and wherein the single replication message is received by one or more other computing devices that are operatively coupled to the first computing device.