|
|||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
See:
Description
Interface Summary | |
---|---|
IndexBuilder | The interface that represents a index builder for the import process. |
Class Summary | |
---|---|
ApproximateIndexer | An implementation of an Indexer for attribute approximate matching. |
AttributeIndex | Class representing an attribute index. |
AttributeIndex.KeyComparator | The default lexicographic byte array comparator. |
BackendImpl | This is an implementation of a Directory Server Backend which stores entries locally in a Berkeley DB JE database. |
BackupManager | A backup manager for JE backends. |
ConfigurableEnvironment | This class maps JE properties to configuration attributes. |
DatabaseContainer | This class is a wrapper around the JE database object and provides basic read and write methods for entries. |
DataConfig | Configuration class to indicate desired compression and cryptographic options for the data stored in the database. |
DbPreloadComparator | This comparator is used to sort databases in order of priority for preloading into the cache. |
DN2ID | This class represents the DN database, or dn2id, which has one record for each entry. |
DN2URI | This class represents the referral database which contains URIs from referral entries. |
EntryContainer | Storage container for LDAP entries. |
EntryContainer.KeyReverseComparator | A lexicographic byte array comparator that compares in reverse byte order. |
EntryID | An integer identifier assigned to each entry in the JE backend. |
EntryIDSet | Represents a set of Entry IDs. |
EntryIDSetSorter | This class provides a mechanism for sorting the contents of an entry ID set based on a given sort order. |
EnvManager | A singleton class to manage the life-cycle of a JE database environment. |
EqualityIndexer | An implementation of an Indexer for attribute equality. |
ExportJob | Export a JE backend to LDIF. |
ID2CIndexer | Implementation of an Indexer for the children index. |
ID2Entry | Represents the database containing the LDAP entries. |
ID2SIndexer | Implementation of an Indexer for the subtree index. |
IDSetIterator | Iterator for a set of Entry IDs. |
Index | Represents an index implemented by a JE database in which each key maps to a set of entry IDs. |
IndexBuffer | A buffered index is used to buffer multiple reads or writes to the same index key into a single read or write. |
IndexBuffer.BufferedIndexValues | A simple class representing a pair of added and deleted indexed IDs. |
IndexBuffer.BufferedVLVValues | A simple class representing a pair of added and deleted VLV values. |
Indexer | This class attempts to abstract the generation and comparison of keys for an index. |
IndexFilter | An index filter is used to apply a search operation to a set of indexes to generate a set of candidate entries. |
IndexIteratorAllIds | Implements an iterator over all the entry IDs in the backend. |
IndexIteratorRange | Implements an iterator over a range of entry IDs. |
IndexMod | A modification to an attribute index, to either insert an entry ID or delete an entry ID, for a given key. |
IndexModComparator | A comparator for index modifications. |
IndexRebuildThread | A thread to do the actual work of rebuilding an index. |
JebFormat | Handles the disk representation of LDAP data. |
JECompressedSchema | This class provides a compressed schema implementation whose definitions are stored in a Berkeley DB JE database. |
Longs | This class represents a sorted set of longs. |
MergeReader | This class represents a reader of an intermediate file created during an import process, and whose contents are to be merged with other intermediate files. |
MergeValue | This is a class used by the index merge thread. |
OctetStringKeyComparator | This class implements a comparator for ASN1OctetString using a byte array comparator supplied in its constructor. |
OrderingIndexer | An implementation of an Indexer for attribute ordering. |
PresenceIndexer | An implementation of an Indexer for attribute presence. |
RebuildConfig | Configuration for the indexType rebuild process. |
RebuildJob | Runs a index rebuild process on the backend. |
RootContainer | Wrapper class for the JE environment. |
SortValues | This class defines a data structure that holds a set of attribute values that are associated with a sort order for a given entry. |
SortValuesSet | This class representsa partial sorted set of sorted entries in a VLV index. |
State | This class is responsible for storing the configuration state of the JE backend for a particular suffix. |
SubstringIndexer | An implementation of an Indexer for attribute substrings. |
VerifyConfig | This class represents the configuration of a JE backend verification process. |
VerifyJob | This class is used to run an index verification process on the backend. |
VLVIndex | This class represents a VLV index. |
VLVKeyComparator | This class is used to compare the keys used in a VLV index. |
Exception Summary | |
---|---|
JebException | This class defines an exception that may be thrown if a problem occurs in the JE backend database. |
Contains the code for the Directory Server backend that uses the Berkeley DB
Java Edition as the repository for storing entry and index information.
First it is important to understand JE (Java Edition) terminology. A JE database environment has similarities to a database in the relational database world. Each environment can have multiple databases, which are similar to tables in a relational database. A JE environment is identified by the file system directory in which it is stored. A JE database is identified by a unique name within its environment. Multiple databases in the same environment may be updated within the same transaction, but transactions cannot span environments.
In this description, database means a JE database.
Each instance of this backend creates a single JE environment to store its data. Unlike previous versions of Directory Server, environments are not shared by backend instances. The backend does support multiple base DNs, so it is still possible for data under multiple suffixes to share the same database environment, by declaring those suffixes as base DNs of a single JE backend instance.
The data for a base DN is kept in a set of databases, so that a database contains data for only one base DN. Each database name is prefixed by the base DN it belongs to, where the DN is simplified by preserving only letters and digits.
For example, if you were to use the DbDump utility to list the databases in the environment corresponding to a backend instance containing the base DN dc=example,dc=com, you might see the following:
dc_example_dc_com_cn.equality dc_example_dc_com_cn.presence dc_example_dc_com_cn.substring dc_example_dc_com_dn2id dc_example_dc_com_givenName.equality dc_example_dc_com_givenName.presence dc_example_dc_com_givenName.substring dc_example_dc_com_id2children dc_example_dc_com_id2entry dc_example_dc_com_id2subtree dc_example_dc_com_mail.equality dc_example_dc_com_mail.presence dc_example_dc_com_mail.substring dc_example_dc_com_member.equality dc_example_dc_com_sn.equality dc_example_dc_com_sn.presence dc_example_dc_com_sn.substring dc_example_dc_com_telephoneNumber.equality dc_example_dc_com_telephoneNumber.presence dc_example_dc_com_telephoneNumber.substring dc_example_dc_com_uid.equality
The data is stored in a format which is independent of system architecture, and is also independent of file system location because it contains no pathnames. The backend, and its backups, can be copied, moved and restored to a different location, within the same system or a different system.
Each entry to be stored in the backend is assigned a 64-bit integer identifier called the entry ID. The first entry to be created is entry ID 1, the second is entry ID 2, etc. This ensures that the ID for any given entry is always greater than its superiors. The backend takes care to preserve this invariant, in particular during Modify DN operations where an entry can be given a new superior. Clients have come to expect child entries to be returned after their parent in search results, and the backend can ensure this by returning entries in ID order.
On disk, an entry ID is stored in eight bytes in big-endian format (from most significant byte to least significant byte). This enables binary copy of the backend from one system to another, regardless of the system architecture.
Currently, IDs of deleted entries are not reused. The use of a 64-bit integer means it is implausible that the entry ID space will be exhausted.
Entries are stored in the id2entry database. The key to the database is the entry ID, and the value is an ASN.1 encoding of the entry contents. The default JE btree key comparator is used for the entry database, such that cursoring through the database will return entries in order of entry ID. When the backend starts it is able to determine the last assigned entry ID by reading the last key value in the entry database.
The format of the entry on disk is described by the following ASN.1.
DatabaseEntry ::= [APPLICATION 0] IMPLICIT SEQUENCE { uncompressedSize INTEGER, -- A zero value means not compressed. dataBytes OCTET STRING -- Optionally compressed encoding of the data bytes. } ID2EntryValue ::= DatabaseEntry -- Where dataBytes contains an encoding of DirectoryServerEntry. DirectoryServerEntry ::= [APPLICATION 1] IMPLICIT SEQUENCE { dn LDAPDN, objectClasses SET OF LDAPString, userAttributes AttributeList, operationalAttributes AttributeList }
Entry compression is optional and can be switched on or off at any time. Switching on entry compression only affects future writes, therefore the database can contain a mixture of compressed and not-compressed records. Either record type can be read regardless of the configuration setting. The compression algorithm is the default ZLIB implementation provided by the Java platform.
The ASN1 types have application tags to allow for future extensions. The types may be extended with additional fields where this makes sense, or additional types may be defined.
Previous versions of Directory Server provide the current number of entries stored in the backend. JE does not maintain database record counts, requiring a full key traversal to count the number of records in a database, which is too time consuming for large numbers of entries.
For this reason the backend maintains its own count of the number of entries in the entry database, storing this count in the special record whose key is entry ID zero.
Although each entry's DN is stored in the entry database, we need to be able to retrieve entries by DN. The dn2id database key is the normalized DN and the value is the entry ID corresponding to the DN. A normalized DN is one which may be compared for equality with another using a standard string comparison function. A given DN can have numerous string representations, due to insignificant whitespace, or insignificant case of attribute names, etc., but it has only one normalized form. Use of the normalized form enables efficient key comparison.
A custom btree key comparator is applied to the DN database, which orders the keys such that a given entry DN comes after the DNs of its superiors, and ensures that the DNs below a given base DN are contiguous. This ordering is used to return entries for a non-indexed subtree or single level search. The comparator is just like the default lexicographic comparator except that it compares in reverse byte order.
For example, a cursor iteration through a range of the DN database might look like this:
dc=example,dc=com ou=people,dc=example,dc=com uid=user.1000,ou=people,dc=example,dc=com uid=user.2000,ou=people,dc=example,dc=com uid=user.3000,ou=people,dc=example,dc=com uid=user.4000,ou=people,dc=example,dc=com uid=user.100,ou=people,dc=example,dc=com uid=user.1100,ou=people,dc=example,dc=com uid=user.2100,ou=people,dc=example,dc=com
At first, it may seem strange that user.1100 comes after user.1000 but it becomes clear when considering the values in reverse byte order, since 0011.resu is indeed greater than 0001.resu.
Index databases are used to efficiently process search requests. The system indexes, id2children and id2subtree, are dedicated to processing one-level and subtree search scope respectively. Then there are configurable attribute indexes to process components of a search filter. Each index record maps a key to an Entry ID List.
An entry ID list is a set of entry IDs, arranged in order of ID. On disk, the list is a concatenation of the 8-byte entry ID values, where the first ID is the lowest. The number of IDs in the list can be obtained by dividing the total number of bytes by eight.
In some cases, the number of entries indexed by a given key is so large that the cost of maintaining the list during entry updates outweighs the benefit of the list during search processing. Each index therefore has a configurable entry limit. Whenever a list reaches the entry limit, it is replaced with a zero length value to indicate that the list is no longer maintained.
The children index is a system index which maps the ID of any non-leaf entry to entry IDs of the immediate children of the entry. This index is used to get the set of entries within the scope of a one-level search.
The subtree index is a system index which maps the ID of any non-leaf entry to entry IDs of all descendants of the entry. This index is used to get the set of entries within the scope of a subtree search.
An attribute equality index maps the value of an attribute to entry IDs of all entries containing that attribute value. The database key is the attribute value after it has been normalized by the equality matching rule for that attribute. This index is used to get the set of entries matching an equality filter.
An attribute presence index contains a single record which has entry IDs of all entries containing a value of the attribute. This index is used to get the set of entries matching an attribute presence filter.
An attribute substring index maps a substring of an attribute value to entry IDs of all entries containing that substring in one or more of its values of the attribute. This index is used to get a set of entries that are candidates for matching a subtring filter.
The length of substrings in the index is configurable. For example, let's say the configured substring length is three, and there is an entry containing the attribute value ABCDE. The ID for this entry would be indexed by the keys ABC BCD CDE DE E. To find entries containing a short substring such as DE, iterate through all keys with prefix DE. To find entries containing a longer substring such as BCDE, read keys BCD and CDE.
An attribute ordering index is similar to an equality index in that it maps the value of an attribute to entry IDs of all entries containing that attribute value. However, the values are normalized by the ordering matching rule for the attribute rather than the equality matching rule, and the btree key comparator is set to the ordering matching rule comparator. This index is used to get the set of entries matching inequality filters (less-than-or-equal, greater-than-or-equal).
|
|||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |