Hi Emmanuel,

On Sun, Jul 18, 2010 at 11:09 AM, Emmanuel Lécharny <elecharny@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