Re: LDAP Performance (long)

Your post has tickled a nagging question I have had for a while.
How do OpenLDAP indexes work? This started as a short post, but
it has grown.

In a nutshell to increase OpenLDAP performance you want to:
Reduce the number of queries sendmail makes.
Create indexes of the attributes you search on.
Cache the slapd's internal database lookups in slapd memory.
Turn off slapd logging.


I) Reduce The Number of LDAP Queries

Something that I teach in both my Managing Internet Mail" and
Advanced Topics In Sendmail" class is what I call "Subtractive
Performance Tuning". One way to tune performance is to find a
bottle neck and add more stuff to it; disks, raid, memory, etc...
A different way is to find a bottle neck and remove un-necessary
activity on the bottle neck. If /var/spool/mqueue is the I/O
bottle neck and it is part of the partition /var, then any other
activity on /var, logging, other spooling, tmp files, take away
performance from /var/spool/mqueue. So install an extra disk
and move all of /var except /var/spool/mqueue to the slower disk.
This will increase the performance of /var/spool/mqueue.

The same thing is true of LDAP queries. If you can eliminate
un-necessary LDAP queries, you can increase the LDAP performance.

With the access map this is fairly simple. In the check_relay,
check_mail, and check_rcpt rulesets sendmail makes two queries for
each lookup. The first is the new TAG:key lookup, the second is
the plain key lookup without a tag for backwards compatibility.
If you can live without backwards compatibility, then you can cut
the number of access map lookups by at least a third with a simple
rule addition to two internal (to the .cf file) rulesets, rulesets
D and A.

Both of these use a workspace that has 4 sets of angle brackets
(focus). The third focus contains a mark, "+" or "!" and a
lookup tag. If the mark is "+", then the ruleset will lookup
both TAG:key and key by itself. If the mark is "!", then the
ruleset will only lookup TAG:key. So by inserting a rule at the
beginning of the rulesets D an d A that replaces the "+" mark with
the "!" mark, sendmail will only lookup the TAG:key. To do this I
take advantage of the feature that if you define a ruleset twice,
the rules in the second definition will be added to the rules added
with the first definition. I use the tag LOCAL_CONFIG to pre-pend
the conversion rule to the beginning of each ruleset.

So add to your host.mc file:

`LOCAL_CONFIG'
`# added with LOCAL_CONFIG'

`SD'
`# convert +tag to !tag to only lookup tag:key and not key by
itself'
`R<$*> <$+> < + $-> <$*> $: <$1> <$2> < ! $3> <$4>'
`# $1 $2 + $3 $4 <tabs>'

`SA'
`# convert +tag to !tag to only lookup tag:key and not key by
itself'
`R<$*> <$+> < + $-> <$*> $: <$1> <$2> < ! $3> <$4>'
`# $1 $2 + $3 $4 <tabs>'

Remember to change the spaces between the LHS and the RHS with tabs.

Be aware that if you go into address test mode, you will get three
errors:
Warning: OperatorChars is being redefined.
It should only be set before ruleset definitions.
WARNING: Ruleset D has multiple definitions
WARNING: Ruleset A has multiple definitions
These are OK and do not affect the operation of the ruleset additions.


II) OpenLDAP Indexes and Cache

General rule: index attributes you frequently search for.

You want to index the attributes that sendmail queries.
Normally OpenLDAP stores its data in a Berkeley BTree database
which while very flexible is also very slow. A number of posts
have mentioned extracting the data into a local hash/key database.
While it would work and would give the best performance, it
also aversely impacts one of the big benefits of using LDAP,
namely centralized administration. A change or addition to LDAP
would not be picked up by the sendmail server until the data was
extracted and the hash/key database was rebuilt. How often do you
do that? Once a day? Once an hour? Every 5 minutes? The better
solution is to have OpenLDAP maintain and use an index database.
I had understood that these were hash/key databases, but having
just generated a few indexes, I see that they are btree databases.
I believe that they are single leaf level btree databases which makes
them functionally equivalent to a hash/key database. (Any database
people out there, is this correct?)

Now the documentation for indexing for OpenLDAP is scant. So here
is my understanding of how they work:

The index statement in the slapd.conf file states what attributes
you want to index and the relationship you want to index. You can
either have a separate index entry for each attribute, or you can
combine multiple attributes with the same relationship types.

I.e:
index cn pres,eq
index sn pres,eq
Is the same as:
index cn,sn pres,eq
They both will generate two databases: cn.dbb and sn.dbb

In your slapd.conf file start with the standard indexes:
index objectClass eq
index cn pres,eq
index sn pres,eq

