5:54 a.m.
Hey everyone,
Some people are already familiar with this thread. They can jump towards the end of email
to read a concrete proposal on how to implement LIRS in Infinispan. Others, those of you
interested obscure eviction algorithms, keep reading :)
Some time ago Manik asked me to look into implementation of a new, LIRS algorithm for
cache eviction. It is a well known fact that plain vanilla LRU algorithm, although simple
and easy to understand, under performs in cases of weak access locality (one time access
pages are not replaced timely, pages to be accessed soonest are unfortunately replaced,
and so on). There has been a new algorithm out there that is rather popular called LIRS
that addresses these shortcomings of LRU yet it retains LRU's simplicity.
That is where the easy part ends. Eviction algorithm, if not implemented in scalable and
lock free fashion can seriously degrade performance. Having a lock protected data
container (to use Infinispan lingo) causes high contention offsetting eviction precision
that we get by using algorithm such as LIRS. That set me off on to a search for
LinkedHashMap (most suitable for LIRS and LRU) like structure that is lock free. Ben
Manes, recently employed by Google, has been working on this problem for a while. His
first attempt to implement ConcurrentLinkedHashMap had a flaw that was discovered by
EhCache people and confirmed by Manik in his own test. Ben Manes' second design for
ConcurrentLinkedHashMap uses ideas from a well known seminal paper in the area of lock
free algorithms [1] and the new design looks valid, at least to me. His implementation of
ConcurrentLinkedHashMap is not finished yet.
However, even if we had ConcurrentLinkedHashMap today that puts us only half way from our
lock free LIRS implementation. LIRS does not use only one stack/list such as LRU but two.
LIRS, in some cases, performs a lot of node shifting within that list and transfers nodes
from one list to another. Manik and I talked about how we could potentially change
original LIRS and stick the whole thing into one stack (ConcurrentLinkedHashMap) by using
additional node markings and such. Overall, I think this is possible but full of potential
pitfalls.
Just before holidays while bashing Google scholar day after day I came across a research
paper [2] that I would say has a lot of potential, not only for our LIRS eviction data
container implementation but any other eviction algorithm implementation.
Instead of making a trade-off between the high hit ratio of an eviction algorithm and the
low lock contention there is a third way, and dare I say a excellent idea of lock
amortization. We can wrap any eviction algorithm with a framework that keeps track of
cache access per thread (ThreadLocal) in a simple data container, say a queue. For each
cache hit associated with a thread, the access history information is recorded in the
thread’s queue. When thread's queue is full or the number of accesses recorded in the
queue reaches a certain pre-determined threshold, we acquire a lock and then execute the
operations defined by the eviction algorithm - once for all the accesses in the queue. A
thread is allowed to access many cache items without requesting a lock to run the eviction
replacement algorithm, or without paying the lock acquisition cost. We can fully exploit a
non-blocking lock APIs like tryLock. As you recall tryLock makes an attempt to get the
lock and if the lock is currently held by another thread, it fails without blocking its
caller thread. Although tryLock is cheap it is not used for every cache access for obvious
reasons but rather on certain pre-determined thresholds. In case when thread's queue
is totally full lock must be explicitly requested. Intuitively speaking this makes a lot
of sense, we significantly lower the cost of lock contention, order/streamline access to
locked structures, retain the precision of eviction algorithm such as LIRS, and best of
all, if we are to believe to the authors claim, we can increase throughput by nearly
two-fold compared to the implementation of an unmodified eviction algorithm, such as LRU,
and at the same time achieve a scalability as good as the one that use lock free
structures.
So how do we translate these ideas in Infinispan?
In order to implement data container with batching lock amortization updates,
DataContainer is structured so that it contains two DataContainers in a chain. As far as
Infinispan code base is concerned DataContainer interface is still exposed as is but the
implementation of the first DataContainer in the chain contains a references to a delegate
– real DataContainer implementation. The first DataContainer in the chain is considered to
be a lock free buffer data container (BDC) while delegate container is thread safe and
interchangeable (LIRS, LRU) data container (DC). BDC has a ConcurrentHashMap whose cache
entry contents are managed as calls are unwound from DC.
As previously discussed BP-Wrapper [1] shared objects are used to batch updates to DC.
BP-Wrappers are envisioned as per thread objects having its own queue to record cache
entry accesses. As Brian mentioned this might be perfectly fine in other systems but it
will present a problem in Infinispan where we can potentially have hundreds of concurrent
threads accessing single data container. Many short lived threads would never fill up
their queue enough to hit a threshold. Manik, suggested that we share BP-Wrapper objects
in a pool among all InvocationContext(s).
XYZInterceptor {
Pool<BP-Wrapper> pool;
// grab BP-Wrapper off pool
// assign to InvocationContext
// try {pass up chain}
// finally {pull off InvocationContext, return to pool}
}
However, after thinking this through a bit more, a better solutions seems to be recording
all cache entry accesses in a lock-free queue within BDC itself. All threads making
invocations into DC share one lock-free queue to record cache entry accesses instead of
having one queue per BP-Wrapper object. In this case, we do not have to manage shared
BP-Wrapper objects, we do not need an extra interceptor and so on.
In order to batch updates to DC we need to “commit” all accessed cache entries into DC. As
of now we do not have such API. Either we introduce a subclass of DataContainer that has a
following new method or we can extend current DataContainer and make all implementations
of DC that do not handle batch updates perform a no-op:
public touch(List<InternalCacheEntry> updates)
Feedback appreciated.
Regards,
Vladimir
[1] http://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf
[2] http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf
7:09 p.m.
Valdimir,
I have used a similar approach to "batching" evictions with good success. It
reduced contention for the lock to handle eviction by about twenty percent.
For this cache, which was not realized using infinispan, I did NO eviction until the cache
reached a target percentage of the JVM heap (this kept the cache hot). For our case, this
was easy as the objects entered in the cache were database records coded as byte[]s so
have a good measure for their memory footprint. Once adding another record to the cache
would push the cache size over the target memory limit, that thread would gain a lock and
then evict a batch of records (in an LRU fashion) until the cache size had been driven
down by a threashold (e.g., 5% of the target memory was recovered).
Let me suggest an alternative approach. Neither LIRS nor LRU need to be strong orderings.
It is enough that a cache eviction policy be "approximately" LRU (or LIRS). As
long as the least desirable entries wind up getting evicted, it does not matter what the
precise eviction order is.
If you accept "approximate" eviction orders, then striped locks could be used to
reduce thread contention. Evictions could be driven on each segment of the cache
independently. If we hash the cache entry key to choose the segment, then each cache
entry will only appear in one segment and all segments should be driven more or less
equally by the application workload (assuming a decent hash function). So using 16
segments / locks, you have 1/16th the contention.
Thoughts?
Bryan
________________________________
From: infinispan-dev-bounces(a)lists.jboss.org
[mailto:infinispan-dev-bounces@lists.jboss.org] On Behalf Of Vladimir Blagojevic
Sent: Thursday, January 07, 2010 6:55 AM
To: infinispan -Dev List
Subject: [infinispan-dev] Implementing LIRS eviction policy [ISPN-299]
Hey everyone,
Some people are already familiar with this thread. They can jump towards the end of email
to read a concrete proposal on how to implement LIRS in Infinispan. Others, those of you
interested obscure eviction algorithms, keep reading :)
Some time ago Manik asked me to look into implementation of a new, LIRS algorithm for
cache eviction. It is a well known fact that plain vanilla LRU algorithm, although simple
and easy to understand, under performs in cases of weak access locality (one time access
pages are not replaced timely, pages to be accessed soonest are unfortunately replaced,
and so on). There has been a new algorithm out there that is rather popular called LIRS
that addresses these shortcomings of LRU yet it retains LRU's simplicity.
That is where the easy part ends. Eviction algorithm, if not implemented in scalable and
lock free fashion can seriously degrade performance. Having a lock protected data
container (to use Infinispan lingo) causes high contention offsetting eviction precision
that we get by using algorithm such as LIRS. That set me off on to a search for
LinkedHashMap (most suitable for LIRS and LRU) like structure that is lock free. Ben
Manes, recently employed by Google, has been working on this problem for a while. His
first attempt to implement ConcurrentLinkedHashMap had a flaw that was discovered by
EhCache people and confirmed by Manik in his own test. Ben Manes' second design for
ConcurrentLinkedHashMap uses ideas from a well known seminal paper in the area of lock
free algorithms [1] and the new design looks valid, at least to me. His implementation of
ConcurrentLinkedHashMap is not finished yet.
However, even if we had ConcurrentLinkedHashMap today that puts us only half way from our
lock free LIRS implementation. LIRS does not use only one stack/list such as LRU but two.
LIRS, in some cases, performs a lot of node shifting within that list and transfers nodes
from one list to another. Manik and I talked about how we could potentially change
original LIRS and stick the whole thing into one stack (ConcurrentLinkedHashMap) by using
additional node markings and such. Overall, I think this is possible but full of potential
pitfalls.
Just before holidays while bashing Google scholar day after day I came across a research
paper [2] that I would say has a lot of potential, not only for our LIRS eviction data
container implementation but any other eviction algorithm implementation.
Instead of making a trade-off between the high hit ratio of an eviction algorithm and the
low lock contention there is a third way, and dare I say a excellent idea of lock
amortization. We can wrap any eviction algorithm with a framework that keeps track of
cache access per thread (ThreadLocal) in a simple data container, say a queue. For each
cache hit associated with a thread, the access history information is recorded in the
thread's queue. When thread's queue is full or the number of accesses recorded in
the queue reaches a certain pre-determined threshold, we acquire a lock and then execute
the operations defined by the eviction algorithm - once for all the accesses in the queue.
A thread is allowed to access many cache items without requesting a lock to run the
eviction replacement algorithm, or without paying the lock acquisition cost. We can fully
exploit a non-blocking lock APIs like tryLock. As you recall tryLock makes an attempt to
get the lock and if the lock is currently held by another thread, it fails without
blocking its caller thread. Although tryLock is cheap it is not used for every cache
access for obvious reasons but rather on certain pre-determined thresholds. In case when
thread's queue is totally full lock must be explicitly requested. Intuitively speaking
this makes a lot of sense, we significantly lower the cost of lock contention,
order/streamline access to locked structures, retain the precision of eviction algorithm
such as LIRS, and best of all, if we are to believe to the authors claim, we can increase
throughput by nearly two-fold compared to the implementation of an unmodified eviction
algorithm, such as LRU, and at the same time achieve a scalability as good as the one that
use lock free structures.
So how do we translate these ideas in Infinispan?
In order to implement data container with batching lock amortization updates,
DataContainer is structured so that it contains two DataContainers in a chain. As far as
Infinispan code base is concerned DataContainer interface is still exposed as is but the
implementation of the first DataContainer in the chain contains a references to a delegate
- real DataContainer implementation. The first DataContainer in the chain is considered to
be a lock free buffer data container (BDC) while delegate container is thread safe and
interchangeable (LIRS, LRU) data container (DC). BDC has a ConcurrentHashMap whose cache
entry contents are managed as calls are unwound from DC.
As previously discussed BP-Wrapper [1] shared objects are used to batch updates to DC.
BP-Wrappers are envisioned as per thread objects having its own queue to record cache
entry accesses. As Brian mentioned this might be perfectly fine in other systems but it
will present a problem in Infinispan where we can potentially have hundreds of concurrent
threads accessing single data container. Many short lived threads would never fill up
their queue enough to hit a threshold. Manik, suggested that we share BP-Wrapper objects
in a pool among all InvocationContext(s).
XYZInterceptor {
Pool<BP-Wrapper> pool;
// grab BP-Wrapper off pool
// assign to InvocationContext
// try {pass up chain}
// finally {pull off InvocationContext, return to pool}
}
However, after thinking this through a bit more, a better solutions seems to be recording
all cache entry accesses in a lock-free queue within BDC itself. All threads making
invocations into DC share one lock-free queue to record cache entry accesses instead of
having one queue per BP-Wrapper object. In this case, we do not have to manage shared
BP-Wrapper objects, we do not need an extra interceptor and so on.
In order to batch updates to DC we need to "commit" all accessed cache entries
into DC. As of now we do not have such API. Either we introduce a subclass of
DataContainer that has a following new method or we can extend current DataContainer and
make all implementations of DC that do not handle batch updates perform a no-op:
public touch(List<InternalCacheEntry> updates)
Feedback appreciated.
Regards,
Vladimir
[1] http://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf
[2] http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf
3:41 a.m.
Hey Bryan,
On 2010-01-08, at 2:09 AM, Bryan Thompson wrote:
Valdimir,
I have used a similar approach to "batching" evictions with good success. It
reduced contention for the lock to handle eviction by about twenty percent.
How different, if at all, was your batching implementation from the one I referred to in
my previous mail?
For this cache, which was not realized using infinispan, I did NO eviction until the
cache reached a target percentage of the JVM heap (this kept the cache hot). For our
case, this was easy as the objects entered in the cache were database records coded as
byte[]s so have a good measure for their memory footprint. Once adding another record to
the cache would push the cache size over the target memory limit, that thread would gain a
lock and then evict a batch of records (in an LRU fashion) until the cache size had been
driven down by a threashold (e.g., 5% of the target memory was recovered).
Let me suggest an alternative approach. Neither LIRS nor LRU need to be strong
orderings. It is enough that a cache eviction policy be "approximately" LRU (or
LIRS). As long as the least desirable entries wind up getting evicted, it does not matter
what the precise eviction order is.
Can you clarify "need to be strong orderings"? Aha, you are referring to
eviction order?
If you accept "approximate" eviction orders, then striped locks could be used
to reduce thread contention. Evictions could be driven on each segment of the cache
independently. If we hash the cache entry key to choose the segment, then each cache
entry will only appear in one segment and all segments should be driven more or less
equally by the application workload (assuming a decent hash function). So using 16
segments / locks, you have 1/16th the contention.
Thoughts?
So what you are basically saying is that we implement LIRS and LRU per Segment of
ConcurrentHashMap, is that right? Interesting idea!
Does your proposal still contain batching? If so, how would you fit it in this new design?
You would have to keep batched record of cache entry accesses in a queue per segment?
Regards,
Vladimir
6:35 a.m.
Vladimir,
Reading the paper, it appears that my suggestion of segments is called "distributed
locks" in this paper and the authors suggests:
For example, the algorithms that need to detect sequence of accesses
cannot retain their performance advantages when pages in the same sequence have been
distributed into multiple partitions and cannot be identified as a sequence.
Overall, I like the approach outlined in the paper. It takes the concept of batching
further than what we did, but in much the same spirit. In our implementation, we only
batched evictions. They are also batching the updates to the replacement policy ordering
which is still a bottleneck for us.
Concerning the FIFO queue, the paper (page 372) considers both per-thread queues or global
queues. They dismiss global queues for batching updates primarily because certain cache
replacement policies need to detect sequences of operations. Can such sequences of
operations be meaningfully detected within infinispan? Is there any thread-affinity for a
transaction? If not, then segmented queues might be an alternative for infinispan.
Also, for java, if the hash map uses weak values then cache entries then any entries on
the FIFO queues will remain pinned in the hash map even if they would have otherwise been
evicted by the cache policy which is a nice touch. That way you can continue to access an
object which remains accessible to the JVM held even if the cache replacement policy would
have discarded the cache entry.
The experiment in the paper compared several cache replacement policies, but the data were
all hot in cache and the cache was large enough to avoid all cache misses, so I am not
clear why they bothered to compare different cache replacement policies -- none of them
did any evictions for their tests. While "prefetching" did reduce the lock
contention slightly, it had no meaningful effect on either throughput or response time.
The authors posit that it might have more effect on machines with many more cores,
depending on the CPU architecture. It seems easily enough to ignore the prefetch
dimension for now and just concentrate on batching.
So, I think that the batching approach per this paper makes sense and could be combined
with LRU or LIRS easily since the cache replacement policy is encapsulated (which might
not be true with prefetch) and seems overall like a good idea and an improvement on what
we were already doing. For our application, I think that we would use a hash map with
weak values (per above) to gain the benefit of the actual retention time of the object by
the JVM. I would also like to explore the use of segmented queues as well as per-thread
queues to control the #of queues in the system separately from the #of threads. By
batching updates to the access order, you are also effectively batching evictions since
they are driven by updates. When combined with a weak value caches, the thread running
the updates should also clear entries from the cache on the weak reference queue, thereby
batching the clearing of stale cache entries (those with cleared references) at the same
time it is batching updates to the access order and inserts to the cache.
Bryan
________________________________
From: infinispan-dev-bounces(a)lists.jboss.org
[mailto:infinispan-dev-bounces@lists.jboss.org] On Behalf Of Vladimir Blagojevic
Sent: Friday, January 08, 2010 4:42 AM
To: infinispan -Dev List
Subject: Re: [infinispan-dev] Implementing LIRS eviction policy [ISPN-299]
Hey Bryan,
On 2010-01-08, at 2:09 AM, Bryan Thompson wrote:
Valdimir,
I have used a similar approach to "batching" evictions with good success. It
reduced contention for the lock to handle eviction by about twenty percent.
How different, if at all, was your batching implementation from the one I referred to in
my previous mail?
For this cache, which was not realized using infinispan, I did NO eviction until the cache
reached a target percentage of the JVM heap (this kept the cache hot). For our case, this
was easy as the objects entered in the cache were database records coded as byte[]s so
have a good measure for their memory footprint. Once adding another record to the cache
would push the cache size over the target memory limit, that thread would gain a lock and
then evict a batch of records (in an LRU fashion) until the cache size had been driven
down by a threashold (e.g., 5% of the target memory was recovered).
Let me suggest an alternative approach. Neither LIRS nor LRU need to be strong orderings.
It is enough that a cache eviction policy be "approximately" LRU (or LIRS). As
long as the least desirable entries wind up getting evicted, it does not matter what the
precise eviction order is.
Can you clarify "need to be strong orderings"? Aha, you are referring to
eviction order?
If you accept "approximate" eviction orders, then striped locks could be used to
reduce thread contention. Evictions could be driven on each segment of the cache
independently. If we hash the cache entry key to choose the segment, then each cache
entry will only appear in one segment and all segments should be driven more or less
equally by the application workload (assuming a decent hash function). So using 16
segments / locks, you have 1/16th the contention.
Thoughts?
So what you are basically saying is that we implement LIRS and LRU per Segment of
ConcurrentHashMap, is that right? Interesting idea!
Does your proposal still contain batching? If so, how would you fit it in this new design?
You would have to keep batched record of cache entry accesses in a queue per segment?
Regards,
Vladimir
9:07 a.m.
Hey Bryan,
On 2010-01-08, at 1:35 PM, Bryan Thompson wrote:
Vladimir,
Reading the paper, it appears that my suggestion of segments is called "distributed
locks" in this paper and the authors suggests:
> For example, the algorithms that need to detect sequence of accesses cannot retain
their performance advantages when pages in the same sequence have been distributed into
multiple partitions and cannot be identified as a sequence.
Indeed, but this sequence access seems to be important for subgroup of algorithms like
SEQ. To be honest, when I first read the paper I was surprised by the authors claim that
batching does not affect precision of LIRS and LRU. LIRS and LRU need order of access too
by it seems that approximated access is not affecting precision significantly.
Along the same lines we have to figure out if segmenting and batching per segment is going
to affect algorithm precision overall. If someone can prove that this is dead end please
argue your point :) Otherwise, intuitively speaking, I cannot see how batching per segment
would suddenly make LIRS imprecise if batching did not do so in the first place.
Overall, I like the approach outlined in the paper. It takes the concept of batching
further than what we did, but in much the same spirit. In our implementation, we only
batched evictions. They are also batching the updates to the replacement policy ordering
which is still a bottleneck for us.
Concerning the FIFO queue, the paper (page 372) considers both per-thread queues or
global queues. They dismiss global queues for batching updates primarily because certain
cache replacement policies need to detect sequences of operations. Can such sequences of
operations be meaningfully detected within infinispan? Is there any thread-affinity for a
transaction? If not, then segmented queues might be an alternative for infinispan.
Yes, they dismiss global queue over algorithms we do not plan to use and locking cost of a
global queue. I am betting that global lock free queue per Infinispan DataContainer is
less costly than shared BP-Wrapper objects that we have to maintain in a pool and share
among threads (they are not shared in the paper but we have to). As I mentioned the
problem for us is that we can potentially have spikes of up to hundreds of threads in a
cache instance. Infinispan use case differs from PostgreSQL used in the paper but I agree
that potential impact of global lock free queue should not be dismissed and I would switch
to pooling approach if it is proven that lock free queue causes bottleneck.
Also, for java, if the hash map uses weak values then cache entries then any entries on
the FIFO queues will remain pinned in the hash map even if they would have otherwise been
evicted by the cache policy which is a nice touch. That way you can continue to access an
object which remains accessible to the JVM held even if the cache replacement policy would
have discarded the cache entry.
The experiment in the paper compared several cache replacement policies, but the data
were all hot in cache and the cache was large enough to avoid all cache misses, so I am
not clear why they bothered to compare different cache replacement policies -- none of
them did any evictions for their tests. While "prefetching" did reduce the lock
contention slightly, it had no meaningful effect on either throughput or response time.
The authors posit that it might have more effect on machines with many more cores,
depending on the CPU architecture. It seems easily enough to ignore the prefetch
dimension for now and just concentrate on batching.
Exactly the same sentiment here :)
So, I think that the batching approach per this paper makes sense and could be combined
with LRU or LIRS easily since the cache replacement policy is encapsulated (which might
not be true with prefetch) and seems overall like a good idea and an improvement on what
we were already doing. For our application, I think that we would use a hash map with
weak values (per above) to gain the benefit of the actual retention time of the object by
the JVM. I would also like to explore the use of segmented queues as well as per-thread
queues to control the #of queues in the system separately from the #of threads. By
batching updates to the access order, you are also effectively batching evictions since
they are driven by updates. When combined with a weak value caches, the thread running
the updates should also clear entries from the cache on the weak reference queue, thereby
batching the clearing of stale cache entries (those with cleared references) at the same
time it is batching updates to the access order and inserts to the cache.
Bryan
Excellent, lets keep cooperating on this one. If you are already in implementation stage,
and it seems that you are, let us know of the progress you make and performance increases
you observe.
Regards,
Vladimir
10:27 a.m.
Vladimir,
Sure. I will keep you updated. We have several of our own implementations and we have
been evaluating an implementation based on the LRUDataContainer, which has a wicked hot
spot as I am sure you know. This batching approach sounds quite promising. We will try
it on our existing implementations and we can evaluate (or help on) the infinispan
version.
Bryan
________________________________
From: infinispan-dev-bounces(a)lists.jboss.org
[mailto:infinispan-dev-bounces@lists.jboss.org] On Behalf Of Vladimir Blagojevic
Sent: Friday, January 08, 2010 10:08 AM
To: infinispan -Dev List
Cc: Martyn Cutcher
Subject: Re: [infinispan-dev] Implementing LIRS eviction policy [ISPN-299]
Hey Bryan,
On 2010-01-08, at 1:35 PM, Bryan Thompson wrote:
Vladimir,
Reading the paper, it appears that my suggestion of segments is called "distributed
locks" in this paper and the authors suggests:
For example, the algorithms that need to detect sequence of accesses
cannot retain their performance advantages when pages in the same sequence have been
distributed into multiple partitions and cannot be identified as a sequence.
Indeed, but this sequence access seems to be important for subgroup of algorithms like
SEQ. To be honest, when I first read the paper I was surprised by the authors claim that
batching does not affect precision of LIRS and LRU. LIRS and LRU need order of access too
by it seems that approximated access is not affecting precision significantly.
Along the same lines we have to figure out if segmenting and batching per segment is going
to affect algorithm precision overall. If someone can prove that this is dead end please
argue your point :) Otherwise, intuitively speaking, I cannot see how batching per segment
would suddenly make LIRS imprecise if batching did not do so in the first place.
Overall, I like the approach outlined in the paper. It takes the concept of batching
further than what we did, but in much the same spirit. In our implementation, we only
batched evictions. They are also batching the updates to the replacement policy ordering
which is still a bottleneck for us.
Concerning the FIFO queue, the paper (page 372) considers both per-thread queues or global
queues. They dismiss global queues for batching updates primarily because certain cache
replacement policies need to detect sequences of operations. Can such sequences of
operations be meaningfully detected within infinispan? Is there any thread-affinity for a
transaction? If not, then segmented queues might be an alternative for infinispan.
Yes, they dismiss global queue over algorithms we do not plan to use and locking cost of a
global queue. I am betting that global lock free queue per Infinispan DataContainer is
less costly than shared BP-Wrapper objects that we have to maintain in a pool and share
among threads (they are not shared in the paper but we have to). As I mentioned the
problem for us is that we can potentially have spikes of up to hundreds of threads in a
cache instance. Infinispan use case differs from PostgreSQL used in the paper but I agree
that potential impact of global lock free queue should not be dismissed and I would switch
to pooling approach if it is proven that lock free queue causes bottleneck.
Also, for java, if the hash map uses weak values then cache entries then any entries on
the FIFO queues will remain pinned in the hash map even if they would have otherwise been
evicted by the cache policy which is a nice touch. That way you can continue to access an
object which remains accessible to the JVM held even if the cache replacement policy would
have discarded the cache entry.
The experiment in the paper compared several cache replacement policies, but the data were
all hot in cache and the cache was large enough to avoid all cache misses, so I am not
clear why they bothered to compare different cache replacement policies -- none of them
did any evictions for their tests. While "prefetching" did reduce the lock
contention slightly, it had no meaningful effect on either throughput or response time.
The authors posit that it might have more effect on machines with many more cores,
depending on the CPU architecture. It seems easily enough to ignore the prefetch
dimension for now and just concentrate on batching.
Exactly the same sentiment here :)
So, I think that the batching approach per this paper makes sense and could be combined
with LRU or LIRS easily since the cache replacement policy is encapsulated (which might
not be true with prefetch) and seems overall like a good idea and an improvement on what
we were already doing. For our application, I think that we would use a hash map with
weak values (per above) to gain the benefit of the actual retention time of the object by
the JVM. I would also like to explore the use of segmented queues as well as per-thread
queues to control the #of queues in the system separately from the #of threads. By
batching updates to the access order, you are also effectively batching evictions since
they are driven by updates. When combined with a weak value caches, the thread running
the updates should also clear entries from the cache on the weak reference queue, thereby
batching the clearing of stale cache entries (those with cleared references) at the same
time it is batching updates to the access order and inserts to the cache.
Bryan
Excellent, lets keep cooperating on this one. If you are already in implementation stage,
and it seems that you are, let us know of the progress you make and performance increases
you observe.
Regards,
Vladimir
7:41 a.m.
On 8 Jan 2010, at 15:07, Vladimir Blagojevic wrote:
Hey Bryan,
On 2010-01-08, at 1:35 PM, Bryan Thompson wrote:
> Vladimir,
>
> Reading the paper, it appears that my suggestion of segments is called
"distributed locks" in this paper and the authors suggests:
>
> > For example, the algorithms that need to detect sequence of accesses cannot
retain their performance advantages when pages in the same sequence have been distributed
into multiple partitions and cannot be identified as a sequence.
Indeed, but this sequence access seems to be important for subgroup of algorithms like
SEQ. To be honest, when I first read the paper I was surprised by the authors claim that
batching does not affect precision of LIRS and LRU. LIRS and LRU need order of access too
by it seems that approximated access is not affecting precision significantly.
Along the same lines we have to figure out if segmenting and batching per segment is
going to affect algorithm precision overall. If someone can prove that this is dead end
please argue your point :) Otherwise, intuitively speaking, I cannot see how batching per
segment would suddenly make LIRS imprecise if batching did not do so in the first place.
In general, lack of precision should not be a concern. In a tradeoff between precision
and performance/throughput, precision ought to lose.
Cheers
Manik
--
Manik Surtani
manik(a)jboss.org
Lead, Infinispan
Lead, JBoss Cache
http://www.infinispan.org
http://www.jbosscache.org
7:38 a.m.
On 8 Jan 2010, at 12:35, Bryan Thompson wrote:
Vladimir,
Reading the paper, it appears that my suggestion of segments is called "distributed
locks" in this paper and the authors suggests:
> For example, the algorithms that need to detect sequence of accesses cannot retain
their performance advantages when pages in the same sequence have been distributed into
multiple partitions and cannot be identified as a sequence.
Overall, I like the approach outlined in the paper. It takes the concept of batching
further than what we did, but in much the same spirit. In our implementation, we only
batched evictions. They are also batching the updates to the replacement policy ordering
which is still a bottleneck for us.
Concerning the FIFO queue, the paper (page 372) considers both per-thread queues or
global queues. They dismiss global queues for batching updates primarily because certain
cache replacement policies need to detect sequences of operations. Can such sequences of
operations be meaningfully detected within infinispan? Is there any thread-affinity for a
transaction?
No there isn't - although there could be, as a side effect of certain use cases and
access patterns, but this should not be expected.
If not, then segmented queues might be an alternative for
infinispan.
Also, for java, if the hash map uses weak values then cache entries then any entries on
the FIFO queues will remain pinned in the hash map even if they would have otherwise been
evicted by the cache policy which is a nice touch. That way you can continue to access an
object which remains accessible to the JVM held even if the cache replacement policy would
have discarded the cache entry.
The experiment in the paper compared several cache replacement policies, but the data
were all hot in cache and the cache was large enough to avoid all cache misses, so I am
not clear why they bothered to compare different cache replacement policies -- none of
them did any evictions for their tests. While "prefetching" did reduce the lock
contention slightly, it had no meaningful effect on either throughput or response time.
The authors posit that it might have more effect on machines with many more cores,
depending on the CPU architecture. It seems easily enough to ignore the prefetch
dimension for now and just concentrate on batching.
+1
So, I think that the batching approach per this paper makes sense and could be combined
with LRU or LIRS easily since the cache replacement policy is encapsulated (which might
not be true with prefetch) and seems overall like a good idea and an improvement on what
we were already doing. For our application, I think that we would use a hash map with
weak values (per above) to gain the benefit of the actual retention time of the object by
the JVM. I would also like to explore the use of segmented queues as well as per-thread
queues to control the #of queues in the system separately from the #of threads. By
batching updates to the access order, you are also effectively batching evictions since
they are driven by updates. When combined with a weak value caches, the thread running
the updates should also clear entries from the cache on the weak reference queue, thereby
batching the clearing of stale cache entries (those with cleared references) at the same
time it is batching updates to the access order and inserts to the cache.
Bryan
From: infinispan-dev-bounces(a)lists.jboss.org
[mailto:infinispan-dev-bounces@lists.jboss.org] On Behalf Of Vladimir Blagojevic
Sent: Friday, January 08, 2010 4:42 AM
To: infinispan -Dev List
Subject: Re: [infinispan-dev] Implementing LIRS eviction policy [ISPN-299]
Hey Bryan,
On 2010-01-08, at 2:09 AM, Bryan Thompson wrote:
> Valdimir,
>
> I have used a similar approach to "batching" evictions with good success.
It reduced contention for the lock to handle eviction by about twenty percent.
How different, if at all, was your batching implementation from the one I referred to in
my previous mail?
>
> For this cache, which was not realized using infinispan, I did NO eviction until the
cache reached a target percentage of the JVM heap (this kept the cache hot). For our
case, this was easy as the objects entered in the cache were database records coded as
byte[]s so have a good measure for their memory footprint. Once adding another record to
the cache would push the cache size over the target memory limit, that thread would gain a
lock and then evict a batch of records (in an LRU fashion) until the cache size had been
driven down by a threashold (e.g., 5% of the target memory was recovered).
>
> Let me suggest an alternative approach. Neither LIRS nor LRU need to be strong
orderings. It is enough that a cache eviction policy be "approximately" LRU (or
LIRS). As long as the least desirable entries wind up getting evicted, it does not matter
what the precise eviction order is.
Can you clarify "need to be strong orderings"? Aha, you are referring to
eviction order?
>
> If you accept "approximate" eviction orders, then striped locks could be
used to reduce thread contention. Evictions could be driven on each segment of the
cache independently. If we hash the cache entry key to choose the segment, then each
cache entry will only appear in one segment and all segments should be driven more or less
equally by the application workload (assuming a decent hash function). So using 16
segments / locks, you have 1/16th the contention.
>
> Thoughts?
So what you are basically saying is that we implement LIRS and LRU per Segment of
ConcurrentHashMap, is that right? Interesting idea!
Does your proposal still contain batching? If so, how would you fit it in this new
design? You would have to keep batched record of cache entry accesses in a queue per
segment?
Regards,
Vladimir
_______________________________________________
infinispan-dev mailing list
infinispan-dev(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/infinispan-dev
--
Manik Surtani
manik(a)jboss.org
Lead, Infinispan
Lead, JBoss Cache
http://www.infinispan.org
http://www.jbosscache.org
7:32 a.m.
On 8 Jan 2010, at 01:09, Bryan Thompson wrote:
Valdimir,
I have used a similar approach to "batching" evictions with good success. It
reduced contention for the lock to handle eviction by about twenty percent.
For this cache, which was not realized using infinispan, I did NO eviction until the
cache reached a target percentage of the JVM heap (this kept the cache hot).
Infinispan does this as well, except that this is based off number of cached entries as
opposed to size (since calculating POJO size every time is expensive). A periodic thread
tests the cache size and based on a threshold, would decide whether to prune off entries
or not.
For our case, this was easy as the objects entered in the cache
were database records coded as byte[]s so have a good measure for their memory footprint.
Once adding another record to the cache would push the cache size over the target memory
limit, that thread would gain a lock and then evict a batch of records (in an LRU fashion)
until the cache size had been driven down by a threashold (e.g., 5% of the target memory
was recovered).
Let me suggest an alternative approach. Neither LIRS nor LRU need to be strong
orderings. It is enough that a cache eviction policy be "approximately" LRU (or
LIRS). As long as the least desirable entries wind up getting evicted, it does not matter
what the precise eviction order is.
With lock amortization, the eviction algorithm would already be an
"approximation", since when an eviction thread kicks in (due to thresholds being
crossed), there is no guarantee that every thread's buffered recency information is
written to the data container yet.
Cheers
Manik
If you accept "approximate" eviction orders, then striped
locks could be used to reduce thread contention. Evictions could be driven on each
segment of the cache independently. If we hash the cache entry key to choose the segment,
then each cache entry will only appear in one segment and all segments should be driven
more or less equally by the application workload (assuming a decent hash function). So
using 16 segments / locks, you have 1/16th the contention.
Thoughts?
Bryan
From: infinispan-dev-bounces(a)lists.jboss.org
[mailto:infinispan-dev-bounces@lists.jboss.org] On Behalf Of Vladimir Blagojevic
Sent: Thursday, January 07, 2010 6:55 AM
To: infinispan -Dev List
Subject: [infinispan-dev] Implementing LIRS eviction policy [ISPN-299]
Hey everyone,
Some people are already familiar with this thread. They can jump towards the end of email
to read a concrete proposal on how to implement LIRS in Infinispan. Others, those of you
interested obscure eviction algorithms, keep reading :)
Some time ago Manik asked me to look into implementation of a new, LIRS algorithm for
cache eviction. It is a well known fact that plain vanilla LRU algorithm, although simple
and easy to understand, under performs in cases of weak access locality (one time access
pages are not replaced timely, pages to be accessed soonest are unfortunately replaced,
and so on). There has been a new algorithm out there that is rather popular called LIRS
that addresses these shortcomings of LRU yet it retains LRU's simplicity.
That is where the easy part ends. Eviction algorithm, if not implemented in scalable and
lock free fashion can seriously degrade performance. Having a lock protected data
container (to use Infinispan lingo) causes high contention offsetting eviction precision
that we get by using algorithm such as LIRS. That set me off on to a search for
LinkedHashMap (most suitable for LIRS and LRU) like structure that is lock free. Ben
Manes, recently employed by Google, has been working on this problem for a while. His
first attempt to implement ConcurrentLinkedHashMap had a flaw that was discovered by
EhCache people and confirmed by Manik in his own test. Ben Manes' second design for
ConcurrentLinkedHashMap uses ideas from a well known seminal paper in the area of lock
free algorithms [1] and the new design looks valid, at least to me. His implementation of
ConcurrentLinkedHashMap is not finished yet.
However, even if we had ConcurrentLinkedHashMap today that puts us only half way from our
lock free LIRS implementation. LIRS does not use only one stack/list such as LRU but two.
LIRS, in some cases, performs a lot of node shifting within that list and transfers nodes
from one list to another. Manik and I talked about how we could potentially change
original LIRS and stick the whole thing into one stack (ConcurrentLinkedHashMap) by using
additional node markings and such. Overall, I think this is possible but full of potential
pitfalls.
Just before holidays while bashing Google scholar day after day I came across a research
paper [2] that I would say has a lot of potential, not only for our LIRS eviction data
container implementation but any other eviction algorithm implementation.
Instead of making a trade-off between the high hit ratio of an eviction algorithm and the
low lock contention there is a third way, and dare I say a excellent idea of lock
amortization. We can wrap any eviction algorithm with a framework that keeps track of
cache access per thread (ThreadLocal) in a simple data container, say a queue. For each
cache hit associated with a thread, the access history information is recorded in the
thread’s queue. When thread's queue is full or the number of accesses recorded in the
queue reaches a certain pre-determined threshold, we acquire a lock and then execute the
operations defined by the eviction algorithm - once for all the accesses in the queue. A
thread is allowed to access many cache items without requesting a lock to run the eviction
replacement algorithm, or without paying the lock acquisition cost. We can fully exploit a
non-blocking lock APIs like tryLock. As you recall tryLock makes an attempt to get the
lock and if the lock is currently held by another thread, it fails without blocking its
caller thread. Although tryLock is cheap it is not used for every cache access for obvious
reasons but rather on certain pre-determined thresholds. In case when thread's queue
is totally full lock must be explicitly requested. Intuitively speaking this makes a lot
of sense, we significantly lower the cost of lock contention, order/streamline access to
locked structures, retain the precision of eviction algorithm such as LIRS, and best of
all, if we are to believe to the authors claim, we can increase throughput by nearly
two-fold compared to the implementation of an unmodified eviction algorithm, such as LRU,
and at the same time achieve a scalability as good as the one that use lock free
structures.
So how do we translate these ideas in Infinispan?
In order to implement data container with batching lock amortization updates,
DataContainer is structured so that it contains two DataContainers in a chain. As far as
Infinispan code base is concerned DataContainer interface is still exposed as is but the
implementation of the first DataContainer in the chain contains a references to a delegate
– real DataContainer implementation. The first DataContainer in the chain is considered to
be a lock free buffer data container (BDC) while delegate container is thread safe and
interchangeable (LIRS, LRU) data container (DC). BDC has a ConcurrentHashMap whose cache
entry contents are managed as calls are unwound from DC.
As previously discussed BP-Wrapper [1] shared objects are used to batch updates to DC.
BP-Wrappers are envisioned as per thread objects having its own queue to record cache
entry accesses. As Brian mentioned this might be perfectly fine in other systems but it
will present a problem in Infinispan where we can potentially have hundreds of concurrent
threads accessing single data container. Many short lived threads would never fill up
their queue enough to hit a threshold. Manik, suggested that we share BP-Wrapper objects
in a pool among all InvocationContext(s).
XYZInterceptor {
Pool<BP-Wrapper> pool;
// grab BP-Wrapper off pool
// assign to InvocationContext
// try {pass up chain}
// finally {pull off InvocationContext, return to pool}
}
However, after thinking this through a bit more, a better solutions seems to be recording
all cache entry accesses in a lock-free queue within BDC itself. All threads making
invocations into DC share one lock-free queue to record cache entry accesses instead of
having one queue per BP-Wrapper object. In this case, we do not have to manage shared
BP-Wrapper objects, we do not need an extra interceptor and so on.
In order to batch updates to DC we need to “commit” all accessed cache entries into DC.
As of now we do not have such API. Either we introduce a subclass of DataContainer that
has a following new method or we can extend current DataContainer and make all
implementations of DC that do not handle batch updates perform a no-op:
public touch(List<InternalCacheEntry> updates)
Feedback appreciated.
Regards,
Vladimir
[1] http://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf
[2] http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf
_______________________________________________
infinispan-dev mailing list
infinispan-dev(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/infinispan-dev
--
Manik Surtani
manik(a)jboss.org
Lead, Infinispan
Lead, JBoss Cache
http://www.infinispan.org
http://www.jbosscache.org
5481
days inactive
5485
days old
infinispan-dev@lists.jboss.org
8 comments
3 participants
participants (3)
-
Bryan Thompson -
Manik Surtani -
Vladimir Blagojevic