LDAP is not relational

Many years ago I held a talk comparing SQL and LDAP at the NetUSE Customer Conference 2002. Kai made a longer, better english language version of these slides for his Linuxtag 2006 talk.

The summary:

• LDAP has a fixed primary key, the DN. This PK is used everywhere. It also has pathname nature, so it is not stable: Move an entry within the LDAP tree, watch the DN for the entry change. Expect referential integrity to break, or if it does not, expect an update storm.
• Of the five base relational algebra operations projection, selection, join, rename and aggregation, LDAP implements one and a half: Selection is present, projection is there, but only half so - there are no synthetic attributes, and there is no join, no rename and no aggregation at all.
• SQL is an algebra: It defines five basic operations on tables, and the result of each operation is a table. That table can be reused in any position in an outer query - subqueries are born. LDAP is not an algebra - the result of any LDAP query is not an LDAP subtree and there are no subqueries.
• Any LDAP schema from the POV of relational theory is not even in first normal form. LDAP schemata violate first normal for example in any multi-value attribute, in any structured attribute such as a password entry (of the form "{plain}secret" for example, this should really be two attributes "passwordEncoding" and "password") or access control list entry. Actually LDAP ACLs, when stored in the schema, violate first normal form twice: They are multivalue attributes that contain structured nonatomic content.

All of these problems have grave implications when you want to deploy LDAP, and they interact.

Primary key instability

For example, to avoid DN changes you might want to store personell data in a flat table-like structure underneath something like "ou=people, dc=mydomain , dc=de", indexed by a synthetic primary key such as a employee number. Each employee will then end up with a DN like "emp=4711, ou=people, dc=mydomain, dc=de" which will not change when the employee marries (sn, cn changes), moves to a different department (ou changes) or is subject to any other administrative operations.

Partitioning by range on PK provokes PK instability

Of course, if you want to partition your LDAP tree across multiple servers that is not possible, because LDAP can only partition by DN. If you want to partition 'ou=people, dc=mydomain, dc=de' across two servers "left" and "right", then you need to split the tree into two components which are visible in the DN: 'ou=left, ou=people, dc=mydomain, dc=de' and 'ou=right, ou=people, dc=mydomain, dc=de', no way around that. In SQL this would be the equivalent of a "partition by range" on the prefix of a compound primary key, but SQL offers many more partitioning schemes and partitioning in general is not tied to the primary key.

Data duplication induced by limited operation set

The fact that LDAP implements relational base operations only in a limited way leads to data duplication.

For example, some applications require passwords as Unix crypt, other want MD5 hashes or other, more complicated structures. We cannot store (protected) plain text fields and then supply functions or queries that return the password from a single source in various encrypted forms. Instead we have to code up an application that takes a single plain text password and stores it in it various encoded forms as various attributes used by the various LDAP consumers such as Unix PAM libraries, NTLM consumers, blade center chassis authenticators and radius servers.

Similar things happen quite often in LDAP, in fact native attributes such as CN (common name) should be synthetic attributes with a calculated value, but are in fact independent attributes not related to SN (surname) and GN (givenname).

Weak query language leads to queries-in-a-loop in applications

The two facts that LDAP is not an algebra and the query language is incomplete work together in an interesting way: You end up coding a lot of things inside the application as loops across repeated LDAP queries that are the equivalent of more complicated single SQL queries. Thus, LDAP servers are often subject to vast storms of very fast repeated queries which are essentially data downloads of subsets of the LDAP tree. LDAP server designers are often very proud of the high speed and low latency of their server designs - 40.000 queries per second and more are sometimes given as numbers by them. They are right - LDAP servers are very fast, especially compared to SQL servers. But: With a proper SQL query the work that is done by an LDAP server in 40.000 queries can often be done with a single SQL statement - SQL is more than just primary key lookups.

"No aggregation in LDAP" for example means: if you want to generate a list of number of users per department, you'll have to download the employee list completely and maintain an array of sum counters inside your application yourself. In SQL this is a very simple GROUP BY query with COUNT() (sorry, no synthetic attributes in LDAP projections, so no COUNT() for you).

"No JOIN in LDAP" for example means: if you want to generate a list of mail addresses for delivery from an LDAP group (a pool of member DNs), you'll have to download the list of DNs that are members of your group and then for each of the DNs query the list of associated email addresses for these DNs. In SQL, this is of course a simple JOIN operation delivering directly the list of email addresses.

Many replicas to cope with many queries

To cope with the large number of queries and to fight latency, LDAP stores data usually very close to the LDAP data consumer applications. For example, if you are running a mail server which is controlled by LDAP data, it is usually a very good idea to have a replica of your LDAP data running on the same server. Otherwise you'll see 4-7 queries on the network for every single simple mail delivery plus the resolution queries for deliveries to groups and lists.

Killing reads with memory

Now: How is this fast? Well, it is not.

To kill the problem of queries to a not-normalized data storage with an incomplete query language we saturate the problem with hardware. In the case of LDAP this is memory: LDAP servers work just fine despite the fact that their data model is completely broken from the POV of the relation model as long as they are able to cache all data in memory. But: This strategy only works for reads. Have a write-heavy server, and watch LDAP die in flames. Have a write-heavy server that is a replication data source and watch your replication network go down due to an update storm.

Of course, writes can not be cached in memory. They have to hit a stable storage eventually. So write-heavy LDAP servers are a big no-no: Due to denormalisation, writes are likely to multiply (all occurences of the item you want to change need to be updated) and eventually you starve your disks.

Nice. And how does this relate to the problem in question?

Serendipity is a blog software that uses an SQL storage backend. It's data storage is not particularly beautifully designed - undernormalized in some places, overnormalized in others, but it is decidedly SQL. It uses SQL in many places to aggregate stuff, and it makes heavy use of joins.

If you want to provide the functionality required by S9Y in SQL, you'll end up coding a JOIN function and aggregation abstractions in PHP with ldap_search() calls in a loop. You'll need to be able to provide callbacks to your ldap_search iterators in order to be able to implement generic aggregators and synthetic attributes. You'll need a local replica of your blog LDAP subtree or latency will kill your search storm. And you'll be desperate to maintain cached versions of your aggregates because they have been hard to come by.

In short: It will suck, but if you are not completely dumb, you'll learn a lot about abstract data types, normalization and the advantages of SQL on your way.