Bug 469800 - Slow import post-processing with large number of non-leaf entries
Slow import post-processing with large number of non-leaf entries
Status: CLOSED CURRENTRELEASE
Product: 389
Classification: Community
Component: Database - Import/Export (Show other bugs)
1.1.3
All Linux
medium Severity medium
: ---
: ---
Assigned To: Noriko Hosoi
Chandrasekar Kannan
:
Depends On:
Blocks: 249650 FDS1.1.4 FDS1.2.0
  Show dependency treegraph
 
Reported: 2008-11-03 22:00 EST by Thomas Lackey
Modified: 2015-01-04 18:34 EST (History)
4 users (show)

See Also:
Fixed In Version: 8.1
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2009-04-29 19:07:33 EDT
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)
Proposed patch (7.06 KB, patch)
2008-11-03 22:04 EST, Thomas Lackey
no flags Details | Diff
cvs diff ldap/servers/slapd/back-ldbm/ancestorid.c (10.50 KB, patch)
2008-12-01 16:45 EST, Noriko Hosoi
no flags Details | Diff
cvs commit message (1.36 KB, text/plain)
2008-12-03 14:17 EST, Noriko Hosoi
no flags Details
sample ldif file to reproduce the problem (15.93 KB, text/plain)
2009-01-15 16:17 EST, Noriko Hosoi
no flags Details
cvs diff ldapserver/ldap/servers/slapd/back-ldbm/ancestorid.c (1.70 KB, patch)
2009-01-15 16:25 EST, Noriko Hosoi
no flags Details | Diff
cvs commit message (799 bytes, text/plain)
2009-01-15 17:45 EST, Noriko Hosoi
no flags Details

  None (edit)
Description Thomas Lackey 2008-11-03 22:00:08 EST
Description of problem:

Import post-processing of large databases is extremely slow when they contain a large number of non-leaf entries.  This slowness is centered in the creation of the ancestorid index.

Version-Release number of selected component (if applicable):

1.1.3

How reproducible:

Always.

Steps to Reproduce:

1.  Create a large LDIF to import, something with 1 million entries or more where many of the entries have children.  In this test, approximately 1/10 of the entries were placed directly beneath the suffix and the other 9/10 were child entries evenly distributed beneath them.  Eg:

  dn: cn=MyEntry0, <suffix>
  ...

  dn: cn=Child0, cn=MyEntry0, <suffix>
  ...

  dn: cn=Child1, cn=MyEntry0, <suffix>
  ...

2. Import with ldif2db.

3. Watch the amount of time spent in the post-processing phase of the import and the difference in the final import rate when compared to the last rate from the import phase.
  
Actual results:

The post-processing time is inordinate to the import time.

[30/Oct/2008:11:22:48 -0500] - import userRoot: Processed 1059199 entries -- average rate 5725.4/sec, recent rate 5565.0/sec, hit ratio 100%
...
[30/Oct/2008:11:22:56 -0500] - import userRoot: Indexing complete.  Post-processing...
...
[30/Oct/2008:11:31:09 -0500] - import userRoot: Import complete.  Processed 1100009 entries in 686 seconds. (1603.51 entries/sec)

This import took 11m31s according to 'time', of which 7m38s was spent post-processing.  This dropped the average rate from 5700 entries/s to 1600 entries/s.

This difference becomes even more pronounced with larger databases.  Importing a very large database on another machine averaged 11k entries/s until post-processing, where the final rate ended at only 283 entries/s.

Expected results:

Building the ancestorid index does not need to be so expensive, since the information is available from the parentid index.  The cost is associated with general overhead in maintaining the IDLists in memory, and in particular to the constant unions done on them to add children.  When these lists may contain millions of entries, the time spent copying the existing data when inserting children is prohibitively expensive.  This does not affect all layouts equally, but does cause problems when large numbers of children are dispersed throughout the tree.

Additional info:

BDB can usually handle inserts efficiently on its own, so it is not necessary to maintain complete IDLists in memory for all the entries and write them out in total.  Updates can be performed directly to the DB instead.

This example is on the same hardware using the same LDIF, but using code that does not maintain all the IDLists in memory and calls through to idl_new_store_block() to perform updates incrementally.

