[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: dynamic groups

MichaÅ SzulczyÅski wrote:
Howard Chu wrote:
One last question that may need an answer:
    what groups does user X belong to?

Obviously you need to perform a search to determine this. And with the current indexing mechanisms, dynamic groups will fail to be matched since they don't actually contain an indexed static member list. If this is the question you're trying to answer, the solution is simply to maintain a list of dynamic group objects (as your current code already does) but not to populate them. Instead, just use a search response callback and see if "member" is a part of the filter. If it is, iterate through the dynamic groups and test the entry whose DN is in the filter assertion against all of the dynamic group filters. This solution will use far less memory than your approach, and it will run efficiently for just about all use cases.

This was actually the first idea we thought of, we concluded that it
would slow the search down, because then the algorithmic complexity of
the search would be O(n), with n as the number of dynamic groups. We
think this would be somewhat against the idea of LDAP directories, where
the number of search operations far outweigh the number of updates. It
is a trade-off between update speed and search speed, but we think that
the search speed is essential, and the update operations are not our
primary concern speed-wise.

You're assuming that the number of dynamic groups will be large, compared to the overall number of entries. Somehow I doubt that. Have you tested your assumptions in any way?

You're also assuming that the cost of returning an indexed populated entry is cheap. The index lookup is relatively cheap, but returning a very large entry will still be expensive, and test_filter() will still have to walk through the member list before returning a result to the client.

The reason dynamic groups exist is because static groups perform poorly with large member lists. Your update/search tradeoff is still subject to this fact. Even with the solution I've been experimenting with, to presort multivalued attributes and use binary search on them for comparisons, the runtime is O(logN) (N is number of members) which in real world deployments is always a larger number than the number of groups in a directory.
-- Howard Chu
Chief Architect, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/