/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
 * or http://forgerock.org/license/CDDLv1.0.html.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at legal-notices/CDDLv1_0.txt.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Copyright 2006-2008 Sun Microsystems, Inc.
 */



/**
 * Contains the code for the Directory Server backend that uses the Berkeley DB
 * Java Edition as the repository for storing entry and index information.
 * <BR><BR>
 *
 * <H3>On-disk Representation</H3>
 * <P>
 * 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.
 * <P>
 * In this description, database means a JE database.
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * 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:
 * <pre>
 * 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
 * </pre>
 * <H4>Database Relocation</H4>
 * <P>
 * 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.
 * <P>
 * <H4>The Entry ID</H4>
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * <P>
 * <H4>The entry database (id2entry)</H4>
 * <P>
 * 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.
 * <P>
 * The format of the entry on disk is described by the following ASN.1.
 * <P>
 * <pre>
 * 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
 * }
 * </pre>
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * <H5>The entry count record</H5>
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * <P>
 * <H4>The DN database (dn2id)</H4>
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * For example, a cursor iteration through a range of the DN database might
 * look like this:
 * <pre>
 * 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
 * </pre>
 * <P>
 * 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.
 * <P>
 * <H4>Index Databases</H4>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Entry ID List</H5>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Index Entry Limit</H5>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Children Index (id2children)</H5>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Subtree Index (id2subtree)</H5>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Attribute Equality Index</H5>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Attribute Presence Index</H5>
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Attribute Substring Index</H5>
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * <P>
 * <H5>Attribute Ordering Index</H5>
 * <P>
 * 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).
 *
 *
 */
@org.opends.server.types.PublicAPI(
     stability=org.opends.server.types.StabilityLevel.PRIVATE)
package org.opends.server.backends.jeb;

