directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Karasulu <akaras...@gmail.com>
Subject Re: [ApacheDS] A solution for the subentry association performance problem
Date Sat, 28 Mar 2009 10:26:36 GMT
On Sat, Mar 28, 2009 at 7:46 AM, Ersin ER <ersin.er@gmail.com> wrote:

> Hi,
>
> The problem you mentioned and many more (collective attrs, dynamic groups)
> of that type are related to computed attributes. The solution is to develop
> a Virtual Attribute Computation layer on top of partitions.


Exactly! I was thinking of some mechanisms to enable this.  Namely the idea
of some kind of virtual subsystem came  to mind which would be passed into
partitions for their utilization in search and lookup operations.  First
virtual attributes must be injected into entries when they are looked up.
Second some kind of virtual Index needs to be presented/exposed to allow a
search engine implementation to be able to correctly apply a filter on these
non-physical attributes.


> Of course it's not that easy to implement as it's said but that's something
> we strongly need for many other features we want to implement. I had
> reported this issue here:
>
> http://issues.apache.org/jira/browse/DIRSERVER-1067
>
> Although I do not have a detailed solution proposal what I want to say is
> that it's a more general problem which blocks us implementing other nice
> features.


In this specific case where a subentry index is used I was thinking it's an
implementation detail that I call it an index.  You just need to expose
mappings and allow partitions to access them.  A btree works well in this
case to store precomputed values of subtree specification evaluation.  In
this specific example you are just caching computed attributes, but
essentially these are just as virtual and computed as other kinds of virtual
attributes we've envisioned.

Alex


>
>
> On Sat, Mar 28, 2009 at 03:57, Alex Karasulu <akarasulu@apache.org> wrote:
>
>> Hi all,
>>
>> <note>
>> Not a dig at anyone for supporting DN presence in entries.
>> </note>
>>
>> Similar Problem We Are Familiar With
>> --------------------------------------------------------------
>>
>> During this ApacheCon we had discussions around the problem of embedding
>> the DN in an entry.  Presently the DN is maintained in an entry and in the
>> DN index.  This makes it very expensive to perform modifyDn operations.  The
>> classic scenario of this is when a parent entry containing millions of
>> descendants has it's DN modified.  The result is devastating:
>>
>> (1) millions of entries are looked up from the master table
>>      (a) millions of disk blocks are accessed
>>      (b) millions of entries are deserialized
>> (2) the entry cache turns over loosing it's cache hit memory
>> (3) the operation can take minutes if not hours
>>
>>
>> The Problem With Subentry Changes
>> ------------------------------------------------------------
>>
>> Almost the same exact problem is causing the subentry performance issue we
>> have been observing.  When a subentry is created, all entries selected by
>> the subentry's subtree specification are altered to point to that subentry
>> for it's administrative purpose.  For example, if the subentry is for access
>> control then the accessControlSubentries multi-valued attribute has the DN
>> of the subentry added to any entry selected by the subentry's
>> subtreeSpecification.  This attribute is persisted in the entry within the
>> master table.  When the subentry is removed, renamed, or it's subtree
>> specification is altered, all the old entries selected previously are
>> recalled from the master table to remove the old reference.  Then the new
>> reference is added to all entries selected by the new filter.
>>
>> This process is very expensive as is the modifyDN issue because of the
>> massive number of master table read-write operations.  As with the modifyDN
>> problem a specialized index could minimize the impact of these kinds of
>> alterations on large sets of entries.
>>
>>
>> The Solution
>> --------------------
>>
>> First a special [subentry ID<->entry ID] index will be maintained.  This
>> maps the ID of a subentry to the ID of the entry the subentry selects via
>> it's subtree specification.  Note we're not differentiating between the
>> different kinds of subentries.  When an entry is looked up specifically
>> asking for a subentry association attribute like accessControlSubentries
>> then we can inject this attribute into the entry before returning it.  To
>> compute the contents of the accessControlSubentries attribute all we have to
>> do is walk this index in the opposite direction for the entry ID.  For each
>> subentry all we have to do is check the objectClass index to see if it is an
>> accessControlSubentry.  If it is then the DN of that entry is added to the
>> accessControlSubentries attribute.  Since subentry reference attributes are
>> all operational and normally are not returned unless explicitly asked for,
>> we seldom need to add these attributes nor do we need to access this index.
>>
>> Presently the authorization/subtree subsystem will inject these attributes
>> into entries before pumping them into the partition.  This means that we can
>> maintain this index by finding these subentry association attributes and
>> using their information before deleting them.
>>
>> Issues
>> ----------
>>
>> I don't like this solution since it puts more responsibility on the
>> partition implementation to consistently adhere to these semantics.  It also
>> presumes every partition will have the ability to create this index. This
>> makes me uncomfortable.  However this would make these server faster in it's
>> ability to respond to subentry changes.  All the changes would occur on this
>> index instead of on the master table.
>>
>> Thoughts?
>>
>> Alex
>>
>>
>>
>>
>
>
> --
> Ersin ER
> http://www.ersiner.net
>

Mime
View raw message