You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Emmanuel Lecharny <el...@gmail.com> on 2010/07/15 19:33:41 UTC

Subentries handling refactoring

  Hi guys,

we have serious issues with the way we manage subentries in the server. 
Not that it's not working, but it's certainly not good enough for 
anything but a toy server.

Let me first give some heads up about what's going on.

A subentry is associated with an AdministrativePoint (AP), and defines a 
selection of entries which will be affected depending on the AP role. 
Those roles are :
- Access Control
- Collective Attributes
- SubSchema (not active atm)
- Triggers (ADS specific).

For instance, if we have a tree with a set of entries associated with a 
location (ie, c=France), we may define a subentry with a Collective 
Attribute role telling the server that every entry under the c=France 
branch will have a specific attribute added. We don't have then to add 
this attribute to *every* entry in this branch...

Anyway...

A subentry defines a selection using a filter, and a base DN for this 
filter to be active from.

Right now, a Subentry is attached to an AP as a (quite) normal entry, 
and when we add this subentry, we modidy *all* the selected entries 
(using the subentry filter and the base DN) will be modified to have a 
new attribute added. This added attribute contains a DN poiting to the 
associated subentry, so that when we process this entry, we can 
immediately know that it's associated with an AP.

So far, so good : processing an entry is fast, as we have all what we 
need when we have the entry. But the dark side is that if we have 
millions of entries, when we add an AP and a subentry, we may have to 
modify potentially *millions* of entries to add this attribute. Not good...

How can we improve this process ?

The idea would be to search for the APs when we process an entry, but it 
has to be fast. How can we do that ? Simple : we use the entry's DN and 
using a DN cache, we can get all the APs associated with an entry 
knowing its DN. It's as costly as the depth of the entry's DN. Once we 
have grabbed the APs, we will have to evaluate the entry to know if it's 
part of the selections defined by the APs' subentry. Done.

Is it costly ? Only marginaly compared to the current algorithm, as we 
have to lookup for the AP, when we have this list in an Attribute in the 
current server. But we spare the big modifications when adding - or 
removing/renaming/moving - a subentry.

What we just need is a APs cache and a way to process it.

This is what I will work on in the next few days if nobody objects or 
find a better algorithm.

-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com


Re: Subentries handling refactoring

Posted by Emmanuel Lecharny <el...@gmail.com>.
  FYI, I closed DIRSERVER_1527 as Won't fix.


-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com


Re: Subentries handling refactoring

Posted by Alex Karasulu <ak...@gmail.com>.
I was a bit reticent to cast a veto but with the right community that  
thinks and discusses the problem this is obviously nothing to worry  
about. Thanks for thoroughly considering my position. I wish I had a  
better solution to offer.

Unfortunately this is a really tough problem to solve. I had thought  
of using indicies for subentry references in entries but like u I  
realized this will incur even more overhead.

Best Regards,
Alex

Sent from my iPhone

On Jul 16, 2010, at 9:26 AM, Emmanuel Lécharny <el...@apache.org>  
wrote:

