Figure 1: LDAP as a front end to X.500.
Timothy A Howes <tim;@umich.edu>
This paper describes a global directory service
framework and a local directory service that fit
within the approach outlined in RFC 1588. It uses
proven Internet technology (e.g., the Domain Name
System and Uniform Resource Locators) and
successful or promising pieces of other services
(e.g., X.500 and WHOIS++), learning from and
correcting the mistakes of its predecessors: X.500,
LDAP, WHOIS++, and SOLO. The service has been
designed with ease of implementation and depoyment
in mind, and with the goal of co-opting the installed
base. Our implementation of the system is also
described.
8 Implementation and Deployment
In Fall of 1993, the Internet Engineering Task Force (IETF) adopted a more pragmatic approach toward developing an Internet directory service, one that takes into account the diverse installed base and allows development of alternative global systems as well. The goal of this egalitarian approach, documented in RFC 1588, remains to arrive at a global uniform service, but to do so in a way that does not favor one candidate service over another, allowing a natural process of selection to take place. This paper describes a global directory service framework and a local directory service that fit within the approach outlined in RFC 1588. It uses proven Internet technology (e.g., the Domain Name System and Uniform Resource Locators) and successful or promising pieces of other services (e.g., X.500 and WHOIS++), learning from and correcting the mistakes of its predecessors: X.500, LDAP, WHOIS++, and SOLO.
The framework is general enough to support sites running virtually any local protocol they choose, while encouraging them to migrate to the more functional service we define. This optional migration allows sites to participate more fully in the global service. The local service we define is based on a stand-alone version of the Lightweight Directory Access Protocol, formerly used exclusively as a front-end to the X.500 directory. This choice makes our service highly compatible with X.500, but free of its shortcomings. We believe ease of implementation and deployment are qualities that will ultimately select the directory service winner on the Internet, and these goals have driven the design of our service.
Each section that follows discusses a particular aspect of the service, starting with the namespace. Next we give an overview of navigation, or how one gets from a name to a server holding data on that name. This section forms the basis for how our system solves the directory service "read" problem. The co-opting of the installed base is tackled in Section 4. Our solution to the directory service "search" problem is presented in Section 5, providing the basis for information retrieval when the name of an object in the directory is not known. Our local directory service is described in Section 6, and we finish with some examples, a discussion of our implementation of the system, and prospects for deployment throughout the Internet.
A hierarchy is not the only option. Services such as WHOIS++ and SOLO favor a more loosely organized "mesh" structure. In this model, information is referred to by its content. An entry in the mesh may have as many "names" as it has collections of attributes that uniquely identify it. New sites come online by announcing their presence to one or more "neighbors," or to a more formal registration authority. In this way, the mesh may grow from the bottom up, or "out," as the case may be. The barriers to getting connected are low, but without careful administration this method can lead to the same scaling problems and tangled information structure that characterize the World Wide Web. In a directory system meant for organizing and finding information, this is a bad thing.
User acceptance is another barrier to deployment that any namespace faces. Internet users have to deal with many different namespaces: an IP address namespace, a host namespace, and several electronic mail and information resource namespaces, to name a few. To succeed, another namespace must bring with it enough benefit to out-weigh the inconvenience that it poses to users. Large and unwieldy names, such as those proposed by X.500, fight an uphill battle for acceptance. Names that users cannot easily grasp or put on a business card, such as those proposed by WHOIS++, are also at a disadvantage. Names that are hard to remember, or have no obvious relationship to the objects they name are also bad.
The Internet relies heavily on the DNS, which is scalable, familiar to users and administrators, and has well-established registration procedures. Just as RFC 822 piggy-backs on the DNS to define an e-mail namespace for the Internet, we build on the DNS to define an Internet directory service namespace. Our namespace has the same local@domain syntax as an Internet e-mail address, and similar semantics. The domain part identifies the server holding the information, while the local part has meaning only to the local directory server.
Aside from having an aesthetic appeal (our directory names in this scheme are tim@umich.edu and mcs@umich.edu, for example), this scheme has the advantage of being familiar to both users and administrators. Having gone without a true directory service for so long, Internet users have gotten used to dealing directly with e-mail addresses, to which our directory names bear a striking resemblance. The names are sufficiently compact and efficient to be carried easily in protocol, while retaining enough mnemonic value to please users. Furthermore, because we piggy-back on the existing DNS infrastructure, the registration problem is neatly averted. A site must register with the DNS to get connected to the Internet in the first place, and by doing so it simultaneously (and unwittingly) registers in our directory service namespace as well.
When it comes to returning information associated with a name, few systems compare in scale or efficiency to the Internet's Domain Name System. The DNS has a variety of uses, from host name to address translation, to the reverse mapping, to e-mail service location for a domain name. It is to this latter function that we make a useful directory service analogy. Among the records associated with a name in the DNS can be a mail exchange, or MX, record. The purpose of this record is to provide a mapping from a domain name to the name of one or more hosts performing mail service for that domain. Since our goal is to provide a mapping from a domain name to a host performing directory service for a domain, the analogy is direct.
We define a directory exchange, or DX, record. The DX record is functionally similar to an MX record, except that it points to a host performing directory service for a domain instead of e-mail service. As with an MX record, multiple hosts can be specified, with different preferences. In fact, as the next section describes, a DX record actually specifies a protocol for retrieving directory information in addition to a host name.
A directory client begins with a name of the form localpart@domain. It looks up domain in the DNS, asking for DX or address records. If no DX records are found, it assumes an LDAP service running on the standard port at the given address. If one or more DX records are found, the client chooses among them, based on priority and protocol. It contacts the corresponding server using the appropriate protocol and retrieves the information.
Using DX records has several advantages over other schemes. First the technology on which they are based is familiar and scalable, proven by years of use in the Internet community. Second, the concepts are well-understood by system administrators who already interact with the DNS to use and provide other Internet services. Finally, all that is necessary to "get connected" to our directory service, using any local service a site wants, is to add a simple record to the DNS, and if a site chooses to run our version of stand-alone LDAP as their local service, even that is not necessary. (See the implementation and deployment section for a discussion of our implementation of DX records using TXT records, which have the advantage of already existing, thus avoiding changes to DNS software.)
The models we have described for namespace and navigation could be easily applied to a number of directory services. Our goal is to broaden them to apply to all services at once. To do this, we extend the DX record concept introduced above. We allow a DX record to be multi-valued and expand its content to alow a partial Uniform Resource Locator, rather than a simple hostname. A client looking up DX records for a directory name is returned one or more partial URLs, pointing to the directory service(s) for the domain. Intelligent clients can then choose the access method they prefer. This method also supports redundant replicated servers.
The URLs returned are "partial"; they contain only enough information to identify the desired server and the protocol used for accessing it. The rest of the URL, enabling the client to retrieve the information it desires, is contained in the localpart of the directory name. How the full URL is constructed and used depends on each protocol. For example, if the local directory service is a CSO nameserver, the localpart of the name might be the desired entry's unique identifier. If the local directory service is a WHOIS or WHOIS++ server, the localpart of the name might be the record's handle. We do not define the exact mappings here, but the approach is clear.
The advantages of this scheme are several. By using URLs, we employ technology familiar to administrators. We also make it relatively easy to add new protocols to the mix - all that's needed is the definition of a new URL format. Furthermore, in addition to incorporating existing directory services, URLs form a basis for information retrieval that allows the potential to make our service easily available via a wide variety of clients with which users are familiar and use every day.
Efficient resource consumption is the primary constraint during the search process. For searches with a naturally restricted scope, this is a minor problem. If only one or a few servers are involved, it is not unreasonable to contact them all with the search request. For wider-area searches, this approach is not feasible. For example, keeping in mind the namespace model described above, suppose a user wants to search for a friend named "Babs Jensen." The problem is that our user met Babs while on spring break and knows only that she is in college "somewhere up north." A simple-minded approach would be to extend the search to every directory server in the edu domain. (At last count, this domain contained over 1,000,000 hosts.) Contacting them all would leave our user waiting quite a while for the results of his query. If more than a few users produced such queries, the network and server resources consumed would soon bring the Internet itself to its knees. Clearly, a better method of handling such searches is needed.
In our system, a client performing the search described above would begin by looking up DX records for the name edu in the usual way (or perhaps through cached knowledge of the "root" information, as is currently done in the DNS). Depending on its preferred choice of protocol, the client picks one of the returned URLs and connects to the indicated service to perform the search. Our only requirement on this service is that it return DX referrals to the client, indicating likely places for the client to continue the search.
A DX referral is similar to the partial URL defined in Section 3. It provides a level of indirection to the information it references, allowing control over the protocol(s) used to access the information to remain in the hands of the site providing the service. For example, the search for Babs in the edu domain might return two DX referrals, dx://umich.edu and dx://cornell.edu. The actual protocols and directories that contain the information are discovered by the client in the nomal way: by looking up DX records for the names umich.edu and cornell.edu, respectively. If a site does not need the indirection provided by a DX referral, it may elect to return a protocol-specific partial URL directly.
The efficiency with which searches are conducted depends on the high-level servers initially contacted for the search returning DX referrals only to those directories which, when searched, will return positive results to the query. Return too few referrals and some information vital to the user may be lost. Return too many, and we revert to the "contact every server" approach.
Since we allow many high-level protocols to provide the searching service in our scheme, it is not really for us to say how they might make this happen. But in our implementation of LDAP, described more fully in the next section, we make use of centroid indexing for this purpose. Originally adapted for use in WHOIS++ as a means of both searching and navigating through the mesh of servers, we adopt the technique as a search-space-pruning device in LDAP.
Our solution to the searching problem has several advantages. First, it allows any protocol that can support the namespace we define to participate as wide-area-search servers. In contrast, other proposals that mandate a particular protocol for searching fix the query language, information model, etc. Our scheme is more flexible. Second, it is based on DX referrals, which introduce a useful level of indirection, again leading to more flexibility and control by local sites. Third, while we propose the use of centroids as a method of pruning the search space, particularly in our implementation of LDAP, our scheme is not tied to centroid technology. Should another distributed indexing mechanism become available, it can be incorporated into our scheme easily. The details of search space pruning are hidden from the user, who sees only a familiar and consistent view of the namespace.
Figure 1: LDAP as a front end to X.500.
The LDAP server chases referrals, merges resuts, etc. from mulltiple X.500 servers. LDAP retains the basic X.500 model, supporting most X.500 operations, and the same namespace and information model. The protocol itself runs directly over TCP, leaving out many of the more esoteric and less often used X.500 features, with most data items encoded in simple string formats. The simplified feature set, transport, and encoding, allow LDAP clients to be more easily developed and run using far fewer resources than their full X.500 counterparts.
We make two key extensions to LDAP, enabling it to function as a stand-alone directory service and to participate fully in the framework outlined above, both as a local service and as a wide-area search service. Both extensions are designed to be transparent to existing LDAP clients, making the new version compatible with the existing one. Old clients will not know enough to take advantage of the new features we introduce, but they will not break. We took a lesson from the developers of MIME here, who transparently enabled new features in RFC 822 e-mail, simply by defining new formats for message bodies that fit within the existing protocol. Our extensions are similar in philosophy.
First, we extend the LDAP Distinguished Name (DN) format to include the Internet-style names described earlier. Since these names are carried in LDAP as simple strings, there are no protocol changes necessary to support this. Second, LDAP allows the server to send back an arbitrary text message to the client as part of a search result. We impose some structure on this message, defining a format for the return of referrals within it. Clients that donÕt understand this format will not be able to follow the referrals, but they will not be bothered by their presence either. The resulting interaction model is shown in Figure 2.
Figure 2: Stand-alone LDAP interaction. A client makes a request in transaction 1 and follows the returned referral in 2.
In this configuration, data is held by the LDAP servers themselves, along with referrals pointing to different LDAP (or other protocol) servers.
Figure 3: In transaction 1, the client retrieves DX records for the edu domain. In transaction 2, the client retrieves DX referrals to servers it should contact.
A client's first step is to look up edu in the DNS, asking for DX records. It may be returned several records, but let's assume it chooses the one providing an LDAP service for the edu domain, ldap://some.host. The client contacts the LDAP port on some.host and sends it an LDAP subtree search of the edu domain for an entry with an objectClass of person, a locality of Michigan, and a name of Babs Jensen. The LDAP server consults the centroid index it has collected and finds that there are two possible services where the client should continue the search, one at the University of Michigan, and another at Michigan State University. The corresponding DX referrals, which it returns to the client, are dx://umich.edu and dx://msu.edu. The client may present these referrals to the user, or it may follow them automatically. Choosing the latter, it looks up umich.edu and msu.edu in the DNS, asking for DX records. For each set of DX records returned, the client chooses one corresponding to a protocol it understands and follows it. In our example, the chosen records might be ldap://umich.edu and cso://msu.edu. The client contacts each directory via the appropriate protocol and continues its search, retrieving the results it desires. The interaction is shown in Figures 1 and 2.
Figure 4: In transaction 3, the client retrieves DX records for each DX referral. In transactions 4 and 5, the client contacts the indicated servers via CSO and LDAP respectively, retrieving results.
Our second example is of an e-mail user agent processing a piece of mail addressed to the directory name babs@umich.edu. The goal is to find the e-mail address to which to forward the message, and illustrates the read capability of the system. This interaction is shown in Figure 5.
Figure 5: In transaction 1, the client retrieves DX records for umich.edu. In transaction 2, the client retrieves the desired information.
The client starts by looking up umich.edu in the DNS, asking for DX records. Among the DX records returned to it is one pointing to an LDAP service for the domain, ldap://umich.edu. The client contacts the LDAP server on the umich.edu host, giving it the name babs@umich.edu and asking for the e-mail address associated with the entry.
Slapd has been designed with high performance, ease of configuration and use, and flexibility in mind. Implemented on a variety of UNIX systems, it is based on a single highly-threaded process. A new thread is started for each operation, maximizing concurrency. We developed our own threads "glue" library, based on draft 4 of the Posix standard. The library provides a mapping onto a number of underlying threads packages (we currently support three and have plans to add more). Support is provided for both preemptive and non-preemptive threads.
Slapd supports multiple database backends, allowing great flexibility when adapting to a site's environment. Communication with a backend is through a well-defined API, making it easy to add new or customized databases. We have implemented three backends so far: an /etc/passwd backend; a "shell" backend; and a high-performance, fully-indexed hash or btree-based backend called ldbm. The relationship between slapd and its backends is shown in Figure 6. Multiple instances of each backend can be enabled by editing a simple tailor file. This allows a single slapd process to serve several portions of the namespace.
Figure 6: slapd architecture supporting multiple simultaneous database backends through a common API.
The shell backend allows the execution of arbitrary administrator-defined commands in response to queries. Slapd executes the command, feeding it a text representation of the request on standard input and reading a text representation of the results from standard output. Although not appropriate for high-performance environments, this method allows easy integration with virtually any system (e.g., via shell scripts).
The ldbm backend is based on technology we originally developed for use in our X.500 DSA. The underlying indexes are implemented by one of a number of dbm or btree packages. As with the threads support, we have developed a library of "glue" routines allowing the use of several different packages and easy addition of more (we support three so far). The ldbm backend can support efficient processing of all types of LDAP searches, including substring, approximate, and range queries. It is targeted at medium to large-scale databases of up to a few hundred thousand entries. It is not meant to handle millions of entries but should be sufficient for the needs of most sites.
We are in the process of adding replication support to slapd. Our approach is to have slapd log changes to a file which is then read by a separate process. The stand-alone LDAP update replication daemon (slurpd) is responsible for distributing the changes to the appropriate replicas (slapd records where each change should go in the replication log file). Changes are made to a replica using the normal LDAP protocol; no special replication protocol is required. Slurpd authenticates itself to each replica as a special entity allowed to make changes. This leads to a master and slave replication scheme. The interaction is depicted in Figure 7.
Figure 7: master and slave slapd replication interaction with slurpd.
The implementation is freely available using the URL ftp://d.rs.itd.umich.edu/ldap/ldap.tar.Z. We invite anyone interested to retrieve the software and participate on either a local or global level with our pilot. Sites wanting to participate strictly at a local level can just bring up one or more stand-alone LDAP daemons and point their local clients at them. If the site wants to be visible to the outside world, it need only add a simple TXT/DX record to its local DNS server. Finally, if the site wants to participate in the global search service, it needs to run centroid generation and updating software. The software will automatically find and connect to the correct indexing server. If a site wants to participate with a directory service protocol other than LDAP, it can do so by adding a TXT/DX record to the DNS pointing to that service.
Deployment on a wider scale will begin as soon as we have gained more experience with the system, worked out the remaining bugs, and improved the documentation.
Tim Howes is a Senior Systems Research Programmer for the University of Michigan's Information Technology Division. He received a B.S.E. in Aerospace Engineering, a M.S.E. in Computer Engineering from U-M, and is completing a Ph.D. in Computer Science. He is currently project director and principal investigator for the NSF-sponsored WINX project, and in charge of campus-wide directory service development and deployment at U-M. He is the primary architect and implementor of the U-M LDAP system, the GDA X.500 DSA, and a major developer of the QUIPU X.500 implementation. He is author or co-author of several RFCs including RFC 1777 and RFC 1778 defining the LDAP protocol. He is chair of the IETF Access, Searching, and Indexing of Directories working group, and an active member of the ACM and IEEE.
Mark Smith is a Project Leader and Systems Research Programmer for the University of Michigan's Information Technology Division, specializing in Directory Service, Unix, Macintosh, and AppleTalk and TCP/IP network programming. He received his B.S.E. in Computer Engineering from U-M and is completing an M.S.E. in Computer Engineering. He is currently leading X.500 Yellow Pages development and deployment at U-M. He is the architect and implementor of the popular maX.500 Directory User Agent, and is a major developer of the U-M LDAP implementation, and has made important contributions to several other Internet software packages for Unix and Macintosh. He is co-author of RFC 1249 describing the DIXIE protocol and an active member of the IETF.