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
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.
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.
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.
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!
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.
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
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?
(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
(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...
(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.
(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.
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.
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
Created attachment 329143 [details] sample ldif file to reproduce the problem
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.
Created attachment 329147 [details] cvs commit message Reviewed by Rich (Thank you!!) Checked in into CVS HEAD.
can you please add steps to verify this bug? simply importing the attached ldif? what are we to expect for performance?
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)
great. thanks Noriko verified DS 8.1 all supported platforms.
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