Fundamentally, the DIT is organized into three key tables:

In addition, Windows Server 2003 and newer domain controllers also have a couple of tables that are used for single-instance storage of ACLs (the security descriptor table) and to track object quotas.

Data table

The data table holds the bulk of the data in the Active Directory database. Regardless of its class (e.g., user versus organizational unit), each object in the directory, including the schema, is stored in an individual row in this table. Each attribute defined in the schema comprises a column in the data table, similar to Figure 7-1.

Figure 7-1. The data table

Note

You might think there would be a storage penalty involved in having attribute columns with null values for objects that don’t have that attribute defined in the schema. Fortunately, the database engine Active Directory uses, the Extensible Storage Engine (ESE), is very efficient at storing null values, and thus there isn’t a penalty for storing data this way.

In addition to identifiers you often see in AD, such as SIDs for security principals or the objectGUID of every object in the directory, the data table also uses a special unique identifier for each row in the table. This identifier is known as a distinguished name tag (DNT) and is shown in the first column of Figure 7-1. When a new object is created, the next available DNT is assigned. An object’s DNT is not replicated, so it is quite likely that the same object will have a different DNT on each domain controller. Additionally, DNTs are not reused when an object is deleted.

Note

AD has a maximum of 2,147,483,393 (2³¹ – 255) DNTs in a given database. It is thus feasible that it will no longer be possible to create new objects on a given DC if it has stored this number of objects throughout its lifetime.

In addition to the DNT column, there are a number of references shown in Figure 7-1. The PDNT column stores the parent DNT. This is a pointer to the object’s direct parent row in the database. When you move an object in the directory, its PDNT column entry is updated to match the object’s new parent. The NCDNT column contains the DNT of the naming context head matching the NC in which the object resides. This NCDNT column helps to demonstrate that application partitions are simply logical partitions. You’ll see that the Configuration and Schema naming contexts are stored alongside the Domain naming context in Figure 7-1. The NCDNT entry for objects in those NCs simply points to the relevant object’s DNT.

Figure 7-1 also includes an Ancestors column. The Ancestors column is used during searching and is simply a listing of all of the DNTs between the root of the database and that object. In other words, the Ancestors column represents the hierarchy in the domain. Like the PDNT column, when an object is moved, the Ancestors column is updated to match.

As we mentioned, each attribute’s data is stored as a separate column in the database, as represented by columns A1 through A3 and so forth. One detail to note is that the RDNType column actually stores the DNT of the RDN attribute in the schema for the object. We have removed this layer of abstraction to make it easier to follow the figures.

Link table

The next table—the link table, shown in Figure 7-2—is responsible for storing the data stored in linked attributes. Group membership is one common example of linked attribute data. Links are stored by referencing the DNT of the object with the forward link, the DNT of the object being linked to, and the link ID of the forward link attribute in the schema. In addition, there are a number of other columns not shown here that track replication metadata for linked value replication (LVR), track whether or not a link is deactivated when the Recycle Bin is in use, and store optional link data for attributes that use DN-Binary or DN-String syntaxes.

Figure 7-2. The link table

Note

Technically, the value in the LinkBase column is not a direct pointer to the forward link ID value for the attribute. We have simplified this detail in the figures as it is not relevant to the discussion.

The depiction of the link table in Figure 7-3 makes explaining the contents a bit easier. In this case, we can see that the row shown is tracking a membership in the Domain Admins group. Specifically, user Brian Desmond (DNT 9601) is a member of Domain Admins (DNT 5615). The LinkBase column tells us that the corresponding attribute has a link ID of 2.

Figure 7-3. Link table references to the data table

The most basic query simply asks AD to return all of the objects that have an attribute containing a specific value. For example, if you wanted to return all of the objects in the Accounting Department, you would use this filter: (department=Accounting). Here we’ve specified an attribute name of department, and a value of Accounting. There are a number of other operators you can take advantage of in addition to the equality (=) operator. Commonly used operators are shown in Table 7-1.

