com.bigdata.cache

Class ConcurrentWeakValueCacheWithBatchedUpdates<K,V>

java.lang.Object

com.bigdata.cache.ConcurrentWeakValueCacheWithBatchedUpdates<K,V>

Type Parameters:

K - The generic type of the keys.

V - The generic type of the values.

All Implemented Interfaces:

IConcurrentWeakValueCache<K,V>

public class ConcurrentWeakValueCacheWithBatchedUpdates<K,V>
extends Object
implements IConcurrentWeakValueCache<K,V>

A low-contention/high concurrency weak value cache. This class can offer substantially less lock contention and hence greater performance than the WeakValueCache. The class batches touches using a thread-local queue in order to improve throughput over the ConcurrentWeakValueCache. Because of the thread-local queues, which must have 64 to 128 elements to be effective, this class is not suitable when the total size of the cache is limited to a relatively small number of entries. Further, since there is no provision for flushing the thread-local queues in response to inactivity or the end of some work cycle for a thread, the thread-local queues can cause hard references to be retained for an arbitrary period of time. Therefore DO NOT use this class when objects entered into the cache MUST have their references cleared in a timely manner.

The role of the HardReferenceQueue is to place a minimum upper bound on the #of objects in the cache. If the application holds hard references to more than this many objects, e.g., in various threads, collections, etc., then the cache size can be larger than the queue capacity. Likewise, if the JVM takes too long to finalize weakly reachable references, then the cache size can exceed this limit even if the application does not hold ANY hard references to the objects in the cache. For these reasons, this class uses an initialCapacity for the inner ConcurrentHashMap that is larger than the queueCapacity. This helps to prevent resizing the ConcurrentHashMap which is a relatively expensive operation.

Version:

$Id: ConcurrentWeakValueCache.java 2265 2009-10-26 12:51:06Z thompsonbry $

Author:

Bryan Thompson

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	ConcurrentWeakValueCacheWithBatchedUpdates.WeakRef<K,V> Adds the key to the weak reference.

Constructor Summary

Constructors

Constructor and Description
ConcurrentWeakValueCacheWithBatchedUpdates() Uses the default queue capacity (16), load factor (0.75) and concurrency level (16).
ConcurrentWeakValueCacheWithBatchedUpdates(IHardReferenceQueue<V> queue, float loadFactor, int concurrencyLevel, boolean removeClearedReferences) Defaults the initial capacity of the map based on the capacity of the IHardReferenceQueue.
ConcurrentWeakValueCacheWithBatchedUpdates(IHardReferenceQueue<V> queue, int initialCapacity, float loadFactor, int concurrencyLevel, boolean removeClearedReferences) Uses the specified values.
ConcurrentWeakValueCacheWithBatchedUpdates(int queueCapacity) Uses the default load factor (0.75) and concurrency level (16).
ConcurrentWeakValueCacheWithBatchedUpdates(int queueCapacity, float loadFactor, int concurrencyLevel) Uses the specified values.
ConcurrentWeakValueCacheWithBatchedUpdates(int queueCapacity, float loadFactor, int concurrencyLevel, boolean removeClearedReferences) Uses the specified values and creates a HardReferenceQueue without a timeout.

Method Summary

Methods

Modifier and Type	Method and Description
int	capacity() The capacity of the backing hard reference queue.
void	clear() Note: This operation IS NOT atomic.
boolean	containsKey(K k) Return true iff the map contains an entry for the key whose weak reference has not been cleared.
protected void	didUpdate(K k, WeakReference<V> newRef, WeakReference<V> oldRef) Notification method is invoked if a map entry is inserted or updated by put(Object, Object) or putIfAbsent(Object, Object).
Iterator<Map.Entry<K,WeakReference<V>>>	entryIterator() An iterator that visits the entries in the map.
V	get(K k) Returns the value for the key.
boolean	isRemoveClearedReferences() Return true iff a ReferenceQueue is being maintained and entries will be removed from the map once the corresponding WeakReference has been cleared.
Iterator<WeakReference<V>>	iterator() An iterator that visits the weak reference values in the map.
protected WeakReference<V>	newWeakRef(K k, V v, ReferenceQueue<V> referenceQueue) Factory for new weak references.
V	put(K k, V v) Adds the key-value mapping to the cache.
V	putIfAbsent(K k, V v) Adds the key-value mapping to the cache iff there is no entry for that key.
V	remove(K k) Remove the entry for the key.
protected void	removeClearedEntries() Remove any entries whose weak reference has been cleared from the map.
protected WeakReference<V>	removeMapEntry(K k) Invoked when a reference needs to be removed from the map.
int	size() Returns the approximate number of keys in the map.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ConcurrentWeakValueCacheWithBatchedUpdates

