You are viewing a plain text version of this content. The canonical link for it is here.
Posted to api@directory.apache.org by Emmanuel Lecharny <el...@gmail.com> on 2010/07/28 10:56:52 UTC
Hi guys,
I was thinking lately about the DN class. I know that OpenDS (and
probably UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory
that returns a DN potentially leveraging a cache associated to a
ThreadLocal.
At first, I thought this was an excellent idea, and started to implement
such a method in the DN class, but I didn't had time to finalize the
code, so I let it beside for a while.
Now that I have had a bit of discussion about caching strategy inside a
server, I'm coming back to this specific valueOf() method.
I don't think it's such a good idea :
- first, as it's ThreadLocal based, you will have as many cache as you
have threads processing requests. Not sure it competes with a unique
cache, not sure either we can't use the memory in a better way...
- second, this is a server side cache : we don'yt need it on the client
side (or, more specifically, if we need it, then I don't think it
deserves to be managed by the DN class)
I would rather define a dedicated class, with a static method - a
factory -, something like :
DnFactory, with a createDn( "<a DN>" ) method. This factory will handle
its cache, which will be global.
thoughts ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: DN and valueOf( "" ) method
Posted by Kiran Ayyagari <ka...@apache.org>.
On Wed, Jul 28, 2010 at 2:26 PM, Emmanuel Lecharny <el...@gmail.com> wrote:
> Hi guys,
>
> I was thinking lately about the DN class. I know that OpenDS (and probably
> UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory that returns a
> DN potentially leveraging a cache associated to a ThreadLocal.
>
> At first, I thought this was an excellent idea, and started to implement
> such a method in the DN class, but I didn't had time to finalize the code,
> so I let it beside for a while.
>
> Now that I have had a bit of discussion about caching strategy inside a
> server, I'm coming back to this specific valueOf() method.
>
> I don't think it's such a good idea :
> - first, as it's ThreadLocal based, you will have as many cache as you have
> threads processing requests. Not sure it competes with a unique cache, not
> sure either we can't use the memory in a better way...
> - second, this is a server side cache : we don'yt need it on the client side
> (or, more specifically, if we need it, then I don't think it deserves to be
> managed by the DN class)
>
> I would rather define a dedicated class, with a static method - a factory -,
> something like :
> DnFactory, with a createDn( "<a DN>" ) method. This factory will handle its
> cache, which will be global.
yeap, global cache sounds cool, will experiment with it
thanks Emmanuel
Kiran Ayyagari
Re: DN and valueOf( "" ) method
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 8/10/10 9:58 AM, Matthew Swift wrote:
> [...]
>> But are you going to have 16K threads anyway ?
>
>
> Perhaps not today, but perhaps tomorrow.
Here, we are entering into the plain IO vs NIO debate.
There is no limit in the number of threads you can start on a JVM except
the available memory, the JVM configuration (especially the -Xss size.
It defaults to 1024, which is way to big if you are going to have 100K
threads...) and obviously the OS you are running on.
>
> There are already very large CMT (core multi-threading) machines in
> the pipeline from various vendors and I have heard and read
> projections of 10K+ thread CMT machines in the next few years. Hence
> the fork/join work going on in JDK7 at the moment and the push for
> closures.
>
> Since many server apps size their thread pools based on the number of
> available processors (core threads on CMT machines) then it is not
> that unlikely in the next few years.
>
> I think that even today some app server environments run with tens of
> thousands of threads.
Most certainly...
>
> Basically, we have no control over how other people use our SDK so,
> while I might not use 16K threads, someone else might :-(
Well, I see no benefit in having 16K threads if the server is NIO based.
But it might well be a good idea to switch to plain IOs, if we can scale
to tens of thousands of connected sessions. This is the main issue here,
compared to a Http server, for instance (where session are short lived).
But even for a LDAP server, I'm not sure that we really need to deal
with hundred of thousands opened sessions... Generally speaking, I'm not
sure it's secure to 'open' the LDAP server to end users, so it's very
likely that the server will be accessed by an application, which will
probably not open a session per user, but instead use a pool of sessions
and reuse it.
This is an interesting debate...
We are using MINA here, which is a NIO based framework, but I foresee a
version which would be a pure IO framework, using either plain IO or
NIO. That could help to conduct tests to see what will be the best
solution (some like Paul Tyma think - and he even demonstrated - that IO
is 30% fatser than NIO, even with thousands of threads :
http://mailinator.blogspot.com/2008/02/kill-myth-please-nio-is-not-faster-than.html)
>
>
>>>
>>> A major problem with this approach if we choose to use it in the
>>> OpenDS SDK is that common ancestor DNs (e.g. "dc=com") are going to
>>> end up in a single LHM so, using our current design (RDN + parent
>>> DN), all decoding attempts will usually end up contending on the
>>> same lock anyway :-( So we may need to change our DN implementation
>>> to better cope with this caching strategy.
>>>
>>> We are not alone though: a concurrent Map implementation which can
>>> be used for caching in a similar manner to LHM is one of the most
>>> frequently demanded enhancements to the java.util.concurrent library.
>> There might be some other data structure available, we may need to do
>> some research in this area...
>>
>>
>
> I did have a poke around some time ago and found a couple. I didn't
> evaluate them though as I seem to remember that they introduced a lot
> of extra "baggage" and I'd like to keep the size of the SDK to a
> minimum (to be honest, I think our OpenDS SDK is already too big).
It would be a pain to carry 1 more Mb of useless libs, true...
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: DN and valueOf( "" ) method
Posted by Matthew Swift <ma...@oracle.com>.
[...]
>> This idea needs testing. In particular, we'd need to figure out the
>> optimal array size (i.e. number of locks / LHMs). For example,
>> distributing the cache over 16 LHMs is not going to help much for
>> really big multi-threaded apps containing 16000+ threads (1000
>> threads contending per lock).
> But are you going to have 16K threads anyway ?
Perhaps not today, but perhaps tomorrow.
There are already very large CMT (core multi-threading) machines in the
pipeline from various vendors and I have heard and read projections of
10K+ thread CMT machines in the next few years. Hence the fork/join work
going on in JDK7 at the moment and the push for closures.
Since many server apps size their thread pools based on the number of
available processors (core threads on CMT machines) then it is not that
unlikely in the next few years.
I think that even today some app server environments run with tens of
thousands of threads.
Basically, we have no control over how other people use our SDK so,
while I might not use 16K threads, someone else might :-(
>>
>> A major problem with this approach if we choose to use it in the
>> OpenDS SDK is that common ancestor DNs (e.g. "dc=com") are going to
>> end up in a single LHM so, using our current design (RDN + parent
>> DN), all decoding attempts will usually end up contending on the same
>> lock anyway :-( So we may need to change our DN implementation to
>> better cope with this caching strategy.
>>
>> We are not alone though: a concurrent Map implementation which can be
>> used for caching in a similar manner to LHM is one of the most
>> frequently demanded enhancements to the java.util.concurrent library.
> There might be some other data structure available, we may need to do
> some research in this area...
>
>
I did have a poke around some time ago and found a couple. I didn't
evaluate them though as I seem to remember that they introduced a lot of
extra "baggage" and I'd like to keep the size of the SDK to a minimum
(to be honest, I think our OpenDS SDK is already too big).
Matt
Re: DN and valueOf( "" ) method
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 8/9/10 4:16 PM, Matthew Swift wrote:
>
>
> On 28/07/10 13:07, Emmanuel Lecharny wrote:
>> On 7/28/10 11:31 AM, Stefan Seelmann wrote:
>>>> I was thinking lately about the DN class. I know that OpenDS (and
>>>> probably
>>>> UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory that
>>>> returns a
>>>> DN potentially leveraging a cache associated to a ThreadLocal.
>>>>
>>> ...
>>>> I don't think it's such a good idea :
>>>> - first, as it's ThreadLocal based, you will have as many cache as
>>>> you have
>>>> threads processing requests. Not sure it competes with a unique
>>>> cache, not
>>>> sure either we can't use the memory in a better way...
>>> An advantage to use ThreadLocal is that you don't need to synchronize
>>> access to the cache Could be worth to measure the performance
>> Using ConcurrentHashMap should not be a major performance penalty. I
>> mean, it *will* be more costly than not having any synchronization
>> but it sounds acceptable.
>
>
> Unfortunately a CHM won't help either since you need to manage cache
> eviction, assuming that you want the cache to have a finite size.
> LinkedHashMap has an eviction strategy which can be defined by
> overriding the removeEldestEntry method, but unfortunately LHM is not
> thread safe.
Doh !!! I should have thought about it immediately... That's the problem
when you are pushing random thoughts on the ML instead of *really*
coding them.
>
>> difference, I wonder if the OpenDS team did some performance analysis?
>
>
> I did some testing some time back and I have forgotten the exact
> figures that I got. I do remember finding a substantial performance
> improvement when parsing DNs when caching is enabled - something like
> 30ns with caching vs 300ns without for DNs containing 4 RDN components
> (i.e. about an order of magnitude IIRC).
>
> We implement our DNs using a recursive RDN + parent DN structure so we
> are usually able to fast track the decoding process to just a single
> RDN for DNs having a common ancestor (pretty common).
Our idea was that the first step would be to quickly compute the DN (as
a String) hashcode, and check if it has already been parsed. If not,
then we fallback to a plain parsing. But having the low level DN stored
in the cache is a good idea.
There are definitively many options, we should conduct some perf tests
based on real world DN to see what's the best.
>
> We opted for the ThreadLocal approach due to the synchronization
> limitations of using a single global cache. However, I have often
> worried about this approach as it will not scale for applications
> having large numbers of threads, resulting in OOM exceptions.
yes, true. But this is also a fast-track solution, bringing immediate
benefits.
>
> Another approach I have thought about is to use a single global
> two-level cache comprising of a fixed size array of LinkedHashMaps
> (think of it as a Map of Maps) each one having its own
> synchronization. We then distribute the DNs over the LHMs and amortize
> the synchronization costs across multiple locks (in a similar manner
> to CHM).
Another aspect we are interested in is the pining of frequently used DN
(cn=schema, etc). Not sure it worth the effort though...
>
> This idea needs testing. In particular, we'd need to figure out the
> optimal array size (i.e. number of locks / LHMs). For example,
> distributing the cache over 16 LHMs is not going to help much for
> really big multi-threaded apps containing 16000+ threads (1000 threads
> contending per lock).
But are you going to have 16K threads anyway ?
>
> A major problem with this approach if we choose to use it in the
> OpenDS SDK is that common ancestor DNs (e.g. "dc=com") are going to
> end up in a single LHM so, using our current design (RDN + parent DN),
> all decoding attempts will usually end up contending on the same lock
> anyway :-( So we may need to change our DN implementation to better
> cope with this caching strategy.
>
> We are not alone though: a concurrent Map implementation which can be
> used for caching in a similar manner to LHM is one of the most
> frequently demanded enhancements to the java.util.concurrent library.
There might be some other data structure available, we may need to do
some research in this area...
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: DN and valueOf( "" ) method
Posted by Matthew Swift <ma...@oracle.com>.
On 28/07/10 13:07, Emmanuel Lecharny wrote:
> On 7/28/10 11:31 AM, Stefan Seelmann wrote:
>>> I was thinking lately about the DN class. I know that OpenDS (and
>>> probably
>>> UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory that
>>> returns a
>>> DN potentially leveraging a cache associated to a ThreadLocal.
>>>
>> ...
>>> I don't think it's such a good idea :
>>> - first, as it's ThreadLocal based, you will have as many cache as
>>> you have
>>> threads processing requests. Not sure it competes with a unique
>>> cache, not
>>> sure either we can't use the memory in a better way...
>> An advantage to use ThreadLocal is that you don't need to synchronize
>> access to the cache Could be worth to measure the performance
> Using ConcurrentHashMap should not be a major performance penalty. I
> mean, it *will* be more costly than not having any synchronization but
> it sounds acceptable.
Unfortunately a CHM won't help either since you need to manage cache
eviction, assuming that you want the cache to have a finite size.
LinkedHashMap has an eviction strategy which can be defined by
overriding the removeEldestEntry method, but unfortunately LHM is not
thread safe.
>
> Another possibility is to use a CopyOnWriteArraySet, but I'm afraid
> that it will crawl if many new DN are added.
Yes - this is not an appropriate collection to use.
>> difference, I wonder if the OpenDS team did some performance analysis?
I did some testing some time back and I have forgotten the exact figures
that I got. I do remember finding a substantial performance improvement
when parsing DNs when caching is enabled - something like 30ns with
caching vs 300ns without for DNs containing 4 RDN components (i.e. about
an order of magnitude IIRC).
We implement our DNs using a recursive RDN + parent DN structure so we
are usually able to fast track the decoding process to just a single RDN
for DNs having a common ancestor (pretty common).
We opted for the ThreadLocal approach due to the synchronization
limitations of using a single global cache. However, I have often
worried about this approach as it will not scale for applications having
large numbers of threads, resulting in OOM exceptions.
Another approach I have thought about is to use a single global
two-level cache comprising of a fixed size array of LinkedHashMaps
(think of it as a Map of Maps) each one having its own synchronization.
We then distribute the DNs over the LHMs and amortize the
synchronization costs across multiple locks (in a similar manner to CHM).
This idea needs testing. In particular, we'd need to figure out the
optimal array size (i.e. number of locks / LHMs). For example,
distributing the cache over 16 LHMs is not going to help much for really
big multi-threaded apps containing 16000+ threads (1000 threads
contending per lock).
A major problem with this approach if we choose to use it in the OpenDS
SDK is that common ancestor DNs (e.g. "dc=com") are going to end up in a
single LHM so, using our current design (RDN + parent DN), all decoding
attempts will usually end up contending on the same lock anyway :-( So
we may need to change our DN implementation to better cope with this
caching strategy.
We are not alone though: a concurrent Map implementation which can be
used for caching in a similar manner to LHM is one of the most
frequently demanded enhancements to the java.util.concurrent library.
> They compared the performances they get with a ThreadLocal cache and
> no cache : the gain was sensible (I don't have the number for OpenDS).
> FYI, the DN parsing count for more or less 13% of the whole CPU needed
> internally (network excluded) to process a simple search, and
> normalization cost an extra 10%. There is most certainly a net
> potential gain to implement a DN cache !
>
>
Agreed DN parsing can be expensive, especially normalization.
Matt
Re: DN and valueOf( "" ) method
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 7/28/10 10:32 PM, Kiran Ayyagari wrote:
> On Wed, Jul 28, 2010 at 4:37 PM, Emmanuel Lecharny<el...@gmail.com> wrote:
>> On 7/28/10 11:31 AM, Stefan Seelmann wrote:
>>>> </snip>
> I have just committed a DNFactory implementation [1].
Seems good to have.
> But the real
> issue with this is that
> the ApacheDS's DN class is mutable and hence will cause issues[2].
Oh, yeah. DN should be immutable !
> A working solution I have is to return a clone of the DN *all* the
> time (whether a hit or a miss)
nah way too costly. I would rather forbid any modification on an
existing DN. Methods adding or removing RDNs from a DN should copy the
DN before applying the modification. The problem is that iterating throw
RDNs to create a DN will be costly. Code like :
RDN rdns = new RDN[] { rdn1, rdn2, rdn3, ..., rdn7 };
DN dn = new DN( "ou=system" );
for ( RDN rdn : rdns )
{
dn.add( rdn );
}
will see 7 copies to be created. Simply insane...
May be we should extend the API to have something like a add( DN, RDN )
method which allow a modification to be done without copy ?
> this is guaranteed to work and am thinking that cloning() is way
> faster than the time required for
> parsing and normalizing a DN from the beginning. But one penalty we
> pay for this solution is that
> two instances(of which one is just a clone) will be created for every
> DN miss in the cache.
We should think about what it would cost to make DN an immutable class,
and see what's the impact on the existing cost. I don't think we can
ignore the problem anymore...
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: DN and valueOf( "" ) method
Posted by Kiran Ayyagari <ka...@apache.org>.
On Wed, Jul 28, 2010 at 4:37 PM, Emmanuel Lecharny <el...@gmail.com> wrote:
> On 7/28/10 11:31 AM, Stefan Seelmann wrote:
>>>
>>> I was thinking lately about the DN class. I know that OpenDS (and
>>> probably
>>> UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory that
>>> returns a
>>> DN potentially leveraging a cache associated to a ThreadLocal.
>>>
>> ...
>>>
>>> I don't think it's such a good idea :
>>> - first, as it's ThreadLocal based, you will have as many cache as you
>>> have
>>> threads processing requests. Not sure it competes with a unique cache,
>>> not
>>> sure either we can't use the memory in a better way...
>>
>> An advantage to use ThreadLocal is that you don't need to synchronize
>> access to the cache Could be worth to measure the performance
>
> Using ConcurrentHashMap should not be a major performance penalty. I mean,
> it *will* be more costly than not having any synchronization but it sounds
> acceptable.
>
> Another possibility is to use a CopyOnWriteArraySet, but I'm afraid that it
> will crawl if many new DN are added.
>>
>> difference, I wonder if the OpenDS team did some performance analysis?
>
> They compared the performances they get with a ThreadLocal cache and no
> cache : the gain was sensible (I don't have the number for OpenDS). FYI, the
> DN parsing count for more or less 13% of the whole CPU needed internally
> (network excluded) to process a simple search, and normalization cost an
> extra 10%. There is most certainly a net potential gain to implement a DN
> cache !
I have just committed a DNFactory implementation [1]. But the real
issue with this is that
the ApacheDS's DN class is mutable and hence will cause issues[2].
A working solution I have is to return a clone of the DN *all* the
time (whether a hit or a miss)
this is guaranteed to work and am thinking that cloning() is way
faster than the time required for
parsing and normalizing a DN from the beginning. But one penalty we
pay for this solution is that
two instances(of which one is just a clone) will be created for every
DN miss in the cache.
P.S:- haven't committed the above mentioned solution
Kiran Ayyagari
[1] https://svn.apache.org/repos/asf/directory/apacheds/branches/apacheds-dnfactory-experiment/core/src/main/java/org/apache/directory/server/core/DNFactory.java
[2] the test testToSysDn() in PreferencesUtilsTest class fails because
of the mutable DN reference returned from cache
Re: DN and valueOf( "" ) method
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 7/28/10 11:31 AM, Stefan Seelmann wrote:
>> I was thinking lately about the DN class. I know that OpenDS (and probably
>> UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory that returns a
>> DN potentially leveraging a cache associated to a ThreadLocal.
>>
> ...
>> I don't think it's such a good idea :
>> - first, as it's ThreadLocal based, you will have as many cache as you have
>> threads processing requests. Not sure it competes with a unique cache, not
>> sure either we can't use the memory in a better way...
> An advantage to use ThreadLocal is that you don't need to synchronize
> access to the cache Could be worth to measure the performance
Using ConcurrentHashMap should not be a major performance penalty. I
mean, it *will* be more costly than not having any synchronization but
it sounds acceptable.
Another possibility is to use a CopyOnWriteArraySet, but I'm afraid that
it will crawl if many new DN are added.
> difference, I wonder if the OpenDS team did some performance analysis?
They compared the performances they get with a ThreadLocal cache and no
cache : the gain was sensible (I don't have the number for OpenDS). FYI,
the DN parsing count for more or less 13% of the whole CPU needed
internally (network excluded) to process a simple search, and
normalization cost an extra 10%. There is most certainly a net potential
gain to implement a DN cache !
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: DN and valueOf( "" ) method
Posted by Stefan Seelmann <se...@apache.org>.
> I was thinking lately about the DN class. I know that OpenDS (and probably
> UnboundId, but not sure) has a DN.valueOf( "<a DN>" ) factory that returns a
> DN potentially leveraging a cache associated to a ThreadLocal.
>
...
>
> I don't think it's such a good idea :
> - first, as it's ThreadLocal based, you will have as many cache as you have
> threads processing requests. Not sure it competes with a unique cache, not
> sure either we can't use the memory in a better way...
An advantage to use ThreadLocal is that you don't need to synchronize
access to the cache Could be worth to measure the performance
difference, I wonder if the OpenDS team did some performance analysis?