> On 7/16/10 12:23 AM, Alex Karasulu wrote:
>> On Thu, Jul 15, 2010 at 8:33 PM, Emmanuel Lecharny<elecharny@gmail.com 
>> >wrote:
>>
>>> This is what I will work on in the next few days if nobody objects  
>>> or find
>>> a better algorithm.
>>>
>>>
>> I'm sorry but I have to veto this change. It's not acceptable to be  
>> taxing
>> an LDAP server's read performance when this should be done during  
>> writes or
>> during administrative changes.
> We discussed this option too : paying the price once for an  
> operation done unfrequently is appealing, that's clear.
>
> In a way, it's like if you create an index on an existing  
> attribute : you have to pay the price for doing so after having  
> added millions of entry.
>
> The problem is that with millions of entries, and with a costly  
> operation like a modify (roughly 15 to 20 times slower than a  
> search), it will take ages to process.
>
> Now, can we do better ? And does it slow down the search a lot if we  
> do what I suggest ?
>
> Let's think about the search penalty first (btw, it's not only  
> search, but *all* operation) : we will have to find the subentry  
> associated with an entry if it belongs to an AP. If we have a decent  
> AP cache, this is just a question of looking in this cache for the  
> list of subentries we will have to check, then evaluate these  
> subentries. The cost of searching for subentires is pretty minimal,  
> but evaluating the SS may be costly for *all* the processed entries,  
> even if they are not impacted.
>
> All in all, I think it will add 5 to 10 % penalty to all the  
> operations.
>
> Is it acceptable ? Well, as Alex says, and this is the reason why I  
> posted this mail before going on with such a major change, if you  
> balance the number of operation done daily on a LDAP server and a  
> change in the administrative model (ie, the addition of a subentry),  
> I would say that he is right.
>
> Can we do better than what is currently done ?
>
> We discussed a bit about other options, and one of them would be to  
> use a side index, which will tell if an entry is dependent on an AP.  
> Instead of modifying all the entries, we just update this index. The  
> problem with this approach is that not only you still have  a  
> penalty to pay for each operation (ie, checking in this index to see  
> if the entry is a part of an AP), plus updating this index will be  
> more costly than upating the master table (becuase you have 2 files  
> to update on disk instead of only one).
>
> I currently don't see any other alternative.
>
> So, all in all, I like this veto :)
>
> We still have things to work on :
> - the subentry interceptor has still to be fixed, as we don't manage  
> correctly the moveAndRename operation
> - the ACI interceptor does a direct access to a method in the  
> subentry interceptor, because the subentry cache is managed by this  
> interceptor. I think this cache shuld be moved the the  
> directoryService instance
> - we can imrprove the modify operation performances :)
>
> One side effect of *not* doing such a modification is that I will  
> spare a few days working on some other bugs we have instead of  
> implementing this.
>
> Side note : this again prove that a community is way better than  
> individuals. Sharing ideas openly is the best way to avoid mistakes.  
> Thanks for the feedback Alex !
>
> -- 
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>

Re: Subentries handling refactoring

Posted by Emmanuel Lécharny <el...@apache.org>.
  On 7/16/10 12:23 AM, Alex Karasulu wrote:
> On Thu, Jul 15, 2010 at 8:33 PM, Emmanuel Lecharny<el...@gmail.com>wrote:
>
>> This is what I will work on in the next few days if nobody objects or find
>> a better algorithm.
>>
>>
> I'm sorry but I have to veto this change. It's not acceptable to be taxing
> an LDAP server's read performance when this should be done during writes or
> during administrative changes.
We discussed this option too : paying the price once for an operation 
done unfrequently is appealing, that's clear.

In a way, it's like if you create an index on an existing attribute : 
you have to pay the price for doing so after having added millions of entry.

The problem is that with millions of entries, and with a costly 
operation like a modify (roughly 15 to 20 times slower than a search), 
it will take ages to process.

Now, can we do better ? And does it slow down the search a lot if we do 
what I suggest ?

Let's think about the search penalty first (btw, it's not only search, 
but *all* operation) : we will have to find the subentry associated with 
an entry if it belongs to an AP. If we have a decent AP cache, this is 
just a question of looking in this cache for the list of subentries we 
will have to check, then evaluate these subentries. The cost of 
searching for subentires is pretty minimal, but evaluating the SS may be 
costly for *all* the processed entries, even if they are not impacted.

All in all, I think it will add 5 to 10 % penalty to all the operations.

Is it acceptable ? Well, as Alex says, and this is the reason why I 
posted this mail before going on with such a major change, if you 
balance the number of operation done daily on a LDAP server and a change 
in the administrative model (ie, the addition of a subentry), I would 
say that he is right.

Can we do better than what is currently done ?