One situation where you might want to take advantage of the greater than or equal to operator shown in Table 7-1 is when you’re searching for locked-out accounts. You could construct a filter such as (pwdLastSet>=1) to find objects that have set their passwords at least once. The negation or not operator is useful for finding a set of objects that do not match a given criterion. For example, if you want to find all the objects that are not in the Accounting Department, you could search for (!(department=Accounting)).

In addition to the operators listed in Table 7-1, you can use the * character to ask for any object that has a specific attribute with a value. For example, the filter (description=*) will return all objects in the directory that have a value for the description attribute. Conversely, the filter (!(description=*)) will return any object that does not have a description attribute populated with a value.

You can also use the * character to perform wildcard matches and medial searches. In the case of a wildcard search, you could conduct a search for (givenName=a*) to find all objects whose first name begins with the letter A. If you wanted to find all of the objects whose job title includes the string vice (such as vice president), you could do a search for (title=*vice*). This is called a medial search.

The examples we’ve looked at so far are trivial in nature in that they only search a single attribute for a single value or criterion. Realistically, it is unlikely that you will commonly have such a trivial requirement. Instead, you’ll likely need to combine multiple filters together to form a Boolean AND or Boolean OR expression (or both). Table 7-2 shows the operators you’ll use to accomplish this.

In the previous section, we searched for all of the objects in the Accounting Department. In addition to users, the (department=Accounting) filter will return other types of objects that have this department attribute value, such as contacts and groups. In order to scope the search to only return users in the Accounting Department, we need to specify the object class we want to filter on. To do this, we can use a filter such as (&(objectClass=user)(department=Accounting)). Here, we’ve asked Active Directory for objects of class user and with a department value of Accounting.

We can use the OR operator in the same fashion. If, for example, you want to find objects affiliated with either the Accounting or Marketing Departments, you could conduct a search for (|(department=Accounting)(department=Marketing)).