[30/Oct/2008:12:02:45 -0500] - import userRoot: Processed 1042117 entries -- average rate 5633.1/sec, recent rate 5752.4/sec, hit ratio 100%
...
[30/Oct/2008:12:02:56 -0500] - import userRoot: Indexing complete.  Post-processing...
...
[30/Oct/2008:12:03:51 -0500] - import userRoot: Import complete.  Processed 1100009 entries in 251 seconds. (4382.51 entries/sec)

The total time for this run was 4m17s, of which only 30s was post-processing.

Most importantly, 'dbscan -r -f ancestorid.db4' shows identical contents:

> md5sum ancestorid.db4.dbscan.prefix ancestorid.db4.dbscan.postfix
7cb9cf17bb45a0e6960dccf17fb45a56 *ancestorid.db4.dbscan.prefix
7cb9cf17bb45a0e6960dccf17fb45a56 *ancestorid.db4.dbscan.postfix
Comment 1 Thomas Lackey 2008-11-03 22:04:48 EST
Created attachment 322386 [details]
Proposed patch

This proposed patch uses a new function, ldbm_ancestorid_new_idl_create_index(), to create the index when idl_get_idl_new() is true.  The existing code is used otherwise.

This is the code reference in the decription.
Comment 2 Noriko Hosoi 2008-12-01 13:53:52 EST
Thank you so much for the patch, Thomas.  Your proposed patch looks excellent.

I imported I million entry ldif files with and without your patch.  I repeated twice each.  Each time, import with the patch ran faster:
Original:
Processed 1000006 entries in 37316 seconds. (26.80 entries/sec)
Processed 1000006 entries in 37593 seconds. (26.60 entries/sec)

With Thomas's patch
Processed 1000006 entries in 36259 seconds. (27.58 entries/sec)
Processed 1000006 entries in 37100 seconds. (26.95 entries/sec)

Note: I used the ldif file generated by dbgen.pl, which has 5 organizational units and 1 million user entries are under them.

I also ran import with valgrind.  There is no leak observed.
Comment 3 Thomas Lackey 2008-12-01 14:41:56 EST
Very welcome!

One quick thing, looking at your numbers, I think we may have laid out our LDIF files differently.  In my case, for a million entries, there would be about one hundred thousand entries each of which having about nine children.  The problem increases in magnitude as you get that well-dispersed tree, with lots of children in lots of locations.
Comment 4 Noriko Hosoi 2008-12-01 14:57:06 EST
Right. My test ldif file is not an ideal test case to show the benefit from your patch.  But at least, it could show a typical topology has a gain, as well!
Comment 5 Rich Megginson 2008-12-01 16:12:10 EST
Thomas, we will require you to submit a CLA.  http://directory.fedoraproject.org/wiki/Contributing - it's all done online now.  I don't know if you were covered under the original Bozeman Pass agreement, but it will make our lives easier if you could just submit the online CLA.  Thanks and sorry for the inconvenience.
Comment 6 Rich Megginson 2008-12-01 16:24:32 EST
https://bugzilla.redhat.com/attachment.cgi?id=322386&action=diff#fedora-ds-base-1.1.3.pristine/ldap/servers/slapd/back-ldbm/ancestorid.c_sec3 line 436 and line 477

the id type is defined 
/*
 * the id used in the indexes to refer to an entry
 */
typedef u_int32_t	ID;

we should use this type instead of u_long, and use %u instead of %lu
Comment 7 Noriko Hosoi 2008-12-01 16:45:10 EST
Created attachment 325304 [details]
cvs diff ldap/servers/slapd/back-ldbm/ancestorid.c

The file has more places using u_long for ID.

