The attached patch set uses special dereference LDAP controls to speed up RFC2307bis group processing. In my setup, with the LDAP server being in Boston and client in Brno, the time for "getent group ipausers" consisting of 2000 entries went down from 1.5 minute to 4 seconds.
One part of the patchset I'd like to draw attention to is the heuristics in patch #9. Dereference can potentially provide huge savings, but it's an all-or-nothing operation. As far as I know, you can't only say "only dereference entries matching this filter", at least not using the OpenLDAP dereference.
This could actually slow down the processing - consider if a single IPA user being created triggered a full dereference of "ipausers" group. In order to overcome this, the code includes a simple heuristics that either issues a full dereference or a series of single lookups.
The heuristics itself was pulled out of thin air, really. If there are any suggestions on a better one, I'll be glad to hear them.
And now the patches:
[PATCH 1/9] sdap_get_generic_ext Add a private sdap_get_generic_ext_send()/_recv() request that exposes more of ldap_search_ext options, in particular the server contols. The existing sdap_generic_search_send()/_recv() request is now a thin wrapper around the new _ext request.
The other important change is that an entry parsing is a callback now. That was done in order to allow custom parsing for results such as OpenLDAP deref or Attribute Scoped Queries.
[PATCH 2/9] Add support for Attribute Scoped Queries For more details on ASQ, see: http://msdn.microsoft.com/en-us/library/aa366976%28VS.85%29.aspx http://msdn.microsoft.com/en-us/library/aa746418%28v=VS.85%29.aspx
[PATCH 3/9] OpenLDAP dereference searches For more details, see: http://tools.ietf.org/html/draft-masarati-ldap-deref-00
[PATCH 4/9] Generic dereference search A generic wrapper around ASQ and OpenLDAP dereference searches. https://fedorahosted.org/sssd/ticket/635
[PATCH 5/9] append_attrs_to_array allocs on a memory context A convenience function
[PATCH 6/9] Change sysdb_add_fake_user to add OriginalDN RFC2307bis code relies heavily on originalDN, so the fake users need to have an option to store it, too.
[PATCH 7/9] Use fake users during RFC2307bis nested group processing Instead of downloading complete user data which is potentionally very slow, only download the necessary minimum information and store the users as dummy entries.
[PATCH 8/9] Refactor RFC2307bis nested group processing This patch splits checking cache and hash tables into standalone functions. This will make it easy to reuse the code in a new branch that uses dereferencing.
[PATCH 9/9] Use dereference in processing RFC2307bis nested groups Instead of issuing N LDAP requests when processing a group with N users, utilize the dereference functionality to pull down all the members in a single LDAP request.
On Wed, 2011-05-04 at 13:19 +0200, Jakub Hrozek wrote:
The attached patch set uses special dereference LDAP controls to speed up RFC2307bis group processing. In my setup, with the LDAP server being in Boston and client in Brno, the time for "getent group ipausers" consisting of 2000 entries went down from 1.5 minute to 4 seconds.
One part of the patchset I'd like to draw attention to is the heuristics in patch #9. Dereference can potentially provide huge savings, but it's an all-or-nothing operation. As far as I know, you can't only say "only dereference entries matching this filter", at least not using the OpenLDAP dereference.
This could actually slow down the processing - consider if a single IPA user being created triggered a full dereference of "ipausers" group. In order to overcome this, the code includes a simple heuristics that either issues a full dereference or a series of single lookups.
The heuristics itself was pulled out of thin air, really. If there are any suggestions on a better one, I'll be glad to hear them.
And now the patches:
[PATCH 1/9] sdap_get_generic_ext Add a private sdap_get_generic_ext_send()/_recv() request that exposes more of ldap_search_ext options, in particular the server contols. The existing sdap_generic_search_send()/_recv() request is now a thin wrapper around the new _ext request.
The other important change is that an entry parsing is a callback now. That was done in order to allow custom parsing for results such as OpenLDAP deref or Attribute Scoped Queries.
Ack
[PATCH 2/9] Add support for Attribute Scoped Queries For more details on ASQ, see: http://msdn.microsoft.com/en-us/library/aa366976%28VS.85%29.aspx http://msdn.microsoft.com/en-us/library/aa746418%28v=VS.85%29.aspx
Ack
[PATCH 3/9] OpenLDAP dereference searches For more details, see: http://tools.ietf.org/html/draft-masarati-ldap-deref-00
Nack
What's the point of derefcount in sdap_x_deref_parse_entry()? It's only ever assigned and never read.
sdap_parse_deref() assumes that it can determine the mapping to use based on the objectClass, but this falls down in situations like Magic Private Groups, where user entries have both the posixAccount and posixGroup attribute.
[PATCH 4/9] Generic dereference search A generic wrapper around ASQ and OpenLDAP dereference searches. https://fedorahosted.org/sssd/ticket/635
Nack. It would be preferable to have a single sdap_deref_search_done() function instead of a separate one for each deref type. See sdap_get_initgr_done() for an example of what I mean. There should be separate _recv() functions, but only one common _done() function to make it simpler to follow execution.
[PATCH 5/9] append_attrs_to_array allocs on a memory context A convenience function
Nack. We discussed this on IRC. This function serves no real purpose (it was never used prior to patch 9 in this set) and this modification has zero net effect, since the mem_ctx attribute has no effect on a talloc_realloc() for previously-allocated memory.
We decided to remove this function entirely, since it just causes confusion.
[PATCH 6/9] Change sysdb_add_fake_user to add OriginalDN RFC2307bis code relies heavily on originalDN, so the fake users need to have an option to store it, too.
Ack.
Review still pending for the RFC2307bis results.
[PATCH 7/9] Use fake users during RFC2307bis nested group processing Instead of downloading complete user data which is potentionally very slow, only download the necessary minimum information and store the users as dummy entries.
[PATCH 8/9] Refactor RFC2307bis nested group processing This patch splits checking cache and hash tables into standalone functions. This will make it easy to reuse the code in a new branch that uses dereferencing.
[PATCH 9/9] Use dereference in processing RFC2307bis nested groups Instead of issuing N LDAP requests when processing a group with N users, utilize the dereference functionality to pull down all the members in a single LDAP request.
On Mon, 2011-05-09 at 10:20 -0400, Stephen Gallagher wrote:
sdap_parse_deref() assumes that it can determine the mapping to use based on the objectClass, but this falls down in situations like Magic Private Groups, where user entries have both the posixAccount and posixGroup attribute.
This never happens, we tried that approach and too many clients failed to handle it. Magic Private Groups in IPA are created through the Managed Entries plugin and are 2 separate objects now.
That said, if we can make the code work if such entries (with both objectclasses) were found I'd like that.
Simo.
Continuing my review. Comments inline.
On Wed, 2011-05-04 at 13:19 +0200, Jakub Hrozek wrote:
[PATCH 7/9] Use fake users during RFC2307bis nested group processing Instead of downloading complete user data which is potentionally very slow, only download the necessary minimum information and store the users as dummy entries.
Nack. sdap_nested_group_populate_users() doesn't properly sanitize the origDN before using it in a search filter.
[PATCH 8/9] Refactor RFC2307bis nested group processing This patch splits checking cache and hash tables into standalone functions. This will make it easy to reuse the code in a new branch that uses dereferencing.
Nack.
I realize this was a problem in my original code, but would you mind fixing two issues with sdap_nested_group_check_cache() while you're there?
1) Please rearrange the code so that all of the user processing takes place before the group processing. It's not terribly readable the way the complete group processing happens in the middle. It would be better to have the return value from sysdb_search_users() set mtype either to SYSDB_MEMBER_USER or SYSDB_MEMBER_GROUP (assumed) and then have another IF statement after that so we can do all of the user processing in series.
2) It's kind of wasteful to allocate filter twice in the case of groups. Better would be to hang onto it until we're sure we're not processing a group. Then we don't need to allocate and free the exact same filter twice.
Please change the comment in the ENOENT block of sdap_nested_group_process_step() since it no longer makes sense with the user and group split in a sub-function.
[PATCH 9/9] Use dereference in processing RFC2307bis nested groups Instead of issuing N LDAP requests when processing a group with N users, utilize the dereference functionality to pull down all the members in a single LDAP request.
Nack.
In sdap_nested_group_process_deref_step(), if sdap_nested_group_check_cache() returns something other than EOK, ENOENT or EAGAIN, it should be returned as an error. Right now, you're treating all errors as ENOENT.
Regarding the tuning for when to perform the deref, I don't have a perfect answer either. My only suggestion would be to make the value configurable in sssd.conf. I think we should get rid of the percentage and make it purely based on number of members. The way to tune it should be that we should deref whenever a deref will take less time to process than N members. I think we should default to ten members.
On 05/09/2011 07:23 PM, Stephen Gallagher wrote:
Continuing my review. Comments inline.
New patches are attached. They are formatted with -M -C --patience --full-index, per Simo's suggestion. I think it helped, especially with patch #1.
I'd like to merge the replies into one thread. Below are replies for the first half of patches.
Patch #1 has no changes.
Patch #2 is a new one that just defines a couple of data structures and one function that are used in later patches in order to process MPGs.
Patches #3 and #4 (previously #2 and #3) that implement the platform-specific dereference methods are now able to dereference MPGs, too. The OpenLDAP patch also removes one unused variable.
If an LDAP object that matches multiple maps is dereferenced, it is returned as multiple sysdb_attrs * results plus the corresponding map to speed up processing.
I tested the functionality by dereferencing an object that was both a posixUser and a posixGroup. The dereference itself worked fine and both objects were saved to sysdb but it seems that the rest of the LDAP provider assumes that originalDN is unique -- so later the back end failed when it was trying to build memberships. This is something to fix if we want to support MPGs, but I don't think it is related to this patchset.
Patch #5 (previously #4) now has single sdap_deref_search_done() function instead of one per method.
The patch that changed append_attrs_to_array was retired. I will send a separate patch to remove that function altogether as it is not used anywhere.
Patch #6 has no changes.
On Wed, 2011-05-04 at 13:19 +0200, Jakub Hrozek wrote:
[PATCH 7/9] Use fake users during RFC2307bis nested group processing Instead of downloading complete user data which is potentionally very slow, only download the necessary minimum information and store the users as dummy entries.
Nack. sdap_nested_group_populate_users() doesn't properly sanitize the origDN before using it in a search filter.
Fixed.
[PATCH 8/9] Refactor RFC2307bis nested group processing This patch splits checking cache and hash tables into standalone functions. This will make it easy to reuse the code in a new branch that uses dereferencing.
Nack.
I realize this was a problem in my original code, but would you mind fixing two issues with sdap_nested_group_check_cache() while you're there?
- Please rearrange the code so that all of the user processing takes
place before the group processing. It's not terribly readable the way the complete group processing happens in the middle. It would be better to have the return value from sysdb_search_users() set mtype either to SYSDB_MEMBER_USER or SYSDB_MEMBER_GROUP (assumed) and then have another IF statement after that so we can do all of the user processing in series.
- It's kind of wasteful to allocate filter twice in the case of groups.
Better would be to hang onto it until we're sure we're not processing a group. Then we don't need to allocate and free the exact same filter twice.
Please change the comment in the ENOENT block of sdap_nested_group_process_step() since it no longer makes sense with the user and group split in a sub-function.
Fixed
[PATCH 9/9] Use dereference in processing RFC2307bis nested groups Instead of issuing N LDAP requests when processing a group with N users, utilize the dereference functionality to pull down all the members in a single LDAP request.
Nack.
In sdap_nested_group_process_deref_step(), if sdap_nested_group_check_cache() returns something other than EOK, ENOENT or EAGAIN, it should be returned as an error. Right now, you're treating all errors as ENOENT.
Fixed
Regarding the tuning for when to perform the deref, I don't have a perfect answer either. My only suggestion would be to make the value configurable in sssd.conf. I think we should get rid of the percentage and make it purely based on number of members. The way to tune it should be that we should deref whenever a deref will take less time to process than N members. I think we should default to ten members.
Making it configurable is a good answer :-) and I agree that the option should only specify absolute values.
On Wed, 2011-05-18 at 16:41 +0200, Jakub Hrozek wrote:
On 05/09/2011 07:23 PM, Stephen Gallagher wrote:
Continuing my review. Comments inline.
New patches are attached. They are formatted with -M -C --patience --full-index, per Simo's suggestion. I think it helped, especially with patch #1.
I'd like to merge the replies into one thread. Below are replies for the first half of patches.
Patch #1 has no changes.
Patch #2 is a new one that just defines a couple of data structures and one function that are used in later patches in order to process MPGs.
Patches #3 and #4 (previously #2 and #3) that implement the platform-specific dereference methods are now able to dereference MPGs, too. The OpenLDAP patch also removes one unused variable.
If an LDAP object that matches multiple maps is dereferenced, it is returned as multiple sysdb_attrs * results plus the corresponding map to speed up processing.
I tested the functionality by dereferencing an object that was both a posixUser and a posixGroup. The dereference itself worked fine and both objects were saved to sysdb but it seems that the rest of the LDAP provider assumes that originalDN is unique -- so later the back end failed when it was trying to build memberships. This is something to fix if we want to support MPGs, but I don't think it is related to this patchset.
Patch #5 (previously #4) now has single sdap_deref_search_done() function instead of one per method.
The patch that changed append_attrs_to_array was retired. I will send a separate patch to remove that function altogether as it is not used anywhere.
Patch #6 has no changes.
On Wed, 2011-05-04 at 13:19 +0200, Jakub Hrozek wrote:
[PATCH 7/9] Use fake users during RFC2307bis nested group processing Instead of downloading complete user data which is potentionally very slow, only download the necessary minimum information and store the users as dummy entries.
Nack. sdap_nested_group_populate_users() doesn't properly sanitize the origDN before using it in a search filter.
Fixed.
[PATCH 8/9] Refactor RFC2307bis nested group processing This patch splits checking cache and hash tables into standalone functions. This will make it easy to reuse the code in a new branch that uses dereferencing.
Nack.
I realize this was a problem in my original code, but would you mind fixing two issues with sdap_nested_group_check_cache() while you're there?
- Please rearrange the code so that all of the user processing takes
place before the group processing. It's not terribly readable the way the complete group processing happens in the middle. It would be better to have the return value from sysdb_search_users() set mtype either to SYSDB_MEMBER_USER or SYSDB_MEMBER_GROUP (assumed) and then have another IF statement after that so we can do all of the user processing in series.
- It's kind of wasteful to allocate filter twice in the case of groups.
Better would be to hang onto it until we're sure we're not processing a group. Then we don't need to allocate and free the exact same filter twice.
Please change the comment in the ENOENT block of sdap_nested_group_process_step() since it no longer makes sense with the user and group split in a sub-function.
Fixed
[PATCH 9/9] Use dereference in processing RFC2307bis nested groups Instead of issuing N LDAP requests when processing a group with N users, utilize the dereference functionality to pull down all the members in a single LDAP request.
Nack.
In sdap_nested_group_process_deref_step(), if sdap_nested_group_check_cache() returns something other than EOK, ENOENT or EAGAIN, it should be returned as an error. Right now, you're treating all errors as ENOENT.
Fixed
Regarding the tuning for when to perform the deref, I don't have a perfect answer either. My only suggestion would be to make the value configurable in sssd.conf. I think we should get rid of the percentage and make it purely based on number of members. The way to tune it should be that we should deref whenever a deref will take less time to process than N members. I think we should default to ten members.
Making it configurable is a good answer :-) and I agree that the option should only specify absolute values.
Patch 0001: Ack Patch 0002: Ack Patch 0003: Ack Patch 0004: Ack Patch 0005: Ack Patch 0006: Ack Patch 0007: Ack Patch 0008: Ack Patch 0009: Nack. Please add ldap_deref_threshold to sssd-ipa.conf (not just sssd-ldap.conf.
On 05/20/2011 12:10 PM, Stephen Gallagher wrote:
On Wed, 2011-05-18 at 16:41 +0200, Jakub Hrozek wrote:
On 05/09/2011 07:23 PM, Stephen Gallagher wrote:
Continuing my review. Comments inline.
New patches are attached. They are formatted with -M -C --patience --full-index, per Simo's suggestion. I think it helped, especially with patch #1.
I'd like to merge the replies into one thread. Below are replies for the first half of patches.
Patch #1 has no changes.
Patch #2 is a new one that just defines a couple of data structures and one function that are used in later patches in order to process MPGs.
Patches #3 and #4 (previously #2 and #3) that implement the platform-specific dereference methods are now able to dereference MPGs, too. The OpenLDAP patch also removes one unused variable.
If an LDAP object that matches multiple maps is dereferenced, it is returned as multiple sysdb_attrs * results plus the corresponding map to speed up processing.
I tested the functionality by dereferencing an object that was both a posixUser and a posixGroup. The dereference itself worked fine and both objects were saved to sysdb but it seems that the rest of the LDAP provider assumes that originalDN is unique -- so later the back end failed when it was trying to build memberships. This is something to fix if we want to support MPGs, but I don't think it is related to this patchset.
Patch #5 (previously #4) now has single sdap_deref_search_done() function instead of one per method.
The patch that changed append_attrs_to_array was retired. I will send a separate patch to remove that function altogether as it is not used anywhere.
Patch #6 has no changes.
On Wed, 2011-05-04 at 13:19 +0200, Jakub Hrozek wrote:
[PATCH 7/9] Use fake users during RFC2307bis nested group processing Instead of downloading complete user data which is potentionally very slow, only download the necessary minimum information and store the users as dummy entries.
Nack. sdap_nested_group_populate_users() doesn't properly sanitize the origDN before using it in a search filter.
Fixed.
[PATCH 8/9] Refactor RFC2307bis nested group processing This patch splits checking cache and hash tables into standalone functions. This will make it easy to reuse the code in a new branch that uses dereferencing.
Nack.
I realize this was a problem in my original code, but would you mind fixing two issues with sdap_nested_group_check_cache() while you're there?
- Please rearrange the code so that all of the user processing takes
place before the group processing. It's not terribly readable the way the complete group processing happens in the middle. It would be better to have the return value from sysdb_search_users() set mtype either to SYSDB_MEMBER_USER or SYSDB_MEMBER_GROUP (assumed) and then have another IF statement after that so we can do all of the user processing in series.
- It's kind of wasteful to allocate filter twice in the case of groups.
Better would be to hang onto it until we're sure we're not processing a group. Then we don't need to allocate and free the exact same filter twice.
Please change the comment in the ENOENT block of sdap_nested_group_process_step() since it no longer makes sense with the user and group split in a sub-function.
Fixed
[PATCH 9/9] Use dereference in processing RFC2307bis nested groups Instead of issuing N LDAP requests when processing a group with N users, utilize the dereference functionality to pull down all the members in a single LDAP request.
Nack.
In sdap_nested_group_process_deref_step(), if sdap_nested_group_check_cache() returns something other than EOK, ENOENT or EAGAIN, it should be returned as an error. Right now, you're treating all errors as ENOENT.
Fixed
Regarding the tuning for when to perform the deref, I don't have a perfect answer either. My only suggestion would be to make the value configurable in sssd.conf. I think we should get rid of the percentage and make it purely based on number of members. The way to tune it should be that we should deref whenever a deref will take less time to process than N members. I think we should default to ten members.
Making it configurable is a good answer :-) and I agree that the option should only specify absolute values.
Patch 0001: Ack Patch 0002: Ack Patch 0003: Ack Patch 0004: Ack Patch 0005: Ack Patch 0006: Ack Patch 0007: Ack Patch 0008: Ack Patch 0009: Nack. Please add ldap_deref_threshold to sssd-ipa.conf (not just sssd-ldap.conf.
Done. I also noticed that ldap_page size was missing, so I added that one, too.
On Fri, 2011-05-20 at 13:15 +0200, Jakub Hrozek wrote:
On 05/20/2011 12:10 PM, Stephen Gallagher wrote:
Patch 0001: Ack Patch 0002: Ack Patch 0003: Ack Patch 0004: Ack Patch 0005: Ack Patch 0006: Ack Patch 0007: Ack Patch 0008: Ack Patch 0009: Nack. Please add ldap_deref_threshold to sssd-ipa.conf (not just sssd-ldap.conf.
Done. I also noticed that ldap_page size was missing, so I added that one, too.
Oops, thanks for catching that.
Ok, ack to all patches. Pushed to master.
sssd-devel@lists.fedorahosted.org
-
Jakub Hrozek -
Simo Sorce -
Stephen Gallagher