Next, add the LASER indexes:
index mailLocalAddress,mailRoutingAddress,mailHost pres,eq

Now for the sendmail schema, start with the generic sendmail attribute:
index sendmailMTACluster,sendmailMTAHost,sendmailMTAKey
pres,eq

For the aliases objects:
index sendmailMTAAliasGrouping,sendmailMTAAliasValue pres,eq

For the database objects:
index sendmailMTAMapName,sendmailMTAMapValue pres,eq

For the class objects:
index sendmailMTAClassName,sendmailMTAClassValue pres,eq

After adding or changing any index statement in slapd.conf,
you need to stop slapd and run slapindex to rebuild the indexes.
After rebuilding the indexes, you can restart slapd.

Now, I am not sure if the returned value parts
need to be index. These include: mailRoutingAddress,
mailHost, sendmailMTAAliasValue, sendmailMTAMapValue, and
sendmailMTAClassValue. I think it is a question of what the
indexes contain. Do they contain a traditional key/value pair, i.e.
key mailLocalAddress, value mailRoutingAddress? Or do they contain a
pointer to the unique identifier, UID, that matches the key? In the
first case the index lookup of a mailLocalAddress would return the
mailRoutingAddress directly. In the second case, the index lookup
would return the UID that matched the mailLocalAddress. That UID
would then be used to query the associated mailRoutingAddress.
(Any LDAP experts out there, are either of these correct?) In
either case, I don't think the returned value parts are needed.
(is this correct?)

As I said, indexes in OpenLDAP are not described very well.


III) OpenLDAP Cache

The cachesize statement for LDBM databases specifies the number
entries that will be stored at any one time in the in-memory cache.
The default is 1000 entries. Increase this by *a lot*

A first pass guesstimate would be to take the number distinguished
names, DNs, that sendmail might be able to query and multiply it
by 2 or 3. i.e. I have 1000 users, so 10,000 mailLocalAddress.
I have an access map with 50,000 entries, I have an an aliases
file with 4,000 entries, and the rest of the maps and classes are
pocket change.

So:
10,000 + 50,000 + 4,000 = 64,000 * 3 = 192,000
Rounded to a nice 200,000 results in:
cachesize 200000

The dbcachesize statement for LDBM databases specifies the size in
bytes of the in-memory cache associated with each open index file.
The default is 100Kb.

From the OpenLDAP documentation:
"Increasing this number uses more memory but can cause
a dramatic performance increase, especially during modifies
or when building indicies."

