LDAP proxy cache docs in HTML. (See attached file: ldapcache.html)(See attached file: usage.html) The package can be accessed from http://www.OpenLDAP.org/its/index.cgi?findid=2062 Thanks Apurva Kumar, Research Staff Member, IBM India Research Lab Phone: +91-11-6861100 Fax: +91-11-6861555Title: LDAP proxy cache
Design and Implementation of an LDAP Caching FrameworkAbstract- A framework for caching Lightweight Directory Access Protocol (LDAP) [1,2] queries is proposed. Unlike other active query caching approaches for web applications, the caching engine is part of the LDAP proxy server rather than a servlet running at the proxy. The implementation of caching at middleware (LDAP proxy server) level allows different applications and directories to use the caching features. As an illustration of its ease of adaptation, we discuss implementation of an LDAP caching extension for the OpenLDAP directory server. I IntroductionTo improve scalability and performance of directory based web services, it is important to be able to cache results of LDAP queries. However, unlike web content, LDAP directories are not accessed for individual resources (entries) directly but through LDAP queries. Hence techniques used for web caching cannot be used for LDAP. For an LDAP cache to answer a query, it needs to check whether the query is semantically contained in earlier queries. This is similar to active query caching in databases[4]. However, since directory is a part of LDAP server, the specification of caching engine can be provided within the LDAP framework. Active proxy caching of database queries for web applications is typically implemented by servlets running at the proxy[4], which makes the solution application dependent. For LDAP directories it is possible to provide caching in the middleware by integrating the caching component with LDAP server. This allows for specification of an LDAP proxy caching framework which can be used by different applications and directories In this paper, we propose a generic design of such an LDAP caching framework. The framework builds upon the LDAP proxy framework already provided by most LDAP servers. II LDAP Caching Framework: DesignFigure1 shows the LDAP caching framework. It consists of the following modules: LDAP Proxy Cache +=============================================================+ | | | +-------------------+ | +-------+ | +--------+ | | +----------+ | |LDAP |<---|--->|Protocol|<---->|Cache Manager [QC]|<--->|Cache | | |Client | | |Engine | | [CR]| |Backend | | +-------+ | +--------+ +--------+----------+ +----------+ | | | | +=============================+===============================+ QC: Query containment, | CR: Cache replacement. | | +--------------+ +----->| Backend LDAP | | Server | +--------------+ Figure 1: LDAP proxy caching framework
CacheManager::handleQuery (request) {
operation = request.operation
if (operation != search) {
ldap.operation(request, server)
return
}
if (query_containment (request) == TRUE) {
entries = cache_be.search(request)
pe.send_entries(entries)
}
else {
entries = ldap.search(request,server)
pe.send_entries(entries)
query = request.query
if (cache_size > hi_thresh) {
while (cache_size > lo_thresh) {
query1 = cache_replace( )
cache_be.remove_query (query1)
remove_query(query1)
}
}
cache_be.merge_query(query)
add_query(query)
}
}
In response to a query Q, the cache manager invokes query containment to find cache-answerability. If the cache has entries to answer Q, it gets them from the local cache and returns query results. Otherwise, it binds with remote LDAP server and sends Q to the remote server. The results obtained from the remote server are sent to the client. The cache manager adds these entries to the database. In case the cache size is more than a high-water-mark threshold, hi_thresh it calls for cache replacement. This process is repeated until memory utilization is below a low-water-mark threshold, lo_thresh. Once the entries have been added to the local cache it adds the query semantics to the query cache. III Brief Overview of Openldap Directory ServerOpenLDAP [3] is an open source implementation of LDAP server. It mainly consists of standalone LDAP daemon (slapd) and stand-alone LDAP update replication daemon (slurpd). slapd can run on different backend databases like disk based embedded database LDBM, an interface to arbitrary shell scripts SHELL and password file database PASSWD. slapd can be configured to serve multiple databases at the same time. In this section we describe the 'LDBM backend' which is a feature rich backend and is used in our caching solution. A special backend type is 'LDAP backend' which implements an LDAP proxy. OpenLDAP can support multiple database instances. In this section we describe a brief overview of OpenLDAP design relevant to the caching framework. Basic structures:
BackendDB:
struct BackendDB {
BackendInfo *bd_info;
BerVarray be_suffix;
AccessControl *be_acl;
// other members
}
BackendInfo:
struct BackendInfo {
char *bi_type; /* type of backend */
BI_op_bind *bi_op_bind;
BI_op_unbind *bi_op_unbind;
BI_op_search *bi_op_search;
// members for other operations
}
The BackendDB contains database instance specific information. The be_suffix member is the suffix of entries stored in the backend. BackendInfo structure contains backend type specific information. It contains pointers to the backend specific implementation of functions for handling each of the LDAP operations. Utility functionsThe following utility functions are provided common to all backends.
LDBM BackendLDBM is a high-performance disk-based database. The LDBM database is designed to provide a highly functional system with good performance which is easy to administer and understand, and has reasonable reliability and recovery capabilities. Each entry is assigned a unique ID. All entries in the database are maintained in a single index file, keyed by this ID. Given an ID, the function id2entry() returns the corresponding entry can efficiently for the cost of a single hash table or btree lookup, depending on the choice of the underlying technology. Similarly, The DN to ID mapping is stored in a dn2id index, which is accessed through dn2id() function. IV LDAP caching framework: implementationLDAP query cache
typedef struct cache_manager_s {
unsigned long cache_size;
unsigned long thresh_hi;
unsigned long thresh_lo;
unsigned long num_cached_queries;
int numattrsets;
int numtemplates;
int num_entries_limit;
query_manager* qm;
} cache_manager;
typedef struct query_manager_s {
struct attr_set** attr_sets;
QueryTemplate** templates;
CachedQuery *lru_top;
CachedQuery *lru_bottom;
QCfunc qcfunc;
CRfunc crfunc;
AddQueryfunc addfunc;
} query_manager;
The caching proxy is implemented in the LDAP backend. The ldapinfo structure has been extended to contain a pointer to the cache_manager structure. cache_manager contains cache specific information and configuration parameters like thresholds for cache replacement, number of templates to be cached, maximum number of entries in a cacheable query etc. It also contains a pointer to the query_manager struct which implements the query cache logic. query_manager contains an array of pointers to the query templates, the top and bottom queries in the LRU list and pointers to functions which implement query containment, cache replacement and query add functionality. QueryTemplate structure contains the template string, and a list of queries belonging to the template. Cache Backend
struct CacheBackendDB {
Backend c_backend;
struct berval* cache_be_suffix;
};
struct CacheBackendInfo {
BackendInfo b_info;
char *bi_type;
int (*cache_be_init)(BackendInfo* c);
int (*cache_be_merge) (Backend* bd,
Entry* entry,
char* query_uuid);
int (*cache_be_remove) (Backend *bd,
char* query_uuid);
int (*cache_be_search) (Backend *bd,
struct berval *nbase,
int scope,
Filter *filter,
AttributeName *attrs);
};
The backend in OpenLDAP is extended to provide a cache backend with the cache specific interfaces. The structure CacheBackendDB contains instance specific cache backend information. The cache_be_suffix member is the suffix of all entries stored in the cache backend. CacheBackendInfo structure contains cache backend type specific information. It contains pointers to the backend specific implementation of the caching interfaces described in Section II. The mapping between the Cache Backend functions in Section II and these functions is given below.
LDBM Backend extensionsWe have extended the LDBM backend to provide implementation of the cache specific interfaces. The function ldbm_back_merge, provides an implementation of the cache_be_merge interface for LDBM backend. If the entry is already present, it adds any attributes which were not previously stored. Otherwise, it adds the entry to the database. A value representing the query ID of the query, for which the entry is being merged, is added for a cache specific operational attribute query_id . The function ldap_back_rm_query implements the cache_be_remove interface. It provides functionality to remove entries having a particular query ID in their query_id attribute from the cache. The least recently used query is removed from the cache. V Usage instructionsThe document usage.ps included in the LDAP cache package contains user instructions on configuring and using the LDAP cache. VI References[1] "Lightweight Directory Access Protocol (v3), RFC 2251". [2] "Lightweight Directory Access Protocol (v3): Attribute Syntax Definitions, RFC 2252". [3] OpenLDAP Administrator's Guide [4] Qiong Luo, Jeffrey F. Naughton, Rajasekar Krishnamurthy, Pei Cao, and Yunrui Li, "Active Query Caching for Database Web Servers", WebDB'2000. Author contact: For any queries please contact: Apurva Kumar IBM India Research Lab +91-11-6861100 kapurva@in.ibm.com |
LDAP proxy cache: User ManualThe package contains the following files:
To use the OpenLDAP server as a query cache, first go through README and INSTALL files. Successful installation will convert the LDAP (proxy) backend of slapd into a caching proxy and extend the LDBM backend for caching. Typical usage scenariosA simple LDAP proxy cache setup is shown below:
+----------+ +-----------+
| | | |
+------------+ | OpenLDAP | | Backend |
|LDAP client |<---->| based |<----->| LDAP |
+------------+ | proxy | | server |
| cache | | |
+----------+ +-----------+
The client application could be a command line tool such as ldapsearch or Netscape browser address book etc. All requests from the client are directed to the proxy. A typical configuration for a directory based web application is shown in the figure below:
+---------------+ HTTP +-----------+
|client(browser)|<---->| Web app |
+---------------+ | server |
+-----------+
JNDI/other | +-------------+ +----------+
LDAP +--->|OpenLdap | |Backend |
API |based proxy | LDAP |LDAP |
|cache |<---->|server |
+-------------+ +----------+
The servlet translates the user request into LDAP queries and uses LDAP APIs to send the request to the LDAP proxy. ConfigurationThe LDAP client (could be the end user or a servlet handling the request of an end user) should be configured to send requests to the LDAP proxy cache. The proxy cache is configured using the slapd configuration file slapd.conf. The following example shows how the complete directory tree under o=University of Michigan,c=US served by the backend server can be cached at the proxy.
include $SCHEMA_DIR/example.schema
access to * by write
pidfile $PID_DIR/slapd.pid
argsfile $ARGS_DIR/slapd.args
database ldap
uri ldap://<backend_server_url>:389
suffix "o=University of Michigan, c=US"
cacheparams 1000000 10000 12000 6 10
attrset 0 cn
attrset 1 sn
attrset 2 cn sn
attrset 3 mail
attrset 4 cn sn mail
attrset 5 cn sn mail telephonenumber
addtemplate (cn=) 1
addtemplate (cn=) 5
addtemplate (mail=) 0
addtemplate (&(cn=)(objectclass=)) 2
addtemplate (&(description=)(cn=)) 4
cachesuffix "o=University of Michigan, c=US" ldbm
directory $DB_FILES_DIR
cachesize 2000
dbcachesize 150000
index default pres,eq
index objectclass
index templates
index uid eq
Line 5 defines an LDAP proxy cache backend. The suffix is set to o=University of Michigan, c=US. All the queries with bases in the subtree rooted at the suffix are served by the ldap? backend. Line 6 makes the proxy point to the backend server. The cacheparams directive sets some cache related parameters. It has the following syntax:
cacheparams <cache_capacity> <lo_thresh> <hi_thresh>
<num_attr_sets> <cacheable_limit>
The hi_thresh is the threshold in bytes after which the cache replacement is invoked. Cache replacement removes queries on LRU basis till the cache size reaches lo_thresh. num_attr_sets is the number of distinct sets of attributes which can be used in cacheable queries. cacheable_limit is a limit on the number of entries returned for a query for it to be cacheable. The attrset directive specifies a set of cacheable attributes:
attrset <index> <list of attributes>
where index ranges from 0 to (num_attr_sets -1) and list_of_attributes specifies a set of cacheable attributes. The addtemplate directive specifies a query template to be cached along with the projected attributes: addtemplate <query_template> <attr_set_index> where query_template is a string representing the query template written in the search filter form of RFC 2254 and attr_set_index is the index (0 to num_attr_sets -1) representing the projected attributes of the query. At present only positive conjunctive queries are cached. Finally, the cachesuffix directive defines the backend which provides the cache store and initializes its suffix. The syntax is: cachesuffix <cache_suffix> <backend> cache_suffix is the suffix for cached entries for the backend. Currently only ldbm can function as a cache backend. Example:The proxy server is started by the command slapd -d <debug_level> -f slapd.conf and it is made to point to ldap://<backend_server_address>389. Now if the following search operation is requested: ldapsearch -H ldap://<proxy_server_address> -b "o=University of Michigan,c=US" "(cn=Roger*)" mail If the number of entries returned are less than the cacheable limit (10 entries in this case), then the result of this query is cached. A subsequent query like the one below which is contained in this query can then be answered from the proxy cache without contacting the backend. ldapsearch -H ldap://<proxy_server_address> -b "o=University of Michigan,c=US" "(cn=Roger Norman)" mail The cache provides query containment for equality, range and substring queries. Author contact: For any queries please contact: Apurva Kumar IBM India Research Lab +91-11-6861100 kapurva@in.ibm.com |