2. LDAP Concepts & Overview

If you already understand what LDAP is, what it is good for, Schemas, objectClasses, Attributes, matchingRules, Operational objects and all that jazz - skip this section. But if you are going to do anything except follow HOWTOs you must understand most of this stuff.

LDAP and X.500 are feet deep in terminology. Some terminology is important, some is just fluff. We have created a glossary to jog your memory and we introduce terms either because they are important or because they are frequently used in the literature.

2.1 A Brief History of LDAP
2.2 LDAP Overview
2.3 LDAP vs. RDBMS
2.3.1 LDAP Usage Summary
2.4 LDAP Data (Object) Model

2.4.1 Object Tree Structure
2.4.2 Attributes
2.4.3 Object Classes
2.4.4 Describing the Tree and Adding Data
2.4.5 Navigating the Tree

2.5 LDAP Replication and Referrals

2.5.1 Referrals
2.5.2 Replication

A brief Note about case sensitivity: it's confusing (well we found it confusing) - the only case sensitive things in LDAP (certainly OpenLDAP) are passwords and the contents of certain attributes based on their matchingRule. Period. You will see both in this and other documentation: objectclasses or objectClasses and even ObjectClasses. They all work.

Once upon a time in the dim and distant past (the late 70's - early 80's) the ITU (International Telecommunication Union) started work on the X.400 series of email standards. This email standard required a directory of names (and other information) that could be accessed across networks in a hierarchical fashion not dissimilar to DNS.

This need for a global network based directory led the ITU to develop the X.500 series of standards and specifically X.519, which defined DAP (Directory Access Protocol), the protocol for accessing a networked directory service.

The X.400 and X.500 series of standards came bundled with the whole OSI stack and were big, fat and consumed serious resources. Standard ITU stuff in fact.

Fast forward to the early 90's and the IETF saw the need for access to global directory services without picking up all the protocol (OSI) overheads and started work on a Lightweight Directory Access Protocol (LDAP) which was designed to provide almost as much functionality as the original X.519 standard but using the TCP/IP protocol - while still allowing inter-working with X.500 based directories. X.500 inter-working and mapping is still part of the IETF LDAP series of RFCs.

A number of the more serious 'angst' issues in the LDAP specs, most notably the directory root naming convention, can be traced back to X.500 inter-working and the need for global directories.

LDAP differs from DAP in the following respects:

1. TCP/IP is used in LDAP - DAP uses OSI as the transport/network layers
2. Some reduction in functionality - obscure, duplicate and rarely used features in X.519 were quietly and mercifully dropped.
3. Replacement of some of the ASN.1 (X.519) with a text representation in LDAP (LDAP URLs and search filters). For this point alone the IETF incurs our undying gratitude - regrettably much ASN.1 notation still remains.

Technically, LDAP is just a protocol that defines the method by which directory data is accessed. Necessarily, it also defines and describes how data is represented in the directory service (the Data Model). Finally, it defines how data is loaded into (imported) and saved from (exported) a directory service (using LDIF). LDAP does not define how data is stored or manipulated. Data storage is an 'automagic' process as far as the standard is concerned.

LDAP defines four models which we will now list and discuss - you can then promptly forget them since they bring very little to the understanding of LDAP.

1. Information Model: We tend to use the term Data Model, in our view a more intuitive and understandable term. The Data (or Informational) Model defines how the information or data is represented in an LDAP enabled system - this may, or may NOT, be the way the data is actually stored as explained above.

2. Naming Model: This defines all that 'dc=mydomain,dc=com' stuff that you stumble across in LDAP systems. We stick pretty much to the specifications here because the terms are so widely used.

3. Functional Model: When you read, search, write or modify the LDAP you are using the Functional Model - wow.

4. Security Model: You can control, in a very fine-grained manner, who can do what to what data. This is complex but powerful stuff. We progressively introduce the concepts and have dedicated a specific chapter to it. To begin with - forget security. You can always go back and retro-fit security in LDAP. Where you cannot retro-fit, we reference security implications in the text.

The scope of the LDAP standards is shown in the diagram below. The red stuff is defined in the protocol. What happens inside the black boxes is 'automagic' and outside the scope of the standards.

Each component is briefly described here, in a bit more detail below and in excrutiating detail in subsequent chapters but there are four important points first:

1. LDAP does not define how data is stored, only how it accessed; BUT most LDAP implementations do use a standard database as a back-end and indeed OpenLDAP offers a choice of back-end database support.

2. When you talk to an LDAP server you have no idea where the data comes from: in fact the whole point about the standard is to hide this level of detail. In theory the data may come from one OR MORE local databases or one OR MORE X.500 services. Where and how you access the data is an implementation detail and is only important when you define the configuration of your LDAP server.

3. Keep the two concepts - access to the LDAP service and operation of the LDAP service - very clearly separate in your mind. When you design a directory based system figure out what you want it to do (the schemas and data organization) and forget the implementation. Then figure out as a second phase where the data is and how and where you want to store it - during LDAP configuration.

4. A number of commercial database products provide an LDAP view (an LDAP wrapper or an LDAP abstraction) of relational or other database types.

LDAP is characterised as a 'write-once-read-many-times' service. That is to say, the type of data that would normally be stored in an LDAP service would not be expected to change on every access. To illustrate: LDAP would NOT be suitable for maintaining banking transaction records since, by their nature, they change on every access (transaction). LDAP would, however, be eminently suitable for maintaining details of the bank branches, hours of opening, employees etc..

Read Optimized

It is never clear in the phrase 'write-once-read-many-times' just how many is many?

Where is the line between sensible use of LDAP vs a classic transaction oriented relational database, for example, MySQL, PostGreSQL. If we update every second access, is this a sensible LDAP application or should it be every 1,000 or 1 million times.

The literature is a tad sparse on this topic and tends to stick with 'slam-dunk' LDAP applications like address books which change once in living memory.

There is no simple answer but the following notes may be useful:

1. The performance hit during writes lies in updating the indexes. The more indexes (for faster reading) the less frequently you want to update the directory. Read:write ratios of less than 1,000:1 or higher for heavily read optimised LDAP directories.

2. LDAP Replication generates multiple transactions for every update so you want the lowest practical update load (1,000:1 or higher).

3. If data volumes are large (say > 10,000 ) the time to update even a small number of indexes may be serious so you want to keep updates as low as practical (10,000:1).

4. If data volumes are relatively small (say < 1,000 records), indexes modest and no replication is being used we see no inherent reason why you could not use LDAP in a form which approaches a transaction based system i.e. every 5 - 10 accesses involve a read followed by write cycle (a modify in the LDAP jargon).

5. We suspect that the real answer to this question (and with apologies to the memory of the late, lamented Douglas Noel Adams) is the ratio of reads to writes is 42!

Visibility of Data Organization

The primitives that are used to access LDAP enabled directories use a model of the data that is (may be) abstracted from its physical organization. The primitives assume an object data model without being aware of the actual structure of the data. Indeed the relative simplicity of LDAP comes from this characteristic.

This is in marked contrast to say SQL in which the SQL queries have complete and detailed knowledge of the data structures and organization into tables, joins, etc..

Data Synchronisation

Relational and other databases go to extreme lengths to ensure that data is consistent during write/update cycles using transactions, locking and other methods. It is a vital and necessary requirement.

The data in a master LDAP server and its slaves use a simple asynchronous replication process. This has the effect of leaving the MASTER and SLAVE systems out of data synchronisation during the replication cycle. A query to the MASTER and SLAVE during this (usually short) period of time may yield a different answer. If the world will come to shuddering halt as a consequence of this discepancy, LDAP is not suitable for this application - but if Bob Smith is shown in both the accounting and sales departments for 30 seconds, who cares.

2.3.1 LDAP Usage Summary

So what are LDAP (Directory) advantages and why would any sane human being use a directory?

Before attempting to answer the question let's dismiss the tactical isssue of performance. In general RDBMS systems are still significantly faster than LDAP implementations. This is changing with the development of second generation Directory Servers and while it is likely that RDBMS will always remain faster than LDAP the gap is reducing significantly to the point where, assuming you compare like with like, (a measured network initiated transaction) the differences will become increasingly non-existent - unless you update a highly indexed attribute on every operation - in which case you deserve eveything you get.

So why use LDAP? Here is our list of key characteristics which make the (currently) high level of pain worthwhile.

1. LDAP provides a remote data access method that is standarised. It is possible to replace the LDAP implementation completely without affecting the external interface to the data. RDBMS systesm provide local access standards such as SQL but remote interfaces tend to be proprietry.

2. Because LDAP uses standardized data access methods Clients and Servers may be sourced (or developed) independently.