We discussed a bit about other options, and one of them would be to use 
a side index, which will tell if an entry is dependent on an AP. Instead 
of modifying all the entries, we just update this index. The problem 
with this approach is that not only you still have  a penalty to pay for 
each operation (ie, checking in this index to see if the entry is a part 
of an AP), plus updating this index will be more costly than upating the 
master table (becuase you have 2 files to update on disk instead of only 
one).

I currently don't see any other alternative.

So, all in all, I like this veto :)

We still have things to work on :
- the subentry interceptor has still to be fixed, as we don't manage 
correctly the moveAndRename operation
- the ACI interceptor does a direct access to a method in the subentry 
interceptor, because the subentry cache is managed by this interceptor. 
I think this cache shuld be moved the the directoryService instance
- we can imrprove the modify operation performances :)

One side effect of *not* doing such a modification is that I will spare 
a few days working on some other bugs we have instead of implementing this.

Side note : this again prove that a community is way better than 
individuals. Sharing ideas openly is the best way to avoid mistakes. 
Thanks for the feedback Alex !

-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com


Re: Subentries handling refactoring

Posted by Ersin Er <er...@gmail.com>.
As I had been involved in developing this part of the server, I have
discussed the issue with Emmanuel and I do not have more information to add
besides Alex's and Emmanuel's concerns.

X.500 is a cool spec that's hard or even impossible to implement in an
acceptable form.


On Sun, Jul 18, 2010 at 21:25, Alex Karasulu <ak...@apache.org> wrote:

> Hi Emmanuel,
>
> On Sun, Jul 18, 2010 at 11:09 AM, Emmanuel Lécharny <el...@apache.org>wrote:
>
>>  On 7/16/10 12:23 AM, Alex Karasulu wrote:
>>
>>> Let me first give some heads up about what's going on.
>>>
>>>> This is what I will work on in the next few days if nobody objects or
>>>> find
>>>> a better algorithm.
>>>>
>>>>
>>>>  I'm sorry but I have to veto this change. It's not acceptable to be
>>> taxing
>>> an LDAP server's read performance when this should be done during writes
>>> or
>>> during administrative changes.
>>>
>> I have to veto this veto :)
>>
>>
> Heh :-).
>
>
>> Ok, more srriously, let me explain what is the problem with the current
>> approach.
>>
>> let's say you have a DIT with 2 naming contexts :
>>
>> dc=A
>> dc=B
>>
>> Both of them are AP.
>>
>> Now, we define a dc=sub-A,dc=A, which is also an AP with an accessControl
>> subentry.
>>
>>
> I figure you mean dc=sub-A is a subentry under dc=A which is the
> Administrative Point? Hmm but cn needs to be used for subentries.
>
>
>> We now have the following structure (with the opAttr in square brackets,
>> for clarity) (subentries are defined in ange brackets):
>> dc=A
>> <cn=A-subentry>
>>  dc=sub-A
>>
>
> OK so dc=sub-A is an Inner Administrative Area nested withing dc=A.
>
>
>> <cn=sub-A-subentry>
>>    cn=entry1
>>      [accessControlSubentries: cn=A-subentry,dc=A]
>>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>>    cn=entry2
>>      [accessControlSubentries: cn=A-subentry,dc=A]
>>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>> dc=B
>> <cn=B-subentry>
>>
>> Now, we want to move dc=sub-A,dc=A to dc=B. This will result to :
>> dc=A
>> <cn=A-subentry>
>> dc=B
>> <cn=B-subentry>
>>  dc=sub-A
>> <cn=sub-A-subentry>
>>    cn=entry1
>>      [accessControlSubentries: cn=A-subentry,dc=A]
>>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>>    cn=entry2
>>      [accessControlSubentries: cn=A-subentry,dc=A]
>>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>>
>>
> I thought dc=B is a peer of dc=A. So for cn=entry1 you should not have the
> reference any longer to subentry cn=A-subentry,dc=A. Likewise for entry2.
>
> OK below you update that ...
>
> Now, all the entries operational attributes are to be modified to gives the
>> correct tree :
>> dc=A
>> <cn=A-subentry>
>> dc=B
>> <cn=B-subentry>
>>  dc=sub-A
>> <cn=sub-A-subentry>
>>    cn=entry1
>>      [accessControlSubentries: cn=B-subentry,dc=B]
>>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=B]
>>    cn=entry2
>>      [accessControlSubentries: cn=B-subentry,dc=B]
>>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=B]
>>
>> So every move operation will impact potentially many entries, for an
>> operation which is definitively *not* an administrative operation.
>>
>>
> Not really this is still an administrative operation. You're moving around
> APs, inner or outer does not matter. The point is there are administrative
> changes and administrative costs associated with it. Moving non-AP entries
> is not an administrative operation.
>
> IMO, it's the same thing than when I decided to inject the full DN in
>> entries, making the move operation costly - and we reverted back to a system
>> where the move operation is O(1) instead of being O(N).
>> When we have subentries and operational attributes stored into entries
>> referring those subentries, then the move operation is again one in O(N).
>>
>>
> This is not a normal move operation. If you move an entry
> like cn=entry1,dc=sub-A,dc=A, then you have that O(1) cost. But you're
> moving an Inner Administrative Area, an Administrative Point. This
> potentially impacts N entries. It's not trivial and very complicated and I
> can see and live with the cost of such an operation.
>
>
>> This is not acceptable, and of course, changing this comes with a price we
>> have to pay for every user operation, but I don't see how we can accept to
>> have an O(N) Move operation when we have subentries, but not when it comes
>> to store the DN within the entries.
>>
>> Thoughts ?
>
>
> I think we have to make sure we understand what it is we're doing in this
> specific example. Moving an AP is an administrative function that can incur
> heavy costs. Your example is very complex because you chose an IAA instead
> of a regular entry to move.
>
>
>>
>>
>>  There's a reason why I implemented it this way 5 years ago. I still think
>>> it's sound. It's a matter of when you choose to pay for the
>>> administrative
>>> change which BTW should not happen that often while reads happen all the
>>> time. I'd rather pay a lot for infrequent operations than a little bit
>>> for
>>> the most common operations.
>>>
>>>
>>
> --
> Alex Karasulu
> My Blog :: http://www.jroller.com/akarasulu/
> Apache Directory Server :: http://directory.apache.org
> Apache MINA :: http://mina.apache.org
> To set up a meeting with me: http://tungle.me/AlexKarasulu
>



-- 
Ersin ER

Re: Subentries handling refactoring

Posted by Alex Karasulu <ak...@apache.org>.
Hi Emmanuel,

On Sun, Jul 18, 2010 at 11:09 AM, Emmanuel Lécharny <el...@apache.org>wrote:

>  On 7/16/10 12:23 AM, Alex Karasulu wrote:
>
>> Let me first give some heads up about what's going on.
>>
>>> This is what I will work on in the next few days if nobody objects or
>>> find
>>> a better algorithm.
>>>
>>>
>>>  I'm sorry but I have to veto this change. It's not acceptable to be
>> taxing
>> an LDAP server's read performance when this should be done during writes
>> or
>> during administrative changes.
>>
> I have to veto this veto :)
>
>
Heh :-).


> Ok, more srriously, let me explain what is the problem with the current
> approach.
>
> let's say you have a DIT with 2 naming contexts :
>
> dc=A
> dc=B
>
> Both of them are AP.
>
> Now, we define a dc=sub-A,dc=A, which is also an AP with an accessControl
> subentry.
>
>
I figure you mean dc=sub-A is a subentry under dc=A which is the
Administrative Point? Hmm but cn needs to be used for subentries.


> We now have the following structure (with the opAttr in square brackets,
> for clarity) (subentries are defined in ange brackets):
> dc=A
> <cn=A-subentry>
>  dc=sub-A
>

OK so dc=sub-A is an Inner Administrative Area nested withing dc=A.