Again, a first pass guesstimate would be to look at the size of your
index databases:
ls -l /var/lib/ldap/*.dbb
Or better yet:
du /var/lib/ldap/*.dbb
(although newdb is very good about compacting the database files,
they are not sparsely populated)

So if my largest database is 3.2Mb, then I would use
dbcachesize 32000000

Do not be afraid of allocating memory for slapd. If the server is
strictly a slapd server, then I would use 50% or more of the memory
for cache. If the server is a sendmail server with a local private
slapd server, then I would recommend using 10% - 20% of the memory
for cache.

If the system does not have a lot of physical memory, then add more.
Memory is cheap these days. I would recommend at least 1/2 a Gig,
1 or 2 Gigs is better. Memory is like gas in your car. Too much
does not do anything, nor does it hurt. It is when you run out
that the problems start.

What you do not want to do is exceed physical memory. Paging is
evil for slapd, I suspect far worse than not using cache and
reading the data directly from disk. The problem with slapd is
that like name, slapd's memory utilization is not well localized.
One ldap request is unlikely to be related to the next ldap request.
So if the system is paging, the likelihood of a page fault is high.

For a more detailed explanation of how to size the cache parameters
check the OpenLDAP FAQ-O-Matic:
http://www.openldap.org/faq -> OpenLDAP Software FAQ ->
Configuration -> SLAPD Configuration -> Performance Tuning
->
How do I determine the proper BDB/HDB database cache
size
Can I tune the LDBM entry and index caches


IV) Indexes, Cache, and slapd Debugging Output.

To find out more, I tried dumping the index file with db_dump,
but it was less than useful. It told me that that the database
was a btree database, but then it listed a bunch of octal data.

I next turned on slapd debug flag 1, trace function calls, and found
more interesting information. What you look for is ldbm_cache_open
and cache_find_entry_id.

With ldbm_cache_open what you look for is the lack of
ldbm_cache_open. If you make a query, and there are indexes
available for the query, you directly get a hit or a miss:

Hit:
Apr 4 02:25:54 ldap1 slapd[1015]: => ldbm_cache_open( "mailLocalAddress.dbb", 9, 600 )
Apr 4 02:25:54 ldap1 slapd[1015]: <= ldbm_cache_open (opened 4)
Apr 4 02:25:54 ldap1 slapd[1015]: => key_read
Apr 4 02:25:54 ldap1 slapd[1015]: <= index_read 1 candidates
Apr 4 02:25:54 ldap1 slapd[1015]: <= equality_candidates 1
Apr 4 02:25:54 ldap1 slapd[1015]: <= filter_candidates 1
Apr 4 02:25:54 ldap1 slapd[1015]: <= list_candidates 1
Apr 4 02:25:54 ldap1 slapd[1015]: <= filter_candidates 1
Apr 4 02:25:54 ldap1 slapd[1015]: <= list_candidates 1
Apr 4 02:25:54 ldap1 slapd[1015]: <= filter_candidates 1

Miss:
Apr 4 03:12:49 ldap1 slapd[1015]: => ldbm_cache_open( "mailLocalAddress.dbb", 9, 600 )
Apr 4 03:12:49 ldap1 slapd[1015]: <= ldbm_cache_open (cache 4)
Apr 4 03:12:49 ldap1 slapd[1015]: => key_read
Apr 4 03:12:49 ldap1 slapd[1015]: <= index_read 0 candidates
Apr 4 03:12:49 ldap1 slapd[1015]: <= equality_candidates NULL
Apr 4 03:12:49 ldap1 slapd[1015]: <= equality_candidates 0
Apr 4 03:12:49 ldap1 slapd[1015]: <= filter_candidates 0
Apr 4 03:12:49 ldap1 slapd[1015]: <= list_candidates 0
Apr 4 03:12:49 ldap1 slapd[1015]: <= filter_candidates 0
Apr 4 03:12:49 ldap1 slapd[1015]: <= list_candidates NULL
Apr 4 03:12:49 ldap1 slapd[1015]: <= filter_candidates 0

Without ldbm_cache_open, what you will see is a recursive checking of
any
entry that might match the filter, i.e the attribute you are looking
for:
Apr 4 03:06:17 ldap1 slapd[1015]: => equality_candidates
Apr 4 03:06:17 ldap1 slapd[1015]: <= equality_candidates: index_param returned=18
Apr 4 03:06:17 ldap1 slapd[1015]: <= filter_candidates 19
Apr 4 03:06:17 ldap1 slapd[1015]: <= list_candidates 19
Apr 4 03:06:17 ldap1 slapd[1015]: <= filter_candidates 19
Apr 4 03:06:17 ldap1 slapd[1015]: <= list_candidates 8
Apr 4 03:06:17 ldap1 slapd[1015]: <= filter_candidates 8

Apr 4 03:29:35 ldap1 slapd[1075]: ====> cache_return_entry_r( 3
): created (0)
Apr 4 03:29:35 ldap1 slapd[1075]: => id2entry_r( 3 )
Apr 4 03:29:35 ldap1 slapd[1075]: ====> cache_find_entry_id( 3 )
"ou=sendmail,dc=gadget,dc=com" (found) (1 tries)
Apr 4 03:29:35 ldap1 slapd[1075]: <= id2entry_r( 3 ) 0x817ba20
(cache)
Apr 4 03:29:35 ldap1 slapd[1075]: ldbm_search: candidate 3 does
not match filter
Apr 4 03:29:35 ldap1 slapd[1075]: ====> cache_return_entry_r( 3
): returned (0)

Apr 4 03:29:35 ldap1 slapd[1075]: => id2entry_r( 4 )
Apr 4 03:29:35 ldap1 slapd[1075]: => ldbm_cache_open(
"id2entry.dbb", 9, 600 )
Apr 4 03:29:35 ldap1 slapd[1075]: <= ldbm_cache_open (cache 1)
Apr 4 03:29:35 ldap1 slapd[1075]: => str2entry
Apr 4 03:29:35 ldap1 slapd[1075]: <=
str2entry(sendmailMTAClassName=R, ou=sendmail, dc=gadget, dc=com) -> -1
(0x8183de8)
Apr 4 03:29:35 ldap1 slapd[1075]: <= id2entry_r( 4 ) 0x8183de8
(disk)
Apr 4 03:29:35 ldap1 slapd[1075]: => send_search_entry:
"sendmailMTAClassName=R, ou=sendmail, dc=gadget, dc=com"
Apr 4 03:29:35 ldap1 slapd[1075]: <= send_search_entry
Apr 4 03:29:35 ldap1 slapd[1075]: ====> cache_return_entry_r( 4
): created (0)

Etc, for the next 6 filter_candidates...

With cache_find_entry_id what you look for are cache hits and misses:

Hit:
Apr 4 02:26:30 ldap1 slapd[1015]: => id2entry_r( 16 )
Apr 4 02:26:30 ldap1 slapd[1015]: ====> cache_find_entry_id( 16 ) "uid=harker,ou=foo.com,dc=gadget,dc=com" (found) (1 tries)
Apr 4 02:26:30 ldap1 slapd[1015]: <= id2entry_r( 16 ) 0x817c948 (cache)
Apr 4 02:26:30 ldap1 slapd[1015]: => send_search_entry:
"uid=harker,ou=foo.com,dc=gadget,dc=com"
Apr 4 02:26:30 ldap1 slapd[1015]: <= send_search_entry
Apr 4 02:26:30 ldap1 slapd[1015]: ====> cache_return_entry_r( 16
): returned (0)

Miss:
Apr 4 02:25:54 ldap1 slapd[1015]: => id2entry_r( 16 )
Apr 4 02:25:54 ldap1 slapd[1015]: => ldbm_cache_open( "id2entry.dbb", 9, 600 )
Apr 4 02:25:54 ldap1 slapd[1015]: <= ldbm_cache_open (cache 1)
Apr 4 02:25:54 ldap1 slapd[1015]: => str2entry
Apr 4 02:25:54 ldap1 slapd[1015]: <=
str2entry(uid=harker,ou=foo.com,dc=gadget,dc=com) -> -1 (0x817c948)
Apr 4 02:25:54 ldap1 slapd[1015]: <= id2entry_r( 16 ) 0x817c948
(disk)
Apr 4 02:25:54 ldap1 slapd[1015]: => send_search_entry:
"uid=harker,ou=foo.com,dc=gadget,dc=com"
Apr 4 02:25:54 ldap1 slapd[1015]: <= send_search_entry
Apr 4 02:25:54 ldap1 slapd[1015]: ====> cache_return_entry_r( 16
): created (0)

Putting the above together. Indexes reduce the number of database
lookups that slapd needs to make in order to answer the query and the
cache keeps the database lookup in slapd server memory. A by product
of indexes is that they reduce the extraneous database lookups
that are made and thus increase the effectiveness of the cache.


V) Turn Off Slapd Logging.

"Slapd logging, just say no"

I know this is obvious, but unless you are trying to debug something,
turn slapd's logging off. Slapd's logging is very much like
sendmail's debug flags, less is more. If you turn all the logging
flags on, logging -1, then a single LDAP query normally will result
in at least 250 lines of output and can generate over 1,000 lines
of logging output. So in your slapd.conf file use:

loglevel 0

Rather long winded, but I hope this helps

RLH

For info about our "Managing Internet Mail, Setting Up and Trouble
Shooting sendmail and DNS" and "Advanced Topics In Sendmail:
Performance Tuning, LDAP Integration and Spam Control" seminars,
and a schedule of dates and locations, please send email to
info@xxxxxxxxxx, or visit www.harker.com

.

Relevant Pages

  • Re: Same database or another?
    ... that I have used the lookup wizard provided. ... if I choose to add tables to database that have absolutely no relation to ... >> work toward the capture of the feral animals. ...
    (microsoft.public.access.tablesdbdesign)
  • Re: Database design question
    ... and what he is talking about is a single code ... Pro SQL Server 2000 Database Design ... > dont know the details of the lookup data. ... > What do we then do with the more "unknown" user-defined lookup data. ...
    (microsoft.public.sqlserver.programming)
  • Re: Lookup Tables and Field Validation Rule Properties
    ... I am in the process of designing my first database and plan to use this ... employees data and track down employees personal info, ... The tables in my original design contained many lookup fields but after ... The other question I asked was, instead of setting the above validation in the table level, can't I implement it in the Form Level. ...
    (microsoft.public.access.gettingstarted)
  • Re: Cache-Size vs Performance
    ... logarithmic decrese in the miss rate as the cache size grows ... in big database applications ... ... where the database uses real storage to compensate for disk record ... database people in stl/bldg90 and the relational/sql system/r people ...
    (comp.arch)
  • Re: Running queries on large data structure
    ... ugly to convert it into some relational shape for the database) ... of time when reloading them from disk but YMMV and you would have to ... pickle it and load it later and work on the data? ... My data layer checks the cache ...
    (comp.lang.python)