3. LDAP provides a method whereby data may be moved (delegated) to multiple locations without affecting any external access to that data. By using referral methods LDAP data can be moved to alternate LDAP servers by changing operation parameters only.

4. LDAP systems can be operationally configured to replicate data to one or more applicationwithout adding either code or changing the external access to that data.

The above definition focuses exclusively on the standard nature of data access and does not consider the ratio of reads to writes which as noted above will depend on the number of operational indeces maintained. It does implicity ignore the use of Directories for transaction processing - though even here there are signs that LDAP implementains are looking at such capabilities.

LDAP enabled directories use a data model that assumes or represents the data as a hierarchy of objects. This does not imply that LDAP is an object-oriented database. As pointed out above, LDAP itself is a protocol that allows access to an LDAP enabled service and does not define how the data is stored - but the operational primitives (read, delete, modify) operate on a model (description) of the data that has object-like characteristics (mostly).

2.4.1 Object Tree Structure

Data is represented in an LDAP enabled directory as a hierarchy of objects, each of which is called an entry. The resulting tree structure is called a Data Information Tree (DIT). The top of the tree is commonly called the root (a.k.a base or the suffix).

Each entry in the tree has one parent entry (object) and one or more child entries (objects). Each child entry (object) is a sibling of its parent's other child entries.

Each entry is composed of (is an instance of) one or more objectClasses. Objectclasses contain zero or more attributes. Attributes have names (and sometimes abbreviations or aliases) and typically contain data (at last!).

The characteristics (properties) of objectClasses and their attributes are described by ASN.1 definitions. Phew!

The diagram below illustrates these relationships:

Summary:

1. Each Entry is composed of one or more objectClasses
2. Each objectClass has a name.
3. Each Attribute has a name, usually contains data and is a member of an object class.

2.4.2 Attributes

Each attribute has a name and normally contains data. Attributes are always associated with (are members of) one or more ObjectClasses. Attributes have a number of interesting characteristics:

1. All attributes are members of one or more objectclass(es)

2. Each attribute defines the data type that it may contain.

3. Attributes can be optional (keyword is MAY) or mandatory (keyword is MUST) as described in the ASN.1 definitions for the objectclass of which they are a member. An attribute may be optional in one objectclass and mandatory in another. It is the objectclass which determines this property.

   One sees apparently random attributes being picked up from all over the place in the documentation - it's confusing at first but comes from the optional characteristic of most attributes. It allows a 'pick-n-mix' approach to populating an entry. Find the attribute you want, include its objectclass, and hope that all the other attributes that you don't want to use in the objectclass are optional! Try browsing here to get a feel for this.

4. Attributes can have single or multi values (as described in their ASN.1 definitions). Single means that only one data value may be present for the attribute. Multi means there can be one or or more data values for the attribute. If the attribute describes say, an email address, there can be one, two or 500 values - this is one of a number of methods of dealing with email aliases in directory designs. The default for an attribute is multi (allow multiple values).

5. Attributes have names and sometimes aliases or abbreviations (as described in their ASN.1 definitions) e.g. commonName is a member of the object class named person (and many others) and has an abbreviated name of cn. Either commonName or cn may be used to reference this attribute.

6. At each level in the hierarchy the data contained in one attribute should uniquely identify the entry. It can be any attribute in the entry. It can even be a combination of two or more attributes.

   Suppose you have a classic white-pages directory containing names, phone number, addresses, favorite drink (yes there is a standard favoritedrink attribute) etc.. To uniquely identify a particular entry you may choose the person's name (the commonName or cn attribute). If the name is not unique in the LDAP directory e.g. 'Bob Smith' then a search for 'Bob Smith' will return all the entries containing the name 'Bob Smith' in the directory and the user will have to select the best one. For reading and searching this may be acceptable or even desirable since the human 'interface' uses well known information - the person's name.

   For writing or updating an entry if 'Bob Smith' is not absolutely unique it is useless - which of the returned entries do we update? In this case it may be necessary to select another attribute that is absolutely unique. It is perfectly permissible to use more that one attribute to access the data depending on the context e.g. person's name for reading and searching, telephone number for writing. Furthermore, as defined above, it is perfectly permissible to use more that one attribute (cn+favoritedrink!) to define the unique entry.

   The attribute value selected to contain the unique'ish data is called the naming attribute(s) or the Relatively Distinguished Name (RDN) - but more of that stuff later.

Browse some common objectClasses and attributes. If it looks pretty scary at this stage just forget you took the link and carry on reading.

