Introduction

Parsing DN is one of the most expensive task in a LDAP server. It's not only consumming CPU, but also memory, which cause the garbage collector to be called more often (some measures show that GC represent 30% of all the time consummed during an intensive searchRequest treatment).

Moreover, DN parsing is a complex operation, due to the numerous special cases, plus the normalization that should occurs in two places, and because we have to store the DN in more than one form to speed up the server by avoiding some useless parsing and normalization.

We will see in this page the way we are parsing DN in the server

LdapDN structure

External structure

From the user point of view, a DN is a composition :

DN => n * RDN
RDN => m * AVA
AVA => AttributeType + AttributeValue
AttributeType => non sensitive String or an OID
AttributeValue => a String

Each RDN is separated from the other ones by a ',' or a ';' character.
Each AVA is separated from the other ones by a '+' character.
Attribute and values are separated by the '=' character.

At this point, we have said nothing about the charset used by DN. DN are supposed to be transmitted as UTF-8 chars to the server, so we might have up to 6 bytes to store a char. The RFCs specified that a user can escape some values by using either '\xx' sequence in a value (where xx is the hexadecimal value of this char), or octothrops strings (a string composed of a starting '#' character followed by hexadecimal pairs, corresponding of the byte values of the value part). We have to deal with those cases.

The last point is that spaces are not meaningfull around the ',', ';', '+' and '=' character, nor they are at the beginning and end of each RDN, AVA, type and value. To be able to store a leading or trailing space into a value, a user must embed this value between two '"' characters.

Of course, some other characters must be escaped : '\', ' ', '#', '=', '', ',', '"', '', ';', and we will have to deal with those cases too...

Internal structure

The internal DN structure we have chose depends on different considerations :

• speed : we must be able to avoid costly operations, by keeping normalized and parsed forms of the DN
• memory consumption : as we said, garbage collecting is a costly operation. We should keep the number of objects necessary to hold a DN as small as possible. We must also have small objects because the smaller they are, the more of them we can store in cache.
• serialization : DN are stored in the backend, which means we must serialize and deserialize those DNs. The operation must be fast, as disk access are slower than memory access by 2 orders of magnitude.
• CPU consumption : we should avoid as much as possible doing twice the same opeation (like parsing, normalization), because the more operation we do, the more latency we generate due to synchronized portions of code. We also have to release the IOExecutor threads which are used to process the incoming requests.

As everyhting is a balance between those elements, we should favor the most frequent cases, which are pure ASCII DNs where RDN contains only one AVA, where value are not escaped.

DN cycle of life

DNs are send by users to identify entries. When a entry is first stored, its DN is created in the DN table. When a user is searching for a specific entry using its DN, it is compared whith the stored DNs.

What is important is that we have two forms for a DN : UP (User Provided) and Norm (normalized DN). UP DNs are used when we return this info to the user. Norm form is used internally to uniquely identify entries. It is very important to understand that DNs are manipulated in their Norm form into the server.

We have one special case : when moving data from a place to another one with the ModifyRDN request, which can modify the DN (its UP and Norm form), so we must be able to construct a new UP and Norm form of the modified DN.

Internally, we will use the normalized form

Normalization

We have for kinds of normalization to apply :

• attribute types are lower cased and spaces are removed around ',', ';', '=', and '+'
• then attribute type are transformed to their OID counterpart to avoid having to deal with multiple form of the same attributeType (AT can have aliases, like CN, CommonNmae, and 2.5.4.4 which are all the same attributeType)
• attribute values are normalized accordingly to their attributeType suyntax.
• at the end, into a RDN, AVA will be ordered following the alphabetic increase order.

For instance, the following RDN :
"ou= Some People + dc = And Some anImAls,dommainComponent = eXample,dc= cOm"
will be transformed into :
"0.9.2342.19200300.100.1.25=and some animals+2.5.4.11=some people,0.9.2342.19200300.100.1.25=example,0.9.2342.19200300.100.1.25=com"

As we can see, types are replaced by their OID, useless spaces are removed, RDN are reordered and values are normalized (lowercased, and multiple inner spaces are replaced by a simple space).

Internal structure

We have five objects to describe :

• DN
• RDN
• AVA
• Type
• Value

The following paragraphs describe those ojects internal structure.

DN internal structure

A DN should not be empty, but we have to accept such a DN (rootDSE is the empty DN). We will store three forms for a DN

• user provided form
• byte array of this user provided form
• normalized form

RDN internal structure

We should keep two forms of a RDN :

• a User Provided form
• a normalized form

This is important because we will often manipulate those RDN, for instance while searching the partition a DN is associated with.

A RDN may contains more than one AVA, but usually contains only one. An optimization could be not to create an array to store more than one ATV, but instead keeping it in a single member. If we have more than one AVA, then we will create an array instead. The extra cost of creating this array is totally acceptable regarding the frequency of such multiple AVAs in a RDN (which is very low). On the osther side, it forces the access metho to deal with the number of AVA, but this cost is obviously less than access an AVA through an ArrayList (to be double checked)

	class RDN
		// The user provided form
		String upRdn;

		// The AVA if we have only one
		AVA ava;

		// A flag set to true if we have only one AVA
		boolean isSingle;

		// An array of AVAs if we have more than one
		List<AVA> avas;

AVA internal structure

An AVA contains an attributeType and an attribute value. We could keep the String representation of an AVA internally, but as those members already have a String representation, and as we rarelly manipulate an AVA (except when creating it while decoding a DN), there is no need to store this duplicated information.

	class AVA
		AttributeType type;
		AttributeValue value;

AttributeType internal structure

We will store only two informations :

• the User provided form
• the attributeType OID

	class AttributeType
		String 	upType;
		OID	normType;

AttributeValue internal structure

This element should be kept as a String (UP form) and as a byte array if the corresponding AT is not H/R, or as a String if the AT is H/R (H/R : Human Readable)

It could be good to keep it as a byte array to avoid a costly conversion when sending back the data to the user (to be checked)

The structure will be :

	class AttributeValue
		// a flag which tells if this value is H/R or not
		boolean isHR; 

		// The user povided value
  		String upValue; 

		// The structure which hold the value, either a String ro a byte[]
  		NormValue normValue; 

with the interface NormValue and the implementing classes :

	
	interface NormValue

	class NormStringValue implements NormValue
		String value; // The value if it's a String

	class NormBytesValue implements NormValue
		byte[] value; // The value if it's a byte array