Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-01
2003-02-11
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06519610
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to distributed directory server systems, and more specifically to a system and method for maintaining referential integrity between objects in a distributed directory server system.
Personal computers or workstations may be linked in a computer network to allow the sharing of data, applications, files, and other resources. In a client/server network, the sharing of resources is accomplished through the use of one or more file servers. Each file server includes a processing unit that is dedicated to managing centralized resources and to sharing these resources with other file servers and/or various personal computers and workstations, which are known as the “clients” of the server.
Directories and directory services are often provided to enable an environment for a digital identity of a particular resource. One example of a directory service is Novell Directory Services (“NDS”) for Novell Netware networks, as provided by Novell, Inc. of Provo, Utah. NDS provides a logical tree-structure view of all resources on the network so that users can access them without knowing where they're physically located.
A directory tree can be partitioned in to several smaller sub-trees that are stored on many file servers. These partitions are said to be “replicated” on the servers. Each file server in the tree may contain anywhere from no replica of any partition to a replica of each partition.
Two important concepts in understanding the internal workings of NDS are external references and backlinks. An external reference is a reference to an entry that is not physically located on the local server. An external reference allows a reference to an entry without duplicating the entry on every server in the directory tree. External references are created for several reasons, including to ensure tree connectivity, to provide for authentication, and to refer to a nonlocal entry that is referenced in the attribute of a local entry.
A corresponding attribute to the external reference is the backlink. A backlink is stored as an object attribute to keep track of external references to the object. The directory uses a “BackLink” attribute to keep track of servers holding external references of an entry. The BackLink attribute has two parts, including the Distinguished Name(s) of the server(s) holding the external reference (this name is commonly referred to as the Remote Server Name) and the Entry ID of the external reference on the remote server (usually referred to as the Remote ID). When creating an external reference to an entry, NDS also schedules the creation of a BackLink attribute for the entry. Periodically, a backlink process checks the external reference to see if the original entry still exists and if there is a reason for the external reference to continue to exist. If the external reference is not needed, NDS removes it.
The backlink process enables easy maintenance of the external references by periodically verifying the remote server name and remote ID of each BackLink attribute of entries. When an entry is deleted, backlinks make it possible for all references to the entry to be deleted. Backlinks also facilitate renaming and moving entries, because the corresponding changes can be made to the external references through the operation of the backlink process. Thus, the backlink process helps to maintain the integrity of external references by allowing them to be updated to reflect the changes made to the objects they refer to. The back link process resolves external references to make sure there is a real entry that it refers to, and for real entries the process makes sure that an external reference exists. A local bit in each external reference is used to keep track of the status of backlinks.
When a server creates an external reference to an entry, it sends a CreateBackLink request to a server holding a writable copy of the entry. This request contains the local Entry ID, the remote Entry ID, the remote server name, and two Time Stamps (Remote Creation Time and Remote Key Time). If the CreateBackLink request fails, it retries periodically until the BackLink attribute is created.
When a server removes an external reference from its local database, it sends a RemoveBackLink request to a server holding a writable entry for the entry. The request contains the Local Entry ID, the Remote Entry ID, the Server Entry ID, and the Time Stamp (Entry Creation Time). This RemoveBackLink request operation causes the backlink to be deleted.
As previously described, when NDS creates a new external reference for an entry not stored on the local server, NDS attempts to place on the real entry a backlink that points to the server that holds the external reference. For example, referring to
FIGS. 1
a
and
1
b,
a tree
100
representing NDS includes two servers NS
1
and NS
2
. The tree
100
is named, in this case, “Novell,” by its root object. As shown in
FIG. 1
b,
the server NS
1
stores a master replica of partitions “[Root]” and “Provo” and a read/write replica of a partition “Core_OS.Provo” and the server NS
2
stores a master replica of the partition Core_OS.Provo. Partitions [Root], Provo and Core_OS.Provo are represented in
FIG. 1
a
by partition objects designated
102
,
104
, and
106
, respectively. Because the server NS
2
does not have a replica of partition Provo, the server NS
2
needs an external reference for partition Provo to connect partition Core_OS.Provo with [Root]. When NDS creates an external reference to partition Provo on server NS
2
, NDS places a backlink on server NS
1
's copy of entry Provo pointing to NS
2
. In operation, server NS
2
sends a CreateBackLink request that includes the backlink as an attribute value for the partition Provo.
The algorithm for creating a backlink is as follows. The server where the external reference is created sends a CreateBackLink request to the server holding a writable copy of the object. The server holding the original entry creates a backlink pointing to the server holding the external reference by adding to the original entry a BackLink attribute identifying the server holding the external reference and the identity of the external reference. The server holding the real entry returns a CreateBackLink reply. If this operation fails, NDS attempts to create the backlink nine more times at three-minute intervals. If all nine attempts fail, a background backlink process creates the backlink. The backlink process occurs every thirteen hours or as set by the system administrator and removes any expired or unnecessary external references from the system and creates and maintains any backlinks that NDS could not create when it created the external reference.
When NDS removes an external reference, the server holding the external reference requests that the server holding the real entry delete the backlink. NDS uses the RemoveBackLink process to delete a backlink. The server holding the external reference sends the server holding the real entry a RemoveBackLink request. The server holding the real entry deletes the backlink and returns a RemoveBackLink code indicating success or failure.
Referring to
FIGS. 2
a
and
2
b,
a directory tree
200
includes a server S
1
that stores a master replica of a partition a and a master replica of a partition b.a and a server S
2
that stores a read/write (“R/W”) replica of partition a and a master replica of a partition c.a. Partitions a, b.a, and c.a are respectively represented in
FIG. 2
a
by partition objects a, b, and c. A printer object P
1
.c.a, represented in
FIG. 2
a
by an object P
1
, in partition c.a is servicing a queue object Q
1
.b.a, represented in
FIG. 2
a
by an object Q
1
, located in partition b.a. In this example, the queue object Q
1
.b.a will appear as a value of the queue attribute of the printer object P
1
.c.a. Because the server S
2
does not have a replica of b.a., server S
2
must have an external reference object of queue object Q
1
.b.a. The only reason the queue objec
Campbell Renea Berry
Higley DeeAnne Barker
Ireland Robert Carey
Olds Dale Robert
Haynes and Boone LLP
Mizrahi Diane D.
Mofiz Apu M
Novell Inc.
LandOfFree
Distributed reference links for a distributed directory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed reference links for a distributed directory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed reference links for a distributed directory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3161334