I have a "thread" branch on ssh://ada.openldap.org/~hyc/OD/head/.git
preliminary patches to improve multi-threaded indexing in back-mdb slapadd. So
far the scale of improvement is small, but there may be ways to enhance it
further from here.
Currently back-mdb's multi-threaded indexing code is largely copied from
back-bdb/hdb, and it is always slower than regular single-threaded slapadd.
The slowdown comes from a number of reasons.
1) Thread synchronization overhead is huge. Much greater than the actual
cost of index processing.
2) Index processing is awkward since MDB doesn't support multi-threaded
writes (while BDB does).
1) is because we're using cond_wait/cond_broadcast to perform synchronization,
and that requires every waiting thread to successfully acquire the condition
mutex before progressing any further. So it is inherently serial, even using
cond_broadcast. Also, we're doing this twice, once to start all of the index
processing for an entry, and once at the end of index processing. The latter
one is required so that we will know it's safe to dispose of the current entry
and move on to the next.
The new code uses a single pthread_barrier for synchronization, and it is only
used at the start of index processing. Index cleanup is deferred, and all of
the relevant data is double-buffered. This allows us to only need to worry
about the start of processing; the processing can take as long as it needs.
This restructure requires a small change in slapadd as well, to maintain two
Entry pointers instead of just one, and free them in a staggered fashion. The
back-bdb/hdb threaded indexer can also be restructured along these lines for a
2) Index results were being gathered in several malloc'd structures and then
individually freed after being written to the DB. Now I'm using sl_malloc, and
simply resetting the memctx between entries, thus eliminating all cost of
These changes are sufficient to bring multithreaded performance down to just
on par with single-threaded slapadd. In fact there's very little to gain here
when all of the DB writes are still single-threaded.
One further tweak: most of our index keys are 4-byte hash values. Using the
MDB_INTEGERKEY flag allows them to be compared word-at-a-time instead of
byte-at-a-time, which gives a further speedup. At present this is the most
With the original back-mdb code currently in git master, slapadd of our test
LDIF (4.9GB, 6326513 entries, 31 indexed attributes) was taking 1h50m on ada.
(Using -q. Without -q, 2h46m.)
With no indexing, it takes only 9m11s. Even though sizewise indices don't
account for much, they cost a lot in numbers of keys. 6M entries means 6M keys
in the id2entry DB and 12M keys in the dn2id DB. Indexing on 31 attributes
with multiple values, substrings, and other such parameters thrown in, amounts
to hundreds of millions of keys, and each of these needs multiple comparisons
to be inserted into their proper index.
I tried a further hack on MDB_APPEND to eliminate some more of this overhead.
Currently, MDB_APPEND only affects the behavior of mdb_page_split, causing the
newly added key to simply be added as the first node of a new page rather than
splitting the existing page in half and copying half of the keys to the new
page. (This in itself is a pretty major speedup for slapadd, but obviously
already factored in.) The new code also simply appends new keys to the end of
the DB's last page (rather than searching for its insertion point), which
again is useful for eliminating unnecessary comparisons. This is only
effective when adding an entryID to an already existing index key. This
brought the slapadd -q time down to 1h46m.
Turning on the MDB_INTEGERKEY flag brought the slapadd -q time down to 1h32m.
Adding the threading rewrite to that, the time came down to 1h29m with
tool-threads set to 4. Using more threads actually slows things down, again
because thread synchronization becomes too expensive.
Only the index key generation is being done in the extra threads, and the
reality is that index key generation is not a very significant cost in the
But anyway, some of the work done here can be ported back into back-bdb/hdb to
improve things there. In particular, the use of two synchronization events per
entry can be reduced to one by adding double-buffering there too. And some
malloc/free overhead in the index threads can be removed by using sl_malloc in
each thread. Of course we first need to add pthread_barrier detection to the
configure script, as well as wrapper functions in libldap_r.
(Anyone interested in handling this? And writing the compatibility code for
In the meantime, I'm considering an MDB environment option to support multiple
threads in a single write TXN, as long as each thread is operating on separate
databases. This would hopefully allow us to further distribute the load of
indexing without adding too much new complexity to libmdb.
If you have an account on ada.openldap.org
I encourage you to checkout this
code and think about what's suitable to merge back into master.
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/