dynamic group caching (was: slapo-dynlist search member=value search?)

[Pierangelo Masarati <ando@sys-net.it>]

[moved to openldap-devel from openldap-software for discussion]

Aleksander Adamowski wrote:

> I don't claim it is easy. In fact, I know this problem is quite hard -
> that's why I was hesitant to try out dynlist since I didn't expect it
> would work this way. The documentation mislead me to think it works,
> however.
> 
> OTOH, this functionality would be so useful, that I might give it a shot.
> But I didn't work with OpenLDAP codebase yet, so obviously I'll need
> some guidance.
> 
> A couple of initial questions spring to my mind:
> 
>   1. I could use the backends' already present indexing mechanism for
>      doing the hard work, but I need dynlist to be able order the
>      backend to update indexes on member attribute for specific dynamic
>      group objects, which could have their member lists changed. Is it
>      possible with the current overlays/backends architecture?
>          * Example scenario:
>          * dynlist detects that a user has his DN changed from
>            uid=phil,l=Brighton,o=MyOrg to uid=phil,l=London,o=MyOrg
>          * dynlist determines which dynamic lists can potentially have
>            him as a member: looks for a logical conjunction of two
>            conditions: 1) the base DN of a memberURL is a prefix to
>            either the old DN or new DN of the user, 2) any attribute in
>            the LDAP filter of that memberURL is present in either the
>            new or old version of the entry (or both). Such a dynamic
>            list could either have the entry as a member or could gain
>            this entry if it didn't have it previously so its member
>            list needs to be reindexed.
>   2. dynlist overlay needs to keep track of base DNs and filter
>      atrributes of all memberURLs present the backend database in two
>      (or more) dictionary-type data structures. So it either needs to
>      store data about memberURL's permanently (not possible for
>      overlays?), or scan the whole backend's database at each startup
>      (slow). Is it possible to implement the first variant - permanent
>      data storage for dynlist overlay? I understand that overlays
>      cannot assume that they are used by a specific backend (e.g. bdb)
>      and cannot order the backend to store arbitrary data, AFAIK. Am I
>      right?
>   3. A significant speed optimization could be made if the overlay
>      could affect backend's indexing operation more directly. I mean,
>      when changing a potential member entry, for a given potential
>      dynamic list affected, either only one entry in its member index
>      is affected (added, removed or DN change), or the index is left
>      unchanged. If dynlist could simply test if the old and new verions
>      of the entry matched the memberURL's filter (possibly a "scope
>      one" search, but for the new verision it should be on a "virtual",
>      non-existing-yet entry), then it could determine immediately which
>      kind of low-level index operation needs to be performed - we have
>      three possible cases that would only affect at most one index
>      leaf. So the questions are: is it possible for the dynlist overlay
>      to test filters on the old and new versions of an entry for the
>      current transaction? Is it possible for the overlay to affect the
>      backend's indexing operation on single index entry level and would
>      it give a speed gain?
> 
> 
> Ad 1. - I'm think that dynlist would have to keep track memberURLs in 2
> dictionaries: one that maps base DN's from memberURL's to objects that
> have those memberURLs, second that maps attributes mentioned in filters
> to to objects that have those memberURLs. The first dictionary should be
> able to effectively search using a reverse-postfix-string match, that is
> "find all the keys which are prefixes of the given DN (the predecessors
> in LDAP hierarchy)".
> 
> Then to determine whether the memberURL is possibly affected, we have to
> determine the intersection of sets that result from lookup in both
> dictionaries - which could be implemented quite effectively if the
> dictionaries would keep the values ordered.
> 
> Now the answers to Howard Chu:
> 
> Howard Chu wrote:
>> If you make the data permanent, then you may as well just use static
>> groups.
> The difference is, static groups are human-managed (or require a special
> application to be written to maintain their definitions algoritmically
> and refresh them on a regular basis).
> 
> The data would just be helper data that would let dynlist optimize its
> work for speed by eliminating unneeded memberURL tests be deciding which
> memberURLs could potentially be affected by a ADD/MOD/MODRDN/DEL operation.
> 
>> Tracking "any memberURL in the directory" is either memory intensive
>> and/or CPU intensive. There's no good way to do this without
>> sacrificing one or both. 
> Well, the server administrator should find the information on the speed
> sacrifice and decide whether the feature is viable or not.
> 
> I think that my scheme is not so memory intensive (especially if
> implemented with an on-disk dictionary structure) and it's CPU intensive
> only for worst-case scenarios (memberURL's anchored in directory's base
> DN and filtering on objectclass attribute) and only for direcotry update
> operations, which are rare for LDAP directories by definition (quoting
> IBM's "Understanding LDAP": "One special characteristic of directories
> is that they are accessed (read or searched) much more often than they
> are updated (written)").
> There would be a warning in the documentation advising to avoid ussage
> of too generic LDAP attributes in memberURL filters (e.g. objectClass,
> cn) and too short base DNs.
> 

Probably a simpler approach would be to have a different type of dynamic
group that's rather a "cachedGroup"; a background thread could take care
of keeping it updated by expanding dynamic members into static (and
indexed), while direct modifications could be trapped and handled
explicitly (e.g. if a memberURL is added/removed).  The drawback would
be that other updates to the database (like another user entering the
scope of a memberURL search) are not immediately reflected in group
membership.  Static members should also be treated specially; this could
be perhaps be done by subtyping the dynamically cached members from the
static ones, so that regular searches for the static member attribute
find both, but caching operations only deal with the dynamically
generated ones.

p.



Ing. Pierangelo Masarati
OpenLDAP Core Team

SysNet s.r.l.
via Dossi, 8 - 27100 Pavia - ITALIA
http://www.sys-net.it
---------------------------------------
Office:  +39 02 23998309
Mobile:  +39 333 4963172
Email:   pierangelo.masarati@sys-net.it
---------------------------------------