[Date Prev][Date Next] [Chronological] [Thread] [Top]

RE: Proxy cache extension for OpenLDAP

LDAP proxy cache docs in HTML.

(See attached file: ldapcache.html)(See attached file: usage.html)

The package can be accessed from

Apurva Kumar,
Research Staff Member,
IBM India Research Lab
Phone: +91-11-6861100
Fax: +91-11-6861555

Title: LDAP proxy cache

Design and Implementation of an LDAP Caching Framework

Abstract- 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 Introduction

To 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: Design

Figure1 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
  • LDAP protocol engine: Provides the protocol funtionality of LDAP server. Handles various LDAP operation requests. Passes the search operation request to the Cache Manager.
    • handle_operation: handles client operation requests.
    • send_search_result: sends search results to the client.
  • Proxy cache manager: Answers the search request by either contacting the origin directory server or the local cache backend. Implements query caching algorithms for query containment and cache replacement. Stores the semantic information for the cached queries.
    • handleQuery: main procedure described below which handles a client query
    • query_containment: returns TRUE if query can be answered. add_query: adds a query to the query cache.
    • remove_query: removes a query from the query cache.
    • cache_replace: uses a cache replacement algorithm to find the query to be removed from the cache.
  • Cache Backend: Provides cache manager with an interface to the local cache. Implements cache specific interfaces for merging results returned from remote server, removing queries, etc.
    • search: performs a local cache search, returns matching entries.
    • remove_query: removes entries belonging only to a particular query.
    • merge_query: merges the result of a query returned from the remote server.
	    CacheManager::handleQuery (request) {
		  operation = request.operation
		  if (operation != search) {
		      ldap.operation(request, server)
		  if (query_containment (request) == TRUE) {
		      entries = cache_be.search(request)
		  else {
		      entries = ldap.search(request,server)
		      query = request.query
		      if  (cache_size > hi_thresh) {
			  while (cache_size > lo_thresh) {
			      query1 = cache_replace( )
			      cache_be.remove_query (query1)

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 Server

OpenLDAP [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:

		struct BackendDB {
				BackendInfo	   *bd_info;
				BerVarray      	be_suffix;
			AccessControl *be_acl; 
			// other members
		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 functions

The following utility functions are provided common to all backends.

  • test_filter(Filter* f, Entry* e): Tests whether an entry satisfies a given filter. Returns TRUE or FALSE.
  • send_search_result: Sends search results to the client.

LDBM Backend

LDBM 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: implementation

LDAP 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.

  • cache_be.merge_query --> cache_be_merge: to be called once for each entry of the query.
  • cache_be.remove_query --> cache_be_remove.
  • cache_be.search --> cache_be_search.

LDBM Backend extensions

We 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 instructions

The 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
Title: LDAP proxy cache

LDAP proxy cache: User Manual

The package contains the following files:

  • README: brief information about LDAP cache.
  • INSTALL: installation instructions.
  • COPYRIGHT:copyright notice.
  • usage.ps: contains usage instructions.
  • ldapcache.ps: Design and Implementation of the LDAP caching solution.
  • proxy_cache_patch_2.1.4: LDAP proxy cache patch for OpenLDAP2.1.4.

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 scenarios

A 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.


The 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.


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