1.5 - Backend

The Backend is the part of the server responsible for storing data in a way we can easily retrieve them. This storage does not necessarily have to be remanent : we can have a in-memory backend.

Existing Backends

We currently have 3 different backends :

• JDBM
• LDIF
• In-Memory

JDBM Backend

The JDBM backend is storing data on disk, using BTrees. It’s fast when it comes to retrieve data, slow when you have to add them.

In-Memory Backend

This Backend loads in memory a full set of entries. ALl of them must be hold by the existig memory, we don’t write on disk anything nor we read anything from disk. If the server is stopped, everything is lost.

LDIF Backend

It comes in two forms : one single file, or many fles (one per entry). It’s always backed by a in-memory Backend, otherwise it would not be possible to retrieve the entries.

As we depend on a in-memory backend, which handles the indexes, we have to create those indexes when this Backend is read, which can be a costly operation.

Future Backends

We intend to add another in-memory backend, based on Mavibot, a MVCC BTREE. The biggest advantage over the other systems is that it’s fast, it allows concurrent reads without locks when the other Backend block the reads when some write operation is being processed. Also it saves on disk it contents periodically, and has a Journal so that we can recover from a crash.

The only drawback is that all the entries and indexes must hold in memory. On the other hand, we don’t anymore need a cache.

How it works

Basically, each Backend instance inherit from the AbstractBTreePartition class. We can see that a Backend must be a Btree.

Data are stored into various tables. In fact, we have one table containing all the entries - the MasterTable - and many indexes.

MasterTable

The MasterTable contains all the entries, serialized.

This table is a <Key, Value> BTree, where the key is the entry’s UUID, and the value the serialized entry.

Indexes

Each index is also a <key, value> BTree, with some exceptions : as we may store multi-valued elements, it’s perfectly possible that the value will grow up to a point it’s extremely costly to store it serialized. For instance, the ObjectClass index may have thousands of entries for the Person key.

In this case, we use a sub-btree, which is a <key,key> BTree (as strange as it sounds, it’s an easy way to add a new key without having to rewrite the full value).

The key can be a String, or a ParentIdAndRdn.

We have 7 system indexes, which are created when the server is started :

• ObjectClass : to easily find any entry associated with a give ObjectClass
• EntryCsn : The Change Sequence Number index
• Rdn : A special index containing a RDN and its parent
• Presence : An index used when searching for the presence of an attributeType in an entry
• Alias : An index used for aliases
• OneAlias : An index used for children aliases
• SubAlias : An index used of descendant aliases

The user may define many different indexes, depending on his or her needs.

The ParentIdAndRdn index

This index is special, as it’s used to associate an entry to a position in the DIT. Assuming that each entry has a Dn, and that this Dn describes a hierarchy, the ParentIdAndRdn index depicts this hierarchy.

The ParentId part refers to the UUID of the parent for the current entry. The Rdn part is the entry Rdn. In order to rebuild the full Dn for a given entry, we must get all the ParentIdAndRdn up to the root to grab all the needed Rdn.

This index is also used to process one level and sub level indexes.