Inherited information propagator for objects
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
38 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11)
-
-
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. - View Dependent Claims (13, 14)
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. - View Dependent Claims (16, 17, 18, 19)
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. - View Dependent Claims (21, 22, 23, 24)
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. - View Dependent Claims (26, 27, 28, 29, 30)
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. - View Dependent Claims (32, 33, 34, 35, 36)
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. - View Dependent Claims (38)
-
Specification