- Chapter 3: Storing Directory Information
- Partitioning the Directory
- Directory Replication
This chapter is from the book
This chapter is from the book
This chapter is from the book
Partitioning the Directory
The DIB can be subdivided into smaller sets of data called partitions (described as a naming context in X.500). A partition is a physical subdivision of the directory database stored on and managed by a specific directory server.
A partition is implemented at the container level and consists of the container object and its associated subtree. The partition root is the container object at the root of the directory partition and usually names the partition. The subtree that begins at the partition root is a single partition, unless another container object within it is designated as the root of a new partition.
Note that different directory service implementations have different rules for how and where partitions can be established. Depending on the specific directory service, partitioning may be constrained or limited in fundamental ways.
To help you see how all these things fit together, take a look at Figure 3.1. In this example, the Mythical organization has a directory with two partitions. The first partition is named by its partition root o=mythical and managed by the Phoenix server. The second partition is ou=US and is managed by Unicorn. Phoenix and Unicorn each have information indicating the location of the other partition.
){kind=link}
Even when the DIB is partitioned on many servers throughout an enterprise, the directory is still represented as a unified tree when viewed by users of directory information. This means that although the DIB is physically stored on separate directory servers, the information contained in it must be combined somehow before presenting it to the user. The directory is responsible for keeping track of where all the data is actually stored and assembling it into a single tree for presentation. Therefore, even though the DIB itself may be in many pieces spread around multiple locations, the user's view of the directory information is seamless.
Example Companies: Mythical and Netmages
This section uses two example companies: a multinational firm called the Mythical organization; and a small, single location firm called Netmages. These examples highlight directory service factors from the perspective of both small and centralized networks, as well as large and distributed networks.
Figure 3.1 A directory tree can be divided into partitions, each of which is a contiguous subtree of the DIT.
Managing Partitions
From an administrative perspective, partitions are created for a number of reasons. Use of partitions:
Provide a key element in scalability by allowing the DIB to be subdivided into many parts.
Can be used to limit replication traffic across WAN links or to any single server.
Can divide the server load (from queries) to improve directory performance.
Some partitioning decisions—such as subdividing the DIB when the directory tree spans WAN links—are relatively clear, but others take considerably more thought. If you need to implement additional partitions for scalability, for example, you probably have several possible partition boundaries from which to select. Choosing the best partition design should involve identifying critical operational contingencies of both the directory and the entities that use it.
When deciding where you want to place partition boundaries, you should take some less-obvious aspects into consideration, such as the following:
Partition constraints
Directory operations across partitions
The next sections discuss partition operations and constraints, and the related implications for directory design.
Partition Constraints
You should carefully evaluate the capabilities of the directory product you are deploying, and the sort of partition design intended by the vendor, early and often in the directory design process. The partitioning approaches of various vendors differ significantly. Don't assume that partitioning will always work a particular way; it just may not. Active Directory has a rather nontraditional approach to partitioning and replication, for example, which Chapter 10, "Active Directory," explores.
A few of the clearer contingencies about how you partition your directory are based on the capabilities of a single partition or directory server. You will want to check your selected directory software for limitations, such as:
Number of objects per partition
Size of partition file(s)
Numbers of references to subordinate (child) partitions
Restrictions on placement of partitions
Number of replicas per server
Maximum number of replicas per partition
Operations Across Partitions
You should also consider the effect of directory operations that span partitions as crossing partition boundaries slows the search process, even if all the servers holding the partitions are on the same LAN. For every query that is not resolved using a local partition, referrals (redirecting the query to another server) are generated and additional servers must process the query, increasing search time.
The cross-partition delay is usually not significant enough to be problematic for users and applications on LANs. If the servers are separated by WAN links, however, the query has to span these links, which are the slowest connections on a network. What should be a fast request can be delayed or even aborted as the request passes through slow links while attempting to complete the request.
In addition to the obvious example of user queries about objects that reside in a remote partition, directory operations will need to access multiple partitions at other times. Applications, and the directory itself, may perform operations that require access to the entire directory tree. If the directory is partitioned across WAN links, this process may take significant time and bandwidth. You should assess the operations of your directory-enabled applications to be sure that, if they frequently traverse the entire tree, adequate replicas are available to support their operations without excessive network traffic.
The following section, "Partitioning Examples," provides several examples of partitioning for single-location and distributed directory implementations.
Consider Partitioning During Tree Design
When you are designing your directory tree, you should keep partitioning in mind. Because a partition can be implemented only at the container object level, you must design your directory tree to support your partitioning needs. Well, okay... you don't have to design your tree to support your partitioning requirements—you can always redesign your tree to support the partitioning needs of your directory implementation (an undesirable and expensive process). In any case, it will be helpful if you remember that the design of your tree determines where the possible boundaries of partitions fall.
Partitioning Examples
To help clarify how partitioning is used, consider the following examples of how and why a directory is partitioned. To begin with, consider the substantial differences between how partitioning is used with small and large directories.
Small directories commonly start with a single partition because when the number of directory objects and replicas is small, the best performance and least administration overhead can be achieved with a single partition and minimal number of replicas. As demonstrated in the following examples, when the directory grows to include more users and resources (and perhaps additional physical sites), the DIB can be partitioned to accommodate the changes.
Large directories must use partitions for scalability. If the directory usage is restricted to a single physical location, partitions may be devised based solely on allowable number of objects per partition or other criteria. In geographically distributed directory installations, the partitions at the top of the directory tree usually reflect WAN topology. If needed, additional partitions may be created within a geographic area for scalability, availability, or administrative reasons.
The following examples discuss some of the factors involved in partitioning decisions.
Limiting Objects in a Partition
A directory might support a million, tens of millions, or more objects in a single directory tree; however, the number of objects that can be stored in an individual partition is often much smaller than that. Accordingly, a common reason for partitioning the DIB is to limit the number of objects per partition.
Even when a directory starts small, it is not necessarily going to stay that way. What starts out as a fairly small directory tree, with few enough objects that a single partition works fine, can outgrow that design and require additional partitions. As the directory grows, existing partitions may need to be adjusted to provide the needed scalability. The focus turns next to what happens when this occurs.
Assume, for example, that the Netmages directory has been operating with a single partition so far. Recently, the network has grown considerably, to the point that the limit on objects per partition is being approached. When this happens, a new partition must be created as a means of subdividing the DIB. Also assume that you know that the corp department in particular has been undergoing rapid growth. Because that department already has its own OU in the directory tree, adding another partition, rooted at ou=corp, should be simple. (Note the words should be simple; not all directory software makes it quite that easy, but it should.)
The directory tree in Figure 3.2 is divided into two partitions, one that starts at the root of the tree and another that begins with the corp OU. Each of these partitions is named by the container object at the partition root; therefore, they are o=netmages and ou=corp.
){kind=link}
As the directory continues to grow, the DIB can be broken into more partitions to ensure that partition limits are not exceeded and directory performance does not degrade.
Controlling Replication Traffic
Another reason for partitioning is to control replication traffic (the data sent across the network to replicate directory changes) by restricting the distribution of directory information to locations where that data is needed. This is usually done when the directory spans multiple locations, and thus spans WAN links. It may also be desirable (or necessary) on a LAN when the directory is updated frequently.
After you have determined that replication traffic needs to be controlled, more questions arise:
Where is the replication traffic being generated?
Who needs access to the data being updated?
If a specific department generates a considerable amount of replication traffic for information that is relevant only to that department, you may want to implement a partition to reduce network traffic.
Figure 3.2 As the directory grows, partitions can be added to provide scalability.
For example, the services department of the Netmages company has decided to use a directory-enabled version of customer tracking and project management software. Accordingly, each Netmages customer has an entry in the directory that stores customer data, information related to ongoing projects, certificates used for secure communication between the customer and the development team, and so on. This is great for the people who provide services because much of their customer and project management has been moved to the directory.
As there is now a considerable amount of customer information stored in the directory, however, and because that information is updated frequently, there are performance implications for the network. In the case of the customer information stored in the services ou, few people outside of that division will be accessing the customer information; therefore, it doesn't make sense to replicate that information to the rest of the company. Accordingly, a partition should be created to segregate replication traffic.
As displayed in Figure 3.3, the tree originally shown in Figure 3.2 has now been divided into three partitions: the two that existed already (starting at the root of the tree and the corp ou) and the newly created partition rooted at ou=services.
){kind=link}
Figure 3.3 This directory tree is now divided into three partitions to segregate replication traffic generated within ou=services.
Implementation of this partition will improve the performance of the directory and reduce the network bandwidth used. The directory servers holding replicas of the netmages partition will not be burdened with unnecessary replication traffic for information seldom accessed by their clients. Because there will be substantially fewer updates without the information used by the services department, the server availability for client requests will also be increased. In addition, the set of data held in the netmages partition is now much smaller, so searches will be faster.
The next example looks at what is perhaps the most obvious reason for partitioning—WAN links.
Partitioning for a WAN
One of the most often repeated guidelines concerning partition design is "Don't span the WAN" with a partition. (In other words, don't create partitions that cross your WAN links.) This is generally a useful guideline because most administrators want to control replication traffic across slow WAN links. Because most WAN links are substantially slower than the rest of the network, the potential for replication traffic to bottleneck exists. It is probably true that, as "slow links" get faster, and vendors get more creative about replication methods, this factor will diminish—but not yet.
In many large directory installations, partitions in the upper levels of the directory reflect the WAN topology. In this case, partitions in the lower levels of the directory might reflect company structure, such as departments. This is a common method of dividing a directory when the contents span different geographic regions. Partitions are kept physically proximate to the resources represented within them and the users who will be accessing those resources to minimize WAN traffic in service fulfillment.
To explore how directory partitioning works on a network consisting of LANs connected via WAN links, consider the example of a different company. This example uses the Mythical organization, a large multinational firm with offices on several continents.
As shown in Figure 3.4, the Mythical organization has added more sites and decided to further partition the directory tree along the same lines as the LAN/WAN borders. This will restrict the bulk of the directory traffic for each partition to a single physical site, minimizing WAN traffic for both replication and lookups.
){kind=link}
Figure 3.4 The Mythical organization has partitioned its directory along geographic boundaries.
As you can tell, a large, geographically distributed company can have an elaborate partitioning scheme for its directory. In addition to the first level of partitions, more partitions could be added within a specific location if needed for scalability or other reasons.
If you choose a partitioning scheme that divides the DIB across WAN boundaries, as described in the preceding scenario, you may want to consider a couple of factors:
If a WAN link goes down, portions of the DIB may become unavailable. To provide for this, you may want to place a replica of any critical partition in a secondary location such as a dedicated replica server in the IT department.
The type of replica placed at each location may limit the operations that can be performed locally. If people frequently modify directory information from a particular location, you may want to place a writeable replica of the relevant partition(s) there to minimize referral traffic to a master replica. Of course, this entails additional traffic for updates, but allows for faster query responses.
Invalid Partitioning
Now that you have reviewed what can be done with partitions, take a look for just a moment at what can't be done with them. When creating directory partitions, you should remember that partitions have some operational limitations:
Each object in the directory must belong to exactly one partition.
Partition boundaries cannot overlap.
Each partition must contain a complete, connected subtree.
Two peer containers cannot be in the same partition without their parent.
The directory tree illustrated in Figure 3.5 does not have a valid partitioning scheme for several reasons. To begin with, the partition rooted at o=netmages and the partition rooted at ou=services have overlapping boundaries. As a result, the o=netmages partition contains the object ou=services, which also serves as a partition root for another partition (which can't work).
){kind=link}
Does Partitioning Impact Directory Operations?
Optimally, users of the directory should be blissfully unaware of all this partition creation and rearranging. Some directory services require that the DIB be locked during partitioning operations so that no other changes can be written to it. This may unavoidably interrupt some directory functionality (most things that require write access to the DIB) briefly, but it won't affect most users because most of the directory use by nonadministrators only requires read access.
In addition, ou=admin and ou=mktg are peer containers and, therefore, cannot be in the same partition without their common parent, ou=corp. (It's not even possible to name this partition because it functionally either has two partition roots, or none at all!)
Figure 3.5 The examples shown here display two partition designs that cannot work in directory partitioning: overlapping partitions and peer containers without their parent.
Now that you have learned how the DIB is broken into smaller pieces and spread around the network, take another look at how it's linked back together. The next section discusses how objects are located when the directory is partitioned.
But I Can't Do That, Can I?
Most directory software is intelligent enough that it won't actually let you create invalid partitions. However, you should determine the functional limitations of the partitioning allowed in your selected directory service, and use this in planning your directory implementation.
Name Resolution Across Partitions
When the directory database has been divided into partitions, two problems present themselves:
Multiple partitions must be logically linked to form the complete directory tree—a unified logical representation of the contents of all partitions in the directory.
Servers holding different partitions must have a means of locating each other to communicate.
To provide the linkage necessary for both of these functions, directory servers maintain internal references to partitions whose data is not stored locally. These internal pointers to other DIB subdivisions are named differently in different models (for example, knowledge references in X.500, and name server records in DNS), but all distributed directories have them.
When a client request exceeds the scope of the current partition (that is, the object sought is not contained in that partition), these references are used to direct the query to a directory server with the appropriate partition to fulfill the request. After the appropriate partition is found, the object is located, the reply is returned to the client and the desired operation is completed.
At a minimum, a server maintains references to any partitions immediately above and below the partitions it holds. Additional references may be maintained for other reasons, such as directing all referral traffic to a specific server or speeding location of frequently accessed partitions by specifically maintaining references to them. Even if every directory server cannot directly locate every other directory server, the assumption is that by following a series of references, any entry in the directory can eventually be located. The process of following a series of references from partition to partition is frequently called tree-walking.
User Authentication Across Partitions
When directory queries span partitions, some method must be chosen to handle user authentication to the directory server holding other partitions. In general, this is handled one of two ways:
The referring directory server passes the user's credentials to the secondary server.
The directory client resubmits the user's credentials directly to the second server.
If you are going to be dealing with directory operations in a nonsecure environment, you should see how your directory service product handles authentication across partitions. If unencrypted information is passed between directory servers, security information may be inadvertently exposed.
Knowledge Information
Although the types of knowledge information supported are implementation specific, knowledge references fall into some general categories, namely the following:
Superior—The partition immediately above the current one, which is used to walk up the tree.
Subordinate—The partition directly below the current one, which is used to walk down the tree.
Root—The partition at the root of the Directory Information Tree (DIT), which is used to locate the tree root.
Other—This kind of knowledge reference can be anything other than the preceding ones in this list, which might be used to speed lookups to frequently accessed partitions, control directory referral traffic, support replication, and so on.
Figure 3.6 shows the knowledge information used to link the servers holding the partitions in the Netmages tree. In this case, the directory servers maintain only the name of the immediately superior and subordinate partitions. By consulting a series of these references in sequence, any entry in the Netmages tree can be located and accessed.
){kind=link}
How the directory obtains the information about servers holding other partitions varies considerably between directory service implementations. Some directory services automate the process entirely and build the appropriate references whenever partitions are created; however, others require manual configuration of the information used in name resolution. Manual configuration of knowledge references can create a substantial administrative load, and present operational issues when directory servers are added or replaced.
A knowledge reference commonly contains the following data:
Type of reference—Superior, subordinate, and so on
Identification—Description of the partition subtree
Server—Name and network address of the server holding the specified partition
A single directory server may store references to multiple replicas of the same partition, each of which is stored on a different server. When servers store multiple references to a single partition, additional information may be added to the knowledge reference to support differentiation between types of partition replicas (such as master or shadow).
Figure 3.6 The directory stores knowledge information, which is used to connect separate partitions into a single DIT.
How Knowledge References Are Used
Now that you know that the directory contains information used to link the various partitions into a single tree, you might be wondering how it actually works. Consider how the name resolution process is handled during a typical client query. Well, almost typical, because the example shows a generic representation of the name resolution process. An actual directory service operation would likely use a different specific path to resolve the name and provide the results back to the client.
In this example, Natashia (who works in marketing) needs to get the phone number of Kara Stone, a customer (information stored in the services partition). Because Natashia is a member of the marketing team, her default directory server is in the corp partition. For Natashia to obtain Kara's phone number, the directory first has to find the object representing Kara. Figure 3.7 shows the name resolution process across partitions.
){kind=link}
Figure 3.7 The name resolution process across partitions.
The following list explains what is going on during the name resolution process shown in Figure 3.7 in a bit more detail:
Client submits query to local (default) directory server.
The directory may be queried for Kara Stone's phone number in a variety of methods, depending on the client; via a form that enables you to specify query parameters and filters, or maybe even a natural language query that enables you to just ask the question.
The local directory server determines whether it holds the object, and processes the query accordingly.
Natashia's default directory server, Merlin, examines the name of the referenced object (cn=Kara Stone, ou=net, ou=services, o=netmages) and determines the object is not contained within the local partition.
Merlin then checks its knowledge references to determine which partitions it can locate directly. In this case, it's o=netmages.
The query is then passed to Zifnab, the directory server holding o=netmages.
The next server determines whether it holds the object and processes the query accordingly.
Zifnab examines the name of the referenced object and determines the object is not held locally.
Zifnab next checks its knowledge references and determines that Haplo holds the ou=services partition.
The query is then sent to Haplo.
The directory server does hold the target object; therefore, the query is serviced and the results are returned to the client.
Haplo, the services directory server, examines the object name and determines that it does hold the object in a local partition replica.
The query is then fulfilled and Kara's phone number is returned to Natashia.
Remember, this diagram denotes the logical return of the data (Kara's phone number) to the client (Natashia). The actual methods by which these processes are accomplished vary according to directory service implementation. In X.500, these methods are called chaining, referrals, and multicasting, and they are discussed in more detail in the "X.500 Operations" section of Chapter 4, "X.500: A Model for Directory Services." Now that you understand partitioning in some detail, it's time to switch to a related aspect of distributed storage: replication of directory data between directory servers.