public ConcurrentWeakValueCacheWithBatchedUpdates()

Uses the default queue capacity (16), load factor (0.75) and concurrency level (16).

ConcurrentWeakValueCacheWithBatchedUpdates

public ConcurrentWeakValueCacheWithBatchedUpdates(int queueCapacity)

Uses the default load factor (0.75) and concurrency level (16).

Parameters:

queueCapacity - The IHardReferenceQueue capacity. When ZERO (0), there will not be a backing hard reference queue.

ConcurrentWeakValueCacheWithBatchedUpdates

public ConcurrentWeakValueCacheWithBatchedUpdates(int queueCapacity,
                                          float loadFactor,
                                          int concurrencyLevel)

Uses the specified values.

Parameters:

queueCapacity - The IHardReferenceQueue capacity.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

ConcurrentWeakValueCacheWithBatchedUpdates

public ConcurrentWeakValueCacheWithBatchedUpdates(int queueCapacity,
                                          float loadFactor,
                                          int concurrencyLevel,
                                          boolean removeClearedReferences)

Uses the specified values and creates a HardReferenceQueue without a timeout.

Parameters:

queueCapacity - The HardReferenceQueue capacity.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

removeClearedReferences - When true the cache will remove entries for cleared references. When false those entries will remain in the cache.

ConcurrentWeakValueCacheWithBatchedUpdates

public ConcurrentWeakValueCacheWithBatchedUpdates(IHardReferenceQueue<V> queue,
                                          float loadFactor,
                                          int concurrencyLevel,
                                          boolean removeClearedReferences)

Defaults the initial capacity of the map based on the capacity of the IHardReferenceQueue.

Parameters:

queue - The IHardReferenceQueue.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

removeClearedReferences - When true the cache will remove entries for cleared references. When false those entries will remain in the cache.

ConcurrentWeakValueCacheWithBatchedUpdates

public ConcurrentWeakValueCacheWithBatchedUpdates(IHardReferenceQueue<V> queue,
                                          int initialCapacity,
                                          float loadFactor,
                                          int concurrencyLevel,
                                          boolean removeClearedReferences)

Uses the specified values.

Parameters:

queue - The backing IHardReferenceQueue. This will be wrapped with a HardReferenceQueueWithBatchingUpdates instance.

initialCapacity - The initial capacity of the backing hash map.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

removeClearedReferences - When true the cache will remove entries for cleared references. When false those entries will remain in the cache.

Method Detail

isRemoveClearedReferences

public boolean isRemoveClearedReferences()

Return true iff a ReferenceQueue is being maintained and entries will be removed from the map once the corresponding WeakReference has been cleared. This behavior is controlled by a constructor option.

size

public int size()

Returns the approximate number of keys in the map. Cleared references are removed before reporting the size of the map, but the return value is still approximate as garbage collection by the JVM can cause references to be cleared at any time.

Specified by:

size in interface IConcurrentWeakValueCache<K,V>

capacity

public int capacity()

The capacity of the backing hard reference queue.

Specified by:

capacity in interface IConcurrentWeakValueCache<K,V>

clear

public void clear()

Note: This operation IS NOT atomic. It can not be made atomic without synchronizing all updates on the backing queue, which would defeat the purpose of this class.

Specified by:

clear in interface IConcurrentWeakValueCache<K,V>

get

public V get(K k)

Returns the value for the key.

Specified by:

get in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

Returns:

The value.

See Also:

http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms, http://www.audiomulch.com/~rossb/code/lockfree/

containsKey

public boolean containsKey(K k)

Return true iff the map contains an entry for the key whose weak reference has not been cleared.

Specified by:

containsKey in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

Returns:

true iff the map contains an entry for that key whose weak reference has not been cleared.

put

public V put(K k,
    V v)

Adds the key-value mapping to the cache.

Specified by:

put in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

v - The value.

Returns:

The old value under the key -or- null if there is no entry under the key or if the entry under the key has has its reference cleared.

putIfAbsent

public V putIfAbsent(K k,
            V v)

Adds the key-value mapping to the cache iff there is no entry for that key. Note that a cleared reference under a key is treated in exactly the same manner as if there were no entry under the key (the entry under the key is replaced atomically).

Specified by:

putIfAbsent in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

v - The value.

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key or if the entry under the key has has its reference cleared.

didUpdate

protected void didUpdate(K k,
             WeakReference<V> newRef,
             WeakReference<V> oldRef)

Notification method is invoked if a map entry is inserted or updated by put(Object, Object) or putIfAbsent(Object, Object). This method IS NOT invoked if putIfAbsent(Object, Object) did not update the map.

Parameters:

k - The key.

newRef - The WeakReference for the new value. This was generated using newWeakRef(Object, Object, ReferenceQueue). Reference.get() will always return the value inserted into the map since it is on the stack and hence can not have been cleared during this callback.

oldRef - The WeakReference for the old value. This will be null if there was no entry under the key for the map. If the entry for a cleared reference is updated then Reference.get() will return null for the oldRef.

remove

public V remove(K k)

Description copied from interface: IConcurrentWeakValueCache

Remove the entry for the key.

Specified by:

remove in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

Returns:

The previous value associated with the key, or null if there was no mapping for the key or if the entry under the key has has its reference cleared.

removeClearedEntries

protected void removeClearedEntries()

Remove any entries whose weak reference has been cleared from the map. This method polls the ReferenceQueue, but the ReferenceQueue uses an internal lock so this does impose synchronization on the callers. For that reason, this method is now invoked from an IBatchedUpdateListener which is called when the access order updates are batched for a given thread. This does not eliminate the possibility of synchronization costs inside of ReferenceQueue, but it should dramatically reduce those costs.

Note: This method does not clear entries from the hard reference queue because it is not possible to have a weak or soft reference cleared by the JVM while a hard reference exists, so it is not possible to have an entry in the hard reference queue for a reference that is being cleared here.

removeMapEntry

protected WeakReference<V> removeMapEntry(K k)

Invoked when a reference needs to be removed from the map.

Parameters:

k - The key.

iterator

public Iterator<WeakReference<V>> iterator()

An iterator that visits the weak reference values in the map. You must test each weak reference in order to determine whether its value has been cleared as of the moment that you request that value. The entries visited by the iterator are not "touched" so the use of the iterator will not cause them to be retained any longer than they otherwise would have been retained.

Specified by:

iterator in interface IConcurrentWeakValueCache<K,V>

entryIterator

public Iterator<Map.Entry<K,WeakReference<V>>> entryIterator()

An iterator that visits the entries in the map. You must test the weak reference for each entry in order to determine whether its value has been cleared as of the moment that you request that value. The entries visited by the iterator are not "touched" so the use of the iterator will not cause them to be retained any longer than they otherwise would have been retained.

Specified by:

entryIterator in interface IConcurrentWeakValueCache<K,V>

newWeakRef

protected WeakReference<V> newWeakRef(K k,
                          V v,
                          ReferenceQueue<V> referenceQueue)

Factory for new weak references. The default implementation uses a WeakReference unless referenceQueue!=null, in which case it uses ConcurrentWeakValueCacheWithBatchedUpdates.WeakRef to pair the key with the WeakReference. This may be extended if you need to track additional information in the map entries.

Parameters:

k - The key.

v - The value.

referenceQueue - The ReferenceQueue used to remove map entries whose WeakReferences have been cleared (optional).

Returns:

An instance of a class extending WeakReference -or- an instance of a class extending ConcurrentWeakValueCacheWithBatchedUpdates.WeakRef if referenceQueue!=null.