Method and apparatus for moving subtrees in a distributed network directory

Claim 3

A method as recited in claim 1, wherein step (d) is achieved by switching in the local record of each such computer the root object's parent from the parent object to the destination object.

Claim 4

A method as recited in claim 1, wherein step (e) is achieved by creating a subordinate reference for the source subtree.

Claim 5

A method as recited in claim 1, wherein step (f) is achieved by creating an external reference for the destination object.

Claim 6

A method as recited in claim 1, wherein one of the computers is a master server holding a master replica of the source subtree.

Claim 7

A method as recited in claim 5, further comprising in step (e) the step of informing the master server to add the subordinate reference to the replica list of the source subtree.

Claim 8

A method as recited in claim 5, further comprising in step (f) the step of informing the master server to create a back link to each such computer.

Claim 9

A method as recited in claim 5, wherein the master server sends a request to each of the computers on the list to move the source subtree.

Claim 10

A computer system as recited in claim 1, wherein the source and destination subtrees are partitions in the distributed directory.

Claim 11

A method as recited in claim 1, wherein the computers are interconnected in a client/server network.

Claim 12

A method as recited in claim 10, wherein the reorganization is initiated by a client in the network.

Claim 13

A computer system as recited in claim 10, wherein the list of computers includes one or more servers that hold one or more of the following: (a) a replica of the source subtree; (b) a replica of the destination subtree; or (c) a reference to an object in the source subtree.

Claim 14

A computer readable medium comprising a program for reorganizing a distributed directory having a hierarchy of objects, said program being operative to perform the steps of: (a) identifying a source subtree having a root object directly subordinate to a parent object, (b) identifying a destination object within a destination subtree; (c) creating a list of computers; (d) for each computer on the list having at least one of the following: i. a replica of the source subtree and a replica of the destination subtree, ii. a replica of the source subtree and a reference to the root object of the destination subtree, iii. a replica of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, or iv. a reference to the root object of the source subtree and a reference to the root object of the destination subtree, changing in each such computer the direct subordination of the root object in the source subtree from the parent object to the destination object; (e) for each computer on the list having at least one of the following: i. a reference to the root object of the source subtree and a replica of the destination subtree, or ii. neither a replica of the source subtree nor a reference to the root object of the source subtree, and a replica of the destination subtree, creating in each such computer a reference to the source subtree; and (f) for each computer on the list having a reference to the root object of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, creating in each such computer a reference to the destination object.

Claim 15

A computer readable medium comprising a program for reorganizing a distributed directory having a hierarchy of objects, said program being operative to perform the steps of: (a) identifying a source subtree having a root object directly subordinate to a parent object, (b) identifying a destination object within a destination subtree; (c) creating a list of computers; (d) for each computer on the list having at least one of the following: i. a replica of the source subtree and a replica of the destination subtree, ii. a replica of the source subtree and a reference to the root object of the destination subtree, iii. a replica of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, or iv. a reference to the root object of the source subtree and a reference to the root object of the destination subtree, changing in each such computer the direct subordination of the root object in the source subtree from the parent object to the destination object; (e) for each computer on the list having at least one of the following: i. a reference to the root object of the source subtree and a replica of the destination subtree, or ii. neither a replica of the source subtree nor a reference to the root object of the source subtree, and a replica of the destination subtree, creating in each such computer a reference to the source subtree; and (f) for each computer on the list having a reference to the root object of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, creating in each such computer a reference to the destination object.

Claim 16

A computer system, comprising: (a) a plurality of objects, said objects including: i. a parent object, ii. a root object, and iii. a destination object; (b) a plurality of pointers defining a hierarchy in the objects, said hierarchy including: i. a source subtree holding the root object, wherein the root object is the child of the parent object, and ii. a destination subtree holding the destination object; (c) a plurality of computers, wherein one or more of said plurality of computers stores replicas of one or more of said objects and at least a portion of said plurality of pointers; and (d) a reorganization mechanism operative to reorganize the hierarchy by modifying the pointers in one or more of the plurality of computers such that the parent of the root object of the source subtree is changed to the destination object of the destination subtree, and the root object of the source subtree is no longer a child of the parent object of the parent subtree.

Claim 17

A computer system, comprising: (a) a plurality of objects, said objects including: i. a parent object, ii. a root object, and iii. a destination object; (b) a plurality of pointers defining a hierarchy in the objects, said hierarchy including: i. a source subtree holding the root object, wherein the root object is the child of the parent object, and ii. a destination subtree holding the destination object; (c) a plurality of computers, wherein one or more of said plurality of computers stores replicas of one or more of said objects and at least a portion of said plurality of pointers; and (d) a reorganization mechanism operative to reorganize the hierarchy by modifying the pointers in one or more of the plurality of computers such that the parent of the root object of the source subtree is changed to the destination object of the destination subtree, and the root object of the source subtree is no longer a child of the parent object of the parent subtree.

Claim 18

A computer system as recited in claim 14, wherein the reorganization mechanism performs one or more of the following steps: (a) for each computer having at least one of the following: i. a replica of the source subtree and a replica of the destination subtree, ii. a replica of the source subtree and a reference to the root object of the destination subtree, iii. a replica of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, or iv. a reference to the root object of the source subtree and a reference to the root object of the destination subtree, changing in each such computer the parent of the root object in the source subtree from the parent object to the destination object; (b) for each computer having at least one of the following: i. a reference to the root object of the source subtree and a replica of the destination subtree, or ii. neither a replica of the source subtree nor a reference to the root object of the source subtree, and a replica of the destination subtree, creating in each such computer a reference to the source subtree; and (c) for each computer having a reference to the root object of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, creating in each such computer a reference to the destination object.

Claim 19

A computer system as recited in claim 15, wherein step (a) is achieved by switching in the local record of each such computer the root object's parent from the parent object to the destination object.

Claim 20

A computer system as recited in claim 15, wherein step (b) is achieved by creating a subordinate reference for the source subtree.

Claim 21

A computer system as recited in claim 15, wherein step (c) is achieved by creating an external reference for the destination object.

Claim 22

A computer system as recited in claim 15, wherein one of said computers is a master server holding a master replica of the source subtree.

Claim 23

A computer system as recited in claim 19, further comprising in step (b) the step of informing the master server to add the subordinate reference to the replica list of the source subtree.

Claim 24

A computer system as recited in claim 19, further comprising in step (c) the step of informing the master server to create a back link to each such relevant server.

Claim 25

A computer system as recited in claim 19, wherein the master server sends a request to each of the computers to move the source subtree.

Claim 26

A computer system as recited in claim 14, wherein the plurality of computers are interconnected in a client/server network.

Claim 27

A computer system as recited in claim 14, wherein the hierarchy of objects comprises a distributed directory.

Claim 28

A computer system as recited in claim 24, wherein the source and destination subtrees are partitions in the distributed directory.

Claim 31

A method as recited in claim 26, wherein the checking step comprises one or more of the following steps: (a) enforcing access control; (b) enforcing directory schema rules; (c) checking whether the object of the server holding the master replica of the destination subtree is itself involved in an reorganization unrelated to the client's request; or (d) checking whether a software version can support the requested move.

Claim 32

A method as recited in claim 26, further comprising the step of checking whether the parent and destination subtrees overlap, and locking the parent subtree if the parent and destination subtrees do not overlap.

Claim 33

A method as recited in claim 26, wherein the source, parent and destination subtrees are partitions in the distributed directory.

Claim 34

A method as recited in claim 26 wherein step (e) is achieved by one or more of the following steps: (a) for each computer on the list having at least one of the following: i. a replica of the source subtree and a replica of the destination subtree, ii. a replica of the source subtree and a reference to the root object of the destination subtree, iii. a replica of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, or iv. a reference to the root object of the source subtree and a reference to the root object of the destination subtree, changing in each such computer the parent of the root object in the source subtree from the parent object to the destination object; (b) for each computer on the list having at least one of the following: i. a reference to the root object of the source subtree and a replica of the destination subtree, or ii. neither a replica of the source subtree nor a reference to the root object of the source subtree, and a replica of the destination subtree, creating in each such computer a reference to the source subtree; and (c) for each computer on the list having a reference to the root object of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, creating in each such computer a reference to the destination object.

Claim 35

A computer system, comprising: (a) a distributed directory having a hierarchy of objects, said distributed directory comprising: i. a parent object, ii. a source subtree having a root object that is a child of the parent object, and iii. a destination object within a destination subtree; (b) a plurality of computers that hold one or more of the following: i. a replica of the source subtree, ii. a replica of the destination subtree, or iii. a reference to an object in the source subtree; and (c) for each computer having at least one of the following: i. a replica of the source subtree and a replica of the destination subtree, ii. a replica of the source subtree and a reference to the root object of the destination subtree, iii. a replica of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, or iv. a reference to the root object of the source subtree and a reference to the root object of the destination subtree, means for changing in each such computer the parent of the root object in the source subtree from the parent object to the destination object; (d) for each computer having at least one of the following: i. a reference to the root object of the source subtree and a replica of the destination subtree, or ii. neither a replica of the source subtree nor a reference to the root object of the source subtree, and a replica of the destination subtree, means for creating in each such computer a reference to the source subtree; and (e) for each computer having a reference to the root object of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, means for creating in each such computer a reference to the destination object.

Claim 36

A computer system, comprising: (a) a distributed directory having a hierarchy of objects, said distributed directory comprising: i. a parent object, ii. a source subtree having a root object that is a child of the parent object, and iii. a destination object within a destination subtree; (b) a plurality of computers that hold one or more of the following: i. a replica of the source subtree, ii. a replica of the destination subtree, or iii. a reference to an object in the source subtree; and (c) for each computer having at least one of the following: i. a replica of the source subtree and a replica of the destination subtree, ii. a replica of the source subtree and a reference to the root object of the destination subtree, iii. a replica of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, or iv. a reference to the root object of the source subtree and a reference to the root object of the destination subtree, means for changing in each such computer the parent of the root object in the source subtree from the parent object to the destination object; (d) for each computer having at least one of the following: i. a reference to the root object of the source subtree and a replica of the destination subtree, or ii. neither a replica of the source subtree nor a reference to the root object of the source subtree, and a replica of the destination subtree, means for creating in each such computer a reference to the source subtree; and (e) for each computer having a reference to the root object of the source subtree and neither a replica of the destination subtree nor a reference to the root object of the destination subtree, means for creating in each such computer a reference to the destination object.