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 Lécharny <el...@gmail.com> on 2012/04/24 13:28:30 UTC
Questions regarding Aliases
Hi guys,
Aliases handling is one of the biggest challenge in LDAP, as it imposes
a lot of constraints. First of all, keep in mind that Alias support is
not mandatory.
Some of the problem we have when dealing with Alaises are :
- cycle detection : we should not allow the creation of an alias that
causes a cycle
- duplicated entry removals in searches : we shuld not return an entry
that has already been returned
- unlinked aliases : when the aliased entry is removed, we should should
handle it
- subtree searches with aliases : we may have a very high nunber of
entries to return
- move operation : how do we handle the aliases modification when the
aliased entries is move ?
- cross-partitions aliases : how do we handle them ?
- replication of aliases
Right now, my concern is about duplicated entries removal and cycle
detection, during a search processing :
1) Cycle detection :
Should we assume that the cycles are detected during the alias creation
? Or should we detect it while processing the search ? (I'm nclined to
think that cycle are forbidden during their creation)
2) duplicated entries removal
I don't see any other way but storing a hash of all the UUID we already
have transmitted, and to check when we have a new candidate if this
candidate has already been processed. This is potentially *extremely*
costly, if we have millions of entries (even if there is a size limit,
which protects us from a OOM, because this size limit is not enforced
for the manager user).
Is there a better way ?
3) Current Aliases index
I didn't have time to check what those index are used for, so if someone
can give me a quick heads up, that would save me a few days of code
diging...
Many thanks !
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Questions regarding Aliases
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/24/12 2:22 PM, Pierre-Arnaud Marcelot a écrit :
> On 24 avr. 2012, at 13:28, Emmanuel Lécharny wrote:
>> Hi guys,
>>
>> Aliases handling is one of the biggest challenge in LDAP, as it imposes a lot of constraints. First of all, keep in mind that Alias support is not mandatory.
>>
>> Some of the problem we have when dealing with Alaises are :
>> - cycle detection : we should not allow the creation of an alias that causes a cycle
>> - duplicated entry removals in searches : we shuld not return an entry that has already been returned
>> - unlinked aliases : when the aliased entry is removed, we should should handle it
>> - subtree searches with aliases : we may have a very high nunber of entries to return
>> - move operation : how do we handle the aliases modification when the aliased entries is move ?
>> - cross-partitions aliases : how do we handle them ?
>> - replication of aliases
>>
>> Right now, my concern is about duplicated entries removal and cycle detection, during a search processing :
>>
>> 1) Cycle detection :
>> Should we assume that the cycles are detected during the alias creation ? Or should we detect it while processing the search ? (I'm nclined to think that cycle are forbidden during their creation)
> I agree there should be a check during the creation of the entry (and move operations too, I guess).
>
> But, I think we also need to check for cycles during the evaluation of the search.
> If we use a batch insert mode with the server turned off to insert a large number of entries (even if we don't have such a possibility now, we might get it in a near future), we might have this kind of inconsistencies in the database.
IMO, even if we provide a batch mode (which we have to provide in the
near future !), the we also must provide a check tool in order to be
sure that we haven't injected crap into the database.
Checking for cycle can be a costly operation...
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Questions regarding Aliases
Posted by Pierre-Arnaud Marcelot <pa...@marcelot.net>.
On 24 avr. 2012, at 13:28, Emmanuel Lécharny wrote:
> Hi guys,
>
> Aliases handling is one of the biggest challenge in LDAP, as it imposes a lot of constraints. First of all, keep in mind that Alias support is not mandatory.
>
> Some of the problem we have when dealing with Alaises are :
> - cycle detection : we should not allow the creation of an alias that causes a cycle
> - duplicated entry removals in searches : we shuld not return an entry that has already been returned
> - unlinked aliases : when the aliased entry is removed, we should should handle it
> - subtree searches with aliases : we may have a very high nunber of entries to return
> - move operation : how do we handle the aliases modification when the aliased entries is move ?
> - cross-partitions aliases : how do we handle them ?
> - replication of aliases
>
> Right now, my concern is about duplicated entries removal and cycle detection, during a search processing :
>
> 1) Cycle detection :
> Should we assume that the cycles are detected during the alias creation ? Or should we detect it while processing the search ? (I'm nclined to think that cycle are forbidden during their creation)
I agree there should be a check during the creation of the entry (and move operations too, I guess).
But, I think we also need to check for cycles during the evaluation of the search.
If we use a batch insert mode with the server turned off to insert a large number of entries (even if we don't have such a possibility now, we might get it in a near future), we might have this kind of inconsistencies in the database.
More importantly, if we don't have such a mechanism and we actually do get a cycle (for one reason or another, shit happens), the server would be looping forever and the user would have no other way than stop/restart the server (and pray for the same search request to never appears again).
> 2) duplicated entries removal
> I don't see any other way but storing a hash of all the UUID we already have transmitted, and to check when we have a new candidate if this candidate has already been processed. This is potentially *extremely* costly, if we have millions of entries (even if there is a size limit, which protects us from a OOM, because this size limit is not enforced for the manager user).
> Is there a better way ?
I had the same mechanism in mind. Costly, but at some point, you need this knowledge of what entries have already been returned.
> 3) Current Aliases index
> I didn't have time to check what those index are used for, so if someone can give me a quick heads up, that would save me a few days of code diging…
Sorry, I have no idea… :(
Regards,
Pierre-Arnaud
> Many thanks !
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
Re: Questions regarding Aliases
Posted by Alex Karasulu <ak...@apache.org>.
On Wed, Apr 25, 2012 at 2:54 AM, Emmanuel Lécharny <el...@gmail.com>wrote:
> Le 4/24/12 8:06 PM, Alex Karasulu a écrit :
>
> On Tue, Apr 24, 2012 at 5:50 PM, Kiran Ayyagari<ka...@apache.org>**
>> wrote:
>>
>> On Tue, Apr 24, 2012 at 7:59 PM, Emmanuel Lécharny<el...@gmail.com>
>>> wrote:
>>>
>>>> Le 4/24/12 4:19 PM, Kiran Ayyagari a écrit :
>>>>
>>>>> On Tue, Apr 24, 2012 at 4:58 PM, Emmanuel Lécharny<elecharny@gmail.com
>>>>> >
>>>>> wrote:
>>>>>
>>>>>> 3) Current Aliases index
>>>>>>
>>>>>> I didn't have time to check what those index are used for, so if
>>>>>>
>>>>> someone
>>>
>>>> can
>>>>>> give me a quick heads up, that would save me a few days of code
>>>>>>
>>>>> diging...
>>>
>>>> this is used exactly for solving the above mentioned 'cycle detection'
>>>>> problem
>>>>>
>>>>
>>>> This was what I suspected, but how does it work ?
>>>>
>>>> we lookup the target entry's ID in the alias Index, if it is present
>>> we don't allow adding the current entry
>>>
>>
>> Kiran is right. There is some documentation on this available in our
>> site's
>> developer docuentation section here:
>>
>> http://directory.apache.org/**apacheds/1.5/alias-and-index.**html<http://directory.apache.org/apacheds/1.5/alias-and-index.html>
>>
>> Oooops it looks empty thought :(. Instead I have a paper I wrote on Alias
>> Dereferencing here on this page which you can access and download:
>>
>> http://people.apache.org/~**akarasulu/<http://people.apache.org/~akarasulu/>
>>
>> Note this paper is ancient. Perhaps even from 2000. However it should be
>> pretty much up to date with perhaps a name change of the indices used.
>>
>
> Thanks a lot ! I don't think we have had a lot of modification in the
> alias handling those past 5 years.
>
> I'll read this paper tomorrow.
>
> Right now, I'm finishing the SubLevel index removal. So far, I just have
> issues in LdifPartion (JdbmPartition tetss are now passing).
>
> What I did is that I have created a DescendantCursor that recursively go
> down the RdnIndex tree, fetching the children up to the point they have no
> children. It works well. For LdifPartition, it's slightly different as we
> have to udate the underlying AvlIndex (which works) but also update the
> ldif files with the minimum modifications.
>
> Note that it's done in a branch atm.
>
> Once this will be done, and merged back in trunk, I think we will be able
> to cut a release.
>
>
>
Sounds great. Thanks!
--
Best Regards,
-- Alex
Re: Questions regarding Aliases
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/24/12 8:06 PM, Alex Karasulu a écrit :
> On Tue, Apr 24, 2012 at 5:50 PM, Kiran Ayyagari<ka...@apache.org>wrote:
>
>> On Tue, Apr 24, 2012 at 7:59 PM, Emmanuel Lécharny<el...@gmail.com>
>> wrote:
>>> Le 4/24/12 4:19 PM, Kiran Ayyagari a écrit :
>>>> On Tue, Apr 24, 2012 at 4:58 PM, Emmanuel Lécharny<el...@gmail.com>
>>>> wrote:
>>>>> 3) Current Aliases index
>>>>>
>>>>> I didn't have time to check what those index are used for, so if
>> someone
>>>>> can
>>>>> give me a quick heads up, that would save me a few days of code
>> diging...
>>>> this is used exactly for solving the above mentioned 'cycle detection'
>>>> problem
>>>
>>> This was what I suspected, but how does it work ?
>>>
>> we lookup the target entry's ID in the alias Index, if it is present
>> we don't allow adding the current entry
>
> Kiran is right. There is some documentation on this available in our site's
> developer docuentation section here:
>
> http://directory.apache.org/apacheds/1.5/alias-and-index.html
>
> Oooops it looks empty thought :(. Instead I have a paper I wrote on Alias
> Dereferencing here on this page which you can access and download:
>
> http://people.apache.org/~akarasulu/
>
> Note this paper is ancient. Perhaps even from 2000. However it should be
> pretty much up to date with perhaps a name change of the indices used.
Thanks a lot ! I don't think we have had a lot of modification in the
alias handling those past 5 years.
I'll read this paper tomorrow.
Right now, I'm finishing the SubLevel index removal. So far, I just have
issues in LdifPartion (JdbmPartition tetss are now passing).
What I did is that I have created a DescendantCursor that recursively go
down the RdnIndex tree, fetching the children up to the point they have
no children. It works well. For LdifPartition, it's slightly different
as we have to udate the underlying AvlIndex (which works) but also
update the ldif files with the minimum modifications.
Note that it's done in a branch atm.
Once this will be done, and merged back in trunk, I think we will be
able to cut a release.
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Questions regarding Aliases
Posted by Alex Karasulu <ak...@apache.org>.
On Tue, Apr 24, 2012 at 5:50 PM, Kiran Ayyagari <ka...@apache.org>wrote:
> On Tue, Apr 24, 2012 at 7:59 PM, Emmanuel Lécharny <el...@gmail.com>
> wrote:
> > Le 4/24/12 4:19 PM, Kiran Ayyagari a écrit :
> >>
> >> On Tue, Apr 24, 2012 at 4:58 PM, Emmanuel Lécharny<el...@gmail.com>
> >> wrote:
> >>>
> >>> 3) Current Aliases index
> >>>
> >>> I didn't have time to check what those index are used for, so if
> someone
> >>> can
> >>> give me a quick heads up, that would save me a few days of code
> diging...
> >>>
> >> this is used exactly for solving the above mentioned 'cycle detection'
> >> problem
> >
> >
> > This was what I suspected, but how does it work ?
> >
> we lookup the target entry's ID in the alias Index, if it is present
> we don't allow adding the current entry
Kiran is right. There is some documentation on this available in our site's
developer docuentation section here:
http://directory.apache.org/apacheds/1.5/alias-and-index.html
Oooops it looks empty thought :(. Instead I have a paper I wrote on Alias
Dereferencing here on this page which you can access and download:
http://people.apache.org/~akarasulu/
Note this paper is ancient. Perhaps even from 2000. However it should be
pretty much up to date with perhaps a name change of the indices used.
--
Best Regards,
-- Alex
Re: Questions regarding Aliases
Posted by Kiran Ayyagari <ka...@apache.org>.
On Tue, Apr 24, 2012 at 7:59 PM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Le 4/24/12 4:19 PM, Kiran Ayyagari a écrit :
>>
>> On Tue, Apr 24, 2012 at 4:58 PM, Emmanuel Lécharny<el...@gmail.com>
>> wrote:
>>>
>>> 3) Current Aliases index
>>>
>>> I didn't have time to check what those index are used for, so if someone
>>> can
>>> give me a quick heads up, that would save me a few days of code diging...
>>>
>> this is used exactly for solving the above mentioned 'cycle detection'
>> problem
>
>
> This was what I suspected, but how does it work ?
>
we lookup the target entry's ID in the alias Index, if it is present
we don't allow adding the current entry
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
--
Kiran Ayyagari
Re: Questions regarding Aliases
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/24/12 4:19 PM, Kiran Ayyagari a écrit :
> On Tue, Apr 24, 2012 at 4:58 PM, Emmanuel Lécharny<el...@gmail.com> wrote:
>> 3) Current Aliases index
>> I didn't have time to check what those index are used for, so if someone can
>> give me a quick heads up, that would save me a few days of code diging...
>>
> this is used exactly for solving the above mentioned 'cycle detection' problem
This was what I suspected, but how does it work ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Questions regarding Aliases
Posted by Kiran Ayyagari <ka...@apache.org>.
On Tue, Apr 24, 2012 at 4:58 PM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Hi guys,
>
> Aliases handling is one of the biggest challenge in LDAP, as it imposes a
> lot of constraints. First of all, keep in mind that Alias support is not
> mandatory.
>
> Some of the problem we have when dealing with Alaises are :
> - cycle detection : we should not allow the creation of an alias that causes
> a cycle
> - duplicated entry removals in searches : we shuld not return an entry that
> has already been returned
> - unlinked aliases : when the aliased entry is removed, we should should
> handle it
> - subtree searches with aliases : we may have a very high nunber of entries
> to return
> - move operation : how do we handle the aliases modification when the
> aliased entries is move ?
> - cross-partitions aliases : how do we handle them ?
> - replication of aliases
>
> Right now, my concern is about duplicated entries removal and cycle
> detection, during a search processing :
>
> 1) Cycle detection :
> Should we assume that the cycles are detected during the alias creation ? Or
> should we detect it while processing the search ? (I'm nclined to think that
> cycle are forbidden during their creation)
>
> 2) duplicated entries removal
> I don't see any other way but storing a hash of all the UUID we already have
> transmitted, and to check when we have a new candidate if this candidate has
> already been processed. This is potentially *extremely* costly, if we have
> millions of entries (even if there is a size limit, which protects us from a
> OOM, because this size limit is not enforced for the manager user).
> Is there a better way ?
>
> 3) Current Aliases index
> I didn't have time to check what those index are used for, so if someone can
> give me a quick heads up, that would save me a few days of code diging...
>
this is used exactly for solving the above mentioned 'cycle detection' problem
> Many thanks !
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
--
Kiran Ayyagari