Finally, both the AND and OR operators can be used if you wanted to limit your search to users who work in either Accounting or Marketing. To do this, you could use a filter like this: (&(objectClass=user)(|(department=Accounting)(department=Marketing)). This may be a little difficult to follow when reading in a linear fashion. One trick for working with complex LDAP filters is to expand them into multiple indented lines, similar to this example:

(&
    (objectClass=user)
    (|
          (department=Accounting)
          (department=Marketing)
    )
)

Here we’ve constructed the same filter, but we’ve made it substantially easier to read by placing each component on a separate line and then indenting the expressions. If you have a complex query and you’re looking for a quick way to arrange it into a more readable format, you can use AdFind. To format the previous query, you would run this command:

adfind -filterbreakdown
 (&(objectClass=user)(|(department=Accounting)(department=Marketing))

Just to give you an example of another complex query that stacks AND and OR operators together along with the NOT operator, consider this next example:

(|
    (&
          (objectClass=user)
          (|
               (department=Sales)
               (department=Marketing)
          )
          (!
               (employeeType=Contractor)
          )
    )
    (&
          (objectClass=contact)
          (|
               (company=Coho Vines)
               (company=Tailspin Toys)
          )
    )
)

In this query, we ask Active Directory to return objects that meet the following criteria:

For reference, written on one line, this query is (|(&(objectClass=user)(|(department=Sales)(department=Marketing))(!(employeeType=Contractor))(&(objectClass=contact)(|(company=Coho Vines)(company=Tailspin Toys)))).

You can specify a search base in an LDAP search in order to tell Active Directory where in the hierarchy to begin searching. There are three types of search scopes: base, one-level, and subtree, as shown in Figure 7-4. By default, you will generally perform subtree searches.

Figure 7-4. Search bases

Subtree searches look for every record under the specified search base. If you specify a one-level search, only records directly under a specific search base (e.g., an organizational unit), including possibly the search base itself, will be returned. Finally, base-level searches return only the object specified.

If you take a minute to refer back to Figure 7-1, you can see how the PDNT (parent DNT) and Ancestors columns make these searches efficient, since Active Directory can filter based on those values.

To specify a search base with AdFind, use the -b parameter. If you wanted to conduct a subtree search (the default) for users in the People OU, you would use this syntax:

adfind -f "(objectClass=user)" -b "OU=People,DC=cohovines,DC=com"

If you wanted to perform a one-level search for only users in the root of the USA OU, you would use syntax similar to the following (all on one line):

adfind -f "(objectClass=user)" -b "OU=USA,OU=People,DC=cohovines,DC=com" 
  -s onelevel

In addition to simply submitting an LDAP query, you may want to modify how the results are returned by the domain controller. You typically perform these modifications through the use of LDAP controls. LDAP controls are session options that are sent as part of the query via the LDAP protocol. The controls in a request are represented in the form of unique object identifier (OID) strings. You can use LDAP controls for common tasks such as sorting a result set on the server, paging the result set, and so forth.

Chances are that you aren’t actually aware that an LDAP control has been loaded when making queries most of the time. For example, AdFind generally includes the LDAP control that enables paged result sets. The following list shows many of the LDAP controls that Active Directory supports with relation to searching, as well as how to use the more common controls with AdFind:

In the case of LDAP controls that we didn’t demonstrate with AdFind in the preceding list, you can use LDP to exercise many controls. In most cases, go to Browse→Search and then click Options. On the Options screen, click Controls, as shown in Figure 7-5. Use the “check in” button to add a control to the request once you configure it on the lefthand side of the screen. Virtual list view (VLV) searches can be conducted by using the dedicated VLV option available under Browse→Virtual List View.

Figure 7-5. LDP Controls dialog

When you need to find users with expired passwords or objects that were created before a certain time, you’ll need to work with the formats that Active Directory stores times in. These formats vary by attribute. The two most common are the 64-bit NT FILETIME format and the more standards-based generalized time syntax.

NT FILETIMEs are integers that count the number of 100-nanosecond intervals since January 1, 1601. Generalized time, on the other hand, simply stores a timestamp in a more legible format: YYMMDDHHMMSS[.fffZ]. This format is year, month, day, hour, minute, and second. The optional three-digit decimal value is fractions of a second. The trailing Z indicates that the time is universal or Zulu time. If the Z is not present, the time is local time.

Encoding values for filters can be accomplished in a couple of ways. In the case of an attribute such as pwdLastSet, which is stored in FILETIME format, you can ask AdFind to perform the conversion for you. To retrieve all of the computers whose passwords were last changed before October 1, 2012, for example, you would use this AdFind command:

adfind -f "(&(objectClass=computer)(pwdLastSet<={{LOCAL:2012/10/01-12:00:00}}))"
 -binenc

If you are using a tool other than AdFind to perform your search, you’ll need to convert the timestamp in advance. You can use Windows PowerShell to perform the conversion: [DateTime]::Parse(“10/01/2012”).ToFileTime(). Once you get the result (in this case, 129935412000000000), construct the filter as follows:

(&(objectClass=computer)(pwdLastSet<=129935412000000000))

Searches for generalized time attributes such as whenCreated and whenChanged should be formatted using the syntax described earlier (YYMMDDHHMMSS.fffZ).

When results are returned, they will be in the same format in which Active Directory expects values to be provided. With AdFind, you can use the -tdcs switch to decode FILETIME fields (such as pwdLastSet) and the -tdcgts switch to decode generalized time fields (such as whenChanged and whenCreated).

Much like converting a value to FILETIME format with PowerShell, you can convert a FILETIME back to readable format by running the following: [DateTime]::FromFileTime(129935412000000000).

The most common example of using a bit mask in a search filter will undoubtedly be to find users that are enabled or disabled. This flag is tracked as the second bit in the userAccountControl attribute. Active Directory supports two special matching rules in the LDAP filter to perform AND and OR operations in a filter.

For example, to find users who are disabled, use this filter:

(&
    (objectCategory=person)
    (objectClass=user)
    (userAccountControl:1.2.840.113556.1.4.803:=2)
)

The opposite, finding users who are enabled, requires the use of the NOT operator:

(&
    (objectCategory=person)
    (objectClass=user)
    (!
          (userAccountControl:1.2.840.113556.1.4.803:=2)
    )
)

If you’re using AdFind, you can simplify these searches quite a bit through the use of the -bit parameter. More specifically, you can execute the following command to find all of the users who are disabled:

 adfind -f
  "(&(objectCategory=person)(objectClass=user)(userAccountControl:AND:=2))" -bit

One last LDAP filter trick that’s worth mentioning is the in-chain matching rule. This modifier allows you to ask Active Directory to walk a group’s membership chain forward or backward, to either determine all the groups a user is a member of, or determine whether or not a user is indirectly a member of a group (e.g., via group nesting).

You can use the in-chain matching rule much like the AND and OR operator matching rules discussed previously. For example, to find out if a user is a member of the group Important People, you would perform a base search of the user on the memberOf attribute. You can do this with AdFind using syntax similar to the following (all on one line):

adfind -s base -b "cn=Brian,OU=People,DC=cohovines,DC=com" `
  -f (memberof:INCHAIN:=(cn=Important People,OU=Groups,DC=cohovines,DC=com)) `
  -bit

You can also do what is effectively the opposite and return all of the groups that user Brian is directly or indirectly a member of, using a similar search:

adfind -f (member:INCHAIN:=(cn=Brian,OU=People,DC=cohovines,DC=com)) -bit

The INCHAIN shortcut in AdFind simply substitutes the actual matching rule OID: 1.2.840.113556.1.4.1941.

At a minimum, efficient searching comes down to knowing whether or not indexes will be used for your filter, as well as the mere practicality of the server being able to rapidly find the results that meet your request. Indexes are the key component of an efficient search. An index is a database-level function that enables the server to quickly find results matching a value. If an index isn’t available, the server must scan the entire database to find rows matching your request.

In Chapter 5, we talked quite a bit about how to index an attribute as well as the different types of indexes available. For simplicity, we’ve reproduced part of one of the tables from Chapter 5 in Table 7-3, which details the different types of indexes you can add to an attribute.

Generally speaking, the most common type of index you’re going to add is the standard index listed first in Table 7-3. If you’re going to be performing medial searches, you should consider adding a tuple index (bit 6). A medial search such as (title=*vice*) finds any object with a job title containing the term vice (such as vice president).

Statistics
=================================
Elapsed Time: 156 (ms)
Returned 1267 entries of 3630 visited - (34.90%)

Used Filter:
 ( & (objectClass=computer) (operatingSystem=*XP*) )

Used Indices:
 idx_objectClass:3798:N

Pages Referenced          : 83092
Pages Read From Disk      : 1
Pages Pre-read From Disk  : 0
Pages Dirtied             : 0
Pages Re-Dirtied          : 21
Log Records Generated     : 0
Log Record Bytes Generated: 0


Analysis
---------------------------------
Hit Rate of 34.90% is Ok

Indices used:

Index Name  : idx_objectClass
Record Count: 3798  (estimate)
Index Type  : Normal Attribute Index


Filter Breakdown:

(
 (&
   (objectClass=computer)
   (operatingSystem=*XP*)
 )
)

One of the urban legends dating back to the early days of Active Directory revolves around why the objectClass attribute wasn’t indexed by default until Windows Server 2008. Originally it was thought that indexing multivalued attributes (such as objectClass) would lead to poor performance. As a result, Windows 2000 shipped with an unindexed objectClass attribute and an additional single-valued attribute called objectCategory that is indexed.

This decision also led to many performance issues related to queries that only used the objectClass attribute, and recommendations abound that queries always use the objectClass and objectCategory attributes in order to ensure the best performance. If you want to be sure that your query will perform well on all versions of Active Directory, we recommend that you use objectClass and objectCategory. If you have indexed objectClass in your directory, or all your domain controllers are running Windows Server 2008 or better, then you can feel free to use objectClass independently without fear of performance repercussions.