<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 8 Jan 2010, at 01:09, Bryan Thompson wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<div style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4">Valdimir,</font></span></div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4"></font></span> </div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4">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.</font></span></div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4"></font></span> </div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4">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).</font></span></div></div></blockquote><div><br></div><div>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.</div><br><blockquote type="cite"><div style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space"><div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4"> 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).</font></span></div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4"></font></span> </div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4">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.</font></span></div></div></blockquote><div><br></div><div>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.</div><div><br></div><div>Cheers</div><div>Manik</div><br><blockquote type="cite"><div style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<div dir="ltr" align="left"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Courier New'; font-size: large; ">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.</span></div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4"></font></span> </div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4">Thoughts?</font></span></div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4"></font></span> </div>
<div dir="ltr" align="left"><span class="427114300-08012010"><font face="Courier New" color="#0000ff" size="4">Bryan</font></span></div><font face="Courier New" color="#0000ff" size="4"></font><br>
<blockquote dir="ltr" style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<div class="OutlookMessageHeader" lang="en-us" dir="ltr" align="left">
<hr tabindex="-1">
<font face="Tahoma" size="2"><b>From:</b> <a href="mailto:infinispan-dev-bounces@lists.jboss.org">infinispan-dev-bounces@lists.jboss.org</a>
[mailto:infinispan-dev-bounces@lists.jboss.org] <b>On Behalf Of </b>Vladimir
Blagojevic<br><b>Sent:</b> Thursday, January 07, 2010 6:55 AM<br><b>To:</b>
infinispan -Dev List<br><b>Subject:</b> [infinispan-dev] Implementing LIRS
eviction policy [ISPN-299]<br></font><br></div>
<div></div>Hey everyone,
<div><br></div>
<div>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 :)<br><br>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.<br><br>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. </div>
<div><br>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.</div>
<div><br>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.<br><br>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.</div>
<div><br></div>
<div>So how do we translate these ideas in Infinispan?</div>
<div><p style="MARGIN-BOTTOM: 0cm" align="left"><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">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.</span></font></font></font></font></p><p style="MARGIN-BOTTOM: 0cm"><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">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). </span></font></font></font></font></p>
<div><br></div>
<div>XYZInterceptor {<br> Pool<BP-Wrapper>
pool;<br><br> // grab BP-Wrapper off pool<br> // assign to
InvocationContext<br> // try {pass up chain}<br> // finally {pull
off InvocationContext, return to pool}<br>}</div><p style="MARGIN-BOTTOM: 0cm"><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">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.</span></font></font></font></font></p><p style="MARGIN-BOTTOM: 0cm"><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">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:</span></font></font></font></font></p><p style="MARGIN-BOTTOM: 0cm"><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">public
touch(List<</span></font></font></font></font><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">InternalCacheEntry</span></font></font></font></font><font color="#000000"><font size="+0"><font size="+0"><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="FONT-SIZE: 13px">>
updates)</span></font></font></font></font></p></div>
<div><br></div>
<div><br></div>
<div>Feedback appreciated. </div>
<div><br></div>
<div>Regards,</div>
<div>Vladimir</div>
<div><br>[1] <a href="http://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf">http://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf</a><br>[2] <a href="http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf">http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf</a></div></blockquote></div>
_______________________________________________<br>infinispan-dev mailing list<br><a href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>https://lists.jboss.org/mailman/listinfo/infinispan-dev</blockquote></div><br><div>
<span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>--</div><div>Manik Surtani</div><div><a href="mailto:manik@jboss.org">manik@jboss.org</a></div><div>Lead, Infinispan</div><div>Lead, JBoss Cache</div><div><a href="http://www.infinispan.org">http://www.infinispan.org</a></div><div><a href="http://www.jbosscache.org">http://www.jbosscache.org</a></div><div><br></div></div></span><br class="Apple-interchange-newline"></span><br class="Apple-interchange-newline">
</div>
<br></body></html>