> <cn=sub-A-subentry>
>    cn=entry1
>      [accessControlSubentries: cn=A-subentry,dc=A]
>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>    cn=entry2
>      [accessControlSubentries: cn=A-subentry,dc=A]
>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
> dc=B
> <cn=B-subentry>
>
> Now, we want to move dc=sub-A,dc=A to dc=B. This will result to :
> dc=A
> <cn=A-subentry>
> dc=B
> <cn=B-subentry>
>  dc=sub-A
> <cn=sub-A-subentry>
>    cn=entry1
>      [accessControlSubentries: cn=A-subentry,dc=A]
>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>    cn=entry2
>      [accessControlSubentries: cn=A-subentry,dc=A]
>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
>
>
I thought dc=B is a peer of dc=A. So for cn=entry1 you should not have the
reference any longer to subentry cn=A-subentry,dc=A. Likewise for entry2.

OK below you update that ...

Now, all the entries operational attributes are to be modified to gives the
> correct tree :
> dc=A
> <cn=A-subentry>
> dc=B
> <cn=B-subentry>
>  dc=sub-A
> <cn=sub-A-subentry>
>    cn=entry1
>      [accessControlSubentries: cn=B-subentry,dc=B]
>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=B]
>    cn=entry2
>      [accessControlSubentries: cn=B-subentry,dc=B]
>      [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=B]
>
> So every move operation will impact potentially many entries, for an
> operation which is definitively *not* an administrative operation.
>
>
Not really this is still an administrative operation. You're moving around
APs, inner or outer does not matter. The point is there are administrative
changes and administrative costs associated with it. Moving non-AP entries
is not an administrative operation.

IMO, it's the same thing than when I decided to inject the full DN in
> entries, making the move operation costly - and we reverted back to a system
> where the move operation is O(1) instead of being O(N).
> When we have subentries and operational attributes stored into entries
> referring those subentries, then the move operation is again one in O(N).
>
>
This is not a normal move operation. If you move an entry
like cn=entry1,dc=sub-A,dc=A, then you have that O(1) cost. But you're
moving an Inner Administrative Area, an Administrative Point. This
potentially impacts N entries. It's not trivial and very complicated and I
can see and live with the cost of such an operation.


> This is not acceptable, and of course, changing this comes with a price we
> have to pay for every user operation, but I don't see how we can accept to
> have an O(N) Move operation when we have subentries, but not when it comes
> to store the DN within the entries.
>
> Thoughts ?


I think we have to make sure we understand what it is we're doing in this
specific example. Moving an AP is an administrative function that can incur
heavy costs. Your example is very complex because you chose an IAA instead
of a regular entry to move.


>
>
>  There's a reason why I implemented it this way 5 years ago. I still think
>> it's sound. It's a matter of when you choose to pay for the administrative
>> change which BTW should not happen that often while reads happen all the
>> time. I'd rather pay a lot for infrequent operations than a little bit for
>> the most common operations.
>>
>>
>
-- 
Alex Karasulu
My Blog :: http://www.jroller.com/akarasulu/
Apache Directory Server :: http://directory.apache.org
Apache MINA :: http://mina.apache.org
To set up a meeting with me: http://tungle.me/AlexKarasulu

Re: Subentries handling refactoring

Posted by Emmanuel Lécharny <el...@apache.org>.
  On 7/16/10 12:23 AM, Alex Karasulu wrote:
> Let me first give some heads up about what's going on.
>> This is what I will work on in the next few days if nobody objects or find
>> a better algorithm.
>>
>>
> I'm sorry but I have to veto this change. It's not acceptable to be taxing
> an LDAP server's read performance when this should be done during writes or
> during administrative changes.
I have to veto this veto :)

Ok, more srriously, let me explain what is the problem with the current 
approach.

let's say you have a DIT with 2 naming contexts :

dc=A
dc=B

Both of them are AP.

Now, we define a dc=sub-A,dc=A, which is also an AP with an 
accessControl subentry.

We now have the following structure (with the opAttr in square brackets, 
for clarity) (subentries are defined in ange brackets):
dc=A
<cn=A-subentry>
   dc=sub-A
<cn=sub-A-subentry>
     cn=entry1
       [accessControlSubentries: cn=A-subentry,dc=A]
       [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
     cn=entry2
       [accessControlSubentries: cn=A-subentry,dc=A]
       [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
dc=B
<cn=B-subentry>

Now, we want to move dc=sub-A,dc=A to dc=B. This will result to :
dc=A
<cn=A-subentry>
dc=B
<cn=B-subentry>
   dc=sub-A
<cn=sub-A-subentry>
     cn=entry1
       [accessControlSubentries: cn=A-subentry,dc=A]
       [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]
     cn=entry2
       [accessControlSubentries: cn=A-subentry,dc=A]
       [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=A]

Now, all the entries operational attributes are to be modified to gives 
the correct tree :
dc=A
<cn=A-subentry>
dc=B
<cn=B-subentry>
   dc=sub-A
<cn=sub-A-subentry>
     cn=entry1
       [accessControlSubentries: cn=B-subentry,dc=B]
       [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=B]
     cn=entry2
       [accessControlSubentries: cn=B-subentry,dc=B]
       [accessControlSubentries: cn=sub-A-subentry,dc=sub-A,dc=B]

So every move operation will impact potentially many entries, for an 
operation which is definitively *not* an administrative operation.

IMO, it's the same thing than when I decided to inject the full DN in 
entries, making the move operation costly - and we reverted back to a 
system where the move operation is O(1) instead of being O(N).
When we have subentries and operational attributes stored into entries 
referring those subentries, then the move operation is again one in O(N).

This is not acceptable, and of course, changing this comes with a price 
we have to pay for every user operation, but I don't see how we can 
accept to have an O(N) Move operation when we have subentries, but not 
when it comes to store the DN within the entries.

Thoughts ?

> There's a reason why I implemented it this way 5 years ago. I still think
> it's sound. It's a matter of when you choose to pay for the administrative
> change which BTW should not happen that often while reads happen all the
> time. I'd rather pay a lot for infrequent operations than a little bit for
> the most common operations.
>


-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com


Re: Subentries handling refactoring

Posted by Alex Karasulu <ak...@apache.org>.
On Thu, Jul 15, 2010 at 8:33 PM, Emmanuel Lecharny <el...@gmail.com>wrote:

>  Hi guys,
>
> we have serious issues with the way we manage subentries in the server. Not
> that it's not working, but it's certainly not good enough for anything but a
> toy server.
>
>
I disagree. Adding a subentry is an administrative operation. If you do so
you better be prepared to pay the price if you've done so after adding
millions of entries as you point out. This is why we add subentries first
then populate the server.

The idea is that the cost is paid not during search time but during
administrative changes and writes.


> Let me first give some heads up about what's going on.
>
> A subentry is associated with an AdministrativePoint (AP), and defines a
> selection of entries which will be affected depending on the AP role. Those
> roles are :
> - Access Control
> - Collective Attributes
> - SubSchema (not active atm)
> - Triggers (ADS specific).
>
> For instance, if we have a tree with a set of entries associated with a
> location (ie, c=France), we may define a subentry with a Collective
> Attribute role telling the server that every entry under the c=France branch
> will have a specific attribute added. We don't have then to add this
> attribute to *every* entry in this branch...
>
> Anyway...
>
> A subentry defines a selection using a filter, and a base DN for this
> filter to be active from.
>
> Right now, a Subentry is attached to an AP as a (quite) normal entry, and
> when we add this subentry, we modidy *all* the selected entries (using the
> subentry filter and the base DN) will be modified to have a new attribute
> added. This added attribute contains a DN poiting to the associated
> subentry, so that when we process this entry, we can immediately know that
> it's associated with an AP.
>
> So far, so good : processing an entry is fast, as we have all what we need
> when we have the entry. But the dark side is that if we have millions of
> entries, when we add an AP and a subentry, we may have to modify potentially
> *millions* of entries to add this attribute. Not good...
>
> How can we improve this process ?
>
> The idea would be to search for the APs when we process an entry, but it
> has to be fast. How can we do that ? Simple : we use the entry's DN and
> using a DN cache, we can get all the APs associated with an entry knowing
> its DN. It's as costly as the depth of the entry's DN. Once we have grabbed
> the APs, we will have to evaluate the entry to know if it's part of the
> selections defined by the APs' subentry. Done.
>
> Is it costly ? Only marginaly compared to the current algorithm, as we have
> to lookup for the AP, when we have this list in an Attribute in the current
> server. But we spare the big modifications when adding - or
> removing/renaming/moving - a subentry.
>
> What we just need is a APs cache and a way to process it.
>
> This is what I will work on in the next few days if nobody objects or find
> a better algorithm.
>
>
I'm sorry but I have to veto this change. It's not acceptable to be taxing
an LDAP server's read performance when this should be done during writes or
during administrative changes.

There's a reason why I implemented it this way 5 years ago. I still think
it's sound. It's a matter of when you choose to pay for the administrative
change which BTW should not happen that often while reads happen all the
time. I'd rather pay a lot for infrequent operations than a little bit for
the most common operations.

-- 
Alex Karasulu
My Blog :: http://www.jroller.com/akarasulu/
Apache Directory Server :: http://directory.apache.org
Apache MINA :: http://mina.apache.org
To set up a meeting with me: http://tungle.me/AlexKarasulu

Re: Subentries handling refactoring

Posted by Emmanuel Lecharny <el...@gmail.com>.
  On 7/15/10 9:03 PM, Kiran Ayyagari wrote:
> have not touched this part of the server so here are some (naive) questions
>
> On Thu, Jul 15, 2010 at 11:03 PM, Emmanuel Lecharny<el...@gmail.com>  wrote:
>>   Hi guys,
>>
>> we have serious issues with the way we manage subentries in the server. Not
>> that it's not working, but it's certainly not good enough for anything but a
>> toy server.
>>
>> Let me first give some heads up about what's going on.
>>
>> A subentry is associated with an AdministrativePoint (AP), and defines a
>> selection of entries which will be affected depending on the AP role. Those
>> roles are :
>> - Access Control
>> - Collective Attributes
>> - SubSchema (not active atm)
>> - Triggers (ADS specific).
>>
>> For instance, if we have a tree with a set of entries associated with a
>> location (ie, c=France), we may define a subentry with a Collective
>> Attribute role telling the server that every entry under the c=France branch
>> will have a specific attribute added. We don't have then to add this
>> attribute to *every* entry in this branch...
>>
>> Anyway...
>>
>> A subentry defines a selection using a filter, and a base DN for this filter
>> to be active from.
>>
>> Right now, a Subentry is attached to an AP as a (quite) normal entry, and
>> when we add this subentry, we modidy *all* the selected entries (using the
>> subentry filter and the base DN) will be modified to have a new attribute
>> added.
> AFAIU we update all the entries with this new info, do we really need
> to do this?

Of course not.

> is it done that way to avoid any search evaluation costs?

No, I think it's was done this way because it was the easiest way to 
make it works, as a preliminary approach. Sometime, you have to balance 
between good and best.
>> This added attribute contains a DN poiting to the associated
>> subentry, so that when we process this entry, we can immediately know that
>> it's associated with an AP.
>>
>> So far, so good : processing an entry is fast, as we have all what we need
>> when we have the entry. But the dark side is that if we have millions of
>> entries, when we add an AP and a subentry, we may have to modify potentially
>> *millions* of entries to add this attribute. Not good...
>>
>> How can we improve this process ?
>>
>> The idea would be to search for the APs when we process an entry, but it has
>> to be fast. How can we do that ? Simple : we use the entry's DN and using a
>> DN cache, we can get all the APs associated with an entry knowing its DN.
>> It's as costly as the depth of the entry's DN. Once we have grabbed the APs,
>> we will have to evaluate the entry to know if it's part of the selections
>> defined by the APs' subentry. Done.
>>
>> Is it costly ? Only marginaly compared to the current algorithm, as we have
>> to lookup for the AP, when we have this list in an Attribute in the current
>> server. But we spare the big modifications when adding - or
>> removing/renaming/moving - a subentry.
>>
>> What we just need is a APs cache and a way to process it.
>>
>> This is what I will work on in the next few days if nobody objects or find a
>> better algorithm.
> how about having a Index on subEntry instead of a cache, one immediate
> advantage I see is
> that we don't need to cache DNs which will help in minimizing the
> modify() operation's time.
We just cache the APs' DN, and we won't have many. We will also have an 
index on subentry, but this is different.

When we init the system, we will load all the subentries in the cache, 
using the index to get them from the backend.--


Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com


Re: Subentries handling refactoring

Posted by Kiran Ayyagari <ka...@apache.org>.
have not touched this part of the server so here are some (naive) questions

On Thu, Jul 15, 2010 at 11:03 PM, Emmanuel Lecharny <el...@gmail.com> wrote:
>  Hi guys,
>
> we have serious issues with the way we manage subentries in the server. Not
> that it's not working, but it's certainly not good enough for anything but a
> toy server.
>
> Let me first give some heads up about what's going on.
>
> A subentry is associated with an AdministrativePoint (AP), and defines a
> selection of entries which will be affected depending on the AP role. Those
> roles are :
> - Access Control
> - Collective Attributes
> - SubSchema (not active atm)
> - Triggers (ADS specific).
>
> For instance, if we have a tree with a set of entries associated with a
> location (ie, c=France), we may define a subentry with a Collective
> Attribute role telling the server that every entry under the c=France branch
> will have a specific attribute added. We don't have then to add this
> attribute to *every* entry in this branch...
>
> Anyway...
>
> A subentry defines a selection using a filter, and a base DN for this filter
> to be active from.
>
> Right now, a Subentry is attached to an AP as a (quite) normal entry, and
> when we add this subentry, we modidy *all* the selected entries (using the
> subentry filter and the base DN) will be modified to have a new attribute
> added.
AFAIU we update all the entries with this new info, do we really need
to do this?
is it done that way to avoid any search evaluation costs?

> This added attribute contains a DN poiting to the associated
> subentry, so that when we process this entry, we can immediately know that
> it's associated with an AP.
>
> So far, so good : processing an entry is fast, as we have all what we need
> when we have the entry. But the dark side is that if we have millions of
> entries, when we add an AP and a subentry, we may have to modify potentially
> *millions* of entries to add this attribute. Not good...
>
> How can we improve this process ?
>
> The idea would be to search for the APs when we process an entry, but it has
> to be fast. How can we do that ? Simple : we use the entry's DN and using a
> DN cache, we can get all the APs associated with an entry knowing its DN.
> It's as costly as the depth of the entry's DN. Once we have grabbed the APs,
> we will have to evaluate the entry to know if it's part of the selections
> defined by the APs' subentry. Done.
>
> Is it costly ? Only marginaly compared to the current algorithm, as we have
> to lookup for the AP, when we have this list in an Attribute in the current
> server. But we spare the big modifications when adding - or
> removing/renaming/moving - a subentry.
>
> What we just need is a APs cache and a way to process it.
>
> This is what I will work on in the next few days if nobody objects or find a
> better algorithm.

how about having a Index on subEntry instead of a cache, one immediate
advantage I see is
that we don't need to cache DNs which will help in minimizing the
modify() operation's time.
Many random thoughts about how this can be implemented are running in
my mind at the moment, but need some feedback if this Index based idea
is correct which means I
understood the problem correctly

thanks Emmanuel

Kiran Ayyagari