All of them should be replaced?
Comment 8 Rich Megginson 2008-12-01 16:51:26 EST
(In reply to comment #7)
> Created an attachment (id=325304) [details]
> cvs diff ldap/servers/slapd/back-ldbm/ancestorid.c
> 
> The file has more places using u_long for ID.
> 
> All of them should be replaced?

argh - ideally yes, but I don't want to get lost in the rat hole of fixing all of these legacy problems - how many are there?

Also, you don't need to the cast - remove the (ID) cast from variables that are already of type ID - casting is bad unless absolutely necessary
Comment 9 Noriko Hosoi 2008-12-01 16:55:47 EST
(In reply to comment #8)
> (In reply to comment #7)
> > Created an attachment (id=325304) [details] [details]
> > cvs diff ldap/servers/slapd/back-ldbm/ancestorid.c
> > 
> > The file has more places using u_long for ID.
> > 
> > All of them should be replaced?
> 
> argh - ideally yes, but I don't want to get lost in the rat hole of fixing all
> of these legacy problems - how many are there?

In addition to the ones you pointed out, there are 6 of them.

> Also, you don't need to the cast - remove the (ID) cast from variables that are
> already of type ID - casting is bad unless absolutely necessary

Yes, I'll clean them up...
Comment 10 Thomas Lackey 2008-12-01 17:10:31 EST
(In reply to comment #8)
> 
> argh - ideally yes, but I don't want to get lost in the rat hole of fixing all
> of these legacy problems - how many are there?
> 
> Also, you don't need to the cast - remove the (ID) cast from variables that are
> already of type ID - casting is bad unless absolutely necessary


Just to mention, for simplicity sake in the patch, I kept the code in the new (ldbm_ancestorid_new_idl_create_index()) and original (now ldbm_ancestorid_default_create_index()) functions as close to identical as possible, hence the casts and the ulongs, which are copied from the original.
Comment 11 Rich Megginson 2008-12-01 17:14:59 EST
(In reply to comment #10)
> (In reply to comment #8)
> > 
> > argh - ideally yes, but I don't want to get lost in the rat hole of fixing all
> > of these legacy problems - how many are there?
> > 
> > Also, you don't need to the cast - remove the (ID) cast from variables that are
> > already of type ID - casting is bad unless absolutely necessary
> 
> 
> Just to mention, for simplicity sake in the patch, I kept the code in the new
> (ldbm_ancestorid_new_idl_create_index()) and original (now
> ldbm_ancestorid_default_create_index()) functions as close to identical as
> possible, hence the casts and the ulongs, which are copied from the original.

Ok.  We've become sensitized to 64-bit issues (e.g. long is 32-bit on x86 and 64-bit on x86_64), so it raises red flags for me to see longs and casts.
Comment 12 Noriko Hosoi 2008-12-03 14:17:14 EST
Created attachment 325584 [details]
cvs commit message

Special thanks to Thomas for the patch and signing CLA.

I've checked in his original patch to CVS HEAD.
Comment 13 Noriko Hosoi 2009-01-15 16:16:18 EST
If the ldif file (to be attached in the next comment) is imported, entry id 24 is not added to the top entry (id = 1).  Entry id 24 is 2 level down from the top entry.

[New ancestorid.c]
=1                                      30
        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29
 30 31 32 
=23                                     1
        24 
=26                                     1
        27 
=8                                      16
        9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 

[Old ancestorid.c]
=1                                      31
	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
=23                                     1
	24 
=26                                     1
	27 
=8                                      16
	9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Comment 14 Noriko Hosoi 2009-01-15 16:17:36 EST
Created attachment 329143 [details]
sample ldif file to reproduce the problem
Comment 15 Noriko Hosoi 2009-01-15 16:25:21 EST
Created attachment 329144 [details]
cvs diff ldapserver/ldap/servers/slapd/back-ldbm/ancestorid.c

Change description:
Fixed ldbm_ancestorid_new_idl_create_index so that the ancestor key has the value including all the descendent ids in the IDlist.  The current code only stores the direct children and their children.
Comment 16 Noriko Hosoi 2009-01-15 17:45:55 EST
Created attachment 329147 [details]
cvs commit message

Reviewed by Rich (Thank you!!)

Checked in into CVS HEAD.
Comment 17 Jenny Galipeau 2009-04-01 13:20:31 EDT
can you please add steps to verify this bug?  simply importing the attached ldif?  what are we to expect for performance?
Comment 18 Noriko Hosoi 2009-04-01 13:39:39 EDT
The test data attached in the comment #14 is from GER test cases.  Since it's passing 100% now, we could say it's covered.

Ger startup(o=ace industry,c=us) 	 100% (1/1) 	  	 
Ger run(o=ace industry,c=us) 	100% (358/358) 	  	 
Ger cleanup 	100% (1/1)
Comment 19 Jenny Galipeau 2009-04-01 13:43:47 EDT
great. thanks Noriko  verified DS 8.1 all supported platforms.
Comment 20 Chandrasekar Kannan 2009-04-29 19:07:33 EDT
An advisory has been issued which should help the problem
described in this bug report. This report is therefore being
closed with a resolution of ERRATA. For more information
on therefore solution and/or where to find the updated files,
please follow the link below. You may reopen this bug report
if the solution does not work for you.

http://rhn.redhat.com/errata/RHEA-2009-0455.html

Note You need to log in before you can comment on or make changes to this bug.