More on Attributes - only if you are comfortable otherwise continue here.

2.4.3 ObjectClasses

Objectclasses are essentially packages of attributes. There are a confusing number of pre-defined objectclasses, each of which contains bucket-loads of attributes for almost all common or garden applications. But of course the one you NEED is never defined! objectclasses have two more characteristics:

1. The objectclass defines whether an attribute member MUST (mandatory) be present or MAY (optional) be present.

2. The objectclass may be part of a hierarchy in which case it inherits all the characteristics of its parent objectclasses.

There is an incomplete list of the most common objectClasses and their attributes here.

More on objectClasses - only if you are comfortable otherwise continue here.

2.4.4 Describing the Tree and Adding Data

Eventually we want to slap some data into our directory and actually use the blasted thing.

Describing the tree structure and initial population of data is usually done using LDAP Data Interchange Files (LDIF) which are fully described in a later chapter. LDIFs are textual files that describe the tree hierarchy - the Directory Information Tree (DIT) and the data to be added to each attribute. The following is a simple example of an LDIF file which sets up a root DN (dc=example,dc=com) and adds a single child entry under people.

It is not important to understand what all the values in this file do at this stage. Chapter 5 (samples) covers the details of setting up files and explains in painful detail the various fields. It is enough, at this stage, to know that LDIF files are used to set up the DIT and that LDIF files look like the one below.

version: 1

## version not strictly necessary but good practice to include for future

## DEFINE DIT ROOT/BASE/SUFFIX ####
## uses RFC 2377 format

## dcObject is an AUXILLIARY objectclass and MUST
## have a STRUCTURAL objectclass (organization in this case)
# this is an ENTRY sequence and is preceded by a BLANK line

dn: dc=example,dc=com
dc: example
description: The best company in the whole world
objectClass: dcObject
objectClass: organization
o: Example, Inc.

## FIRST Level hierarchy - people 
# this is an ENTRY sequence and is preceded by a BLANK line

dn: ou=people, dc=example,dc=com
ou: people
description: All people in organisation
objectClass: inetOrgPerson

## SECOND Level hierarchy - people entries 
# this is an ENTRY sequence and is preceded by a BLANK line

dn: cn=Joe Schmo,ou=people,dc=example,dc=com
objectclass: inetOrgPerson
cn: Joe Schmo
sn: Schmo
uid: jschmo
mail: joe@example.com
mail: j.schmo@example.com
ou: sales

We'll explain about LDIF files later as we need them but the above LDIF sets up the structure below:

Once the DIT is up and running, further data may be added using LDIF, an LDAP Browser, a web or other application interface.

Data can be exported (saved) for backup or other purposes using LDIF files.

2.4.5 Navigating the Tree

Having gotten data into our Tree (DIT) we would now - normally - like to use it!

To do that we have to send commands (read, search, modify etc.) to the LDAP server, and in order to do that we have to be able to tell the LDAP server where the data is (for a write) or roughly where it is (for a search).

We have to be able to navigate the directory.

We defined previously that attributes have names and that at each level in the hierarchy one or more of the attributes must contain data that somewhat uniquely identifies each entry.

By constructing paths that comprise these named attributes and their data content we can get to our desired entry or search start position.

These paths are quaintly called Distinguished Names (DN). Each unique data attribute that is a part of this DN is called a Relatively Distinguished Name (RDN). Whatever your views of the merits, or otherwise, of LDAP and X.500 the ability of the standard group to generate unique terminology is beyond question. The following diagram illustrates the DN and RDNs.

Further explanation with some worked examples.

One of the more powerful aspects of LDAP (and X.500) is the inherent ability within the design to delegate the responsibility for maintenance of a part of the directory while continuing to see the directory as a consistent whole. Thus, a company directory may create a delegation (referral is the LDAP term) of the responsibility for a particular department's part of the overall directory to that department's LDAP server. In this respect LDAP almost exactly mirrors the DNS delegation concept.

Unlike the DNS system, there is no option in the standards to tell the LDAP server to follow (resolve) a referral - it is left to the LDAP client to directly contact the new server using the returned referral. Equally, because the standard does not define LDAP data organisation it does not contravene the standard for an LDAP server to follow (resolve) the link and some LDAP servers perform this function automatically using a process that is usually called chaining.

OpenLDAP takes a literal view of the standard and does not chain by default it always returns a referral. However OpenLDAP can be configured to provide chaining by use of the database ldap directive.

The built-in replication features of LDAP allows one or more copies of a directory (DIT) to be slaved from a single master thus inherently creating a resilient structure.

It is important, however, to emphasize the difference between LDAP and a transactional database. When an update is performed on a master LDAP enabled directory, it may take some time (in computing terms) to update all the slaves - the master and slaves may be unsynchronised for period of time.

In the LDAP context, temporary lack of DIT synchronisation is regarded as unimportant. In the case of a transactional database even a temporary lack of synchronisation, is regarded as catastrophic. This emphasises the differences in the characteristics of data that should be maintained in an LDAP enabled directory versus a transactional database.

The configuration of Replication and Referral is discussed further and featured in the samples.

2.5.1 LDAP Referrals

Figure 2.5-1 below shows a search request with a base DN of dn:cn=thingie,o=widgets,dc=example,dc=com, to a referral based LDAP system, that is fully satisfied from the first LDAP (LDAP1) server:

Figure 2.5-1 - Request satisfied from LDAP1 only

Figure 2.5-2 below shows a search request with a base DN of dc:cn=cheri,ou=uk,o=grommets,dc=example,dc=com, to a referral based LDAP system, that results in a series of referrals to the LDAP2 and LDAP3 servers:

Figure 2.5-2 - Request generates referrals to LDAP2 and LDAP3

Notes:

1. All client requests start at the global directory LDAP 1
2. At LDAP 1, requests for any data with widgets as an RDN in the DN are satisfied immediately from LDAP1, for example:

   dn: uid=cheri,ou=uk,o=widget,dc=example,dc=com
   

3. At LDAP 1 requests for any data with grommets as an RDN in the DN are referred to LDAP2, for example:

   dn: uid=cheri,ou=uk,o=grommets,dc=example,dc=com
   

4. At LDAP 2, requests for any data with uk as an RDN in the DN are referred to LDAP3, for example:

   dn: uid=cheri,ou=uk,o=grommets,dc=example,dc=com
   

5. If the LDAP server is configured to chain (follow the referrals as shown by the alternate dotted lines) then a single data response will be supplied to the LDAP client. Chaining is controlled by LDAP server configuration and by values in the search request. Information on chaining.

6. The Figures illustrate explicit chaining using the referral ObjectClass, OpenLDAP servers may be configured to return a generic referral if the requested DN is not found during a search operation.

2.5.2 LDAP Replication

Replication features allow LDAP DIT updates to be copied to one or more LDAP systems for backup and/or performance reasons. In this context is is worth emphasizing that replication operates at the DIT level not the LDAP server level. Replication occurs periodically within what we call the replication cycle time. In general there are methods to reduce the replication cycle time by configuration but which typically have a performance or network usage overhead. OpenLDAP historically used a separate daemon (slurpd) to perform replication but since version 2.3 this has changed significantly. There are two possible replication configurations and multiple variations on each configuration type.

1. Master-Slave: In a master-slave configuration a single DIT is capable of being updated and these updates are replicated or copied to one or more designated servers running slave DITs. The slave servers operate with read-only copies of the master DIT. Read-only users will access the servers containing the salve DITs and users who need to update the directory will access the server containing the master DIT. This configuration has two obvious shortcomings:

   • If all/most users have the ability/need to update the DIT then they either they will have to access one server (with the slave DIT) for normal read access and another server (with the master DIT) to perform the update. Alternatively they can always point to the server running the master DIT. In this latter case replication provides backup functionality only.

   • Since there is only one server containing a master DIT it represents a single point of failure.

2. Multi-Master: In a multi-master configuration one or more servers running master DITs may be updated and the resulting updates are propagated to the corresponding masters.

   Historically OpenLDAP has not supported multi-master operation but version 2.4 introduced a multi-master capabiity. In this context it may be worth pointing out two specific variations of the generic update-contention problem of all multi-master configurations identified by OpenLDAP and which are true for all LDAP systems:

   1. Value-contention If two attribute updates are performed at the same time (within the replication cycle time) with different values then, depending on the attribute type (SINGLE or MULTI-VALUED) the resulting entry may be in an incorrect or unusable state.

   2. Delete-contention If one user adds a child entry at the same time (within the replication cycle time) as another user deletes the original entry then the deleted entry will re-appear.

Figure 2.5-3 shows a number of possible replication configurations.

Figure 2.5-3 - Replication Configurations