Hey Bryan, Does it happen with LIRS as well? Pick up the latest version from svn so we know which file to look at. I've never seen this kind of exception in compareAndSwap, anyone? Vladimir On 2010-02-06, at 7:53 PM, Bryan Thompson wrote:

Vladimir, Here is an expanded concept for the cache implementation. I am thinking that the right approach is a class which encapsulates: (a) an unmodified ConcurrentHashMap (CHM); combined with (b) non-thread-safe thread-local buffers (TLB) for touches, managed by an inner CHM<ThreadId,TLB> instance. The reason for this inner map is to allow the TLB instances to be discarded by clear(); The TLBs get batched onto; (c) a shared non-thread safe access policy (LIRS, LRU) built on double-linked nodes (DLN) stored in the inner CHM. Updates are deferred until holding the lock (d). The DLN reference to the cached value is final. The (prior, next, delete) fields are only read or written while holding the lock (d). Other fields could be defined by subclassing a newDLN() method to support LIRS, etc. The access policy will need [head, tail] or similar fields, which would also be guarded by the lock (d); (d) a single lock guarding mutation on the access policy. Since there is only one lock, there can be no lock ordering problems. Both batching touches onto (c) and eviction (per the access policy) require access to the lock, but that is the only lock. If the access policy batches evictions, then lock requests will be rare and the whole cache will be non-blocking, wait free, and not spinning on CAS locks 99% of the time; and (d) explicit management of the threads used to access the cache. e.g., by queuing accepted requests and servicing them out of a thread pool, which has the benefit of managing the workload imposed by the clients. This should have the best possible performance and the simplest implementation. (b) The TLB could be a DLN[] or other simple data structures. The access policy (c) is composed from linking DLN instances together while holding the lock. A get() on the outer class looks up the DLN on the inner CHM and places it into the TLB (if found). A put() or putIfAbsent() on the outer class creates a new DLN and either unconditionally or conditionally puts it into the inner CHM. The new DLN is added to the TLB IFF it was added to the inner CHM. The access order is NOT updated at this time. A remove() on the outer class acquires the lock (d), looks up the DLN in the cache, and synchronously unlinks the DLN if found and sets its [deleted] flag. I would recommend that the clients do not call remove() directly, or that an outer remove() method exists which only removes the DLN from the inner CHM and queues up remove requests to be processed the next time any thread batches its touches through the lock. The inner remove() method would synchronously update the DLNs. When batching touches through the lock, only the access order is updated by the appropriate updates of the DLN nodes. If the [deleted] flag is set, then the DLN has been removed from the cache and its access order is NOT updated. If the cache is over its defined maximums, then evictions are batched while holding the lock. Evictions are only processed when batching touches through the lcok. A clear() clear the ConcurrentHashMap<Key,DLN<Val>> map. It would also clear the inner ConcurrentHashMap<ThreadId,TLB> map, which would cause the existing TLB instances to be discarded. It would have to obtain the lock in order to clear the [head,tail] or related fields for the access policy. Bryan ________________________________________ From: Bryan Thompson Sent: Sunday, February 07, 2010 8:19 PM To: Vladimir Blagojevic Cc: infinispan -Dev List Subject: RE: [infinispan-dev] Initial LIRS implementation Vladimir, I am thinking that the right approach is a class which encapsulates: (a) an unmodified ConcurrentHashMap; combined with (b) per-thread non-thread-safe buffers for touches; which get batched onto (c) a shared non-thread safe access policy (LIRS, LRU); and (d) explicit management of the threads used to access the cache. e.g., by queuing accepted requests and servicing them out of a thread pool. This should have the best possible performance and the simplest implementation. (b) can be use an Object[]. (c) can be composed from simple arrays or other non-thread safe data structures. Both batching touches onto (c) and eviction (per the policy) require access to a lock for (c), but that is the only lock. If the policy batches evictions, then lock requests will be rare and the whole cache will be non-blocking, wait free, and not spinning on CAS locks 99% of the time. Bryan ________________________________________ From: Vladimir Blagojevic [vblagoje(a)redhat.com] Sent: Sunday, February 07, 2010 7:55 AM To: Bryan Thompson Cc: infinispan -Dev List Subject: Re: [infinispan-dev] Initial LIRS implementation Hey Bryan, Does it happen with LIRS as well? Pick up the latest version from svn so we know which file to look at. I've never seen this kind of exception in compareAndSwap, anyone? Vladimir On 2010-02-06, at 7:53 PM, Bryan Thompson wrote:

FYI, those results were with 4 concurrent clients issuing query mixes. Throughput is higher for all conditions of that matrix with 8 concurrent clients. Bryan ________________________________________ From: Bryan Thompson Sent: Monday, February 08, 2010 7:59 PM To: Bryan Thompson; Vladimir Blagojevic Cc: infinispan -Dev List; Martyn Cutcher Subject: RE: [infinispan-dev] Initial LIRS implementation Vladimir, Here are some throughput numbers for our application on a query benchmark (The Berlin Sparql Benchmark using the "reduced query mix") comparing the performance with our existing cache (known hotspot) and the BCHM cache from infinispan. The metric is Query Mixes per Hour. Base: Cold Cache=1851; Hot Cache=18,537 LIRS: Cold Cache=2317; Hot Cache=28,709 You can see that there is a significant effect for both the cold and hot cache conditions when compared to the baseline cache implementation, which is great. I have also validated correctness for the benchmark using the BHCM LIRS cache. I have not yet resolved the deadlock when using the BHCM LRU cache (I have not tried your most current update of that class). I have not put this under a profiler yet either. These are use some early results. Bryan ________________________________________ From: Bryan Thompson Sent: Monday, February 08, 2010 6:39 AM To: Bryan Thompson; Vladimir Blagojevic Cc: infinispan -Dev List Subject: RE: [infinispan-dev] Initial LIRS implementation Vladimir, Here is an expanded concept for the cache implementation. I am thinking that the right approach is a class which encapsulates: (a) an unmodified ConcurrentHashMap (CHM); combined with (b) non-thread-safe thread-local buffers (TLB) for touches, managed by an inner CHM<ThreadId,TLB> instance. The reason for this inner map is to allow the TLB instances to be discarded by clear(); The TLBs get batched onto; (c) a shared non-thread safe access policy (LIRS, LRU) built on double-linked nodes (DLN) stored in the inner CHM. Updates are deferred until holding the lock (d). The DLN reference to the cached value is final. The (prior, next, delete) fields are only read or written while holding the lock (d). Other fields could be defined by subclassing a newDLN() method to support LIRS, etc. The access policy will need [head, tail] or similar fields, which would also be guarded by the lock (d); (d) a single lock guarding mutation on the access policy. Since there is only one lock, there can be no lock ordering problems. Both batching touches onto (c) and eviction (per the access policy) require access to the lock, but that is the only lock. If the access policy batches evictions, then lock requests will be rare and the whole cache will be non-blocking, wait free, and not spinning on CAS locks 99% of the time; and (d) explicit management of the threads used to access the cache. e.g., by queuing accepted requests and servicing them out of a thread pool, which has the benefit of managing the workload imposed by the clients. This should have the best possible performance and the simplest implementation. (b) The TLB could be a DLN[] or other simple data structures. The access policy (c) is composed from linking DLN instances together while holding the lock. A get() on the outer class looks up the DLN on the inner CHM and places it into the TLB (if found). A put() or putIfAbsent() on the outer class creates a new DLN and either unconditionally or conditionally puts it into the inner CHM. The new DLN is added to the TLB IFF it was added to the inner CHM. The access order is NOT updated at this time. A remove() on the outer class acquires the lock (d), looks up the DLN in the cache, and synchronously unlinks the DLN if found and sets its [deleted] flag. I would recommend that the clients do not call remove() directly, or that an outer remove() method exists which only removes the DLN from the inner CHM and queues up remove requests to be processed the next time any thread batches its touches through the lock. The inner remove() method would synchronously update the DLNs. When batching touches through the lock, only the access order is updated by the appropriate updates of the DLN nodes. If the [deleted] flag is set, then the DLN has been removed from the cache and its access order is NOT updated. If the cache is over its defined maximums, then evictions are batched while holding the lock. Evictions are only processed when batching touches through the lcok. A clear() clear the ConcurrentHashMap<Key,DLN<Val>> map. It would also clear the inner ConcurrentHashMap<ThreadId,TLB> map, which would cause the existing TLB instances to be discarded. It would have to obtain the lock in order to clear the [head,tail] or related fields for the access policy. Bryan ________________________________________ From: Bryan Thompson Sent: Sunday, February 07, 2010 8:19 PM To: Vladimir Blagojevic Cc: infinispan -Dev List Subject: RE: [infinispan-dev] Initial LIRS implementation Vladimir, I am thinking that the right approach is a class which encapsulates: (a) an unmodified ConcurrentHashMap; combined with (b) per-thread non-thread-safe buffers for touches; which get batched onto (c) a shared non-thread safe access policy (LIRS, LRU); and (d) explicit management of the threads used to access the cache. e.g., by queuing accepted requests and servicing them out of a thread pool. This should have the best possible performance and the simplest implementation. (b) can be use an Object[]. (c) can be composed from simple arrays or other non-thread safe data structures. Both batching touches onto (c) and eviction (per the policy) require access to a lock for (c), but that is the only lock. If the policy batches evictions, then lock requests will be rare and the whole cache will be non-blocking, wait free, and not spinning on CAS locks 99% of the time. Bryan ________________________________________ From: Vladimir Blagojevic [vblagoje(a)redhat.com] Sent: Sunday, February 07, 2010 7:55 AM To: Bryan Thompson Cc: infinispan -Dev List Subject: Re: [infinispan-dev] Initial LIRS implementation Hey Bryan, Does it happen with LIRS as well? Pick up the latest version from svn so we know which file to look at. I've never seen this kind of exception in compareAndSwap, anyone? Vladimir On 2010-02-06, at 7:53 PM, Bryan Thompson wrote: